Как компьютер играет в шахматы, шашки, реверси, го и другие игры

Алгоритмическая основа стратегических игр. Просто и доступно!

В далеком 1989 году на пятилетие дочери я подарил ей настольную игру реверси, она еще называется «отелло». Это игра с несложными правилами развивает логическое и стратегическое мышление, умение предвидеть и просчитать позиции на быстро меняющемся игровом поле.

Как сообщает Википедия, игра «реверси» была изобретена в 1880 году в Великобритании и вначале пользовалась большой популярностью, но впоследствии была забыта. В 1971 году под названием «отелло» её возродили в Японии и она вновь стала популярна.

Начальная позиция игры реверси (отелло).

Эта игра подобна шашкам и шахматам, ведется на поле из 64-х клеток (8х8) специальными двусторонними фишками, окрашенными в черный и белый цвета. Первоначально в центре игрового поля находятся четыре фишки — по две каждого цвета. Игроки, делая ходы по очереди, ставят фишку «своим» цветом на игровое поле так, чтобы между ней и другой «своей» фишкой были фишки противника (другого цвета), которые переворачиваются, изменяя свой цвет. Игра ведется до заполнения всего игрового поля или до момента, когда все фишки не станут одного цвета. Побеждает тот, у кого будет больше «своих» фишек на поле. 

В конце 1980-х начали массово появляться персональные компьютеры PC/XT и PC/AT. Обучая маленькую дочку игре в реверси, я задался мыслью, а не написать ли компьютерную игровую программу, которая смогла бы выиграть у человека?

Окунувшись в процесс программирования, не имея под рукой специализированной литературы и знаний в области кодирования стратегических игр, я самостоятельно «изобрел» все основные игровые компоненты, входящие в большинство компьютерных играющих программ, и написал программный код на языке программирования Модула-2. Размер скомпилированной на основе этого кода программы был всего лишь 32 Кб, но выиграть у своего же детища я не мог.

Через год, прочитав в журнале «Наука и Жизнь» о том, что компания IBM проводит Олимпиаду компьютерных программ, играющих в шахматы, шашки и отелло (реверси), я подал заявку на участие. Моя программа прошла предварительный отбор и я стал участником этого международного турнира.

Разумеется, я не занял призового места, но мой результат был достойным — 5-е место из 12 отобранных участников. Не хватило знаний нюансов самой игры и игрового опыта, чтобы построить хорошую оценивающую функцию.

Но, тем не менее, моя программа была единственной на турнире, которая могла просчитывать позиции до 7–12 хода вглубь  и сумела поставить «мат» (ситуация, когда все фишки на доске становятся одного цвета). Причем, противником была программа, занявшая 3-е место в турнирной таблице. Это для меня был большой успех!

Итак, из каких же основных алгоритмических компонентов состоит компьютерная игровая программа? В большинстве компьютерных играющих программ можно выделить три основные компоненты: 

• генератор ходов; 
• функцию, оценивающую позицию;
• минимаксную процедуру. 

Еще один важный момент — это «дерево» игры. Оно участвует в работе всех трех основных компонетов игровой программы.

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

Рассмотрим подробнее, как все три игровых компоненты работают в совокупности.

Корневой узел дерева представляет собой исходную позицию на доске, а каждая ветвь ведет к какой-то позиции, достигаемой при помощи одного хода. Примечательно, что подобное дерево изображается обычно «вверх ногами» — его корень располагается вверху. Дерево можно разделить на уровни так, что все позиции n-го уровня соответствуют всем возможным ходам одного игрока, делающего n-й ход. 

Хотя игровые деревья, как правило, не очень высоки (точнее говоря, глубоки), они могут быть очень кустистыми. Дело в том, что число позиций на каждом последующем уровне в несколько раз превышает число позиций на предыдущем уровне. Даже если бы у каждой позиции на доске было лишь две последующие позиции, то число ветвей очень скоро бы достигло бы огромной величины. Дерево, разветвившееся подобным образом всего лишь 10 раз, имело бы более 1000 (точнее 1024 — 2 в 10-й степени) ветвей. И при каждых последующих 10 ветвлениях, число ветвей увеличивалось бы в 1024 раза. 

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

Матрица начальной позиции в игре реверси (отелло).

Каждая позиция записывается в память компьютера в виде матрицы. Например, для игры в реверси белая фишка (которыми играет противник) в матрице имеет значение -1, черная (фишка компьютера) +1, а пустая клетка — 0. Таким образом, начальная позиция в этой игре — это матрица чисел размером 8 на 8, в которой все ячейки, кроме 4-х центральных, заполнены нулями (пустые клетки), а в центре две ячейки имеют значение -1, и еще две +1.

Каждый элемент в этой матрице имеет двумерный индекс (строка, колонка). А сами матрицы позиций игрового дерева также проиндексированы и имеют уникальный числовой идентификатор, посредством которого связываются позиции-родители с позициями-потомками, что помогает перемещению по игровому дереву. Эти идентификаторы помещены в специальный массив, называемый таблицой указателей.

Указателем для каждой позиции является список чисел, первое из которых указывает на позицию «родителя», а последующие — на позиции «потомков». Таким образом производится перемещение по игровому дереву. 

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

Создать хорошую оценивающую функцию очень трудно, поскольку надо учитывать множество факторов, влияющих на игру. Это могут быть как «вес» фигур (в шахматах), так и их позиции и конфигурации. Например, игровой «вес» пешки, которая вот-вот превратится в ферзя будет гораздо выше, чем у любой другой пешки.

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

В любой игре, будь-то шахматы, шашки, го или реверси, игровой «вес» каждого фактора определяется исходя из опыта игры. Первоначально каждый весовой фактор получает значение единицы. Затем компьютерная программа начинает играть сама с собой и после каждого выигрыша-проигрыша, анализирует причины и вносит коррективы в соответствующие весовые факторы — уменьшая одни и увеличивая другие. Таким образом, постепенно происходит самообучение. Иногда к такому анализу привлекаются хорошие игроки — мастера и гроссмейстеры.

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

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

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

На любой стадии исследования игрового дерева все позиции определенного уровня оцениваются этой функцией по следующему правилу:

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

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

Игровое дерево, минимакс и альфа-бета алгоритм.

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

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

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

Как он работает, поясняется  на рисунке выше. Оценочная функция рассчитывает оценки позиций на самом нижнем уровне слева-направо. Первая ветка последнего уровня получает оценку 5, вторая — 6. По минимаксу на следующий уровень основной ветки переносится минимальная оценка (5). В этом уровне есть еще одна ветка, которая разделяется на три ветки нижнего уровня. Сначала находится оценка 7, затем — 4. Поскольку 4 меньше минимальной оценки (5) первой ветки на уровне выше, то далее вести расчет оценок не имеет смысла — вторая ветка проигрывает первой. Последняя ветка отсекается и оценочная функция не ведет расчет, тем самым экономится время (если бы вела, то получила бы значение 5).

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

Таким образом, альфа-бета отсечение значительно экономит время на расчеты оценок позиций.

В целом, работа компьютерной игровой стратегической программы — это проведение больших массивов расчетов и выбор из их результатов оптимального. Чтобы минимизировать эти расчеты, многие программы имеют базы данных типовых ситуаций, как правило дебютов, где лучшие ходы уже записаны и нет необходимости их рассчитывать.

Компьютерный алгоритм — это рациональные действия, основанные на точных расчетах глубоких позиций игрового дерева, не более того. Чем глубже может просчитать программа и чем точнее ее оценочная функция, тем она сильнее играет. Здесь нет полета фантазии и импровизаций. Нет рисков и красивых комбинаций. Только холодный расчет!