Победный трюк AlphaGo: руководство для начинающих по поиску по дереву Монте-Карло

[код github]: https://github.com/int8/monte-carlo-tree-search

Долгое время академическое сообщество считало, что машина не может достичь уровня человека-мастера в игре Го. Академия видит в этом «Святой Грааль» искусственного интеллекта — веху, до которой нам еще далеко в следующем десятилетии. Deep Blue произвел фурор более 20 лет назад, но с тех пор ни один го-движок не приблизился к гроссмейстеру-человеку. Идея «цифрового хаоса» в Go настолько глубоко укоренилась, что появляется и в фильме.

Удивительно, но в марте 2016 года алгоритм под названием Alpha Go, изобретенный Google Deepmind, победил южнокорейского чемпиона мира по го со счетом 4:1, доказав, что скептики не правы. Почти год спустя Alpha Go Zero, второе поколение Alpha Go Lee (победившее корейского мастера), по сообщениям, побило своего предшественника с рекордом 100-0, с которым людям было бы трудно сравниться.

Система Alpha Go/Zero — это творение великих инженеров, собранное из множества методов. Основные компоненты:

• Поиск дерева Монте-Карло(вариант функции PUCT для обхода дерева)

• остаточная сверткаНейронные сети- Сети стратегии и оценки для оценки игры и предварительной оценки вероятности действия

• обучение с подкреплением- используется для обучения сети, играя против самой себя

• В этой статье мы будемСосредоточьтесь только на поиске по дереву Монте-Карло.

Поиск дерева Монте-КарлоОн был предложен Реми Куломом в 2006 году как часть Crazy Stone. Crazy Stone — это высокопроизводительный игровой движок для игры в го.

Поиск по дереву Монте-Карло имеет одну главную цель:Состояние игры, выберите следующий ход, который с наибольшей вероятностью выиграет.В оставшейся части этой статьи мы попытаемся подробно рассказать вам о поиске по дереву Монте-Карло, чтобы лучше понять поиск по дереву Монте-Карло. Мы также будем время от времени комбинировать Alpha Go/Zero, чтобы попытаться объяснить, какие варианты поиска по дереву Монте-Карло были применены в ИИ Deepmind.

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

• играозначает, что мы имеем дело синтерактивная ситуация. Существует взаимодействие между участником (ами)

• ограниченноеЭтот термин указывает на то, что в любой момент времени существуют ограниченные способы взаимодействия участников.

• два человекаКонечная игра означает, что в игре участвуют два игрока.

• ПоследовательныйПоскольку игроки ходят последовательно, обе стороны ходят по очереди.

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

Го, шахматы и крестики-нолики, очевидно, являются конечными последовательными играми с нулевой суммой для двух игроков. Играют два игрока, каждый из которых всегда ограничен в количестве возможных ходов, и игра строго конкурентная — цели двух игроков совершенно противоположны (сумма всех выходов игры равна нулю).

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

Формально (ознакомьтесь с этой бесплатной книгой для обзора теории игр) игра может быть представлена ​​набором лежащих в основе математических сущностей. В книге по теории игр уровня PhD вы найдете следующие определения:

Определение сложное, и математику может быть очень интересно его углубиться.

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

Игровое дерево — это древовидная структура данных, в которой каждый узел представляет определенныйгосударство.Переход от узла ко всем его дочерним элементам (если они есть) является перемещением. Количество дочерних узлов узла называетсякоэффициент ветвления. Корневой узел дерева представляет начальное состояние игры, а листовые узлы (узлы без дочерних элементов) дерева представляют конечное состояние игры.

Попробуем описать игру крестики-нолики, как вы можете (частично) увидеть:

• Наверху можно увидеть деревокорневой узел, представляющая игру крестики-ноликиначальное состояние, пустая доска (отмечена зеленым)

• Любой переход от одного узла к другому представляет собойодно действие

• крестики-ноликикоэффициент ветвленияПостоянно меняется - это зависит от глубины дерева

• игра в одномлистовой узелКонец позиции (отмечен красным)

• Переход от корневого узла дерева к листовым узлам представляет собой полный процесс игры.

Чтобы ограничить размер дерева игры, отображаются только посещенные состояния.расширятьОтображение, неразвернутые узлы выделены серым цветом

Игровое дерево представляет собой рекурсивную структуру данных, поэтому после выбора наилучшего хода вы фактически выбираете дочерний узел, и этот дочерний узел является корневым узлом своего поддерева. Таким образом, вы можете думать об игре как о серии задач на лучший следующий ход, каждая из которых может быть представлена ​​игровым деревом (с другим корнем). На практике вам обычно не нужно запоминать путь, ведущий к текущему состоянию, потому что он не влияет на текущее состояние игры.

