Сто тринадцать раз в секунду оно тянется, и достает все дальше. Если бы пришло подтверждение, сигнал — оно могло бы остановиться, и оно не останавливается. Оно тянется и находит всё новые способы. Оно импровизирует, оно изучает. Оно не сознает, что делает…

        Джеймс Кори «Пожар Сиболы»

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

Целью моего проекта является популяризация настольных игр. Я ищу малоизвестные или просто забытые настольные игры и стараюсь вернуть их к жизни. Самые разные игры: древние, современные, сложные и совсем детские, для двух игроков или большего их количества. Даже для одного игрока (головоломки — это тоже игры). Критерий один — игры должны быть интересны! По крайней мере, мне.

На текущей стадии развития проекта не подразумевается серверная часть хоть сколь-нибудь более сложная чем просто набор html-страничек с сопутствующим кодом на JavaScript. Я хочу чтобы игра загружалась и работала в любом современном Web-браузере, в том числе и локально, без доступа к Internet. Всевозможные соревнования, рейтинги и всё что связано со взаимодействием игроков-людей между собой — всё это не про мой проект. Возможно это будет, но вряд ли в ближайшем будущем.

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

Основной инстинкт

Как я уже говорил, есть игры, в которых от машины требуется не столько интеллект, сколько инстинкты. И это не значит, что игры плохие! Как правило, такие игры ассиметричны. От одной из сторон требуется творческий подход (этим займётся человек), игра другой стороны более рутинна. Вот хороший пример такой игры.

Имея на своей стороне полную шахматную «армию», требуется поймать (съесть) всего одну фигуру — Махараджу, сочетающую в себе ходы шахматного коня и ферзя. Это очень сильная фигура, но, при правильной игре белых, исход предрешён. С другой стороны, игра за чёрных довольно тривиальна. Реализация бота мало чем отличается от рандомного. Он делает следующее:

1. Среди всех доступных ходов ищет ход непосредственно ведущий к победе (в нашем случае, это взятие короля противника)
2. Если такого хода нет, ищет любой ход берущий фигуру противника и не подставляющий «Махараджу» под ответный удар
3. Если подходящих ходов нет — делает любой безопасный ход
4. Если нет безопасных ходов — передаёт эстафету другому боту (как правило, рандомному)

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


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


Играя за «мушкетёров», вполне можно было бы обойтись рандомом, но было бы обидно, если бы компьютер выстраивал линию случайно, имея в запасе другой, безопасный ход. Бот должен играть более осторожно. Код прост настолько, насколько это возможно.


Разумеется, я вовсе не хочу сказать, что боты не играли бы в эти игры лучше, используя более сложные алгоритмы, но и самые простейшие решения имеют своё применение (например, рандом может бросать кости в тех играх, где это требуется). Кроме того, у простых алгоритмов имеется одно важное достоинство. Они работают очень быстро.

Игры для одного

В случае головоломок, игровой AI является не столько необходимостью, сколько способом «набить» руку. В конце концов, предполагается, что человек будет решать их сам! С другой стороны, можно до бесконечности смотреть, как компьютер пытается решить головоломку вместо тебя:


Простой алгоритм перебора (ничего более эффективного для этого класса головоломок пока не придумали). Чтобы позиции не повторялись, используем Zobrist Hash. В этом видео, можно заметить, что одиночные квадратики как то слишком уж долго вальсируют друг с другом. Всё потому что бот считает их разными фигурами. Это легко исправить. Теперь решение находится гораздо быстрее:


Другой момент, который лично меня очень сильно нервировал, заключался в том, что не дойдя до заветной цели всего пару шагов «по прямой», бот мог сделать шаг «в сторону» и двигать плашки ещё с полчаса, уходя от решения всё дальше и дальше. Чтобы решить эту проблему, я использовал время выделяемое для анимации хода. За 100 миллисекунд, практически незаметные для человека, можно успеть перебрать сотни позиций.


Просто перебираем всевозможные ходы, пока есть время. Если находим цель — идём к ней по прямой! Хотя работа этого бота довольно наглядна, он использует не лучший способ, чтобы решить задачу. Было бы разумнее потратить больше времени вначале, чтобы заняться анимацией уже после того как решение найдено. Именно так я и поступил при разработке бота для решения пасьянсов "Солитёра":


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


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


Изрядно потренировавшись на пазлах, можно переходить к более сложным материям.

Оно тянется

Довольно очевидно, что для более менее серьёзных игр, вроде шахмат или шашек, потребуется более сложный AI, чем всё то, о чём я писал выше. Выбор, по большому счёту, невелик: Минимакс, с его "Альфа-бета отсечением" и метод "Монте-Карло" (и по тому и по другому имеются замечательные статьи на Хабре). Каждый из этих подходов универсален. У каждого из них есть свои плюсы и минусы. Не претендуя на полноту обзора, перечислю первое, что приходит в голову.

