Ним

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

$python play.py
Playing training game 1
Playing training game 2

Пояснение

Напомним, что в игре Ним мы начинаем с некоторого количества кучек, в каждой из которых находится определённое количество предметов. Игроки ходят по очереди: в свой ход игрок убирает любое неотрицательное количество предметов из любой непустой кучки. Проигрывает тот, кто уберут последний предмет.

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

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

Как мы будем представлять состояния и действия внутри программы Python? «Состояние» игры «Ним» — это текущие размеры всех кучек. Например, состоянием может быть [1, 1, 3, 5], представляющее состояние с 1 объектом в кучке 0, 1 объектом в кучке 1, 3 объектами в кучке 2 и 5 объектами в кучке 3. «Действием» в игре Ним будет пара целых чисел (i, j), представляющая действие по взятию j предметов из кучки i. Таким образом, действие (3, 5) представляет собой действие «из кучки 3 забрать 5 предметов». Применение этого действия к состоянию [1, 1, 3, 5] приведёт к созданию нового состояния [1, 1, 3, 0] (то же самое состояние, но стопка 3 теперь пуста).

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

Q(s, a) <- Q(s, a) + alpha * (new value estimate - old value estimate)

В приведённой выше формуле alpha — это скорость обучения (насколько мы ценим новую информацию по сравнению с информацией, которая у нас уже есть). Новая оценка значения представляет собой сумму награды, полученной за текущее действие, и оценку всех будущих наград, которые получит игрок. Старая оценка значения — это просто существующее значение для Q(s, a). Применяя эту формулу каждый раз, когда наш ИИ предпринимает новое действие, со временем наш ИИ начнёт узнавать, какие действия лучше в том или ином состоянии.

Начало

Загрузите код и распакуйте.

wget "https://cs204.github.io/psets/data/nim.zip"
unzip nim.zip
cd nim

Понимание

Сначала откройте nim.py. В этом файле определены два класса (Nim и NimAI) и две функции (обучать и играть). Nim, обучать и играть уже реализованы за вас, а NimAI оставляет вам несколько функций для реализации.

Взгляните на класс Nim, который определяет, как ведётся игра Nim. Обратите внимание, что в функции __init__ каждая игра Nim должна отслеживать список кучек, текущего игрока (0 или 1) и победителя игры (если таковой существует). Функция доступные_действия возвращает набор всех доступных действий в состоянии. Например, Nim.доступные_действия([2, 1, 0, 0]) возвращает набор {(0, 1), (1, 1), (0, 2)}, поскольку три возможных действия должны выполнить либо 1 или 2 предмета из кучки 0, или взять 1 предмет из кучки 1.

Остальные функции используются для определения игрового процесса: функция другой_игрок определяет, кто является противником данного игрока, сменить_игрока меняет текущего игрока на игрока противника, а "ход" выполняет действие в текущем состоянии и переключает текущего игрока на игрока противника.

Далее взгляните на класс NimAI, который определяет наш ИИ, который будет учиться играть в Ним. Обратите внимание, что в функции __init__ мы начинаем с пустого словаря self.q. Словарь self.q будет отслеживать все текущие значения Q, полученные нашим ИИ, путём сопоставления пар (состояние, действие) с числовыми значениями. В качестве детали реализации, хотя мы обычно представляем состояние в виде list (списка), поскольку списки не могут использоваться в качестве ключей dict (словаря) Python, вместо этого мы будем использовать tuple (кортежную) версию состояния при получении или установке значений в self.q.

Например, если бы мы хотели установить значение Q состояния [0, 0, 0, 2] и действия (3, 2) равным -1, мы бы написали что-то вроде

self.q[(0, 0, 0, 2), (3, 2)] = -1

Также обратите внимание, что каждый объект NimAI имеет значения alfa и epsilon, которые будут использоваться для Q-обучения и выбора действия соответственно.

