Алгоритм генерации хода для игры Эрудит

Доброго времени суток, хабр!

В этой статье я расскажу о том, как я создавал искусственный интеллект для игры Эрудит. Подробности под катом.

Эрудит

Эрудит — отечественный аналог всемирно известной игры Scrabble — настольной игры, в которую могут играть от 2 до 4 человек, выкладывая слова из имеющихся у них букв в игровое поле. Игровое поле состоит из 15 х 15, то есть 225 клеток, на которых участники игры составляют слова. Каждое составленное слово приносит очки в зависимости от ценности используемых букв и клеток поля.

Поле для игры Эрудит выглядит так:


Рисунок 1. Поле для игры

Основные правила

Обычно правила оговариваются игроками до начала игры, но имеются некоторые общепринятые правила игры:

• В начале игры каждому игроку даётся по семь фишек. За один ход можно выложить несколько слов. Каждое новое слово должно соприкасаться (иметь общую букву или буквы) с ранее выложенными словами. Слова читаются только по горизонтали слева направо и по вертикали сверху вниз.
• Если игрок не хочет или не может выложить ни одного слова, — он имеет право поменять любое количество своих букв, пропустив при этом ход
• Если за ход игрок использовал все семь фишек, то ему начисляются дополнительные 15 очков.
• Сумма очков каждого хода состоит из суммы очков составленных букв, а также премий, получаемых за размещение букв на премиальных клетках.
• Премиальные клетки для букв: очки буквы, расположенной на зеленой клетке, удваиваются, на желтой – утраиваются.
• Премиальные клетки для слов: если одна из букв слова расположена на синей клетке, сумма очков всего слова удваивается, на красной – утраивается.

Первые шаги

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

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

Суффиксом слова называется любой последовательный набор букв слова, оканчивающийся последней буквой слова, но не включающий в себя первую.

Точки привязки

Рисунок 2. Рассматриваемый ряд

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


Рисунок 3. Точки привязки

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


Рисунок 4. Возможное количество букв префикса

Алгоритм нахождения слов в ряду

Для каждой клетки, являющейся точкой привязки – ищем все возможные слова следующим образом:

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

Префикс слова будет содержать либо клетки из руки игрока, либо клетки, уже размещенные на доске, но не одновременно.

Теперь, имея способ нахождения всех слов на поле, можно перейти непосредственно к описанию алгоритмов генерации хода.

Алгоритмы генерации хода

Я выбрал три алгоритма генерации хода: алгоритм выбора максимального значения, метод полного перебора, метод альфа-бета отсечения.

Алгоритм выбора максимального значения

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

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

Метод полного перебора

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

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

Метод альфа-бета отсечения

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

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

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

Результаты

Для реализации я использовал язык программирования Java. Словарь состоял из 12 тысяч слов, в программе был представлен в виде обычного Set'a.

Среднее время генерации представлено на диаграмме ниже:

Рисунок 5. Диаграмма времени генерации

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

Однако выигрыш по времени генерации повлек за собой проигрыш по очкам: алгоритм выбора максимального значения в среднем приносит игроку порядка 30 очков, в то время как остальные методы — порядка 60 очков.

TODO

К сожалению, из рассмотрения были исключены следующие пункты:

• Анализ комбинаций с редкими буквами
• Анализ букв, остающихся после хода
• Анализ дальнейших действий противника
• Буквы, которые следует менять при пропуске хода

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

Литература

• Лекция Peter Norvig по игре Scrabble. Из этого источника заимствовано наибольшее количество идей.
• Правила игры
• Полный перебор wiki
• Великий Томас Кормен: Алгоритмы. Построение и анализ.
• Альфа-бета отсечение

Спасибо за внимание!