Копирование AlphaGo для шахмат

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

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

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

К настоящему времени вы, возможно, задаетесь вопросом, почему я рассказываю вам эту историю. Ну, это потому, что я нашел способ победить своего брата в шахматах, и это было с помощью глубокого обучения. После моего первого проекта глубокого обучения я начал искать новый проект, чтобы продолжить учебу в машинном обучении. Посоветовавшись с некоторыми из моих коллег и друзей, я подумал, что было бы забавно повторить результаты AlphaGo и AlphaZero в меньшем масштабе. Первоначально я планировал попробовать два подхода: воспроизвести AlphaGo для меньшей доски 9x9 Go и AlphaZero для шахмат, но вскоре это оказалось трудным, потому что данных для тренировок 9x9 Go просто не хватало. В результате я скорректировал свой план и решил воспроизвести AlphaGo для шахмат, и это дает дополнительный бонус: я мог бы победить своего брата в шахматах, хотя и по доверенности.

AlphaGo

Прежде чем погрузиться в мой шахматный движок, было бы полезно узнать, что именно делает AlphaGo. Для этого сначала мы должны понять, что значит хорошо играть в го, шахматы или любую идеальную информационную игру, то есть вся информация доступна каждому. Проще говоря, вам нужно на каждом ходу делать оптимальный ход. Люди ищут оптимальные ходы, используя свою интуицию и моделирование в голове (заглядывая вперед на несколько ходов). С другой стороны, компьютеры традиционно полагались на поиск методом грубой силы, используя свои вычислительные возможности. Например, DeepBlue, первая шахматная программа, победившая чемпиона мира, использовала перебор с использованием алгоритма под названием Minimax в сочетании с ручной эвристикой, разработанной шахматными экспертами. При запуске на современных компьютерах этого было достаточно для поиска оптимального хода, по крайней мере, лучше, чем у людей, на каждом повороте, несмотря на его вычислительную трудоемкость.

К сожалению, подход DeepBlue не совсем сработал для Го, потому что его сложность на порядки больше, чем шахматы. Для решения этой, казалось бы, непреодолимой проблемы были использованы другие алгоритмы поиска, и один алгоритм, названный поиск по дереву Монте-Карло (MCTS), оказался наиболее многообещающим. Хотя одного этого было недостаточно, чтобы победить человека в го, AlphaGo доказала, что MCTS может победить лучшего игрока в го, если дополнить его моделями глубокого обучения.

Поиск по дереву Монте-Карло

Название происходит от казино в Монте-Карло, Монако, и, как следует из названия, оно связано с случайностью. Вместо детерминированного анализа ходов с использованием математических формул, таких как Minimax, MCTS полагается на моделирование для оценки ходов. Во-первых, он представляет игру в виде дерева, где каждый узел является состоянием игры, а ребра, соединяющие каждый узел, представляют ходы. Затем он повторно выполняет следующие 4 шага:

  1. Выбор: начиная с корня, несколько раз следуйте по дереву, выбирая лучший ход на каждом повороте, пока не достигнете дна (называемого листом).
  2. Расширение: если листовой узел не является конечным (то есть это не конец игры), добавьте к нему дочерние узлы и случайным образом выберите один дочерний узел.
  3. Моделирование: от выбранного ребенка запускайте моделирование, пока игра не закончится, и вычислите ценность игры (например, если игрок выиграл игру 1, в противном случае -1).
  4. Обратное распространение: обновите количество посещений для каждого узла, который мы посетили из корня, а также значение, рассчитанное на основе моделирования.

Повторив эти шаги достаточное количество раз, мы выбираем ход, который максимизирует значение, вычисленное на основе количества посещений и значения моделирования. Если вы хотите узнать больше о MCTS, вот некоторые ресурсы, на которые я часто ссылался, когда реализовывал его: Что такое MCTS?, Видео от Udacity.

Теперь у нас есть общая структура алгоритма, но есть пара деталей, которые все еще неясны:

  1. Как выбрать лучший ход в Selection?
  2. Как мы рассчитываем значение узла в Simulation?

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

Выбор

Как глубокое обучение помогает выбрать лучший ход на этапе выбора MCTS? Модель, разработанная командой AlphaGo, которую они назвали сетью политик, в основном смотрит на доску Go и сообщает нам, что она думает о следующем лучшем шаге. Более конкретно, сначала текущее состояние платы преобразуется в стопку изображений. Каждая стопка относится к типу информации, такой как положение камней и различные узоры камней (вы можете найти полный список в их бумаге). Затем этот стек изображений передается в сеть политик, и он сообщает нам, что делать дальше. Политическая сеть использует нейронную сеть, называемую сверточной нейронной сетью (CNN), структура которой основана на том, как работает наша собственная зрительная кора. Благодаря своей структуре CNN отлично справляется с визуальными задачами и активно используется в таких задачах, как распознавание лиц и объектов. Поскольку задачу определения следующего наилучшего хода на основе текущей конфигурации платы можно было рассматривать как визуальную задачу, CNN был хорошим выбором для сети политик.

