Gemini 2.5 Pro добавил в код соблюдение правила "турецкого удара", а так же добавил улучшение в алгоритм сортировки ходов.
Вот как Gemini объясняет новую логику:
Алгоритм сортировки ходов в этом коде — ключевой элемент, который делает альфа-бета отсечение (minimax с альфа-бета) значительно эффективнее. Без хорошей сортировки альфа-бета отсечение работает ненамного лучше простого минимакса.
Общая стратегия
Основная идея сортировки ходов — проверять самые "перспективные" ходы в первую очередь. Если мы сразу найдем очень хороший ход, это позволит установить высокие (для максимизирующего игрока) или низкие (для минимизирующего игрока) значения `alpha` и `beta`. Чем раньше мы это сделаем, тем больше "плохих" веток поиска можно будет отсечь, не тратя время на их анализ.
Алгоритм в этой игре реализован в функции `getAllPossibleMovesForBoard` и использует две вспомогательные функции для оценки ходов: `_scoreCaptureMove` и `_scoreQuietMove`.
Весь процесс можно разбить на следующие шаги:
Шаг 1: Принудительное взятие (Правило "Бить обязательно")
Это самый важный и первый уровень сортировки, продиктованный правилами самих шашек.
1. Проверка на наличие взятий: Алгоритм сначала ищет все возможные ходы со взятием (captures) для текущего игрока на всей доске.
2. Приоритет взятий:
- Если ходы со взятием существуют, то все остальные ("тихие" ходы, без взятия) полностью игнорируются. Рассматриваться будут только ходы со взятием.
- Если ходов со взятием нет, только тогда алгоритм переходит к генерации и анализу "тихих" ходов.
Это само по себе является мощнейшей эвристикой, так как взятия кардинально меняют оценку позиции и являются самыми важными ходами в игре.
Шаг 2: Сортировка ходов со взятием (Capture Moves)
Если на первом шаге были найдены ходы со взятием, они не просто берутся в случайном порядке. Они сортируются по "качеству" с помощью функции `_scoreCaptureMove`. Чем выше оценка хода, тем раньше он будет проверен в минимаксе.
Критерии сортировки взятий (в порядке убывания важности):
1. Количество сбитых шашек (Самый высокий приоритет):
- `score += (move.captureSequence.length || 1) * 100;`
- Ход, который бьет две шашки (турецкий удар), будет оценен гораздо выше, чем ход, бьющий одну. Это самый сильный фактор, так как он напрямую влияет на материальное преимущество.
2. Ценность сбитых шашек:
- `if (capturedPiece && capturedPiece.isKing) { score += 50; } else { score += 10; }`
- Взятие дамки (king) ценится значительно выше (50 очков), чем взятие простой шашки (10 очков).
3. Превращение в дамку в результате взятия:
- `if (becomesKing) { score += 80; }`
- Если в результате взятия простая шашка достигает последней горизонтали и становится дамкой, такой ход получает большой бонус (80 очков).
Итог по взятиям: Алгоритм в первую очередь будет рассматривать взятия, которые бьют больше всего шашек, предпочитая бить дамки и ходы, которые приводят к появлению своей дамки.
Шаг 3: Сортировка "тихих" ходов (Quiet Moves)
Если ходов со взятием нет, алгоритм генерирует все возможные "тихие" ходы (передвижение на пустую клетку) и сортирует их с помощью функции `_scoreQuietMove`.
Критерии сортировки тихих ходов (в порядке убывания важности):
1. Превращение в дамку (Самый высокий приоритет):
- `if (becomesKing) { score += 100; }`
- Тихий ход, который приводит к превращению шашки в дамку, получает наивысшую оценку. Это "killer move" (ход-убийца), который может полностью изменить ход игры.
2. Продвижение простых шашек вперёд:
- `score += move.to.row - move.from.row;` (для черных)
- `score += move.from.row - move.to.row;` (для белых)
- Ходы, которые продвигают простые шашки ближе к полю превращения, получают небольшой бонус. Это поощряет развитие и создание угроз.
3. Централизация (позиционное преимущество):
- `if (isToCentral && !isFromCentral) { score += 5; }`
- Ход, который перемещает шашку в центр доски (условно, клетки с `c` от 2 до 5 и `r` от 2 до 5), получает небольшой бонус.
- `else if (!isToCentral && isFromCentral) { score -= 5; }`
- Ход из центра на край доски, наоборот, получает небольшой штраф. Шашки в центре контролируют больше полей и более мобильны.
Итог по тихим ходам: Алгоритм сначала проверит ходы, создающие дамку, затем — ходы, продвигающие шашки к цели и улучшающие позицию (захват центра).
Как это помогает альфа-бета отсечению?
Представим, что ИИ (черные) ищет свой лучший ход.
1. Он генерирует все свои возможные ходы и сортирует их по описанным выше правилам.
2. Допустим, лучший по оценке ход — это взятие, которое превращает шашку в дамку. ИИ делает этот ход в уме.
3. Затем он начинает анализировать ответные ходы игрока (белых). Скорее всего, после такого сильного хода у белых будет мало хороших ответов.
4. Минимакс быстро получает оценку этой ветки (например, +500 в пользу ИИ). Эта оценка становится значением `alpha`.
5. Теперь ИИ начинает анализировать свой второй по качеству ход (например, простое продвижение шашки). Если после этого хода найдется хотя бы один ответ белых, который приведет к оценке ниже, чем +500, ИИ сможет отсечь все остальные ответы белых на этот второй ход.
Если бы ИИ сначала проанализировал слабый ход, он бы установил низкое значение `alpha`, и ему пришлось бы перебирать гораздо больше веток, прежде чем найти сильный ход и получить возможность для отсечения. Таким образом, умная сортировка максимизирует количество отсечений и позволяет за то же время просмотреть дерево поиска на большую глубину.
