Как AlphaZero играет в шахматы?

Наверное, вы уже слышали о новой программе AlphaZero и ее убедительной победе над  Stockfish, сильнейшим движком с открытым исходным кодом.

Оценки матча со стороны шахматного сообщества варьировались от восхищения до полного недоверия.

Так как же работает AlphaZero?

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

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

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

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

Как ей это удалось?

Так штаб-квартира Google в Лондоне выглядит изнутри, отдел DeepMind расположен на восьмом этаже. | Фотография Марии Емельяновой/Chess.com.

Она не рассчитывала больше вариантов, чем Stockfish.

Совсем наоборот: Stockfish оценивал 70 миллионов позиций в секунду, а AlphaZero хватало на  99.89 процентов меньше позиций: 80,000 в секунду. Вспоминаются слова, сказанные Джонатаном Роусоном после сокрушительного матчевого поражения от Майкла Адамса в 1998 году: “Я был потрясен тем, как мало он видел”.

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

Каким образом?

ММ Дэнни Ренш рассказывает о матче AlphaZero в серии видео на Twitch.

The Analysis Tree

Шахматные движки используют дерево счета вариантов и оценочную функцию, которая выставляет оценку позициям в конце вариантов, например: +1.5 (преимущество белых составляет полторы пешки) или -9.0 (преимущество черных равно ферзю). Подход AlphaZero к счету вариантов и оценке позиций радикально отличается от того, что делают другие движки.

Все распространенные шахматные движки основаны на минимаксном алгоритме, то есть, они выбирают ход, дающий наибольшее преимущество при любом ответе противника. Минмаксный алгоритм обязательно связан с альфа-бета отсечением, позволяющим уменьшить размер изучаемого дерева вариантов. Приведем радикальный пример того, как работает отсечение: допустим, что движок пытается оценить ход и видит, что у противника есть 20 ответных ходов, один из которых форсировано матует. Это позволяет движку больше не рассматривать (отсечь) ход независимо от оценки позиций, которые возникают после 19 оставшихся ответов.

Если движок начнет отсекать ходы, которые только кажутся плохими, например, связаны с отдачей материала, он перестанет рассматривать любые жертвы. Кстати, именно поэтому ранние движки так держались за материал. В современных движках похожих на Stockfish альфа-бета отсечение сочетается со специализированными алгоритмами: "эвристикой убийцы" (сильный ход в одной позиции, скорее всего, окажется сильным и в похожей), "эвристикой ответного хода" (ответы на некоторые ходы очевидны независимо от позиции — например, на axb5 обычно отвечают axb5, не так ли?) и многими другими.

В отличие от этих программ, AlphaZero для поиска в дереве ходов использует метод Монте-Карло (Monte Carlo Tree Search или MCTS). Город Монте-Карло известен своими казино, поэтому в программировании этот термин используется, когда что-то происходит случайным образом. Движок, использующий чистый метод Монте-Карло, оценивал бы позицию, случайным образом создавая несколько последовательностей ходов (называемых “розыгрыши”) и получая средний итоговый результат (победа/ничья/поражение), к которому они ведут. Этот подход может показаться слишком простым, но поразмыслив, вы поймете, что это вполне возможный способ оценки позиции.

Казино Монте-Карло.

AlphaZero проводит 800 розыгрышей для каждого хода. Кроме того, чистый метод Монте-Карло усовершенствован тем, что предпочитаются ранее не (слишком часто) применявшиеся ходы; ходы, кажущиеся возможными, и ходы, которые, по-видимому, ведут к "хорошим" позициям. "Хорошие" - те, для которых оценочная функция показывает большие значения (об этом подробнее в следующей статье). Таким образом, розыгрыши выбираются не случайно, а в соответствии с непрерывно совершенствующейся оценочной функцией. Разве вы не ищете лучший ход именно так, фокусируясь на оптимальных продолжениях?

Заметьте, что мы не рассказали о работе AlphaZero ничего, характерного исключительно для шахмат. В следующей статье мы узнаем, как AlphaZero учится оценивать шахматные позиции, и увидим, что и там нет ничего специфически шахматного!

Как новорожденный малыш, AlphaZero появилась на свет со скудными знаниями, но у этой программы были великолепные способности к самообучению. Единственной слабостью метода Монте-Карло является то, что розыгрыши все же наполовину случайны, поэтому в острой позиции, где существует серия строго единственных оптимальных ходов, программа может ошибиться, если сильнейший ход не попадет в выборку. Скорее всего, именно это привело к поражению предшественницы AlphaZero, программы AlphaGo, проигравшей партию в го Ли Седолю, 18-кратному чемпиону мира по этой игре. Кажется, в матче со Stockfish таких зевков не было.

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

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

А что вы думаете о том, как AlphaZero играет в шахматы? Поделитесь с нами в комментариях.