В 2016 году в журнале Nature вышла статья "Mastering the game of Go with deep neural networks and tree search", в которой была представлена программа, в дальнейшем не раз побеждающая сильнейших игроков мира. При этом ранее существовавшие программы были способны соревноваться лишь с игроками любительского уровня.
Комбинирование глубокого обучения, обучения с подкреплением, деревьев Монте-Карло, столь успешно показавшее себя в игре го, дало нам идею применить схожую архитектуру и в игре рендзю, представляющей из себя крестики-нолики, в которых от игроков требуется выстроить непрерывный ряд из пяти или более фишек своего цвета на доске 15x15.
Данная задача была нами реализована на языке Python с использованием связки библиотек numpy + tensorflow + keras.
При создании нашей программы мы в основном руководствовались архитектурой AlphaGo, в которой можно выделить несколько частей:
- SL policy. На собранной базе игр была обучена нейронная сеть, предсказывающая вероятность хода игрока-человека.
- Rollout policy. На той же выборке был обучен менее точный, но гораздо более быстрый вариант первой сети.
- RL policy. С помощью обучения с подкреплением на базе первой сети на серии игр с вариантами самой себя была обучена нейронная сеть, выполняющая ту же функцию
- Value network. С помощью SL policy и RL policy была сгенерирована база игр для обучения сети, по текущему состоянию предсказывающей вероятность выигрыша игроков.
Дерево игры состоит из состояний доски, соединённых ходами, которые переводят одни состояния в другие. В начале работы алгоритма дерево содержит только из состояния пустой доски. Затем в каждой итерации происходит спуск по дереву, когда на каждом шаге мы из текущего состояния переходим в его потомка с наибольшей ценностью (ценности в начале работы алгоритма нулевые), кроме того, с помощью вариации метода Upper Confidence Bound алгоритм побуждает выбирать малопосещаемые состояния. После попадания в "лист" происходит расширение: у листа создаётся потомок, награда в котором считается как усреднённое значение предсказания value network и результата игры, доигранной из этого состояния с помощью rollout policy. Далее ценности всех состояний, по которым мы пришли в текущее, обновляются, чтобы быть средним арифметическим из всех подобных наград. В конце в качестве хода выбирается ход, приводящий в непосредственного потомка корневой ноды с наибольшей ценностью.
Для предсказания наиболее вероятного хода противника была обучена нейронная сеть со следующей архитектурой:
- 5x5 Convolution (16 карт)
- 5x5 Convolution (32 карты)
- 5x5 Convolution (32 карты)
- 5x5 Convolution (48 карт)
- Dense (2048 нейронов)
- Dense (1024 нейрона)
- Dense (225 нейрона)
После каждого слоя (кроме последнего) стоит ReLU-активация и 10%-dropout. После последнего слоя стоит softmax, возвращающий вектор вероятностей поставить фишку на конкретную позицию развёрнутой (из размерности 15x15 в 225) доски. На вход подаётся тензор 15x15x3, а именно три карты 15x15. Первая карта в конкретной ячейке имеет значение 1, если там стоит фишка игрока, вторая карта имеет значение 1, если там стоит фишка соперника, третья карта имеет значение 1, если там ничего не стоит. В противном случае значение элемента карты - 0. Кроме того, при подаче в нейронную суть этот тензор расширяется нулями по границе до размера 19x19x3.
Для обучения нейронной сети из предварительно собранных игр были вычищены не доведённые до конца. Кроме того, для подчёркивания инвариантности относительно поворотов и отражений доски каждая игра была размножена относительно своей диэдральной группы. Дополнительно для лучшего обнаружения угроз и возможностей на краю доски для каждой игры было сгенерировано восемь её случайных сдвигов. В качестве оптимизатора был использован алгоритм Adadelta.
На C++ был написан алгоритм быстрого спуска, который по текущей позиции может сделать быстрый и относительно хороший ход. Так, в случае существования открытой линии из четырёх "своих" фишек, алгоритм делает этот, очевидно, являющийся выигрышным ход. В результате выделяется несколько приоритетных групп предтавляющих из себя позиции, которые являются соседями с:"своими" четвёрками, "чужими" четвёрками, тройками, прочими комбинациями. К выбору случайного хода из каждой группы алгоритм приступает в случае отсутствия элементов в предыдущей группе. В случае отсутствия на доске фишек алгоритм выбирает ход "h8", т.е. ставит фишку в центр.
В процессе работы алгоритма строится дерево игры, где каждая вершина - состояние доски (состояния не обязаны быть уникальными), а ребро - ход, приводящий доску из одного состояния в другое. В начале игры в дереве ровно одно корневое состояние - пустая доска. Каждое состояние по умолчанию имеет суммарную награду R и счётчик посещений C, равные нулю.
Алгоритм выбора хода состоит из N итераций (величина N определяется допустимым временем на вычисления). Каждая итерация состоит из следующих фаз:
- Спуск по дереву.
Согласно предсказанию policy network выбирается пять действий
с наибольшими вероятностями 
. Если текущее состояние является терминальным (т.е. в нём достигнута ничья или выигрыш одного из игроков), то начинается фаза 2. В противном случае, из состояний, соответствующих переходам по действиям a1...a5 выбирается минимальный ещё не созданный из данной вершины потомок. Если же все пять (или меньше, если у нас меньше пяти доступных ходов) потомков были созданы, то выбирается потомок с наибольшей ценностью. Ценность определяется как 
, где p - предсказание нейронной сети для действия, приводящего в этого потомка.
После выбора потомка фаза 1 запускается из него. - Из текущей вершины запускается алгоритм быстрого спуска. Его результат - 1, если игрок-владелец текущей вершины выиграл, -1 - если проиграл, 0 - если сыграл в ничью. Далее, в зависимости от "принадлежности" вершины, результат прибавляется с положительным или отрицательным знаком ко всем состояниям, по которым мы спускались в фазе 1. Также для них обновляется и счётчик посещений C.
После завершения всех N итераций выбирается действие, которое стоит совершить программе. Этим действием является действие, непосредственно приводящее в состояние с наибольшей средней наградой, т.е. с наибольшим 
.
В процессе разработки программы пришлось отказаться от обучения с подкреплением, value network, rollout policy.
- Использование обучения с подкреплением не помогло обучить нейронную сеть, играющую объективно лучше supervised policy.
- Обучение value network в большой степени опиралось на наличие RL policy. Кроме того, можно предположить, что различие сути игр го и рендзю отразилось на разнице в эффективности этой идеи.
- Недостаточные вычислительные мощности не позволили использовать rollout policy в качестве эффективного метода доигрывания игр.
- Тем не менее, использование достаточного количества эвристик в "ручном" алгоритме быстрого выбора хода показало себя очень хорошо, возможно, показывая даже лучшие результаты по сравнению с хорошей rollout policy.
Результирующая программа конкурентно играет с человеком, обладая способностью выстраивать сложные комбинации и думать на несколько ходов вперёд. Это свойство сохраняется даже при относительно небольшом (1 секунда) времени на обдумывание хода. Из нескольких десятков игр, сыгранных с автором проекта и прочими людьми, все игры были выиграны программой без наличия каких-либо очевидных ошибок её соперника.
Применение наработок AlphaGo к игре рендзю показало, что, с одной стороны, некоторые идеи не могут быть бесшовно перенесены в новую игру, страдая как от высоких технических требований, так и от различий в самих играх. С другой стороны, даже с заменой или даже полным отказом от отдельных компонентов, общая архитектура оказалось весьма эффективной в играх на любительском уровне, и, быть может, даже в играх с провессиональными игроками. Хоть последнее и может потребовать дополнительной доработки, но её можно производить в рамках текущей архитектуры. Например, возможно добавление дополнительных эвристик в существующий алгоритм быстрого выбора хода, или, быть может, даже возврат к идее применения обучения с подкреплением.
Работа данной программы гарантируется только при наличии 8Гб оперативной памяти или более. При разработке и тестировании использовался Python 3.5, работа других версий не гарантируется. Для установки требуется:
- Склонировать на локальный компьютер данный репозиторий.
- Перейти в корневую директорию репозитория.
- Перейти в поддиректорию renju.
- Запустить установочный скрипт:
- sys_setup.sh в случае, если требуется system-wide установка. Работа данного скрипта была проверена на свежеустановленной Ubuntu 16.04 и не гарантируется на других системах или системах, в которых установлены конфликтующие версии используемых библиотек.
- env_setup.sh в случае, если уже создано и задействовано python virtual environment без конфликтующих библиотек.
- Выполнить команду "jupyter notebook"
- В открывшемся окне браузера открыть файл play.ipynb
- В верхнем меню выбрать Cell -> Run All
- Внизу окна начнётся игра, для которой сначала стоит определить время, отведённое компьютеру на обдумывание хода, а затем - цвет своих фишек. Игрок может вводить ходы в стандартной нотации (примеры: h8, a1, j14, k15)
- Для перезапуска игры в верхнем меню нужно выбрать Kernel -> Restart & Run All.