Затем команда AlphaGo обучила сеть политик на 30 миллионах позиций, извлеченных из экспертных онлайн-игр го, процесс, называемый контролируемым обучением. Для дальнейшего обучения контролируемой обучающей сети (сеть SL) они также использовали обучение с подкреплением, по сути, заставляя его многократно воспроизводить себя, подобно игровым тренировочным матчам. На этом этапе сеть обучения с подкреплением (сеть RL) смогла выиграть в 85% игр у Pachi, очень сложного движка Go, основанного на MCTS, основанного исключительно на «интуиции» без какого-либо поиска. Однако, несмотря на свои превосходные навыки игры в го, сеть RL не работала так же хорошо при использовании в качестве сети политики в MCTS, чем сеть SL, предположительно потому, что сеть RL «оптимизируется для единственного наилучшего хода», где, как говорят люди, и посредством расширяя сеть SL, «выбирайте разнообразные перспективные ходы».

Моделирование

Теперь, когда мы знаем, как выбрать лучший ход в Selection, давайте посмотрим, как команда AlphaGo решила, как вычислить значение узла на этапе моделирования в MCTS. Они сделали это, объединив два метода: 1. фактическое моделирование до конца игры из данного узла и 2. использование другой сети на основе CNN для оценки значения. Ключевым моментом здесь является то, что скорость важнее точности, потому что MCTS гарантированно сходится к оптимальному ходу при наличии достаточного времени. В результате команда AlphaGo разработала более простую, но более быструю сеть политик, названную сетью политик развертывания для метода 1, и сеть значений, которая эффективно оценивала бы ценность узла для метода 2. Сеть политик развертывания была обучена экспертом. позиции точно такие же, как в сети SL, но с более простыми изображениями и меньшим размером сети для повышения скорости. Они пытались обучить сеть ценностей, используя позиции экспертов, но это привело к тому, что сеть в основном запомнила ценности вместо того, чтобы обобщать их на новые позиции (это явление называется переобучением). Это связано с сильной корреляцией между последовательными позициями, поскольку они отличаются только одной позицией. В результате команда AlphaGo решила смоделировать 30 миллионов игр с использованием сети SL и сети RL и выборки одной позиции из каждой игры. Это устранило сильную корреляцию между позициями и привело к созданию сети создания ценности, которая хорошо обобщалась.

Победа над людьми на ходу

Со всеми компонентами AlphaGo смогла выполнять MCTS более эффективно, чем когда-либо прежде. Они даже пошли дальше и распараллелили большую часть вычислений. В результате AlphaGo смогла определить оптимальный ход быстрее и точнее, чем мог бы сделать любой человек, победив 18-кратного чемпиона мира Ли Седол 4 раза из 5 матчей, а действующего чемпиона мира Кэ Джи - в все три матча. Китайский чемпион даже назвал AlphaGo Богом Го после матчей.

Юрека

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

Двигатель

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

  1. Компонент, который преобразует шахматную доску в стопку изображений, которые можно передать в мои нейронные сети.
  2. Компонент, который переводит выходные данные сетей в настоящий шахматный ход.

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

Выбор

Я создал свою политическую сеть, используя новую библиотеку под названием PyTorch, и обучил ее с помощью профессиональных шахматных игр, которые я загрузил из KingBase Chess Database. Я сгенерировал около 10 миллионов позиций и примерно три дня запускал алгоритм обучения. Сеть контролируемого обучения (сеть SL) к этому моменту стала достаточно хорошей, чтобы играть против нее, поэтому несколько моих друзей и мой брат играли против нее, но, хотя она была приемлемой в дебюте и в середине игры, она понятия не имела, когда она добрался до конца игры. Предположительно это связано с тем, что набор тренировочных данных в основном состоит из дебютов и позиций в середине игры (сеть просто не видит столько позиций в конце игры), а также трудно закончить игру только с интуицией, как это должно выглядеть. впереди несколько ходов. Я смягчил первую проблему, добавив позиции из конечной базы данных, и отложил рассмотрение второй проблемы, так как пришел к выводу, что она будет решена MCTS. Когда я сравнил политическую сеть с современным шахматным движком StockFish на самом простом уровне, я обнаружил, что добавление позиций в конце игры действительно помогло.

