Игра в крестики-нолики с использованием обучения с подкреплением
Обо мне
Я опытный специалист по данным и веб-разработчик с опытом работы более 4 лет. Я специализируюсь на использовании аналитики данных, чтобы помочь компаниям принимать более разумные решения и, таким образом, помочь им масштабироваться. Кроме того, я предоставляю комплексные услуги по разработке веб-сайтов, чтобы помочь вам установить присутствие в Интернете и, таким образом, максимально увеличить охват вашего бизнеса и расширить клиентскую базу. Кроме того, я могу помочь вам интегрировать услуги ИИ в ваш стек независимо от размера вашей организации. Я всегда стараюсь внедрять в свои приложения современные и минималистичные принципы дизайна пользовательского интерфейса, которые помогают вашим клиентам соотносить ваш бренд с качеством.
Проблема, которую я хотел решить
Меня всегда восхищала потрясающая работа OpenAI. Больше всего мне запомнился бот с искусственным интеллектом, который мог играть в очень популярную игру — Dota 2. Dota 2 была средством побега из реального мира для меня и моих друзей, когда я учился в старшей школе. Это вдохновило меня узнать больше о области RL. Я хотел начать с малого, поэтому я начал с Tic Tac Toe.
Процесс создания игры в крестики-нолики с использованием обучения с подкреплением
«Решение крестиков-ноликов с кучей кода». Внимательный зритель может заметить, что я использовал фразу «куча кода» просто потому, что не хотел сосредотачиваться только на методах обучения с подкреплением для решения игр, но также исследовать другие, хотя и неэффективные методы, такие как поиск по дереву, генетический анализ. Алгоритмы и т. д. Я бы с удовольствием занялся более сложной игрой, такой как шахматы, но, будучи новичком в этой области, я решил убить свое эго и начать с игры с одним из самых маленьких пространств состояний — крестики-нолики. .
Давайте посмотрим на нашего первого гладиатора:
1. Минимаксный алгоритм
Минимаксный алгоритм — это правило принятия решений, сформулированное для игр с нулевой суммой для двух игроков (крестики-нолики, шахматы, го и т. д.). Этот алгоритм видит на несколько шагов вперед и ставит себя на место своего оппонента. Он продолжает играть и исследовать последующие возможные состояния, пока не достигнет конечного состояния, приводящего к ничьей, выигрышу или проигрышу. Пребывание в любом из этих возможных конечных состояний имеет некоторую пользу для ИИ — например, состояние «Победа» — это хорошо (полезность положительна), состояние «Проигрыш» — плохо (полезность отрицательна) и ничья ни хороша, ни плоха (полезность нейтральна).
В нашем исполнении минимаксного алгоритма для решения крестиков-ноликов он работает путем визуализации всех будущих возможных состояний доски и строит ее в виде дерева. Когда текущее состояние доски передается алгоритму (корень дерева), он разбивается на «n» ветвей (где n обозначает количество ходов, которые может выбрать ИИ/количество пустых ячеек, в которых ИИ может находиться). размещен). Если какое-либо из этих новых состояний является терминальным состоянием, для этого состояния дальнейшие разбиения не выполняются, и ему присваивается оценка следующим образом:
- оценка = +1 (если побеждает ИИ)
- оценка = -1 (если ИИ проигрывает)
- счет= 0 (если ничья)
Если же терминальных состояний нет — каждое из этих новых состояний считается новыми корнями и порождает собственное дерево. Но есть загвоздка — поскольку это игра для двух игроков, и игроки ходят по очереди, поэтому всякий раз, когда мы углубляемся на один слой в сеть, нам нужно менять игрока, который будет помещен в одну из пустых ячеек. Таким образом, мы можем визуализировать, какие ходы сделал бы другой игрок в результате нашего хода. Алгоритм оценивает наилучший ход, выбирая ход с максимальным количеством очков, когда наступает очередь ИИ, и выбирая наименьшее количество очков, когда наступает очередь человека.
Код для минимаксной реализации
Поскольку пространство состояний крестиков-ноликов очень мало, у нас не может быть дерева с глубиной более 9. Таким образом, нам не нужно использовать здесь такие методы, как альфа-бета-обрезка. Однако особенность минимакса в том, что он предполагает определенный способ игры противника. Например, минимаксный игрок никогда не достигнет игрового состояния, из которого он может проиграть, даже если на самом деле он всегда выигрывал из этого состояния из-за неправильной игры противника.
Вот пример игры:
New Game!
----------------
| || || |
----------------
| || || |
----------------
| || || |
----------------
Choose which player goes first - X (You - the petty human) or O(The mighty AI): O
AI plays move: 2
----------------
| || O || |
----------------
| || || |
----------------
| || || |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 3
----------------
| || O || X |
----------------
| || || |
----------------
| || || |
----------------
AI plays move: 9
----------------
| || O || X |
----------------
| || || |
----------------
| || || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 5
----------------
| || O || X |
----------------
| || X || |
----------------
| || || O |
----------------
AI plays move: 7
----------------
| || O || X |
----------------
| || X || |
----------------
| O || || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 6
----------------
| || O || X |
----------------
| || X || X |
----------------
| O || || O |
----------------
AI plays move: 4
----------------
| || O || X |
----------------
| O || X || X |
----------------
| O || || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 1
----------------
| X || O || X |
----------------
| O || X || X |
----------------
| O || || O |
----------------
AI plays move: 8
----------------
| X || O || X |
----------------
| O || X || X |
----------------
| O || O || O |
----------------
Draw!
Wanna try again BIYTACH?(Y/N) : n
2. Обучение с подкреплением
Я чувствую, что этот алгоритм легче понять, поскольку вы можете использовать его каждый день, даже не осознавая этого. Возьмем практический пример:
Скажем, вы владелец собаки. Вы несколько месяцев приставали к своей супруге и, наконец, заполучили маленького парня, но этому пушистому комку (нашему агенту) нужно приучиться к горшку. Физический мир, в котором наш агент может взаимодействовать и творить чушь, это его среда. Проблема проста — мы хотим, чтобы наш собачий приятель занимался своими делами в желаемом нами месте. Но как нам сказать ему, какое место хорошее, а какое плохое, не пытаясь «говорить с собакой» и выглядеть глупо? Да, мы используем систему вознаграждения. Всякий раз, когда наш агент сваливает на наш модный ковер, он получает отрицательное вознаграждение (называя его плохим мальчиком, отменяя угощение, сильно хлопая по носу и т. д.). Всякий раз, когда он сваливает перед дверью нашего соседа, которого вы считаете действительно раздражающим, он получает положительную награду (называет его лучшим мальчиком, его любимое лакомство, поглаживание живота и т. д.). Со временем агент узнает, что всякий раз, когда он хочет взять свалку (определенное состояние), лучше испачкать тротуар соседа, чем драгоценный ковер, так как это приведет к тому, что он будет в лучшем состоянии, которое дает положительный результат. награда.
Эксплуатация против разведки
Одним из фундаментальных компромиссов в обучении с подкреплением является компромисс между эксплуатацией и разведкой. Эксплуатация означает выбор действия, которое максимизирует наше вознаграждение (может привести к застреванию в локальном оптимуме). Исследование означает выбор действия независимо от вознаграждения, которое оно обеспечивает (это помогает нам обнаружить другие локальные оптимумы, которые могут привести нас ближе к глобальному оптимуму). Изо всех сил использовать любой из них вредно, любая эксплуатация может привести к неоптимальному агенту, а все исследования просто дадут нам глупого агента, который продолжает совершать случайные действия.
Широко используемой стратегией для решения этой проблемы, которую я также использовал в своей реализации, является стратегия уменьшения эпсилон. Это работает следующим образом:
- Инициализируйте переменную «эпсилон» со значением от 0 до 1 (обычно около 0,3).
- Теперь с вероятностью = эпсилон мы исследуем, а с вероятностью = 1-эпсилон мы используем.
- Мы уменьшаем значение эпсилон с течением времени, пока оно не станет равным нулю.
Используя эту стратегию, агент может исследовать лучшие действия на ранних этапах обучения, а затем использовать лучшие действия на более поздних этапах игры. Это похоже на то, как мы, люди, функционируем: мы изучаем различные варианты и ищем новый опыт в возрасте 20 лет (исследование), а затем выбираем определенный карьерный путь и продолжаем двигаться по этому пути (эксплуатация).
Обучение временной разнице
Метод обучения с подкреплением, используемый в этой реализации, называется обучением с временной разницей. Он работает по принципу, согласно которому каждое состояние имеет определенную стоимость. Скажем, если состояние приводит к победе ИИ, оно должно иметь положительное значение (значение = 1). Если ИИ проигрывает в каком-то состоянии, оно должно иметь отрицательное значение (значение = -1). Все остальные состояния будут иметь нейтральное значение (значение = 0). Это инициализированные значения состояния.
Как только игра запущена, наш агент вычисляет все возможные действия, которые он может предпринять в текущем состоянии, и новые состояния, которые могут возникнуть в результате каждого действия. Значения этих состояний собираются из вектора state_value, который содержит значения для всех возможных состояний в игре. Затем агент может выбрать действие, которое приводит к состоянию с наивысшим значением (эксплуатация), или выбрать случайное действие (исследование), в зависимости от значения эпсилон. В ходе нашего обучения мы играем в несколько игр, после каждого хода значение состояния обновляется по следующему правилу:
где V(s) — текущее состояние игровой доски, V(s^f) — новое состояние доски после того, как агент предпримет какое-либо действие, а альфа — параметр скорости обучения/размера шага.
Используя это правило обновления, состояния, которые приводят к потере, также получают отрицательное значение состояния (величина которого зависит от скорости обучения). Агент узнает, что нахождение в таком состоянии может привести к убыткам в будущем, поэтому он будет стараться избегать попадания в это состояние, если в этом нет необходимости. С другой стороны, состояния, ведущие к выигрышу, получают положительное значение состояния. Агент узнает, что нахождение в таком состоянии может привести к выигрышу в будущем, поэтому его пребывание в этом состоянии будет поощряться.
Есть 2 версии кода для этого алгоритма:
Код тестирования — Вы можете играть против обученного ИИ: Ссылка на гитхаб
Код обучения — оба игрока ИИ, где каждый из них помогает тренировать друг друга. Это для моей ленивой команды. Если вы предпочитаете взять немного попкорна и позволить двум ИИ сразиться между собой, то вот код: Ссылка на гитхаб
Ниже приведен пример игры против бота, обученного примерно 10000 эпох.
New Game!
----------------
| || || |
----------------
| || || |
----------------
| || || |
----------------
Choose which player goes first - X (You - the petty human) or O(The mighty AI): X
Oye Human, your turn! Choose where to place (1 to 9): 5
----------------
| || || |
----------------
| || X || |
----------------
| || || |
----------------
Possible moves = [1, 2, 3, 4, 6, 7, 8, 9]
Move values = [-0.218789, -0.236198, -0.147603, -0.256198, -0.365461, -0.221161, -0.234462, -0.179749]
AI plays move: 3
----------------
| || || O |
----------------
| || X || |
----------------
| || || |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 1
----------------
| X || || O |
----------------
| || X || |
----------------
| || || |
----------------
Possible moves = [2, 4, 6, 7, 8, 9]
Move values = [-0.633001, -0.625314, -0.10769, -0.543454, -0.265536, 0.034457]
AI plays move: 9
----------------
| X || || O |
----------------
| || X || |
----------------
| || || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 6
----------------
| X || || O |
----------------
| || X || X |
----------------
| || || O |
----------------
Possible moves = [2, 4, 7, 8]
Move values = [-0.255945, 0.003558, -0.2704, -0.25632]
AI plays move: 4
----------------
| X || || O |
----------------
| O || X || X |
----------------
| || || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 2
----------------
| X || X || O |
----------------
| O || X || X |
----------------
| || || O |
----------------
Possible moves = [7, 8]
Move values = [0.0, 0.03941]
AI plays move: 8
----------------
| X || X || O |
----------------
| O || X || X |
----------------
| || O || O |
----------------
Oye Human, your turn! Choose where to place (1 to 9): 7
----------------
| X || X || O |
----------------
| O || X || X |
----------------
| X || O || O |
----------------
Draw!
Wanna try again?(Y/N) : n
Suit yourself!
Это шоу
Теперь, когда у нас есть два готовых чемпиона, давайте бросим их в виртуальный Колизей и позволим им сражаться, пока мы с трепетом смотрим. Так как у нас сейчас только 2 из них, у нас будет битва техническим нокаутом 1 на 1. В общем, вот что получилось:
Results(10 games):
Minimax Wins = 0
RL Agent Wins = 10
(Я вызвал монстра, не так ли?)
Заключительные мысли и следующие шаги
Если вы хотите увидеть весь матч, вот код: Полный код
Это единственные алгоритмы, с которыми я пока работал. Я мог бы изучить некоторые другие интересные алгоритмы, такие как генетические алгоритмы, но это на потом. Если вы нашли мое письмо хоть немного полезным или даже достаточно забавным, чтобы заставить вас немного посмеяться, хлопните в ладоши и оставьте ответ ниже.
Спасибо за прочтение ❤