Опять же, наша конечная цель — найти следующий лучший шанс на победу на основе предполагаемого состояния игры и подразумеваемого дерева игры. Но что именно это означает?

На это нет однозначного ответа. Во-первых, вы не можете заранее знать стратегию своего оппонента - он может играть хорошо, а может и нет. Возьмем в качестве примера шахматы. Зная, что ваш противник — любитель (то, что математики называют «знаниемсмешанная стратегия»), вы можете выбрать простые стратегии, чтобы заманить его на удочку и быстро победить. Однако, если вы используете ту же стратегию против сильного противника, это, очевидно, будет стоить вам разгромного поражения.

Если вы совсем не знаете своего противника, существует агрессивная стратегия, которая называетсяминимизировать максимизировать(минимакс). Эта стратегия предполагает, что ваш оппонент ведет лучшую игру, а затем корректирует стратегию, чтобы максимизировать ваш выигрыш. В последовательной игре двух игроков с конечной нулевой суммой между A и B (A хочет максимизировать свою полезность, а B хочет минимизировать полезность A),минимизировать максимизироватьАлгоритм можно описать следующей рекурсивной формулой:

в

• и функции полезности для игрока A и игрока B соответственно (полезность = выигрыш, выигрыш)

• это функция, которая генерирует следующее состояние игры (поддерево текущего узла) в соответствии с текущим состоянием и действием во время состояния

• это функция, определяющая конечное состояние игры (в листовых узлах)

• ŝ — любое конечное состояние игры (конечный узел)

• Знак минус в терминальном состоянии указывает на то, что игра является игрой с нулевой суммой — не беспокойтесь!

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

Дерево игры выше демонстрирует, как в минимаксном алгоритмелучший шагвыберите. Белая Королева хочет, чтобы результат игры был максимально темным (холодным) (награда = интенсивность пикселей), а Темная Королева хочет, чтобы цвет результата игры был максимально ярким (теплым). Каждый выбор на каждом уровне оптимален в смысле минимизации. Результат самого нижнего листового узла уже очевиден, и оттуда мы можем работать в обратном направлении. Темная Королева всегда выбирает самый яркий цвет. Затем Белая Королева будет стремиться к своему величайшему возвращению и выберет путь, ведущий к самому темному цвету. И так далее... до узла, представляющего текущее состояние игры. Так работает минимаксный алгоритм.

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

Есть ли средство от этого?

Есть несколько способов. Один из возможных способов,Выводим наше игровое дерево только до определенной пороговой глубины. Но тогда мы не можем гарантировать, что любой узел дерева на нашем пороговом уровне является конечным узлом. Поэтому нам нужна функция для оценки состояния нетерминальной игры. Для человека это естественно: глядя на шахматную доску или доску для игры в го, можно предсказать победителя еще до окончания игры. Например: следующая игра может быть анонсирована заранее.

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

Интуитивное введение в минимаксный алгоритм и алгоритм сокращения альфа-бета можно найти здесь. Отсечение Minimax/Alpha-beta — это очень зрелое решение, которое сегодня успешно используется в различных игровых движках, таких как Stockfish, основа серии игр, проведенных Alpha Go в конце 2017 года Competitors (хотя это спорно).

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

Основной концепцией поиска по дереву Монте-Карло является поиск. Поиск — это серия обходов дерева игры вниз. Один проход — от корневого узла (текущее состояние игры) к узлу, который не полностью расширен. Узел, который не полностью раскрыт, означает, что по крайней мере один из дочерних элементов этого узла небыл посещен. однажды столкнулисьне полностью расширенузел, один из его непосещенных дочерних узлов будет выбран как одиночныймоделированиекорневой узел. Затем результат моделирования будет отправлен обратно в корневой узел текущего дерева для обновления статистики узла игрового дерева. После завершения поиска (ограниченного временем или вычислительной мощностью) решения могут приниматься на основе собранной статистики.

В этом определении много посылов, но вы не можете собрать их все вместе, не так ли?

Мы можем попытаться упростить приведенное выше описание, задав несколько ключевых вопросов, чтобы медленно понять все информационные моменты:

• Расширенный узел дерева игры ине полностью расширенИз каких узлов состоит игровое дерево?

• существуетпоискпроцесс"Траверс вниз"означает? Как выбирается следующий (дочерний) узел?

• что такое когда-томоделирование?

• что обратноераспространять?

• Среди расширенных узлов игрового дерева, которыеСтатистические данныеОбратное распространение и обновление?

