Поиск по дереву Монте-Карло: реализация обучения с подкреплением в игре в реальном времени

Часть 1 - Основные концепции обучения с подкреплением

Введение

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

То, что вы собираетесь прочитать, будет частью серии статей, в которых мы рассмотрим взлеты и падения при реализации General Game Player в настольной игре, а именно HEX. Если вы торопитесь, вы можете найти чистый код Python здесь:

masouduut94 / MCTS-agent-python
Поиск по дереву Монте-Карло (MCTS) - это метод поиска оптимальных решений в заданной области путем взятия случайных выборок в… github.com

а также более новая версия, которая использует cython для ускорения моделирования здесь:

masouduut94 / MCTS-agent-cythonized
Поиск по дереву Карло в MONTE (MCTS) - это метод поиска оптимальных решений в заданной области путем отбора случайных выборок в… github.com

Это демонстрация конечного продукта. Проверить это:

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

ОБЗОР

Описание проблемы
Что такое обучение с подкреплением
Q-обучение
Заключение

Описание проблемы

Предположим, вы шахматист и рассматриваете эту доску как текущее состояние игры:

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

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

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

Вот некоторые из вариантов для черных игроков:

Переместите черную ладью в D8 и убейте белого слона в D2.
Переместите черного коня в G4 и убейте белого ферзя в E3.
Переместите черного ферзя в H5, поместите его на H1, мат и выиграйте игру .

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

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

Другими словами, есть немедленная награда (удаление фишек противника) и долгосрочная награда (победа в игре), и последнее более желательно для игроков.

Давайте подведем итоги того, что мы обсуждали, на этом этапе:

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

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

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

Что такое обучение с подкреплением?

Р. Саттон и др. [1] очень хорошо описывают RL:

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

Ключевые элементы RL:

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

Как утверждает [1], ключевые различия между RL и другими методами заключаются в его методе проб и ошибок и отложенном вознаграждении. Я нашел [2] и [3] лучше всего для понимания различий между RL и другими техниками.

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

Я рекомендую вам посмотреть это видео, которое суммирует все, что я объяснил к этому моменту, и лучше всего объясняет математические обозначения:

Q - Обучение

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

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

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

Я рекомендую это короткое видео, предоставленное командой Udacity, которое разъясняет разницу между средой, моделируемой агентом, и средой, которую этот агент взаимодействует с участием:

Именно здесь на помощь приходит метод Q-обучения. Q-обучение - это алгоритм RL, который изучает оптимальную политику, а не максимизацию долгосрочных вознаграждений в отношении любых и всех последовательных состояний, начиная с текущего состояния (планирование).
Q-Learning может изучить лучшую политику, если ему дано бесконечное время исследования и частично случайная политика [4].
Отметьте это статью, чтобы просмотреть подробности в контексте [5].

Заключение

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

1 - если есть только один лучший ход между другими, как мы можем его найти, если мы не можем обработать все последовательные состояния один за другим из-за ограниченного количества времени?
2 - как мы сопоставим поиск лучшего хода к длинным -срочные награды, если мы ограничены с точки зрения вычислительных ресурсов и времени?

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