Reinforcement Learning для настольных игр: введение

Большинство введений в reinforcement learning начинаются с абстрактных Марковских процессов принятия решений и игрушечных задач типа grid-world. Это математически чисто, но пропускает историческую причину, по которой RL стал знаменит: настольные игры. Короткие нарды, шахматы, Go — именно там алгоритмы впервые доказали, что могут конкурировать с лучшими игроками-людьми. Эта статья — RL primer именно через эту призму.

Мы разберём базовые ингредиенты (состояния, действия, награды, политики, функции ценности), почему игры с костями особенно хорошо ложатся на них, и почему короткие нарды стали тем поворотным моментом, который вывел область в мейнстрим. Каждое понятие подкреплено конкретным примером из настольной игры — короткие нарды для коротких сюжетов, длинные нарды для специфики варианта.

Что такое RL в одном абзаце

Reinforcement learning — это фреймворк, в котором агент учится действовать, взаимодействуя со средой и наблюдая последствия. Нет размеченных тренировочных данных, говорящих агенту: «в этом состоянии правильный ход — X». Вместо этого агент получает награду (число) в конце каждого эпизода (партии) и со временем корректирует своё поведение, чтобы максимизировать ожидаемую суммарную награду.

Для настольной игры: агент видит позицию, выбирает легальный ход, бросаются кости, оппонент отвечает, цикл продолжается, пока кто-то не выиграет. Единственная обратная связь агента — исход партии: +1 за победу, -1 за поражение, возможно, промежуточные награды за промежуточные цели. Из тысяч или миллионов таких партий RL извлекает политику (какой ход играть в какой позиции), причём агенту никогда не сообщают, какой ход был правильным в каждой конкретной ситуации.

Пять ингредиентов

В каждой формулировке RL есть одни и те же пять компонент. Отображение их на настольную игру делает абстракцию конкретной:

Состояние (s). Полная информация, нужная, чтобы решить, что делать дальше. Для коротких нард: позиции всех 30 шашек (15 на сторону), чей ход, кости, состояние куба удвоения и счёт матча. Для длинных нард: то же плюс индикатор фазы (blocking / race / X-escaped / O-escaped) — хотя фазу можно вывести из позиций шашек, поэтому в чистом представлении состояния она избыточна.

Действие (a). Что агент может сделать из текущего состояния. Для ходов шашками: множество легальных последовательностей ходов при данных костях. Для действий с кубом: удвоить / не удваивать, принять / отказаться. Пространство действий велико для коротких нард (обычно 5–60 легальных последовательностей ходов на бросок, в зависимости от позиции и костей) — гораздо больше, чем ветвление на ход в шахматах.

Награда (r). Сигнал, который агент максимизирует. Стандарт для настольных игр: 0 во время партии, +1 при терминальной победе, -1 при терминальном поражении. Варианты могут быть богаче: +2 за марс (gammon), +3 за backgammon, с кубом удвоения как множителем. Длинные нарды используют 1/2/3 за обычную победу/марс/кокс. Выбор функции награды важен — агенты, обученные только с наградой за победу, не научатся играть на марс.

Политика (π). Функция, отображающая состояние в вероятности действий. То, что агент пытается выучить. Изначально случайная; в ходе обучения смещается в сторону лучших ходов. Многие RL-алгоритмы выдают детерминированную политику (всегда выбирать действие с наивысшей ожидаемой ценностью); другие — стохастические политики (сэмплировать из распределения действий).

Функция ценности (V или Q). Оценка того, насколько хорошо состояние — ожидаемая суммарная будущая награда из этого состояния при текущей политике. V(s) — ценность нахождения в состоянии s. Q(s, a) — ценность взятия действия a из состояния s. Большинство RL-алгоритмов работают, улучшая функцию ценности и используя её для вывода лучшей политики.

Почему игры с костями — хорошие цели для RL

Короткие нарды и длинные нарды обладают тремя свойствами, которые делают их особенно дружественными к reinforcement learning:

  1. Полная информация. Оба игрока видят всю доску, поэтому состояние можно зафиксировать чисто, без машинерии информационных множеств.
  2. Встроенная стохастичность. Кости обеспечивают естественное исследование. RL-агент, всегда выбирающий действие с наивысшей ценностью, редко исследовал бы альтернативы в детерминированных играх типа шахмат; в играх с костями одна и та же позиция никогда не повторяется идентично, потому что кости разные.
  3. Ограниченная длина эпизода. Большинство партий в короткие нарды заканчиваются в пределах 50–80 ply; длинные нарды аналогично. По сравнению с 200+ ply в Go или переменными горизонтами в no-limit покере это означает больше тренировочных партий на единицу вычислений.

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

TD-обучение и почему TD-Gammon важен

Самый влиятельный алгоритм в RL для настольных игр — temporal-difference (TD) обучение. Идея проста: на каждом шаге сравнивайте свою текущую оценку ценности с оценкой ценности на шаг вперёд (после того как взяли действие и увидели следующее состояние). Разница — TD-ошибка — это ваш обучающий сигнал. Вы сдвигаете V(s) в сторону V(s’) на маленькую величину.

В виде уравнения (обновление TD(0)):

V(s_t) ← V(s_t) + α [ r_{t+1} + γ V(s_{t+1}) − V(s_t) ]

