Не так давно я уже писал небольшой пост о разработке ИИ для игры в т.н. мини-сёги, но опрос показал, что хабрасообществу будет интересен и более полный пост о разработке. Кому интересно, прошу под кат.
Построение программ, способных играть в интеллектуальные игры, — весьма интересная задача, имеющая большую практическую и научную ценность.
Первые попытки создать машины для игры в интеллектуальные игры (в первую очередь в шахматы) появились задолго до появления компьютеров. Около 1769 года появился известный шахматный аппарат «механический турок». Машина играла весьма неплохо, но весь её секрет заключался в спрятанном внутри сильном шахматисте.
В XX веке механические машины уступили свои позиции цифровым компьютерам. Первопроходцем в этой области (как и во многих других) можно назвать известного математика Алана Тьюринга. По современным меркам разработанный им алгоритм был весьма примитивным, а ввиду отсутствия доступа к реальным вычислительным машинам, выполнять алгоритм приходилось вручную.
Примерно в то же время Клод Шеннон обосновал наличие лучшего хода для любой позиции. Он даже предложил алгоритм нахождения такого хода для любой игры на конечной доске. К сожалению, несмотря на существование оптимального алгоритма, его практическая реализация невозможна ввиду ограниченности аппаратных и временных ресурсов.
Со времён Шеннона задача программирования интеллектуальных игр переместилась из области развлечений в область серьёзных исследований. За последние годы на основе исследований Шеннона были построены реализуемые на практике алгоритмы, с помощью которых компьютеры научились безошибочно играть в шашки и достигли выдающихся успехов в шахматах и го.
Японские шахматы сёги — одна из немногих игр, где человек пока сильнее компьютера. В первую очередь это обусловлено возможностью возвращения в игру взятых фигур, это правило резко увеличивает количество возможных ходов, а значит, затрудняет анализ игры. Если в шахматах из произвольной позиции можно сделать около 40 ходов, то в сёги число возможных ходов измеряется сотнями.
Правила игры
Прежде чем говорить о построении алгоритмов для игры в сёги, необходимо описать правила этой игры.
Фигуры
В сёги есть 8 различных фигур (если учитывать перевёрнутые фигуры, то 14). Правила ходов для различных фигур представлены в таблице:
Если проанализировать таблицу, можно сделать следующие наблюдения:
- Дальнобойных фигур в сёги всего две: ладья и слон;
- Возможности отступления многих фигур ограничены или совсем отсутствуют.
Эти наблюдения позволяют разбить все фигуры на четыре группы:
- Король, обладающий абсолютной ценностью;
- Старшие фигуры (ладья и слон), способные к дальнобойным атакам и быстрому отступлению;
- Генералы (золотой и серебряный), чьи возможности наступления значительно превышают возможности отступления;
- Младшие фигуры (конь, стрела, пешка), не способные отступать.
Начальная расстановка и очерёдность хода
В сёги играют два игрока, которых принято называть сэнтэ (ходящие первыми) и готэ (ходящие вторыми), на квадратной доске 9x9 клеток. Начальная расстановка фигур показана на рисунке:
Также у каждого игрока есть специальная подставка (комадай), куда помещаются взятые у противника фигуры. Также принято говорить, что взятые фигуры оказываются «в руке».
Перевороты
Три последние горизонтали (относительно каждого игрока) являются зоной переворота. Любая неперевёрнутая фигура (кроме золота и короля), начинающая или заканчивающая свой ход внутри этой зоны, может перевернуться и превратиться в другую фигуру. Правила превращения фиксированы и показаны в таблице:
Важно отметить, что решение о том переворачивать фигуру или нет, принимает игрок. Случаи, когда переворот необходим, описаны в разделе запрещённые ходы.
Сбросы
Правило сброса — это то, что делает игру сёги одной из самой сложных игр, придуманных человечеством. Суть правила заключается в том, что любую съеденную у противника фигуру можно выставить на любое свободное поле как свою.
В правиле сброса есть несколько ограничений, но они довольно просты:
- Все фигуры сбрасываются не перевёрнутыми (даже если они сбрасываются в зону переворота);
- Нельзя сбрасывать пешку на ту вертикаль, где уже есть пешка (токин не считается пешкой);
- Нельзя сбрасывать пешку с матом.
Запрещённые ходы
Если противник сделал запрещённый ход, ему немедленно засчитывается поражение, поэтому крайне важно знать список запрещённых ходов:
- Ходы, нарушающие правила (например, отсутпление золотом по диагонали);
- Нарушение правил сброса (например, сброс второй пешки на вертикаль);
- Ход, после которого фигура не сможет сделать ни одного хода. Это правило требует пояснения. Нельзя ходить пешкой на последнюю горизонталь без переворота или конём на последнюю или предпоследнюю горизонталь без переворота. Очевидно, что и сбрасывать фигуры таким образом нельзя.
Ситуация с оставлением короля под шахом не до конца ясна. Если игрок не заметил шах своему королю, то следующим ходом противник может (но не обязан) съесть короля. В этом случае игра считается законченной.
Завершение игры
Игра заканчивается, когда один из игроков поставил мат или сделал запрещённый ход. Но в сёги существуют дополнительные правила окончания игры:
- Если позиция повторилась трижды в результате непрерывной серии шахов (т.н. «вечный шах»), то на четвёртый раз атакующий игрок должен сделать другой ход, иначе ему будет засчитано поражение.
- Если же позиция повторилась 4 раза без объявления шаха, то игроки переигрывают партию без объявления результатов, но с переменой цвета на оставшееся время.
Вышеописанные правила делают ничейный результат крайне редким для сёги (не более 3% от всех сыгранных игр). Но тем не менее, ничья возможна в одном случае: если оба короля вошли в лагерь противника и укрепились там. Если оба игрока согласны с тем, что возникшая ситуация тупиковая, то происходит подсчёт очков. Все фигуры (в т.ч. и в руке) кроме короля, слона и ладьи оцениваются в 1 очко, слон и ладья — в 5 очков, король в подсчёте не участвует.
В профессиональных партиях проигрывает игрок, у которого меньше 24 очков, если у обоих игроков не меньше 24 очков, то объявляется ничья. В любительских партиях побеждает тот, у кого не менее 27 очков, если у обоих игроков по 27 очков, то победа присуждает готэ.
Алгоритм нахождения лучшего хода
Алгоритм MiniMax
Впервые стратегия поиска лучшего хода для любой заданной позиции была описана ещё Клодом Шенноном. Если немного подумать, то можно заметить, что эта стратегия довольно проста и применима к любой игре.
Пусть у нас есть некоторая позиция, в которой нам необходимо сделать оптимальный ход. Вначале необходимо сгенерировать все разрешённые правилами ходы. Потом каждый из корректных ходов необходимо оценить. Ходы, ведущие к победе, будут оцениваться как +1, ведущие к поражению, — как -1, и ходы, ведущие к ничейным позициям, получат оценку 0.
Для того, чтобы определить к какому результату приведёт нас рассматриваемый ход, мы должны предположить, что противник будет на каждый наш ход отвечать лучшим возможным способом. Т.е. фактически воспользуется рассматриваемым алгоритмом: сгенерирует все свои корректные ходы и среди них выберет лучший, причём для оценки того насколько хорош его ход, он предположит, что мы ответим лучшим возможным способом и т.д.
Получается, что в процедуре поиска лучшего хода с нашей стороны будет вызвана процедура поиска лучшего ответа со стороны противника, из которой будет вызвана процедура поиска лучшего нашего ответа на ответ противника, и т.д.
Функция поиска лучшего хода будет рекурсивно вызывать сама себя до тех пор пока не возникнет матовая или ничейная ситуация.
При этом оценка итоговой позиции не представляет сложности, а при оценке родительских узлов пользуются следующими правилами:
- Оценка хода для первого игрока вычисляется как максимум оценок дочерних узлов;
- Оценка хода для второго игрока вычисляется как минимум оценок дочерних узлов.
Такой алгоритм называют MiniMax. Если графически изобразить цепочку вызовов, то получится т.н. игровое дерево:
Каждый узел в этом дереве представляет собой один анализируемый ход. Оценка узла будет равна максимальной оценке его дочерних узлов. Ниже показан порядок в котором будут анализироваться узлы (зелёный — победа, красный — поражение, жёлтый — ничья):
Alpha-Beta отсечение
В рассмотренном выше примере для получения итоговой оценки узла У0, пришлось получить оценки для всех остальных узлов У1-У16, но на самом деле в этом не было необходимости: как только мы узнали, что узел У1 приводит к победе, необходимость в анализе узлов У7-У16 отпадает, т.к. любые оценки, полученные для тех узлов, не превысят оценку узла У1 (т.к. она максимальна), а это значит, что хода лучше чем У1 просто нет. Если учесть это, то анализируемое дерево будет выглядеть следующим образом:
Очевидно, что такой сокращённый анализ не ухудшает точность решения, но значительно сокращает время поиска лучшего хода. Именно идея «обрезки» неперспективных ветвей дерева лежит в основе алгоритма Alpha-Beta отсечений.
При использовании отсечений дополнительно вводятся две переменные: минимум для сэнтэ (A) и максимум для готэ (B). Сам алгоритм Alpha-Beta отсечений похож на алгоритм MiniMax, за исключением следующих пунктов:
1. Если оценка какого-либо хода выходит за диапазон [A,B], то анализ ветви можно досрочно прекратить, т.к. у игроков есть ходы, приводящие к лучшей позиции.
- Если в какой-либо момент оценка первого игрока становится больше A, то значение A обновляется;
- Аналогично поступают и с оценкой B для второго игрока.
Важным моментом при использовании этого алгоритма является порядок просмотра ходов. Если сначала рассматривать те ходы, которые сильнее всего сужают диапазон [A,B], то количество отсечённых ветвей будет достаточно большим. Возвращаясь к рассмотренному выше дереву, легко заметить, что порядок просмотра У7, У12, У1 даст гораздо меньший выигрыш в производительности. Поэтому перед использованием алгоритмов с отсечениями производят предварительную сортировку ходов по ожидаемой эффективности.
Конечно, заранее невозможно узнать, какой ход будет самым лучшим, но есть некоторые эвристические правила. Например, хорошими считаются ходы-взятия, шахи, ходы, улучшающие позицию, и т.д.
Функция оценки позиции
Все описанные выше алгоритмы производят просмотр игрового дерева на всю глубину, но реализовать такие алгоритмы на практике практически невозможно, поэтому глубину просмотра искусственно ограничивают: рекурсивные вызовы прекращают не только в случаях мата и ничьих, но и при достижении максимальной глубины анализа. Маты при просмотре дерева на ограниченную глубину встречаются сравнительно редко, а всем нематовым позициям приходится присваивать некоторую эвристическую оценку, для получения которой используют методы, описанные ниже.
Материальная оценка
В большинстве шахматоподобных игр весьма точной оценкой позиции является оценка материала. При этом каждой фигуре присваивается определённая стоимость, а оценкой позиции для игрока является разность между суммой его фигур и суммой фигур противника. В сёги тоже используется оценка материала, таблица стоимости фигур приведена ниже:
Все фигуры в руке оцениваются на 30% дороже, т.к. их мобильность за счёт возможности сброса значительно возрастает.
Некоторых пояснений требует высокая стоимость короля и токина. Столь высокая стоимость короля объясняется тем, что король — фигура абсолютной важности, с его проигрышем партия заканчивается, поэтому король ценится дороже, чем все остальные фигуры вместе взятые. А стоимость токина так высока, потому что токин — лучшая фигура для обменов: при обмене токин-серебро один игрок получает в руку серебряного генерала, а второй игрок получается всего лишь пешку.
Стратегическая оценка
Прежде чем говорить о важности стратегической оценки, необходимо ещё раз отметить тот факт, что фигуры никогда не покидают игру и все взятые фигуры могут вернуться в любой момент. Этот факт кардинальным образом меняет подход к оценке позиции.
Во-первых, крайне эффективная в шахматоподобных играх эвристика обменов становится не только неэффективной, но и вредной. Если в шахматах выиграть одну пешку и постоянно идти на равноценные обмены, то в эндшпиле преимущество в одну пешку часто оказывается решающим. В сёги такие обмены могут привести к сбросам вражеских фигур в ваш лагерь.
Во-вторых, в сёги очень популярны жертвы. Например, в конце партии часто приходится отдавать старшую фигуру за золотого генерала или коня, чтобы получить в руку фигуру, которой можно поставить мат или сделать эффективную вилку.
Если посмотреть, что общего у этих двух ситуаций, то можно заметить, что противник воспользовался неудачным расположением ваших фигур. В таких случаях принято говорить, что у фигур «плохая форма». В сёги форма зачастую оказывается важнее материального перевеса, поэтому характеристики формы обязательно должны оцениваться при оценке позиции. На рисунках ниже приведены примеры плохих и хороших форм (красным выделены ничем не защищённые генералы):
Дальнейшим развитием идеи «хороших форм» являются крепости — укрепления для короля, обеспечивающие ему безопасность и защищающие от шахов. Примеры распространённых крепостей приведены в таблице:
Понятно, что хорошие формы должны давать некоторый плюс в стратегическую оценку, а плохие формы, соответственно, ухудшать оценку, но помимо формы необходимо учитывать также контроль доски, близость генералов к своему или вражескому королю, наличие запертых фигур и т.д…
Подводя итог вышесказанному, надо ещё раз отметить, что в функции оценки позиции необходимо учитывать не только материальную составляющую, но и стратегическую.
Алгоритм выборочных продлений
Уже рассмотренные алгоритмы MiniMax и Alpha-Beta отсечения всегда находят лучший ход на заданной глубине, но проблема в том, что глубина анализа (8-10 ходов) недостаточна для сильной игры. Профессионалы просчитывают позиции на 12-14 ходов, а некоторые позиции более чем на 20 ходов. Такая глубина для компьютеров пока недостижима
.
Некоторым компромиссным вариантом является просмотр на значительную глубину только некоторых ветвей дерева, в то время как остальные ветви будут просматриваться на уменьшенную глубину. Такой подход называется методом выборочных продлений.
В шахматных программах обычно продлевают шахи, ходы пешки на последнюю горизонталь и сильные взятия. Но в сёги такой подход оказывается неэффективным. Было принято решение выполнять поиск без фиксированной глубины
, увеличивая глубину шаг за шагом. При этом все возможные ходы теоретически могут быть рассмотрены на разную глубину, поэтому необходимо дополнительно запоминать глубину, на которую был рассмотрен каждый ход.
Изначально глубина просмотра каждого хода равна 0, а оценка хода равна -INF (т.е. проигрыш). На первой итерации выполняется анализ позиции на глубину 1 для всех ходов, при этом каждый ход получает свою оценку эффективности, а глубина его просмотра увеличивается на 1. Затем все ходы упорядочиваются по эффективности, и лучшие ходы анализируются на глубину 2. Если во время очередного продления выяснилось, что ход с максимальной оценкой уже проанализирован на максимальную глубину, то этот ход исключается из дальнейшего рассмотрения. Процесс углубления продолжается до тех пор, пока все ходы не будут просмотрены на минимальную глубину. На рисунке ниже показан примерный порядок построения дерева при использовании выборочных продлений (максимальная глубина — 4, минимальная глубина — 2, в узлах показана оценка позиция на текущей глубине просмотра):
Дополнительным плюсом этого алгоритма является его эффективность в играх с ограничением времени: когда отведённое на ход время истекает, можно вернуть лучший из просчитанных результатов.
Кеширование
Известно, что кеширования является одним из самых эффективных способов повышения быстродействия программ. В контексте построения игровых алгоритмов кеширование используется для поиска уже проанализированных позиций.
Действительно, во время поиска лучшего хода некоторые позиции могут повторяться в пределах одной ветви или встречаться в разных ветвях дерева. Классический алгоритм рассматривал бы каждую такую позицию заново. Такие многократные вычисления значительно снижают общую производительность. Кеширование призвано избавить от необходимости выполнять повторные расчёты.
Поиск позиции в кеш основан на сравнении хеш-функции рассматриваемой позиции с хеш-функциями позиций, уже попавших в кеш. Особенностью большинства хеш-функций является наличие коллизий (ситуаций, когда разные входные данные дают одинаковое значение). Для игр такое поведение хеш-функций недопустимо, т.к. даже малейшие изменения в позиции очень сильно влияют на оптимальный ход. Учитывая вышесказанное, было принято решение использовать в качестве хеш-функции строку, однозначно описывающую позицию.
Для использования кеширования результатов в алгоритм поиска лучшего хода необходимо внести следующие изменения:
- Перед началом просчёта проверять наличие позиции в кеш;
- Если позиция содержится в кеш, то прекратить расчёт и вернуть полученное ранее значение;
- При завершении просчёта записывать результат в кеш;
Есть ещё один довольно тонкий момент. Если в кеш уже содержится искомая позиция, просчитанная на малую глубину, этот результат тоже можно использовать. Вспомним, что алгоритм Alpha-Beta отсечений очень чувствителен к порядку ходов. Практика показывает, что оценка, полученная с малой глубиной просчёта, является довольно качественной эвристической оценкой качества хода. Т.е. значения, хранящиеся в кеш, могут быть использованы для сортировки ходов перед вызовом Alpha-Beta отсечений.
Эффективность использования кеш можно оценить с помощью следующего графика, на котором показана зависимость глубины просчёта позиции в зависимости от времени и количества повторных обращений.
По графику видно, что использование кеш значительно повышает глубину просчёта для повторяющихся позиций. Например, при ограничении времени в 5 секунд на ход использование кеш позволяет добиться такой же глубины анализа, как и 100-секундный анализ без использования кеш.
Т.о. можно сделать вывод, что использование кеширования значительно повышает скорость анализа, но требует значительных затрат памяти на хранение обработанных позиций.
И в качестве заключения небольшой пример игры разработанной программы против программы Shogi Lvl. 100:
