Кодирование алгоритма AlphaZero с нуля, чтобы играть в игру TicTacToe, и он никогда не проигрывает!
AlphaZero (или его более известный предшественник AlphaGo) совершил один из самых известных прорывов в области ИИ. Способность достигать сверхчеловеческих результатов в играх в шахматы, сёги и го, создание фильма на Netflix, посвященного этому достижению (AlphaGo — The Movie), — это не скромные достижения.
AlphaZero был разработан исследовательским подразделением Google DeepMind в 2017 году. Он смог достичь сверхчеловеческой производительности в различных идеальных информационных играх полностью за счет самостоятельной игры… это означает, что он не научился играть в игры, наблюдая за людьми, скорее, он разработал игровую стратегию, играя только против самого себя. Кроме того, не было жестко запрограммированных правил или эвристик, которыми можно было бы управлять в игре. Это означало, что один и тот же алгоритм можно обобщить для любой игры (идеальные информационные игры). Это очень впечатляет.
В этой статье я расскажу об общей интуиции, лежащей в основе AlphaZero, и объясню различные компоненты и процессы в алгоритме. Я изменил алгоритм из бумаги, чтобы играть в крестики-нолики. Я разместил веб-демонстрацию, с которой вы играете здесь. Вы можете найти полный код для реализации на моем Github.
Бот никогда не проигрывает!! Он выиграет или сыграет вничью в каждой игре. Попробуйте сами: https://alphazerotictactoe.herokuapp.com/
Как это работает?
Одной из главных достопримечательностей AlphaZero является его элегантная простота. Алгоритм прост для понимания и интуитивно понятен. AlphaZero состоит из 2 основных компонентов:
- Инстинкт:
Это включает в себя значение и политические нейронные сети. Сеть значений дает предрасположенность игрока к победе в игре с учетом текущего состояния игры. Сеть политик предлагает следующее действие для данного состояния. Обе эти функции моделируют алгоритмический эквивалент человеческого инстинкта, который разработан на основе нашего прошлого опыта. Мы обсудим, как обучаются эти 2 сети позже.
2. Смотри вперед:
Это процесс использования вашей интуиции для рассмотрения нескольких сценариев «что, если», а затем принятия решения о наилучшем следующем шаге на основе результатов рассмотренных вами сценариев. Это достигается алгоритмически с помощью поиска по дереву Монте-Карло. Мы обсудим это более подробно в следующем разделе.
Как сделать следующий ход?
Есть 2 шага для выбора следующего хода:
- Информированный взгляд вперед (поиск по дереву Монте-Карло с использованием сети ценностей и политик)
- Move Selection (Выбор действия, которое чаще всего посещалось в MCTS)
Попробуем объяснить это на примере. Скажем, текущее состояние игры выглядит следующим образом:
Шаг 1. Информированный прогноз
Как правило, с вычислительной точки зрения невозможно выполнить исчерпывающий поиск всех возможных будущих возможностей. Итак, мы выбираем некоторое конечное число симуляций (заглядывая вперед), скажем, N=5.
Решая, какую из будущих возможностей исследовать дальше, мы полагаемся на предварительно обученные сети ценности (инстинкт), которые направляют нас. Выбор шага «заглянуть вперед», который приводит к наибольшей ценности, будет подходом эксплуатации. Иногда мы делаем исследовательский взгляд вперед, когда выбираем не максимальное значение движения. В конце каждой симуляции мы откатываем результаты, чтобы определить среднюю вероятность выигрыша для каждого хода/состояния. Будущие симуляции информируются об этой оценке.
Это гарантирует, что ходы с более высокой средней вероятностью выигрыша будут чаще выбираться во время прогнозных симуляций. Следовательно, состояния, полученные в результате хороших ходов, будут иметь большее количество посещений в MCTS.
Шаг 2. Переместите выделение
После MCTS (Look Ahead) у нас будет такое дерево состояний:
Чем больше посещений, тем лучше движение. Затем мы выбираем ход с наибольшим количеством посещений.
Именно так AlphaZero решает, какой шаг предпринять дальше. Довольно интуитивно верно?!!!
Как устроен инстинкт?
Компонентами инстинкта являются сети создания ценности и сети политики. По сути, это нейронные сети, которым для обучения требуются данные. Данные собираются посредством самостоятельной игры — алгоритм играет против самого себя.
Важно отметить, что данные, собранные в ходе самостоятельной игры, не являются исчерпывающими и, следовательно, не охватывают все возможные игровые состояния и действия. Таким образом, модели, обученные этому, будут содержать лишь частичные знания об игре. Вот почему исследовательская игра в MCTS важна на этапе выбора хода, подробно описанном в предыдущем разделе.
Сеть значений принимает в качестве входных данных состояние доски и предсказывает вероятность того, что игрок выиграет эту игру. Этот набор данных может быть создан на основе собранных данных.
Сеть политик принимает в качестве входных данных состояние игры и прогнозирует среднюю вероятность выигрыша для каждого возможного хода. Эта сеть предназначена для прогнозирования результатов MCTS — нормализованного количества посещений для каждого разрешенного хода. Это значение записывается во время самостоятельного воспроизведения, а затем используется для обучения сети.
Эта статья была разработана, чтобы дать представление об AlphaZero на высоком уровне. Мне пришлось опустить несколько деталей реализации. Пожалуйста, ознакомьтесь с кодом на моем Github.
Репозиторий Github: https://github.com/kvsnoufal/alphazeroTicTacToe
Демо: https://alphazerotictactoe.herokuapp.com/
Плечи гигантов
- Освоение игры Го без человеческого ведома: https://www.nature.com/articles/nature24270
- http://joshvarty.github.io/AlphaZero/
- Памятка AlphaZero: https://medium.com/applied-data-science/alphago-zero-explained-in-one-diagram-365f5abf67e0
- Простое руководство по Alpha(Go) Zero: https://web.stanford.edu/~surag/posts/alphazero.html
- https://en.wikipedia.org/wiki/Monte_Carlo_tree_search
- https://www.youtube.com/watch?v=MPXGiowUr0o&ab_channel=SkowstertheGeek
Об авторе
Я работаю в Dubai Holding, ОАЭ, в качестве главного специалиста по данным. Вы можете связаться со мной по адресу [email protected] или https://www.linkedin.com/in/kvsnoufal/
