Как компьютеры играют в шахматы: перебор вариантов

Почему нельзя просчитать шахматы до самого конца

В крестиках-ноликах на поле три на три существует всего 255 168 возможных партий. Обычный компьютер просчитывает такую игру целиком за сотые доли секунды. В шахматах этот номер не пройдет из-за так называемого комбинаторного взрыва.

В самом начале партии у белых есть ровно 20 вариантов первого хода. Черные могут ответить двадцатью способами. После одного полного хода на доске может возникнуть 400 разных ситуаций. На втором ходу количество вариантов подскакивает почти до 200 тысяч, а после третьего превышает 120 миллионов. В среднем шахматист выбирает примерно из 35 допустимых ходов на каждом шаге.

Американский математик Клод Шеннон еще в 1950 году подсчитал приблизительное число уникальных шахматных партий. Это число называют числом Шеннона, и оно составляет примерно 10 в 120-й степени. Для сравнения, во всей наблюдаемой Вселенной насчитывают порядка 10 в 80-й степени атомов. Никакому суперкомпьютеру в мире не хватит ни памяти, ни времени до конца существования галактики, чтобы перебрать всю игру от дебюта до мата.

Оценочная функция и превращение позиции в число

Поскольку заглянуть до финала партии невозможно, программа ограничивает глубину расчета, например, на 10, 15 или 20 полуходов вперед. Когда перебор упирается в заданный предел глубины, программа должна понять, у кого из игроков позиция лучше. Этим занимается оценочная функция.

Оценочная функция превращает расстановку фигур на доске в одно понятное число, измеряемое в пешках или сантипешках (сотых долях пешки). Положительное число означает перевес белых, отрицательное число указывает на преимущество черных, а ноль говорит о примерном равенстве.

В простейшем виде функция складывает ценность материала по классической шкале:

• Пешка принимается за единицу или 100 условных очков.
• Конь и слон оцениваются примерно в 3 пешки, то есть в 300 очков каждый.
• Ладья приравнивается к 5 пешкам или 500 очкам.
• Ферзь получает вес в 9 пешек или 900 очков.
• Король имеет условно бесконечную ценность, поскольку его потеря означает поражение.

Однако считать один лишь материал рискованно. Если просто набрать больше фигур, можно сразу получить мат от легкой фигуры соперника. Поэтому современные алгоритмы добавляют десятки других признаков. Программа начисляет баллы за захват центральных полей, за продвинутые проходные пешки, за открытые линии для ладей и штрафует за сдвоенные пешки или раскрытого короля.

Алгоритм минимакс и логика расчета вариантов

После составления оценочной функции программе требуется выбрать конкретный ход. Для этого используется алгоритм минимакс, который моделирует игру двух противников с абсолютно противоположными целями.

Представь дерево ходов. Верхний узел — текущее положение на доске. От него отходят ветви — возможные ответы белых. От каждого ответа белых идут ответные ветви черных. Расчет идет снизу вверх, от самых дальних просчитанных вариантов обратно к началу.

Суть минимакса заключается в двух простых предположениях:

• Игрок за белых стремится выбрать вариант с максимально высокой оценкой позиции (узел типа MAX).
• Игрок за черных стремится свести оценку к минимуму и выбрать худший для белых расклад (узел типа MIN).
• Компьютер всегда исходит из того, что соперник сделает сильнейший возможный ход, а не ошибется на ровном месте.

Программа спускается по дереву до установленной глубины, считает оценку на концах веток, а потом передает значения наверх. На уровне черных выбирается минимальное число из доступных, а на уровне белых поднимается максимальное. В итоге к корневому узлу приходит значение, гарантирующее лучший результат при безошибочной защите соперника.

Альфа-бета отсечение и отказ от лишней работы

Чистый алгоритм минимакс все еще работает слишком медленно, ведь число ветвей растет с каждым шагом лавинообразно. Проверять миллионы бессмысленных ходов не имеет практического смысла. Для ускорения поиска используют метод альфа-бета отсечения.

Принцип отсечения строится на логике здравого смысла. Если программа уже нашла надежный ход с гарантированным выигрышем ладьи в одной ветке, а в другой ветке после первого же ответа соперника белые теряют ферзя, просчитывать продолжение второй ветки глубже нет необходимости. Этот вариант заведомо хуже уже найденного.

В ходе работы алгоритм хранит две переменные. Переменная альфа означает минимальный выигрыш, который максимизирующий игрок уже гарантировал себе на данный момент. Переменная бета показывает максимум, который минимизирующий игрок готов позволить сопернику. Как только значение беты становится меньше или равно альфе, дальнейший перебор этой подветки немедленно прекращается.

Грамотное применение альфа-бета отсечения позволяет сократить количество просматриваемых узлов в разы. В идеально упорядоченном дереве, где сильные ходы рассматриваются первыми, компьютер может за то же самое процессорное время заглянуть в два раза глубже, чем при обычном переборе.

Исторический матч Deep Blue против Гарри Каспарова

Классический перебор вариантов достиг своего триумфа в мае 1997 года. В Нью-Йорке состоялся знаменитый матч-реванш между чемпионом мира Гарри Каспаровым и шахматным суперкомпьютером Deep Blue, созданным инженерами корпорации IBM.

Deep Blue представлял собой гигантскую вычислительную систему, состоящую из 32 узлов и сотен специализированных шахматных микросхем. Машина была способна анализировать до 200 миллионов позиций за одну секунду. Компьютер использовал именно алгоритм альфа-бета отсечения вкупе с громадной базой дебютов и эндшпилей.

В шестой решающей партии чемпион мира допустил неточность в защите Каро-Канн на седьмом ходу, попав под жертву коня. Deep Blue рассчитал последствия за секунды и довел партию до капитуляции человека уже к 19-му ходу. Это событие доказало всему миру мощь грамотно оптимизированного перебора вариантов.