После того, как моя сеть политик контролируемого обучения достигла приемлемого уровня, я попытался улучшить ее дальше, используя обучение с подкреплением. К сожалению, это оказалось трудным, поскольку не удалось улучшить себя с помощью самостоятельной игры. Основные причины неудач были не столь ясны, но я предполагаю, что в шахматах, в отличие от Го, есть ничьи, и поскольку моя SL-сеть была плохой в эндшпиле, она чаще всего была связана сама с собой, что не давало сильных результатов. достаточно сигнала, чтобы улучшить себя. Я попытался настроить свой алгоритм так, чтобы сигнал был сильным, но безуспешно. После еще нескольких попыток решить проблему я решил отказаться от сети RL.

Моделирование

Следуя тому, что сделала команда AlphaGo, я попытался реализовать оба подхода. Сначала я начал с сети ценностей, поскольку метод обучения аналогичен сети политики, которую я обучал ранее. Я попытался сгенерировать данные обучения так же, как команда AlphaGo, смоделировав миллионы игр с использованием сети SL, но на моем рабочем столе это заняло слишком много времени. Вместо этого я отобрал 10 миллионов позиций из экспертных партий из базы данных KingBase Chess Database, которую раньше использовал для обучения сети SL. Поскольку эти позиции были выбраны случайным образом, я решил, что они не будут слишком коррелировать друг с другом. К счастью, моя интуиция подтвердилась, и я не заметил переобучения.

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

Победа над моим братом в шахматах

С сетью политик SL для Selection и сетью создания ценности для Simulation, Юрека, наконец, была завершена. Я попытался провести формальную оценку, попросив Yureka поиграть в Stockfish и подсчитав его рейтинг ELO, но это занимало слишком много времени на моем рабочем столе, особенно с контролем времени, поэтому мне пришлось отказаться от этого. Я планирую провести эти формальные оценки на более совершенных машинах (возможно, на AWS) в будущем, поэтому я обновлю этот блог с результатами.

Самое главное, Юрека сыграл моего брата, и вот что получилось:

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

Заключение и дальнейшая работа

Основываясь на методах, описанных в статье AlphaGo, я успешно реализовал компетентный шахматный движок, который может обыграть некоторых игроков-людей. Он состоял в основном из трех частей: 1. «мозг» движка, основанный на глубоких нейронных сетях, 2. компонент трансляции, который превращает конфигурацию платы в стек изображений, понятный нейронным сетям, 3. реализация метода Монте. Алгоритм поиска по дереву Карло, который использует выходные данные нейронных сетей для поиска лучшего хода. Как отметила команда AlphaGo в своей статье, я также заметил, что эффективность обычного алгоритма, такого как MCTS, может быть значительно повышена в сочетании с моделями машинного обучения, такими как глубокие нейронные сети. Расширяя этот момент, я получил еще одно важное понимание: хорошие модели машинного обучения - это только часть всего движка, и для них требуются другие компоненты, которые используют его выходные данные для получения значимых результатов.

Также было очень интересно провести параллели между тем, как Юрека играет в шахматы, и тем, как люди играют в шахматы. Магнус Карлсен, действующий чемпион мира по шахматам, однажды сказал это в интервью, когда его спросили, как он играет в шахматы:

Я думаю, что это отчасти подсознательно, потому что иногда в моей голове происходит процесс принятия решений, а затем внезапно я делаю шаг, и я действительно не знаю, почему я это сделал. Иногда я действительно не могу ощутить момент, когда решаюсь на этот конкретный ход… и в какой-то момент я просто его делаю.

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

Опираясь на успех, я планирую поработать над несколькими оставшимися задачами для моего шахматного движка, такими как очистка кода, объединение сети политик и сети ценностей, как описано в статье AlphaGo Zero, и обучение сети с большим набором данных. . Кроме того, я планирую реализовать движок Go, который мог бы играть на доске 9x9 (в отличие от стандартной доски 19x19) на основе бумаги AlphaGo Zero. Конечно, я буду продолжать писать новые сообщения в блоге для будущих проектов, поэтому, пожалуйста, следите за обновлениями!

Обновление от 22.10.2018: я обновил код, чтобы объединить сеть политик и сеть значений. Я не пробовал писать движок Go, так как требуемые вычислительные мощности казались мне слишком большими. Вы можете ознакомиться с кодом здесь. Хотелось бы, чтобы у меня было больше времени, чтобы еще больше почистить код, но пока я думаю, что этого достаточно. Кроме того, прошлой весной я с большим успехом представил Юреку на сессии инженерного образования моей компании! Демо в конце было очень захватывающим.