В предыдущей статье я писал о том, как реализовать агент обучения с подкреплением для игры в крестики-нолики с использованием алгоритма TD (0). Я реализовал 2 вида агентов. Первый - табличный агент обучения с подкреплением, что означает, что функция значения хранится в виде таблицы, содержащей все значения каждого состояния, которое существует в игре для оптимальной политики (которая изучается во время итераций алгоритма). Все значения можно сохранить, потому что в игре меньше 6000 состояний. Вторая реализация предназначалась для агентов глубокого обучения с подкреплением, что означает, что вместо сохранения всех значений в таблице мы обучаем нейронную сеть предсказывать значение для данного состояния. Этот метод является более общим и надежным, поскольку сеть может изучать сходства, такие как перевод или отражение в пространстве состояний.
В этой статье я хотел бы сделать еще один шаг вперед и попытаться реализовать агент, который учится играть в игру Connect 4. Игра содержит доску с 7 столбцами и 6 строками. Каждый игрок в свою очередь выбирает один из столбцов и сбрасывает один цветной диск сверху, который падает в самое нижнее пустое место. Выигрывает тот, у кого будет 4 диска одного цвета на горизонтальной, вертикальной или диагональной линии. Connect 4 намного сложнее, чем Tic-Tac-Toe, потому что он имеет более 10¹⁴ состояний. В этой статье я опишу 2 разных подхода. Первый подход - это известный алгоритм глубокого обучения Q или DQL, а второй - поиск по дереву Монте-Карло (или MCTS).
Глубокое обучение
Давайте сначала определим наш марковский процесс. Как и в предыдущей статье, процесс обучения будет индивидуальным для каждого игрока, первого или второго, без смешивания между ними. Это потому, что у них разное пространство состояний (например, пустая доска находится в пространстве состояний первого игрока, а не в пространстве состояний второго игрока):
- Пространство состояний - это все состояния, которые видит каждый игрок. Для первого игрока это все доски с четным числом дисков, а для второго игрока - все доски с нечетным числом дисков.
- В ячейке действия будут числа от 1 до 7 для каждого столбца, в который может играть игрок.
- Награда будет 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 - коэффициент скидки.
Несколько заметок об учебном процессе:
- Я обнаружил, что автономное обучение с планированием дает лучшие результаты, чем онлайн-обучение. Автономное обучение означает, что пакеты пар состояние-действие были сохранены, и сеть была обучена на этих пакетах. Я использовал партии по 300 игр. Планирование означает, что каждая партия обучалась более одного раза, а цели пересчитывались каждую эпоху. Я использовал примерно 5 эпох для замеса.
- Политикой игры была политика «е-жадности», что означает, что был выбран фактор исследования е. Фактор определяет шанс сделать случайный ход или оптимальный ход в соответствии с изученной функцией Q. Фактор снизился во время тренировки. Вначале я хотел поощрять исследования, в то время как позже я хотел научиться играть против все более и более оптимальных игроков. Однако время от времени я увеличивал коэффициент исследования по следующей причине: я обнаружил, что первый игрок очень быстро узнает, что лучший первый ход будет играть в середине, поэтому второй игрок учится в основном (когда коэффициент исследования мала), как играть против «первого хода в середине», но других вариантов нет. Чтобы исправить это (и другие подобные проблемы), я время от времени увеличивал коэффициент разведки.
- В первых тренировках я использовал функцию ReLu как функцию активации. Я обнаружил, что сеть не очень хорошо обучается, потому что обучающая выборка имеет много образцов с нулевой меткой, а функция ReLu легко обучается выводить нули. Я заменил его функцией LeakyReLu и получил лучшие результаты.
- Чтобы проверить агента, я дал ему сыграть 300 эпизодов против случайного игрока и измерил процент выигрышей. Чтобы добиться более 80% успеха, потребовалось менее 2000 эпизодов, но когда я попытался сыграть против него, я легко выиграл. Позже я протестировал обучение, позволив агенту соревноваться с фиксированным агентом, а также измерил процент выигрышей.
- В итоге у меня появился довольно хороший агент. Это не сверхчеловеческий уровень, но все же его сложно превзойти (можете попробовать сами).
- График ниже показывает процент выигрышей агента Q против случайного игрока в начале процесса обучения. Он также показывает среднее количество ходов в каждой игре, в среднем более 300 игр. Мы видим, что по мере увеличения коэффициента выигрыша количество ходов уменьшается, что показывает, что агент учится выигрывать и выигрывать быстро.
Поиск по дереву Монте-Карло
В качестве совершенно другого подхода я реализовал агента с использованием алгоритма поиска по дереву Монте-Карло или MCTS.
Идея этого алгоритма заключается в создании дерева игр, но вместо изучения всех возможных игр выбираются только наиболее многообещающие маршруты. Каждый узел в дереве хранит 2 значения: количество посещений узла и количество выигрышей, которые выиграл игрок при посещении этого узла. Алгоритм состоит из 4 шагов, в которых повторяются несколько эпизодов.
- Выделение - вы начинаете с корня - состояния, а выбираете дочернее - ход. Я использовал верхнюю достоверную границу (UCB1), чтобы выбрать ребенка. Для каждого ребенка я вычислил выражение: w / n + c * sqrt (ln (N) / n), где w - количество побед, n - это количество посещений узла, N - количество посещений родительского узла, а c - фактор, балансирующий между исследованием и эксплуатацией. Это самое важное в MCTS. Выбираются наиболее многообещающие дочерние узлы с небольшими шансами на изучение.
- Расширение - когда вы дойдете до узла, где есть дочерние узлы, которые еще не были посещены, выберите один случайным образом и разверните дерево.
- Симуляция - играйте в случайную симуляцию, пока игра не закончится.
- Обратное распространение - обратное распространение на все посещенные узлы, увеличьте на 1 число посещений и, если вы выиграете, увеличьте на 1 выигрышное число.
Несколько замечаний о процессе обучения MCTS:
- Агенту требуется гораздо больше эпизодов для изучения, чем агенту обучения Q, но обучение происходит намного быстрее. На моем компьютере (не очень хорошем) требуется несколько часов, чтобы изучить более 1 миллиона эпизодов.
- Для удобства у каждого игрока есть собственное дерево, хотя оба дерева имеют одинаковую информацию. Я обнаружил, что так поступать более строго и более гибко играть и учиться против других типов агентов (например, агента Q-обучения или случайного агента).
- Чтобы сохранить дерево из 1 миллиона эпизодов, требуется около 800 МБ, и оно растет, когда агент продолжает обучение. Так что это намного больше, чем CNN, который оставался неизменным на протяжении всего процесса обучения.
- На приведенном ниже графике показан процент выигрышей агента MCTS против случайного игрока в процессе обучения.
О коде
Я попытался реализовать код как можно более обобщенным. Код содержит 4 типа классов.
- Игра - класс, содержащий все основы игры на двоих. От этого класса наследуются определенные игровые классы. Я реализовал классы Connect 4 и Tic-Tac-Toe. В игровом классе объявляются все функции, которые необходимо реализовать в конкретном игровом классе.
- Класс агента Q - содержит все основные функции игрового агента для двух игроков. Обучающий агент connect 4 Q унаследован от этого класса.
- Класс модели - содержит модель NN и все связанные с ней функции.
- Класс агента MCTS - аналогичен классу агента Q, но с другими методами
При желании вы можете использовать этот код в качестве основы для других игр или других агентов, реализуя только объявленные нереализованные функции родительских классов.
Резюме
В этой статье мы видели, как обучить агента обучаться игре в Connect 4. Хотя Connect 4 имеет более 10⁴ возможных состояний, а это означает, что, вероятно, каждая игра, в которую когда-либо играли, уникальна, агенты учатся обобщать и хорошо играть. Игрок Q-агента учится обобщать, изучая сходство между различными состояниями, а агент MCTS учится выбирать наиболее многообещающий путь.
Теперь мы можем попробовать и позволить обоим агентам соревноваться друг с другом:
Из результата видно, что в большинстве случаев побеждает первый игрок, а это означает, что, хотя это не выглядит так, первый игрок имеет большое преимущество.
Исходный код можно найти здесь
Спасибо за чтение, если вы обнаружите какие-либо ошибки в моем коде, дайте мне знать, и я исправлю их, если вам понравилась статья, пожалуйста, хлопайте в ладоши, и если у вас есть вопросы, я буду более чем счастлив ответить.