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

В этой статье я хотел бы сделать еще один шаг вперед и попытаться реализовать агент, который учится играть в игру Connect 4. Игра содержит доску с 7 столбцами и 6 строками. Каждый игрок в свою очередь выбирает один из столбцов и сбрасывает один цветной диск сверху, который падает в самое нижнее пустое место. Выигрывает тот, у кого будет 4 диска одного цвета на горизонтальной, вертикальной или диагональной линии. Connect 4 намного сложнее, чем Tic-Tac-Toe, потому что он имеет более 10¹⁴ состояний. В этой статье я опишу 2 разных подхода. Первый подход - это известный алгоритм глубокого обучения Q или DQL, а второй - поиск по дереву Монте-Карло (или MCTS).

Глубокое обучение

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

  1. Пространство состояний - это все состояния, которые видит каждый игрок. Для первого игрока это все доски с четным числом дисков, а для второго игрока - все доски с нечетным числом дисков.
  2. В ячейке действия будут числа от 1 до 7 для каждого столбца, в который может играть игрок.
  3. Награда будет 1 за победу, -1 за проигрыш, 0,5 за ничью и 0 в противном случае.

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

Научиться играть против новичка - это не то же самое, что научиться играть против профессионального игрока, потому что вероятности перехода будут другими. Об этом я подробнее расскажу в статье.

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

Область функции Q содержит более 7 * 10¹⁴ (7 возможных действий для более чем 10¹⁴ состояний) и сопоставляет их с числом от -1 до 1 (диапазон вознаграждений). Для представления этой функции мы будем использовать CNN.

Входом CNN будет матрица 7 * 7, где первая строка - это горячий вектор, соответствующий действию, а 6 других строк - это представление состояния, где 1, -1 и 0 - диск игрока, диск соперника или пустое место соответственно.

Сеть описана на следующем рисунке:

где было выбрано 5 ядер в первом сверточном слое и 4 для остальных сверточных слоев (мне кажется логичным выбрать 4, потому что игрокам нужно 4 подряд, чтобы выиграть).

Цели рассчитывались согласно алгоритму обучения Q:

Q (s, a) = Q (s, a) + α (max (Q (s ’, a’)) + g R-Q (s, a))

где Q - функция Q, s - состояние, a - действие, α - скорость обучения, R - это вознаграждение, а g - коэффициент скидки.

Несколько заметок об учебном процессе:

  1. Я обнаружил, что автономное обучение с планированием дает лучшие результаты, чем онлайн-обучение. Автономное обучение означает, что пакеты пар состояние-действие были сохранены, и сеть была обучена на этих пакетах. Я использовал партии по 300 игр. Планирование означает, что каждая партия обучалась более одного раза, а цели пересчитывались каждую эпоху. Я использовал примерно 5 эпох для замеса.
  2. Политикой игры была политика «е-жадности», что означает, что был выбран фактор исследования е. Фактор определяет шанс сделать случайный ход или оптимальный ход в соответствии с изученной функцией Q. Фактор снизился во время тренировки. Вначале я хотел поощрять исследования, в то время как позже я хотел научиться играть против все более и более оптимальных игроков. Однако время от времени я увеличивал коэффициент исследования по следующей причине: я обнаружил, что первый игрок очень быстро узнает, что лучший первый ход будет играть в середине, поэтому второй игрок учится в основном (когда коэффициент исследования мала), как играть против «первого хода в середине», но других вариантов нет. Чтобы исправить это (и другие подобные проблемы), я время от времени увеличивал коэффициент разведки.
  3. В первых тренировках я использовал функцию ReLu как функцию активации. Я обнаружил, что сеть не очень хорошо обучается, потому что обучающая выборка имеет много образцов с нулевой меткой, а функция ReLu легко обучается выводить нули. Я заменил его функцией LeakyReLu и получил лучшие результаты.
  4. Чтобы проверить агента, я дал ему сыграть 300 эпизодов против случайного игрока и измерил процент выигрышей. Чтобы добиться более 80% успеха, потребовалось менее 2000 эпизодов, но когда я попытался сыграть против него, я легко выиграл. Позже я протестировал обучение, позволив агенту соревноваться с фиксированным агентом, а также измерил процент выигрышей.
  5. В итоге у меня появился довольно хороший агент. Это не сверхчеловеческий уровень, но все же его сложно превзойти (можете попробовать сами).
  6. График ниже показывает процент выигрышей агента Q против случайного игрока в начале процесса обучения. Он также показывает среднее количество ходов в каждой игре, в среднем более 300 игр. Мы видим, что по мере увеличения коэффициента выигрыша количество ходов уменьшается, что показывает, что агент учится выигрывать и выигрывать быстро.

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

