Мы потратили семь лет на эксперименты с ИИ для царской игры Ура, и, наконец, пришли к сильному решению по правилам Финкеля, Блица и Мастерса! В конечном итоге, для этого понадобилась пара красивых уравнений, которые я объясню в статье.
На самом деле, мы не «просто» нашли сильное решение игры. Для сильного решения необходимо находить наилучший ход из каждой позиции. Мы сделали это, плюс вычислили точную вероятность победы каждого игрока при оптимальной игре из каждой позиции. Для этого мы воспользовались нашей опенсорсной библиотекой RoyalUr-Java.
Ниже мы опишем, как это работает. Также мы написали технический отчёт.
Идеальная партия
Прежде, чем переходить к подробностям, покажем небольшое живое демо. В нём два бота участвуют в ничейной дуэли — это идеальная партия! Лично меня это завораживает. Как часто вам доводится наблюдать за чем-то математически идеальным?
Идеальная партия в Royal Game of Ur между двумя ботами. Чтобы ускорить игру, мы не отображаем кости. Вы сами можете сыграть с идеальным ботом.
Идеальность означает максимизацию вероятности выигрыша
Чтобы создать идеально играющего бота, нужно чтобы он максимизировал свою вероятность выигрыша.
В отличие от шахмат или го, при игре в царскую игру Ура нельзя заранее спланировать идеальную победу. Этого не позволят сделать кости! Из-за этого решение царской игры Ура фундаментально отличается от решения игр без вероятностей.
Вместо того, чтобы планировать единственный путь к победе, нам нужно учитывать каждый возможный будущий путь, который становится возможен или невозможен из-за бросков костей, а затем взвесить их все при выборе ходов. Это взвешивание вариантов будущего развития делает решение игры Ура больше похожей на решение покера, чем шахмат.
Для обработки вероятностей мы используем итерации состояний среды
Как же вычислить, какой ход максимизирует вероятность нашей победы, если до конца игры может пройти сотни ходов? Мы используем для этого итерацию состояний среды.
Итерация значений позволяет нам воспользоваться преимуществом игры Ура, а именно относительно низким количеством состояний. Например, по правилам Финкеля есть всего 276 миллионов состояний. Этот размер достаточно мал для того, чтобы можно было хранить весь граф состояний для правил Финкеля в памяти. Затем можно использовать итерацию состояний среды для распространения вероятности выигрыша или проигрыша обратно на весь процесс игры.
Имитация состояний среды обратным распространением потока состояний по графу.
Выше показан упрощённый пример того, как итерация состояний среды модифицирует граф. Значения перемещаются от состояния к состоянию, изначально из состояний победы или проигрыша, а затем обратно, к началу игры. В этом примере значение, к которому приходит каждое состояние — это вероятность оказаться во состоянии победы, если выполнить случайный переход из этой точки.
В более крупных графах, например, в графе царской игры Ура, я предпочитаю воспринимать итерацию состояний среды, как симуляцию жидкости. «Вероятность выигрыша» — это жидкость, которая медленно течёт обратно по всей партии игры. Особенно удобно то, что вероятности, к которым приходит итерация состояний среды — это наша вероятность выигрыша!
Как работает итерация состояний среды?
Основной принцип итерации состояний среды таков: мы распространяем победы и проигрыши обратно.
Пример: если вы знаете, насколько хороши следующие позиции, которых вы можете достичь, то можете вычислить, насколько хороша текущая позиция. А зная, насколько хороша эта позиция, можете вычислить, насколько хороши были позиции до неё и так далее...
При помощи этой методики мы можем пройти назад по всей игре, обновляя значения состояний на основании состояний, идущих после них.
Обратный проход
Этот обратный проход реализован с помощью простого взвешенного среднего. Вероятность выигрыша в одном состоянии равно взвешенному среднему вероятности выигрыша во всех состояниях после каждого броска костей (пока мы не будем рассматривать выбор хода).
При помощи этой простой операции мы каскадно распространяем победы и проигрыши по пространству царской игры Ура.
Достаточно ли этого? К сожалению, нет. Из-за петель в графе состояний одного обратного прохода оказывается недостаточно. Есть неудобные позиции, в которых можно сыграть множество ходов и вернуться к той же позиции, которая была до них. Основная ценность итерации состояний среды заключается в решении этих петель.
Нам понадобится множество обратных проходов
Именно благодаря итерации мы можем работать с петлями. Вместо того, чтобы делать один обратный проход, мы выполняем несколько. При каждом выполняемом проходе наши оценки вероятности выигрыша из каждой позиции становятся точнее.
Недостаточность одного обратного прохода из-за петель вызвана тем, что процент выигрыша в некоторых состояниях будет некорректным, если использовать его для вычисления вероятности выигрыша другого состояния. Их значение некорректно, потому что только что вычисленное состояние может влиять на состояния, использованных в этих вычислениях (циклическая зависимость)!
Оказывается, было доказано, что используемые нами уравнения со временем сходятся. Мы знаем это, потому что уравнения, применяемые нами для решения царской игры Ура — это формулировки уравнений Беллмана. А в математике доказано, что уравнения Беллмана со временем сходятся.
Как оценивать ходы, которые делают противники?
Это очень важная особенность! И она тесно связана с ограничением решений любых игр, содержащих вероятности.
В любой игре, содержащей вероятности, лучшая стратегия выигрыша сильно зависит от того, что делает противник. Однако мы не можем спрогнозировать особенности и склонности каждого игрока. Поэтому мы предполагаем, что оба игрока играют оптимально, делая по очереди наилучшие ходы.
Исходя из предположения об оптимальной игре противников, мы можем вычислить стратегию, при которой ни один из игроков не может повысить свою вероятность победы изменением своих ходов. Такой тип стратегии называется равновесием Нэша. Эту стратегию невозможно победить. Но в то же время эта стратегия не всегда замечает и использует погрешности в игре противника. Нам приходится идти на этот компромисс.
Оказалось, что для вычисления оптимальной игры достаточно простого «жадного» решения. В каждом состоянии мы предполагаем, что игрок совершит ход, который приведёт к наибольшей вероятности выигрыша. Хотя процент победы, используемый нами для принятия этого решения, поначалу может быть некорректным, он всё равно достаточно хорош, чтобы проценты выигрыша со временем могли сойтись.
Внутри нашего ядра итерации состояний среды выбор оптимального хода для каждого игрока представлен максимумом или минимумом среди значений его возможных ходов.
Окончательный обзор итерации состояний среды
Итак, мы поняли, как можно вычислять значение одного состояния на основании других состояний. Давайте объясним, как эти части объединяются в конечное множество уравнений, и как мы применяем их для создания решённой таблицы игры.
Взвешенное среднее и выбор хода образуют простое ядро. Это ядро комбинирует взвешенное среднее с нашим оптимальным выбором хода. Мы итеративно применяем это ядро ко всем состояниям в игре снова и снова, пока вероятности выигрыша не сойдутся. Применяя это ядро, мы используем его для обновления значений V(state) в таблице, пользуясь другими значениями из той же таблицы.
Нашим конечным результатом становится таблица состояний и значений. Создаваемая конечная таблица будет содержать наши оценки вероятности выигрыша каждого игрока из каждой позиции. Далее мы можем использовать эту таблицу, чтобы обеспечить оптимальную игру агентов, заставив их выбирать ход, приводящий в состояние с наибольшей вероятностью победы.
В этом и заключается итерация состояний среды! Она позволила нам решить царскую игру Ура с точностью, ограниченной лишь точностью 64-битных чисел с плавающей запятой. В случае правил Финкеля это означает вычисление вероятности победы с точностью до 3E-14%, или 0,00000000000003%. Мне кажется, это очень круто.
А теперь давайте ускорим вычисления! Настало время оптимизации.
Урезаем игру ради скорости!
Выполнение итерации состояний среды для всей игры — это и затратно, и неэффективно. В течение тысячи итерации, необходимых для обучения наших моделей, возникла лишь узкая граница состояний, со временем сходящихся к своему истинному значению. Состояния, более близкие к состоянию победы, уже сошлись, а у отдалённых состояний ещё недостаточно информации для схождения.
Нам бы очень хотелось обновлять только те состояния, которые близки к схождению на каждой итерации, чтобы не тратить время на обновление всех остальных. К счастью, есть один хитрый трюк, позволяющий это сделать!
После вывода фишки с доски вернуть её невозможно.
Выведя фишку, её нельзя вернуть [прим. пер.: по правилам в интерпретации Финкеля для победы игроку нужно вывести все свои фишки с поля]. Эта, казалось бы, несущественная деталь даёт нам огромное преимущество: она разрывает все петли в графе состояний. Поэтому состояния после вывода фишки не могут зависеть от состояний до них.
Это очень важно! Это позволяет нам разбить одну большую игру Ура на множество мелких «мини-игр». После вывода фишки мы переходим от одной мини-игры к другой. Благодаря этому мы получаем преимущество при обучении моделей, потому что каждая из этих мини-игр зависит только от собственных состояний и от состояний, следующих мини-игр, которых можно достичь.
Поэтому можно обучать модель не всей игре целиком, а одной за другой каждой из этих маленьких игр. А поскольку каждая из этих мини-игр намного меньше целой партии, обучаться им можно более эффективно с гораздо меньшей тратой лишних ресурсов! Благодаря этому время решения игры по правилам Финкеля на моём M1 Macbook Pro снизилась с 11 часов до менее чем 5 часов.
Хранение всех вероятностей победы в плотно упакованной таблице
Ещё один важный при решении царской игры Ура вопрос — обеспечение эффективного использования памяти.
Нам нужна таблица поиска для каждой позиции игры вероятности того, что игрок выиграет, начиная с этой позиции. Для правил Финкеля (самых популярных) это означает создание карты из 275827872 уникальных позиций. Для правил Мастерса она ещё крупнее, более миллиарда позиций.
Как же нам создавать эти большие таблицы? Мы решили, что лучше всего ещё больше усложнить процесс! Нас волновало использование памяти, поэтому создали собственную реализацию таблиц, оптимизированную под этот аспект.
Наши таблицы состоят из плотно упакованных двоичных ключей и значений. Мы не хэшируем ключи для поиска элементов, как это делается обычно, а сортируем ключи и используем двоичный поиск. Это позволяет сохранять минимально возможный размер таблиц, обеспечивая при этом высокую скорость.
Благодаря нашей переусложнённой таблице мы можем снизить потребление памяти до всего 12 байтов на каждый элемент таблицы, то есть полное решение по правилам Финкеля уместится всего в 1,6 ГБ. А сжатые версии занимают всего 827 МБ, если вас устроит точность в пределах 0,01%.
Запись состояний игры в 32-битные ключи
Ключи поиска в нашей таблице обозначают каждую позицию, которой можно достичь в игре. Эти позиции (состояния) — это «снимки» игры в конкретный момент, в том числе и порядок хода, количество фишек и очков у каждого из игроков, а также расположение фишек на поле. Для каждого из этих состояний мы сохраняем вероятность победы игрока со светлыми фишками, если в дальнейшем оба игрока будут играть идеально.
Чтобы использовать как можно меньше памяти, мы закодировали состояния в небольшие двоичные числа. По правилам Финкеля мы кодируем состояния в 32 бита. Для упаковки всей этой информации нужны небольшие хитрости...
Самый простой способ упаковки состояния в двоичный вид по правилам Финкеля потребовал бы 54 бита:
1 бит: чей сейчас ход?
1 бит: в игре уже кто-то выиграл?
2 x 3 бита: фигуры и очки игрока со светлыми фишками.
2 x 3 бита: фигуры и очки игрока с тёмными фишками.
20 x 2 бита: содержимое каждой плитки на поле (они могут быть пустыми, содержать светлую фишку или тёмную фишку).
54 бита — это не так уж плохо. Для хранения таких ключей можно использовать стандартные 64 битные числа, и это всё равно окажется достаточно быстро и эффективно по памяти. Но разве не здорово будет здорово, если удастся уместить всё в 32 бита?
К счастью, можно воспользоваться простыми трюками для снижения необходимого количества битов.
Первым делом стоит отметить, что часть информации в ключах избыточна. Количество фишек, которое осталось у игроков, и то, настало ли состояние выигрыша, можно вычислить из другой информации, хранящейся в ключах. Следовательно, мы можем убрать эти значения и сэкономить 7 битов!
Ещё от 12 битов можно избавиться, поменяв способ хранения плиток, достижимых только для одного игрока. Мы называем эти плитки «мирными зонами». Так как доступ к ним есть только у одного игрока, нам нужно только по 1 биту на каждую. Это вдвое уменьшает место, необходимое для хранения этих плиток, и мы получаем суммарный размер ключа в 35 бита. Уже довольно близко к желаемым 32 битам!
Оставшиеся 3 бита можно убрать, сжав плитки военной зоны. До сжатия каждая военная плитка использует 2 бита для хранения одного из трёх состояний (пустая, светлая фишка, тёмная фишка). Это значит, что в 2 битах есть дополнительное четвёртое состояние, которое мы не используем. Иными словами, можно выполнить сжатие!
Для сжатия военной зоны мы создаём список всех допустимых 16 битных вариаций, которые может принимать военная зона, и присваиваем их новым меньшим числам при помощи небольшой таблицы поиска. Это позволяет нам сжать 16 битов до 13, добившись нашей цели — 32 битов!
Игра Ура симметрична — симметрична Ура игра
В качестве вишенки на торте мы можем удалить и бит хода, потому что царская игра Ура симметрична. На самом деле, это достаточно важно! Это значит, что если поменять местами светлого и тёмного игроков, то их вероятность победы остаётся той же. Это очень полезно, ведь благодаря этому можно хранить и вычислять лишь половину игровых состояний. Очень солидная экономия!
Теперь у нас есть 31-битная кодировка, которую можно применять для хранения ключей в таблице! Теоретически, минимальное количество битов, которое необходимо для представления всех 137913936 состояний — это 28. Так что мы немного не дотягиваем, но меня вполне устраивает, что мы на расстоянии всего 3 битов до идеала!
Для других правил потребуется больше 32 битов
К сожалению, при попытке перейти к другим правилам мы столкнулись с препятствием. В случае правил Мастерса и Блица мы при помощи тех же методик смогли сжать состояние всего до 34 битов из-за более длинного пути по полю. То есть на 2 бита больше, чем нам требуется...
Но в нашем мешке ещё остались трюки! Вместо того, чтобы удваивать размер ключа до 64 битов, можно разбить таблицу на 4 части. 2 дополнительных бита можно использовать для выбора части, в которой нужно выполнять поиск, а затем выполнять поиск при помощи оставшихся 32-битов. Это позволило нам уместить полмиллиарда элементов по правилам Мастерса в 3 ГБ вместо 5 ГБ!
Вот и вся таблица! В нашей реализации нет ничего особенного, но она хорошо подходит для нашей цели — снижения объёма используемой памяти и обеспечения быстрого чтения и записи.
Мы выложили решённую игру в опенсорс
Теперь у вас есть всё необходимое для самостоятельного решения царской игры Ура! Однако если вам больше хочется поэкспериментировать сразу с решённой игрой, то можете воспользоваться несколькими реализациями для обучения и использовать наши модели, выложенные в опенсорс.
Готовые обученные модели выложены на HuggingFace.
Наша Java-библиотека RoyalUr-Java способна считывать и обучать эти модели.
Наша Python-библиотека RoyalUr-Python способна считывать 16-битную модель по правилам Финкеля.
Реализация на Julia разработчика Jeroen позволяет быстро обучать модели, использующие другой формат файлов.
Raph выпустил Lut Explorer, при помощи которого можно исследовать различные позиции решённой игры.
Если вы займётесь экспериментами с решённой игрой, то нам бы любопытно было узнать, чего вы смогли добиться! Если вам любопытно, приглашаю вас в наш Discord. У нас есть канал, посвящённый обсуждениям исследований, подобных тем, о котором я рассказывал выше.
Теперь отойдём от технических подробностей и поговорим о том, как решение царской игры Ура соотносится с областью ИИ в целом.
Можем ли мы решить другие игры?
Сложно найти игру, столь же подходящую для итерации состояний среды, как царская игра Ура. Из-за элемента удачи, неконечного геймплея и ограниченного количества позиций итерация состояний среды идеально подходит для её решения. Для других игр она подходит не так хорошо.
Некоторые игры, которые мне бы хотелось решить, например короткие нарды, имеют слишком много позиций, чтобы их можно было решать итерацией состояний среды. У игры Ура примерно 276 миллиардов позиций, а у коротких нард — примерно 100 квинтиллионов... Это значит, что для решения коротких нард при помощи итерации состояний среды потребуется столько памяти, что эта задача не представляется возможной. Понадобилось бы примерно 3% от общемирового размера хранилищ данных, или триллион гигабайтов.
Решение других популярных игр, например, «Четыре в ряд» (Connect-Four) или покера на костях (Yahtzee) при использовании итерации состояний среды было бы неэффективным. В Connect-Four нет костей, поэтому её эффективнее будет решать при помощи поиска. В Yahtzee есть кости, но она упрощена своим неизбежным движением вперёд. Выполнив действие в Yahtzee, вы ни за что не сможете вернуться к состоянию до этого действия; поэтому Yahtzee эффективнее решать, оценивая партию сзади вперёд.
По нашим оценкам, любую игру со сложностью пространств-состояний порядка 1E+11 или ниже реалистично решать при помощи итерации состояний среды. Это отсекает возможность применения итерации для решения более сложных игр, в том числе и коротких нард.
Именно поэтому, несмотря на то, что решение игры Ура стало примечательным достижением для игры, оно не будет прорывом в решении более сложных игр. Могут существовать некоторые игры с вероятностями и полной информацией, для которых можно найти сильное решение при помощи итерации состояний среды. Но сама по себе итерация не позволит нам решать сложные игры наподобие коротких нард.
Тем не менее, мы не должны полностью сбрасывать со счетов итерацию состояний среды! На напряжённых последних ходах настольной игры итерация состояний среды может принести много пользы. Продвинутые ИИ-системы для игр часто используют базы данных для безошибочных ходов в эндшпиле, а итерация состояний — это одна из методик, которые можно использовать для создания таких баз данных. Например, базы данных часто используются для идеальных стратегий конца игры в коротких нардах. Схожие техники можно также использовать для идеальных ходов в других играх наподобие лудо или парчиси!
Для чего мы будем использовать решённую игру?
Решение игры позволяет нам вычислять точность игрока в играх, создавать подробный анализ партий и дать игрокам идеального соперника (Panda). Всё это сильно влияет на то, как игроки играют в царскую игру Ура на нашем сайте.
Если вам интересно почитать о том, что это значит для игры Ура, можете изучить наш пост.