• Как выбирается финальное действие?

Сконцентрируйтесь, и мы во всем разберемся по крупицам.

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

Как выбирался каждый шаг во время моделирования?

В процессе моделирования каждый шаг основан нафункция политики развертыванияВыбрано:

Эта функция принимает параметр, представляющий состояние игры, и возвращает следующее действие. На самом деле, он спроектирован так, чтобы быть очень быстрым, что позволяет быстро выполнять многие симуляции — функция политики развертывания по умолчанию — этоРавномерно распределенные случайные числаСгенерировать функцию.

В Alpha Go Lee оценка конечного узла представляет собой взвешенную сумму двух компонентов:

• использовать пользовательскийбыстрая шахматная стратегияСтандартная оценка движения , которая представляет собой неглубокую нейронную сеть softmax с функциями, созданными вручную.

• Оценка местоположения на основе 13-слойной сверточной нейронной сети, называемойСеть оценки, извлеченный из 30 миллионов различных позиций самостоятельной игры Alpha Go (не может быть двух очков из одной и той же игры)

В Alpha Zero инженеры Deepmind пошли еще дальше, и ониМоделирование не выполняется вообще, вместо этого напрямую оценивая текущий узел с помощью 19-слойной остаточной нейронной сети CNN. (В Alpha Zero есть сеть 0, которая выводит оценку положения и сразу перемещает вектор вероятности)

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

При поиске по дереву Монте-Карло симуляция обычнопосещенные узлыНачало работы — позже мы объясним, что означает посещенный узел.

Как люди думают в таких играх, как го или шахматы?

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

Таким же образом можно выделить игровые деревья поиска по дереву Монте-Карло. Узлы классифицируются как посещенные узлы или непосещенные узлы. Когда посещается узел? Узел считается посещенным, если симуляция уже началась с этого узла, т. е. он был оценен хотя бы один раз. Узел является полностью развернутым узлом, если все его дочерние узлы являются посещенными узлами, в противном случае он является не полностью расширенным узлом и может продолжать расширяться.

На практике, когда начинается поиск, все дочерние узлы корневого узла не посещаются — как только один из дочерних элементов выбран, сразу начинается первая симуляция.

Обратите внимание, что вПроцесс моделирования, узлы, выбранные функцией политики развертывания,Не будет считаться посещаемым узлом.Они по-прежнему остаются непосещенными, даже если через них проходит развертывание. Только узлы, с которых началось моделирование, помечаются как посещенные.

Как только процесс симуляции для только что посещенного узла (иногда называемого конечным узлом) завершен, результаты симуляции могут быть распространены в обратном направлении на корневой узел текущего игрового дерева. Затем узел, с которого начинается эта симуляция, помечается как посещенный.

Обратное распространение — это переход от конечного узла (узла, с которого начинается симуляция) обратно к корневому узлу. Результаты моделирования передаются на корневой узел, и для каждого узла на пути обратного распространения вычисляются или обновляются определенные статистические данные. Обратное распространение гарантирует, что статистика каждого узла будет отражать результаты всех симуляций, начиная с его потомков (поскольку результаты симуляции передаются в корень дерева игры).

Целью результатов моделирования обратного распространения является обновление смоделированного общего дохода и общего количества посещений для всех узлов на пути обратного распространения, включая узел, с которого началось моделирование.

• ——Смоделируйте общий доход, свойство узлаПроще говоря, это сумма всех результатов моделирования, проходящих через узел.

• ——Общее количество посещений, еще одно свойство узла, указывающее, сколько раз путь обратного распространения проходил через этот узел (и сколько раз он вносил свой вклад в смоделированный общий доход).

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

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

Есть еще одна загадка. Как начать симуляцию от корневого узла к непосещенному узлу?

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

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

Чтобы начать следующую симуляцию, выбрав следующий узел на нашем пути через полностью развернутый узел, нам нужно рассмотреть все дочерние узлы: информацию о самом узле, а также информацию о самом узле. Давайте подумаем, какая информация доступна сейчас:

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

UCT — это функция, которая позволяет нам выбрать следующий узел для прохождения из узлов, которые были посещены. Это основная функция поиска по дереву Монте-Карло.

При обходе дерева Монте-КарлоВыберите узел, который максимизирует UCT, в качестве следующего узла.. Давайте посмотрим, что делает функция UCT:

Во-первых, наша функция определена для дочернего элемента узла. Это сумма двух частей — первая, также известная как компонент эксплуатации, может пониматься как соотношение выигрышей и проигрышей — смоделированная общая прибыль, деленная на общее количество посещений, которая предсказывает выигрыш в узле Rate. Эта часть выглядит неплохо — в конечном итоге мы пройдём узлы с высокой вероятностью победы.