В качестве совершенно другого подхода я реализовал агента с использованием алгоритма поиска по дереву Монте-Карло или MCTS.

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

  1. Выделение - вы начинаете с корня - состояния, а выбираете дочернее - ход. Я использовал верхнюю достоверную границу (UCB1), чтобы выбрать ребенка. Для каждого ребенка я вычислил выражение: w / n + c * sqrt (ln (N) / n), где w - количество побед, n - это количество посещений узла, N - количество посещений родительского узла, а c - фактор, балансирующий между исследованием и эксплуатацией. Это самое важное в MCTS. Выбираются наиболее многообещающие дочерние узлы с небольшими шансами на изучение.
  2. Расширение - когда вы дойдете до узла, где есть дочерние узлы, которые еще не были посещены, выберите один случайным образом и разверните дерево.
  3. Симуляция - играйте в случайную симуляцию, пока игра не закончится.
  4. Обратное распространение - обратное распространение на все посещенные узлы, увеличьте на 1 число посещений и, если вы выиграете, увеличьте на 1 выигрышное число.

Несколько замечаний о процессе обучения MCTS:

  1. Агенту требуется гораздо больше эпизодов для изучения, чем агенту обучения Q, но обучение происходит намного быстрее. На моем компьютере (не очень хорошем) требуется несколько часов, чтобы изучить более 1 миллиона эпизодов.
  2. Для удобства у каждого игрока есть собственное дерево, хотя оба дерева имеют одинаковую информацию. Я обнаружил, что так поступать более строго и более гибко играть и учиться против других типов агентов (например, агента Q-обучения или случайного агента).
  3. Чтобы сохранить дерево из 1 миллиона эпизодов, требуется около 800 МБ, и оно растет, когда агент продолжает обучение. Так что это намного больше, чем CNN, который оставался неизменным на протяжении всего процесса обучения.
  4. На приведенном ниже графике показан процент выигрышей агента MCTS против случайного игрока в процессе обучения.

О коде

Я попытался реализовать код как можно более обобщенным. Код содержит 4 типа классов.

  1. Игра - класс, содержащий все основы игры на двоих. От этого класса наследуются определенные игровые классы. Я реализовал классы Connect 4 и Tic-Tac-Toe. В игровом классе объявляются все функции, которые необходимо реализовать в конкретном игровом классе.
  2. Класс агента Q - содержит все основные функции игрового агента для двух игроков. Обучающий агент connect 4 Q унаследован от этого класса.
  3. Класс модели - содержит модель NN и все связанные с ней функции.
  4. Класс агента MCTS - аналогичен классу агента Q, но с другими методами

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

Резюме

В этой статье мы видели, как обучить агента обучаться игре в Connect 4. Хотя Connect 4 имеет более 10⁴ возможных состояний, а это означает, что, вероятно, каждая игра, в которую когда-либо играли, уникальна, агенты учатся обобщать и хорошо играть. Игрок Q-агента учится обобщать, изучая сходство между различными состояниями, а агент MCTS учится выбирать наиболее многообещающий путь.

Теперь мы можем попробовать и позволить обоим агентам соревноваться друг с другом:

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

Исходный код можно найти здесь

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