Существует ли такая буква, что игрок 1 всегда будет выигрывать?

Оглавление

The Game
Introducing Minimax
Applying Minimax
Improvements
Conclusion

Игра

Простую словесную игру для двух игроков можно описать так:

Сначала игрок 1 начинает с того, что имеет в виду слово длиной не менее 4 букв, например: 'середина'. Он играет первую букву слова, то есть «м». Затем игрок 2 выбирает следующую букву, которая соответствует любому известному ему слову, начинающемуся с «м». Затем два игрока продолжают по очереди выбирать буквы, стараясь не выбирать букву, которая приводит к образованию слова (учитываются только слова, содержащие не менее 4 букв).

Например, если текущая строка букв или префикс — «меди», игрок 1 не выберет букву «а», потому что «медиа» — допустимое слово, из-за которого он проиграет.

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

Типичная игра (здесь проигрывает игрок 2) может выглядеть так:

Player 1: m
Player 2: e
Player 1: d
Player 2: i
Player 1: u
Player 2: m

В эту простую словесную игру довольно весело играть с друзьями. Я рекомендую вам сначала попробовать игру самостоятельно, прежде чем читать дальше.

Представляем Минимакс

Сыграв несколько раундов игры, вы можете начать задаваться вопросом, а что, если бы мы могли придумать алгоритм, который подсказывал бы нам оптимальную следующую букву для выбора, учитывая текущий префикс, который у нас есть? Еще лучше, если бы он мог сказать нам, какие буквы может выбрать игрок 1, чтобы он всегда выигрывал, тогда мы могли бы объявить эту игру решенной!

Как следует из названия этой статьи, на самом деле существует алгоритм, который мы можем использовать: минимакс.

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

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

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

Чтобы присвоить значение конкретному состоянию (в этом случае мы в конечном итоге хотим присвоить значение состоянию A), алгоритму придется рекурсивно учитывать все последующие игровые состояния. Для синих состояний, поскольку это ход игроков, мы выберем ход, ведущий к состоянию с наивысшим значением, поэтому они помечены как «максимальные» состояния. Например, состояние A выберет ход справа, так как оно приведет к состоянию C с более высоким значением 3 по сравнению с состоянием B, значение которого равно 2. И наоборот, красные состояния, являющиеся состояниями противника, будут выберите ход, ведущий к состоянию с наименьшим значением. Таким образом, они помечены как «минимальные» состояния. Например, состояние C выберет ход слева, так как оно ведет к состоянию D с меньшим значением 3 вместо состояния E со значением 4.

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

Затем, как только значения всех состояний будут присвоены, оптимальным ходом для состояния A будет именно тот ход, который приводит к состоянию с наивысшим значением (состояние C), и все готово!

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

Применение минимакса

После общего обзора того, как работает минимаксный алгоритм, давайте сразу перейдем к фактической реализации.

Настройка словаря

Во-первых, нам понадобится словарь, который послужит нашим банком слов. Мы будем использовать пакет nltk, который вам потребуется pip install вместе со списком слов unix, который можно загрузить с помощью кода или здесь.

Обратите внимание, что словарь содержит некоторые слова, которые не будут иметь для нас значения, например, местоимения и слова, в которых меньше 4 букв. Следовательно, мы сделаем быструю обработку словаря, чтобы избавиться от этих слов, используя удобную функцию Python filter.

Кроме того, мы будем хранить наш словарь в структуре данных trie, так как это позволит нам искать слова быстрее, чем простой список. В частности, мы будем использовать pygtrie модуль с открытым исходным кодом, реализованный Google, который вам также потребуется pip install.

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

Идеальный!

Вспомогательные функции

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

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

get_score возвращает 1, когда игрок (игрок 1 или 2) выигрывает, и 0 в противном случае. Это легко вычислить, сравнивая четность длины слова и номера игрока с помощью функции xor (^).

Функция значения

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

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

Собираем это вместе

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

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

И вот оно! Теперь вы знаете, как победить своего друга.

Улучшения

Одна вещь, которую вы заметите, если попытаетесь запустить код, это то, что он не особенно быстр, его выполнение занимает около 9,2 с.

В следующем разделе мы рассмотрим различные способы ускорения этого процесса менее чем за секунду:

  • Альфа-бета обрезка
  • Удаление ненужных слов
  • Эвристика оценки

Альфа-бета обрезка

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

Например, обращаясь к приведенной выше диаграмме, как только мы оценили состояние G, мы знаем, что максимальное значение состояния H равно -3, и поэтому оно никогда не будет выбрано состоянием F, значение которого равно как минимум 7. Следовательно, не существует необходимо дополнительно оценить состояние I. Это уменьшит количество вычислений, которые мы должны выполнить, поскольку нам не нужно оценивать все вычеркнутые состояния.

Реализовать сокращение альфа-бета в нашем алгоритме игры в слова довольно просто (нам нужно добавить только 4 строки!), потому что, пока «максимальное» состояние игры найдет один ход, который может гарантировать победу, это состояние игры определенно будет иметь значение из 1, и нет необходимости рассматривать какие-либо другие ходы или состояния.

Для этого все, что нам нужно сделать, это проверить, равно ли текущее значение максимального состояния 1 (или 0 для минимального состояния), и в этом случае мы просто вернем 1 и прекратим проверку оставшихся игровых состояний.

Как видно выше, это на самом деле позволяет нам значительно сократить количество оцениваемых игровых состояний, что приводит к сокращению времени выполнения на 75% до 2,3 с!

Удаление ненужных слов

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

Например, мы никогда не придем к «медиумам», потому что слово «медиум» первым завершит игру.

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

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

Мы видим, что этот алгоритм (на выполнение которого ушло 18 секунд) уменьшает количество слов в нашем словаре на 60%, что приводит к дополнительному сокращению времени выполнения на 52% до 1,1 секунды!

Эвристика оценки

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

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

Например, если текущим префиксом является «medi», а единственными возможными словами являются «media» и «medical», то мы знаем, что игрок 2 выиграет, что делает это фактически терминальным состоянием игры.

Реализация также довольно проста — помимо проверки того, что осталось только одно возможное слово, мы также проверяем, совпадают ли четность длины слова для оставшихся слов.

Это дает нам окончательное время выполнения 0,9 с, что на 90% больше, чем у исходного алгоритма!

Заключение

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

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

Некоторые заключительные мысли

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

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

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