α — это learning rate, γ — discount factor. Всё обновление локально — вам не нужен финальный исход партии, чтобы начать обучение, только следующее состояние и награда.

TD-Gammon Тезауро (1992) поставил 3-слойную нейросеть на место табличного V(s) и обучил её с TD(λ), используя почти чистый self-play. За несколько месяцев обучения (на железе, которое сейчас выглядит смехотворно медленным) она играла на уровне чемпионата мира. Две вещи были беспрецедентны:

  • Никаких партий экспертов. TD-Gammon учился из self-play, а не из базы партий мастерского уровня. Сравните с шахматными и Go-программами той эпохи, которые сильно опирались на дебютные книги и базы гроссмейстеров.
  • Сети открывали концепции. TD-Gammon нашёл стратегии прайминга, блитца и back-game, которые игроки-люди уже знали, и несколько таких, которых не знали. Его предпочтения повлияли на теорию коротких нард.

Современные движки (gnubg, eXtreme Gammon, Nardex) — прямые потомки. Архитектура больше, режимы обучения изощрённее, но центральная идея — TD-обучение поверх нейросетевой функции ценности, обученной из self-play, — та же линия.

Выбор действия: от ценностей к ходам

Обученная функция ценности V(s) напрямую не говорит вам, какой ход играть. Чтобы выбрать ход, обычно делают:

  1. Перечислить все легальные последовательности ходов при текущих костях.
  2. Для каждой последовательности симулировать получающуюся позицию s’.
  3. Оценить V(s’) обученной сетью.
  4. Выбрать ход, минимизирующий V(s’) с точки зрения оппонента (поскольку мы сделали свой ход и теперь его очередь — мы хотим оставить ему худшую позицию).

Это просто one-ply поиск. Движки типа gnubg-2-ply делают ещё один шаг: для каждого вашего кандидата они прокатывают все 21 комбинацию костей для оппонента и вычисляют V над лучшим ответом оппонента, усредняя. Это даёт лучшую оценку, но в 21 раз дороже.

Q-learning хранил бы V на уровне (state, action), пропуская явный поиск, — но для коротких нард это непрактично, потому что пространство действий слишком велико. Стандарт — это V(s) уровня состояния плюс поиск во время принятия решения.

Self-play как тренировочный движок

Self-play — это метод обучения, который сделал TD-Gammon знаменитым и который большинство современных систем по-прежнему использует. Постановка:

  1. Инициализировать сеть ценности случайно.
  2. Играть партии, где обе стороны используют текущую сеть для выбора действий (с некоторым шумом исследования).
  3. После каждой партии прогонять TD-обновление по траектории.
  4. Повторять для миллионов партий.

Агенту не нужен внешний оппонент. Он улучшается, играя против чуть улучшенных версий самого себя. Риск — сходимость к локальному оптимуму (стратегия, стабильная против самой себя, но эксплуатируемая другим оппонентом), но для коротких и длинных нард self-play стабильно даёт сильных агентов.

Распространённое уточнение — поддерживать историю прошлых версий и играть против сэмплированной смеси, а не только против текущей. Это предотвращает забывание агентом позиций, с которыми он раньше научился справляться.

Что выучивается, по-простому

Когда TD-сеть для коротких нард обучена, что она «знает»? Самый ясный тест — посмотреть на её предпочтения в хорошо понятых позициях:

  • Дебютные ходы. Обученная сеть выучивает стандартное ранжирование дебютов (24/13 split для 6-1, 13/11 7/2 для 5-2 и т. д.), причём ей никогда не говорили, что это хорошие ходы.
  • Прайминг. Она выучивает, что удержание структур типа 6-prime ценно, хотя «prime» нигде не определён в кодировании входов.
  • Pip-гонка. Она неявно выучивает считать пипы — когда контакт разорван, она стабильно предпочитает позиции стороны с меньшим пип-каунтом.

Для длинных нард похожее эмерджентное обучение происходит вокруг правила головы, запрета 6-в-ряд и марс/кокс-скоринга. Мы видели, как сети выучивают, что 6-prime в длинных нардах должен быть «escapable», прежде чем проявится структурная ценность, — они выучивают эффект правила, не получая правило в явном кодировании.

За пределами TD-обучения

Современный RL ушёл далеко за пределы чистого TD. Три направления, которые стоит знать:

  • Policy-gradient методы (REINFORCE, A2C, PPO) напрямую оптимизируют политику без явной функции ценности. Policy-сеть AlphaGo относится к этому семейству.
  • Actor-critic комбинирует policy-сеть (актора) с сетью ценности (критика), обновляя обе вместе. Это фундамент большинства современных систем для игр.
  • MCTS-augmented learning (AlphaZero) переплетает Монте-Карло поиск по дереву с нейросетевой оценкой, обучая сеть имитировать улучшенные MCTS политики. Это дало сверхчеловеческую игру в шахматах и Go.

Для коротких нард MCTS менее критичен из-за костей — пришлось бы сэмплировать по броскам костей в каждом узле, что экспоненциально раздувает дерево. Поэтому магистральные движки коротких нард держатся ближе к TD с поиском, ограниченным по ply.

Что дальше в этой серии

Это был фундаментальный primer. Следующие статьи покрывают более сложные вопросы:

Если вы хотите конкретный код, а не сначала теорию, API quickstart и analysis output reference покрывают разработческую поверхность, которую эта RL-машинерия питает.