Почему мы не можем просто использовать эксплойт-компоненты? Потому что (если использовать только компоненты) мы изучаем только узлы, которые приносят смоделированный выигрыш на раннем этапе (игнорируя потенциал выигрыша узла на протяжении всей игры).

один пример:

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

Поэтому нам нужен второй компонент UCT, называемыйКомпонент обнаружения(разведочная составляющая). Компонент зонда отдает предпочтение тем узлам, которые не исследуются — тем, которые посещаются относительно редко (т. е. более низким узлам). Мы можем взглянуть на форму пробного компонента функции UCT — он уменьшается по мере увеличения числа посещений узла, что дает тем менее посещаемым узлам более высокие шансы быть выбранными, тем самым смещая направление поиска в сторону изучения менее посещаемый узел.

Наконец, параметры в формулировке UCT управляют балансом использования и исследования компонентов в поиске по дереву Монте-Карло.

Важный комментарий к функции UCT: в соревновательных играх ее эксплойтная составляющая всегда вычисляется относительно игрока, движущегося к узлу — это означает, что при обходе дерева игры точка обзора меняется вместе с пройденными узлами: Для любых двух последовательных узлы, вид обратный.

И в Alpha Go Lee, и в Alpha Zero обходы дерева следуют за теми узлами, которые максимизируют следующие варианты UCT:

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

В Alpha Go есть две сети политик.

• Сеть политик SL (Supervise Learning, контролируемое обучение), Контролируемое обучение на наборах данных человеческих игр.

• Сеть политик RL (обучение с подкреплением, обучение с подкреплением), расширенная сеть политик SL, которая имеет ту же архитектуру, но глубоко обучена обучению с подкреплением (самостоятельная игра).

Интересно, что в варианте поиска по дереву Монте-Карло от Deepmind, поскольку контролируемая сеть политик обучения работает лучше на практике, ее результаты используются для оценки предшествующей вероятности действия (авторы утверждают, что человеческие данные используются для изучения более обильных сексуальных действий). ). Итак, какова цель сети политик обучения с подкреплением? Более сильная сеть политики обучения с подкреплением использовалась для создания набора данных из 30 миллионов позиций, которые использовались для обучения сети оценки (и сети оценки для оценки состояния игры).

С другой стороны, в Alpha Zero есть только одна сеть, которая одновременно является сетью оценки и сетью политик. Он полностью обучается, играя против самого себя, начиная со случайного начального состояния. Несколько сетей обучаются параллельно, и в каждой контрольной точке на основе текущей оптимальной нейронной сети выбирается оптимальная сеть для генерации обучающих данных.

Теперь, когда мы знаем почти все детали успешного внедрения поиска по дереву Монте-Карло, нам еще предстоит ответить на некоторые вопросы. Во-первых,Когда мы закроем программу поиска по дереву Монте-Карло?Ответ на этот вопрос таков: это зависит от контекста. Если вы создаете игровой движок, ваше «время на обдумывание» может быть ограничено, и, кроме того, ограничена ваша вычислительная мощность. Поэтому безопаснее всего запускать поиск по дереву Монте-Карло, пока позволяют ваши ресурсы.

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

После выбора вашего хода с помощью поиска по дереву Монте-Карло выбранный вами узел становится игровым состоянием, в котором ваш противник начинает двигаться. Как только он выбирает свой ход, вы снова начинаете поиск по дереву Монте-Карло из состояния игры, представленного узлом, выбранным вашим противником. Некоторые статистические данные из предыдущих раундов поиска по дереву Монте-Карло могут все еще быть в новой ветви, которую вы рассматриваете. Это приводит к новой идее повторного использования статистики, а не построения нового игрового дерева с нуля. Собственно, так и сделали создатели Alpha Go и Alpha Zero.

Рассмотрев все детали, давайте рассмотрим упрощенное описание поиска по дереву Монте-Карло с самого начала и прикрепим псевдокод:

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

Это открыто для всех, и я надеюсь, вам понравится читать, и это поможет вам понять поиск по дереву Монте-Карло - написав этот пример, я лучше понимаю поиск по дереву Монте-Карло.

Следующий шаг (вероятно, материал для следующего поста в блоге) — попытаться реализовать простого шахматного бота с компонентами, подобными AlphaGo: сетями оценки и политик и поиском по дереву Монте-Карло (некоторые из которых все еще находятся в разработке, вы можете нажать здесь смотреть).

Посмотреть исходный английский текст:

https://int8.io/monte-carlo-tree-search-beginners-guide/