1. Чтобы использовать метод минимакса, необходимо определить функцию, выполняющую оценку позиции (как разработчик настольных игр со стажем, могу заметить, что для некоторых игр это может быть очень непросто).
2. Альфа-бета отсечение особенно эффективно при выполнении поиска в глубину, либо комбинированного поиска (в ширину, до некоторой гарантированной глубины, например на 2-3 хода, после чего, в глубину, не более чем на N уровней). Это делает его малопригодным в условиях ограниченных вычислительных ресурсов и, самое главное, при необходимости вывода ответа не позднее заданного времени (пусть знающие люди поправят меня, если я ошибаюсь).
3. Эффективность альфа-бета отсечения можно значительно улучшить, применяя предварительно ранжирование ходов по их качеству (как я скажу ниже, при использовании метода «Монте-Карло» такие эвристики тоже полезны).
4. При использовании метода минимакса, перебор в глубину нельзя останавливать в произвольном месте. При обнаружении форсированных ходов (в Шахматах такими являются шахи и взятия фигур) поиск следует продолжать до возникновения более «спокойной» позиции.
5. При использовании метода «Монте-Карло» симуляция производится до терминальной позиции (победы одного из игроков или признания ничьей). В играх с большой продолжительностью партии это может быть проблемой.

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

Это простая игра со взятиями, целью которой является лишение противника всех его фигур или возможности хода. Взятие в Коно довольно своеобразно. Чтобы забрать фигуру противника, на неё необходимо «приземлиться», перепрыгнув одной из своих фигур через другую (благодаря этому, можно начать игру, несмотря на то, что в начальной позиции доска полностью забита фигурами). Вот отладочный вывод при расчёте одного из ходов (ограничение времени ~3 секунды):


Имея перед глазами такой вывод, можно оценивать корректность работы алгоритма. Первое, на что следует обратить внимание это то, соответствуют ли «цели», зафиксированные алгоритмом, целям игрока согласно правилам игры. В процессе отладки, у меня была пара ситуаций, когда алгоритм пытался искать попросту «не то». Если с целями всё нормально, смотрим на оценку ходов (Win — количество зафиксированных побед, All — общее количество сыгранных игр). UCT «из коробки» работает, в принципе неплохо, но я внёс пару изменений:

1. Ограничил глубину поиска (100 по умолчанию)
2. Добавил эвристики ходов

То есть, взятия в 10 раз более предпочтительны чем «тихие» ходы. Здесь следует заметить, что в отличии от метода минимакса, сортировать ходы в Монте-Карло (в соответствии с их эвристиками) бесполезно. Необходимо строить алгоритм таким образом, чтобы вероятность выбора хода была пропорциональна его эвристической оценке. Оба нововведения благоприятно сказались на статистике побед/сыгранных игр для Коно и я взялся за другие игры.


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


С точки зрения отладки, игра дала информацию о поведении алгоритма на больших досках. Все оценки количества побед для ходов мгновенно обнулились. Алгоритм просто не успевал найти ни одной победы, в результате чего начал делать первые попавшиеся ходы (совсем не лучшие). Увеличение глубины поиска помогло не сильно — трёх секунд явно не хватало на набор «критической» массы партий, сыгранных в фазе симуляции. Пришлось учитывать эвристики при выборе хода:


Ходы по эвристикам конечно хуже чем то, что даёт UCT, но, в не очень сложных играх, они дают компьютеру «дожить» до того момента, когда UCT сможет работать. Весовые коэффициенты подобраны таким образом, чтобы эвристики оказывали заметное влияние лишь в тех случаях, когда алгоритм Монте-Карло не работает.

Следующей игрой стала Камисадо. Я уже писал о ней раньше. Нельзя сказать, что метод Монте-Карло работает здесь вполне удачно. Программа делает вполне адекватные ходы, но если задаться целью, победить её совсем не сложно:


Главная причина в том, что я не смог придумать для этой игры простую и адекватную эвристику. В результате, программа делает свои ходы «на ощупь». При наличии достаточных вычислительных ресурсов это не было бы проблемой (алгоритм Монте-Карло подходит для этой игры как нельзя кстати), но 3 секунды расчёта хода в одном потоке — это пока максимум того, что я могу себе позволить (кстати, UCT можно очень хорошо масштабируется при наличии нескольких потоков).

Конечно же, метод Монте-Карло, в том виде, как он у меня сейчас реализован, подходит далеко не для всех игр. Я не собираюсь на нём зацикливаться. Для игр, подобных Шахматам, пожалуй, минимакс подойдёт лучше. Я ещё буду иметь возможность исследовать этот вопрос. Также, у меня есть кое какие мысли по поводу улучшения текущей реализации UCT. Посмотрим, что получится лучше.