MCTS — это востребованный алгоритм обучения с подкреплением в таких играх, как шахматы, го, крестики-нолики и т. д. Что такое MCTS и почему он так хорош для игр? Узнайте больше в этом блоге…

[Следующий пост является выдержкой из моего блога на soumilrathi.com. Если вы хотите прочитать больше такого контента, посетите его!]

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

Что такое MCTS?

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

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

Структура MCTS

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

Однако между MCTS и типичными деревьями в пространстве состояний есть одно фундаментальное различие, которое показано на изображении ниже.

Как мы видим, после 2–3 ходов количество возможных состояний в модели для простой игры, такой как крестики-нолики, становится огромным! Теперь представьте такой же подход к такой игре, как шахматы, с гораздо большим количеством возможных состояний и действий на каждом ходу.

На самом деле, по словам ученого-компьютерщика Джона Тромпа, всего возможно 7,7 × 10⁴⁵ состояний. Просто чтобы повторить, насколько это пугающе велико: 7728772977965919677164873487685453137329736522.

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

Алгоритм MCTS

Алгоритм MCTS следует следующим шагам: выбор, расширение, развертывание, резервное копирование.

1. Выбор. Алгоритм MCTS начинается с корневого узла, в котором сейчас находится агент. Отсюда он продолжает рекурсивно выбирать между дочерними корнями, чтобы в конечном итоге достичь последнего из исследованных узлов, который будет узел с неисследованными дочерними узлами. Этот обход был выполнен с помощью специальной политики дерева, с помощью которой MCTS решает, какой дочерний узел посетить. Политика дерева, которую использует MCTS, основана на выборе дочернего узла с самым высоким значением верхней доверительной границы (UCB).

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

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

Формула для значения UCB содержит термин (второй член), который автоматически уравновешивает исследование и эксплуатацию, так что ценность узла уменьшается с увеличением посещений узла.

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

2. Расширение. Шаг расширения вступает в силу, когда алгоритм MCTS достигает конечного узла. Этот шаг действительно прост, без использования каких-либо сложных механизмов. Здесь алгоритм случайным образом выбирает дочерний узел и исследует его. После его посещения инициируется шаг развертывания, который представляет собой исследование дочернего узла.

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

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

Таким образом, состояние развертывания помогает алгоритму MCTS определить значение конкретного состояния посредством запуска симуляций и оценки ожидаемого вознаграждения от состояния.

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

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

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

Почему MCTS так полезен?

  1. Не требует серьезной предварительной подготовки. MCTS не нужно изучать и понимать правила самой игры, ему просто нужен доступ к Окружающей среде и система для перехода из одного состояния в другое. Таким образом, он может определить лучшие ходы, даже не требуя миллионов обучающих данных.
  2. Отсутствие требований к обучающим данным означает, что MCTS также может хорошо обобщаться на другие игры. Именно по этой причине DeepMind использовала MCTS для своей программы AlphaZero — она может хорошо обобщаться на другие подобные игры.
  3. MCTS можно запускать и останавливать в любом конкретном состоянии. В отличие от других алгоритмов обучения с подкреплением, MCTS не нужно начинать в самом начале или заканчивать в самом конце, при необходимости его можно просто запустить за один ход.

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

Ну вот и все на сегодня, увидимся в следующий раз.