Автор оригинала: Rohit Agrawal.
Обо мне
Я опытный специалист по обработке данных и веб-разработчик с более чем 4 – летним опытом работы. Я специализируюсь на использовании аналитики данных, чтобы помочь компаниям принимать более разумные решения и, таким образом, помочь им масштабироваться. Кроме того, я предоставляю комплексные услуги по разработке веб-сайтов, чтобы помочь вам установить присутствие в Интернете и, таким образом, максимизировать охват вашего бизнеса и расширить клиентскую базу. Кроме того, я могу помочь вам интегрировать сервисы искусственного интеллекта в ваш стек независимо от размера вашей организации. Я всегда стараюсь внедрять в свои приложения современные и минималистичные принципы дизайна пользовательского интерфейса, которые помогают вашим клиентам соотносить ваш бренд с качеством.
Проблема, которую я хотел решить
Я всегда был очарован удивительной работой, проделанной OpenAI. Тот, который выделялся для меня, был ИИ – ботом, который мог играть в массово популярную игру- Dota 2. Dota 2 была убежищем от реального мира для меня и моих друзей, когда я учился в средней школе. Это вдохновило меня узнать больше о области RL. Я хотел начать с малого, поэтому начал с крестиков-ноликов.
Процесс построения игры в крестики-нолики с использованием обучения с подкреплением
“Решение крестиков-ноликов с кучей кода”. Внимательный зритель может заметить, что я использовал фразу “куча кода” просто потому, что я не хотел сосредотачиваться только на методах обучения с подкреплением для решения игр, но также исследовать другие, хотя и неэффективные, методы, такие как поиск по дереву, генетические алгоритмы и т. Д. Я бы с удовольствием выбрал более сложную игру, например шахматы, но, будучи новичком в этой области, я решил убить свое эго и начать с игры с одним из самых маленьких пространств состояний — Крестики-нолики.
Давайте взглянем на нашего первого гладиатора:
1. Алгоритм Минимакса
Алгоритм минимакса-это правило принятия решений, сформулированное для игр с нулевой суммой для 2 игроков (Крестики-нолики, шахматы, Го и т. Д.). Этот алгоритм видит на несколько шагов вперед и ставит себя на место своего противника. Он продолжает играть и исследовать последующие возможные состояния, пока не достигнет терминального состояния, приводящего к ничьей, выигрышу или проигрышу. Пребывание в любом из этих возможных терминальных состояний имеет некоторую полезность для ИИ — например, быть в состоянии “Выигрыша” хорошо (полезность положительна), быть в состоянии “Проигрыша” плохо (полезность отрицательна) и быть в ничьей ни хорошо, ни плохо (полезность нейтральна).
В нашем исполнении минимаксного алгоритма для решения крестиков-ноликов он работает путем визуализации всех будущих возможных состояний доски и строит ее в виде дерева. Когда текущее состояние доски задается алгоритму (корень дерева), он разбивается на “n” ветвей (где n обозначает количество ходов, которые могут быть выбраны AI/количество пустых ячеек, в которых может быть размещен AI). Если какое-либо из этих новых состояний является терминальным состоянием, для этого состояния не выполняется никаких дальнейших разбиений, и ему присваивается оценка следующим образом:
- оценка = +1 (если победит ИИ)
- оценка = -1 (если AI проиграет)
- счет= 0 (если произойдет ничья)
Если, однако, нет терминальных состояний — каждое из этих новых состояний рассматривается как новые корни, и они порождают свое собственное дерево. Но есть одна загвоздка — поскольку это игра для 2 игроков, и игроки по очереди чередуются, поэтому всякий раз, когда мы идем на один уровень глубже в сети, нам нужно изменить игрока, который будет помещен в одну из пустых ячеек. Таким образом, мы можем визуализировать, какие ходы сделает другой игрок в результате нашего хода. Алгоритм оценивает лучший ход, выбирая ход, который имеет максимальный балл, когда наступает очередь ИИ, и выбирая минимальный балл, когда наступает очередь Человека.
Код для минимаксной реализации
Поскольку пространство состояний крестиков-ноликов настолько мало, у нас не может быть дерева глубиной более 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)
- Теперь с, мы исследуем и с-эпсилон, мы эксплуатируем.
- Мы уменьшаем значение эпсилона с течением времени, пока оно не станет равным нулю
Используя эту стратегию, агент может исследовать лучшие действия на ранних этапах обучения, а затем использовать лучшие действия на более поздних этапах игры. Это похоже на то, как мы, люди, функционируем — мы исследуем различные варианты и ищем новый опыт в начале 20-х годов(исследование), а затем выбираем определенный карьерный путь и продолжаем двигаться по этому пути(эксплуатация).
Обучение с временными различиями
Метод обучения с подкреплением, используемый в этой реализации, называется обучением с временными различиями. Он работает по принципу, согласно которому каждое государство имеет определенную ценность. Скажем, если государство приводит к победе ИИ, оно должно иметь положительный результат). Если AI проигрывает в каком-то состоянии, он должен иметь отрицательное значение(значение = -1). Все остальные штаты были бы нейтральными). Это значения инициализированного состояния.
Как только игра запущена, наш агент вычисляет все возможные действия, которые он может предпринять в текущем состоянии, и новые состояния, которые возникнут в результате каждого действия. Значения этих состояний собираются из вектора state_value, который содержит значения для всех возможных состояний в игре. Затем агент может выбрать действие, которое приводит к состоянию с наибольшим значением(эксплуатация), или выбрать случайное действие(исследование), в зависимости от значения эпсилона. В течение нашего обучения мы играем в несколько игр, после каждого хода значение состояния обновляется с использованием следующего правила:
где V(s) — текущее состояние игрового поля, V(s^f) — Новое состояние игрового поля после того, как агент выполнит какое — либо действие, а альфа-параметр скорости обучения/размера шага.
Используя это правило обновления, состояния, которые приводят к потере, также получают отрицательное значение состояния(величина которого зависит от скорости обучения). Агент узнает, что пребывание в таком состоянии может привести к потере в будущем, поэтому он постарается избежать посадки в этом состоянии, если это не будет необходимо. С другой стороны, состояния, которые приводят к победе, получают положительное значение состояния. Агент узнает, что пребывание в таком состоянии может привести к победе в будущем, поэтому ему будет рекомендовано находиться в этом состоянии.
Существует 2 версии кода для этого алгоритма:
Тестовый код — Вы можете играть против обученного ИИ: Ссылка на Github
Код обучения — оба игрока являются ИИ, где каждый из них помогает тренировать друг друга. Это для моего ленивого отряда. Если вы предпочитаете взять немного попкорна и позволить двум ИИ сразиться между собой, то вот код: Ссылка на Github
Ниже приведен пример игры против бота, обученного в течение ~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 наших чемпиона, давайте бросим их в виртуальный Колизей и позволим им сражаться, пока мы смотрим с благоговением. Поскольку у нас сейчас только 2 из них, у нас будет просто бой 1 на 1. В принципе, это был результат:
Results(10 games): Minimax Wins = 0 RL Agent Wins = 10
(Я вызвал монстра, не так ли?)
Заключительные мысли и следующие шаги
Если вы хотите увидеть все совпадение, вот код: Полный код Это единственные алгоритмы, с которыми я еще поработал. Я мог бы изучить некоторые другие интересные алгоритмы, такие как генетические алгоритмы, но это на потом. Если вы нашли мое письмо хотя бы отдаленно полезным или даже достаточно забавным, чтобы заставить вас слегка посмеяться, хлопните в ладоши и напишите ответ ниже.
Спасибо за чтение ❤