Недавно я научил своих детей игре в крестики-нолики, в которые, как я помню, играл сам в детстве. Это игра с простыми правилами, и поэтому ее легко освоить в детстве, по сути, на один шаг впереди от камня-ножниц-бумаги. Игра иногда также называется крестики-нолики, поскольку два игрока поочередно ставят крестик («x», игрок 1) и ноль («o», игрок 2) в таблице 3 на 3. Выигрывает тот игрок, который первым наберет три подряд по вертикали, горизонтали или диагонали. Вот пример игры, последовательность ходов, в которой выигрывает первый игрок (x).

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

За последние пару лет в качестве исследователя я все больше сосредотачивался на применении машинного обучения в сочетании с традиционными математическими алгоритмами. Простота крестиков-ноликов позволяет решать их, используя самые разные приемы. В этой последовательности сообщений я опишу, как компьютер может научиться играть в крестики-нолики, используя простую форму обучения с подкреплением. Хотя игра в крестики-нолики не так уж и интересна, математические идеи, которые играют роль в решении игры, довольно увлекательны. Мы будем использовать эти идеи, чтобы посмотреть, какие варианты крестиков-ноликов приведут к более интересным играм.

Обучение с подкреплением

Книга Саттона и Барто [1] представляет собой отличный вход в обучение с подкреплением, предлагая следующее интуитивно понятное описание:

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

Давайте разберемся с этим описанием в контексте крестиков-ноликов. Здесь ситуация относится к состоянию игры (называемому марковским состоянием, обозначается символом s), примеры которого показаны выше. Действие (обозначается a) - это ход, который можно выбрать в определенном игровом состоянии, то есть размещении кирпича игрока в одном из открытых полей. Цифровой сигнал вознаграждения (обозначается r) направлен на то, чтобы направить учащегося к выбору действий, которые достигают его цели, например, награждение победившей игры наградой +100, наказание проигрышная игра с отрицательной наградой -100 или даже наказание за неправильные ходы некоторой отрицательной наградой. В последнем случае учащийся может выучить правила игры, даже не говоря об этих правилах.

Этот учащийся называется агентом, так как он имеет право решать, какие действия предпринять в данном состоянии. Процесс принятия решения - это политика для сопоставления ситуаций с действием, описывающая в каждом конкретном состоянии, как часто выбирается каждое из действий. Математически это называется условным распределением вероятностей и кратко записывается как π (a | s) («вероятность выбора действия a в данное состояние s ”).

Крестики-нолики - это простая игра, в которой ясно, что будет происходить при каждом действии. Одна из основных сильных сторон обучения с подкреплением - иметь дело с ситуациями, в которых это не так ясно. Неопределенность обрабатывается путем введения среды, которая представляет все за пределами агента, с чем агент может взаимодействовать. Для каждого данного состояния s и выбранного действия a среда описывает, как часто игра переходит в каждое новое состояние s ' и как часто соответствующее награда r раздается. Математически эта динамика среды снова представлена ​​условным распределением вероятностей, кратко записанным как p (s ', r | s, a) («вероятность перехода для состояния s ' и получения вознаграждения r за данное состояние s и действие a »).

Таким образом, агент и среда попеременно выбирают действия и генерируют новые состояния и награды, что можно графически изобразить в следующем цикле [1]:

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

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

Учимся играть

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

Почти все алгоритмы подкрепления обучаются, оценивая значение v (s; π) состояний или оценивая значение q (s, a; π) действий, предпринятых в данное состояние. Здесь значение имеет техническое определение, а именно общее вознаграждение, которое можно ожидать при соблюдении данной политики π. Когда агент хорошо понимает значение состояний и действий, он может просто следовать политике, которая максимизирует это значение.

Q-обучение обеспечивает простой способ изучения функции ценности. Здесь все значения состояния-действия хранятся в таблице, в которой перечислены все комбинации состояний и действий. Для крестиков-ноликов количество таких комбинаций достаточно мало, чтобы мы могли их обработать. Эта Q-таблица итеративно обновляется путем распространения информации от переходов к будущим состояниям и возврата к более ранним состояниям с использованием простого правила обновления. Математические детали представлены ниже, но их можно пропустить.

В случае, если вышеуказанный цикл продолжается бесконечно, можно избежать досадных бесконечных значений, дисконтируя будущие вознаграждения. Как оказалось, умножение вознаграждения r на будущем временном шаге t на коэффициент γᵗ, равный 0 ‹γ‹ 1, дает особенно элегантную математическую формулировку. Чтобы быть точным, значение состояния s в рамках данной политики π определяется как ожидаемое общее дисконтированное вознаграждение при запуске в состоянии s и следующая политика π:

Точно так же ценность выполнения действия a в состоянии s в соответствии с данной политикой π определяется как ожидаемое общее дисконтированное вознаграждение после выполнения действия a в состоянии s и следующей политике π:

Правило обновления в Q-Learning:

В этом правиле значение «состояние-действие» корректируется путем перемещения с шагом α в направлении значения «состояние-действие», оцененного на следующем временном шаге.

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

Мы начинаем с предположения, что противник играет случайную игру из разрешенных ходов (как это было бы вначале после знакомства с игрой для моих детей, хотя и на короткий период времени). Даже назначение агенту случайной политики уже может дать интересное представление об игре. В игре существует фундаментальная асимметрия, определяемая тем, кто начинает. Насколько велико расхождение для двух случайных игроков? Моделирование 100 000 игр в моей реализации Python привело к тому, что Игрок 1 выигрывал в 58% случаев, Игрок 2 выигрывал в 29% случаев, а игра заканчивалась ничьей в оставшихся 13% случаев.

Как отмечалось выше, после изучения значений «состояние-действие» агент может следовать политике, которая максимизирует значение «состояние-действие». Это будет тема следующей части.

[1] Саттон и Барто, Обучение с подкреплением: введение, 2-е издание (2018 г.)