«Я с нетерпением ждал времени, чтобы увидеть все возможные исходы надвигающегося конфликта». - Доктор Стивен Винсент Стрэндж, супергерой из кинематографической вселенной Marvel.

Если бы только мы могли заранее предсказать все результаты наших действий! К сожалению, мы не можем, и машины тоже не могут, если задача, которую они пытаются решить, не является действительно простой. Однако машины по-прежнему могут предсказывать будущее состояние игры намного быстрее, чем любой человек. Эта способность позволяет ИИ превосходить людей в шашках, шахматах, го и других играх. Alpha Zero также использует возможности прогнозов с помощью алгоритма под названием Поиск по дереву Монте-Карло (MCTS).

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

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

Игры и агент

Мы собираемся определить два простых интерфейса в Python: Game и Agent. Интерфейс Игра позволяет нам создавать игровой сеанс, получать наблюдения за текущим состоянием, выполнять действия и получать результат игрового сеанса. Интерфейс Агент позволяет нам прогнозировать политику и значение на основе текущего состояния игры.

Уделите минуту или две, чтобы познакомиться с этими интерфейсами. Когда вы будете готовы, мы приступим к реализации MCTS!

Агент на базе MCTS

Теперь мы собираемся создать Агента на основе MCTS. Я знаю, что странно реализовывать алгоритм без объяснений, но поверьте мне в этом; это не так сложно, как кажется. Чтение реализации даст вам общее представление о том, как работает алгоритм, и все это будет иметь смысл, когда я объясню все более формально.

Вау! Это был большой объем кода, который нужно было обработать. Пора объяснить, что здесь происходит.

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

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

Для каждого края мы поддерживаем значение Q, обозначенное Q (s, a), которое является ожидаемой наградой за выполнение этого действия, и N (s, a). , который представляет количество раз, когда мы выполняли действие a из состояния s в различных симуляциях.

Гиперпараметры MCTS:

  • количество симуляций - это параметр, который представляет, сколько ранее не исследованных узлов мы хотим посещать каждый раз, когда вызываем функцию agent.predict;
  • cpuct - параметр, контролирующий степень изучения;
  • скорость исследования - это параметр, контролирующий распространение окончательной политики. Установка высокого значения дает почти равномерное распределение, а установка 0 заставляет нас всегда выбирать лучшее действие.

Процесс исследования повторяется. Он начинается с получения наблюдения из игры и получения хэша наблюдения с помощью метода:

game.get_observation_str (наблюдение):

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

Итак, поиски начинаются ...

Если мы достигли конечного узла, нам просто нужно распространить значение для текущего игрока:
Итак, поиск начинается ...

Если мы достигли конечного узла, нам просто нужно распространить значение для текущего игрока:

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

Если мы столкнулись с известным состоянием, мы вычисляем значения U (s, a) для каждого края (действие- ›переход между состояниями), что является верхней границей достоверности для Q ценность нашего края. Эти значения рассчитываются как:

После завершения моделирования MCTS значения N (s, a) обеспечивают хорошее приближение для политики для каждого состояния. Осталось только применить наш параметр скорость исследования для управления распределением значений политики:

Поздравляю! Теперь вы понимаете, как работает поиск по дереву Монте-Карло! Однако остается еще кое-что, прежде чем мы сможем заставить его работать.

Нейронная сеть

Вы помните эти строки из нашего AgentMCTS?

Именно так мы собираемся использовать здесь нашу нейронную сеть. Он создает политику и значение, поэтому интерфейс Агента также можно повторно использовать с нейронной сетью. Напишем Агента на основе нейронной сети! Мы будем использовать библиотеку Keras, чтобы сделать наш код максимально чистым. Сначала мы определяем нашу абстрактную нейронную сеть:

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

Если вам интересно, как заставить нейронную сеть выводить политику и значение, вот пример простой сверточной нейронной сети для Alpha Zero:

Собираем все вместе

Сегодня мы определили наши основные интерфейсы: Game, Agent и NNet. Мы реализовали Агент на основе нейронной сети и Агент на основе поиска по дереву Монте-Карло! Итак, для инициализации нашего агента Монте-Карло нам просто нужно написать код:

И наш agent_mcts может предсказывать политику и значение игрового состояния следующим образом:

Что дальше?

Потрясающие! Теперь у нас есть наши основные классы, почти готовые для написания обучающего конвейера Alpha Zero. В следующий раз мы покажем вам, как обучить агента игре в английские шашки, используя поиск по дереву Монте-Карло и глубокую остаточную сеть. Игра имеет сложность примерно 500 995 482 682 338 672 639 возможных позиций, так что задача будет веселой.

Будьте на связи!