Функция обновить написана для вас и принимает в качестве входных данных состояние старое_состояние, действие, выполненное в этом состоянии, результирующее состояние после выполнения этого действия новое_состояние и немедленное вознаграждение за выполнение этого действия. Затем функция выполняет Q-обучение, сначала получая текущее значение Q для состояния и действия (путём вызова получить_q_значение), определяя наилучшие возможные будущие награды (путём вызова лучшая_будущая_награда), а затем используя оба этих значения для обновления Q-значения (путём вызова обновить_q_значение). Эти три функции вам надо определить.

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

Классы Nim и NimAI в конечном итоге используются в функциях обучать и играть. Функция обучать тренирует ИИ, запуская против него самого n симулированных игр и возвращая полностью обученный ИИ. Функция играть принимает на вход обученный ИИ и позволяет игроку-человеку сыграть в игру Ним против ИИ.

Спецификация

Завершите реализацию получить_q_значение, обновить_q_значение, лучшая_будущая_награда и выбрать_действие в nim.py. Для каждой из этих функций каждый раз, когда функция принимает состояние в качестве входных данных, вы можете предположить, что это список целых чисел. Каждый раз, когда функция принимает действие в качестве входных данных, вы можете предположить, что это целочисленная пара (i, j) стопки i и количества объектов j.

Функция получить_q_значение должна принимать в качестве входных данных состояние и действие и возвращать соответствующее значение Q для этой пары состояние/действие.

• Напомним, что Q-значения хранятся в словаре self.q. Ключи self.q должны быть в виде пар (состояние, действие), где состояние — это кортеж всех размеров стопок по порядку, а действие — это кортеж (i, j), представляющий стопку и число.
• Если в self.q не существует значения Q для пары состояние/действие, функция должна вернуть 0.

Функция обновить_q_значение принимает состояние состояния, действие действие, существующее значение Q старое_q, текущее вознаграждение и оценку будущих вознаграждений будущие_награды, и обновляет значение Q для пары состояние/действие в соответствии с формулой Q-обучения. .

• Напомним, что формула Q-обучения выглядит следующим образом:

   
  		 
        Q(s, a) <- старая оценка значения + альфа * (новая оценка значения - старая оценка значения)
        
  		

• Напомним, что альфа — это скорость обучения, связанная с объектом NimAI.
• Старая оценка значения — это просто существующее значение Q для пары состояние/действие. Новая оценка стоимости должна представлять собой сумму текущего вознаграждения и предполагаемого будущего вознаграждения.

Функция лучшая_будущая_награда принимает состояние в качестве входных данных и возвращает наилучшую возможную награду за любое доступное действие в этом состоянии, согласно данным в self.q.

• Для любого действия, которого ещё нет в self.q для данного состояния, следует предположить, что его значение Q равно 0.
• Если в состоянии нет доступных действий, вы должны вернуть 0.

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

• Если epsilon имеет значение False, ваша функция должна вести себя жадно и возвращать наилучшее возможное действие, доступное в этом состоянии (т. е. действие, которое имеет наибольшее значение Q, используя 0, если значение Q не известно).
• Если epsilon имеет значение True, ваша функция должна вести себя в соответствии с эпсилон-жадным алгоритмом, выбирая случайное доступное действие с вероятностью self.epsilon и в противном случае выбирая лучшее доступное действие.
• Если несколько действий имеют одно и то же значение Q, любая из этих опций является приемлемым возвращаемым значением.

Вам не следует изменять что-либо ещё в nim.py, кроме функций, которые спецификация требует от вас реализовать, хотя вы можете писать дополнительные функции и/или импортировать другие модули стандартной библиотеки Python. Вы также можете импортировать numpy или pandas, если знакомы с ними, но вам не следует использовать какие-либо другие сторонние модули Python. Вы можете изменить play.py для самостоятельного тестирования.

Подсказки

Если lst — это список, то можно использовать tuple(lst) для преобразования lst в кортеж.