Почему RL для стохастических игр сложнее, чем для детерминированных?

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

Делает ли случайность короткие нарды стратегически проще?

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

Как движки обрабатывают кости в поиске?

Два основных подхода. Ply-0 (только сеть) пропускает поиск по костям и доверяет функции ценности. Ply-2 перебирает все 21 комбинацию костей соперника, оценивает каждую и усредняет. Более глубокий поиск (3+) продолжает раскрывать деревья костей обеих сторон, но стоимость растёт быстро (~21× за каждый ply).

Почему движки коротких нард не используют Monte-Carlo Tree Search как в Го?

MCTS работает лучше всего, когда можно сэмплировать много линий без комбинаторного взрыва. С костями в каждом узле есть 21-стороннее ветвление случая, которое нужно либо раскрывать, либо сэмплировать, что раздувает дерево. Большинство движков коротких нард придерживаются ограниченного по глубине поиска с NN-оценкой в листьях; выигрыш MCTS над сетью+поиском недостаточен, чтобы оправдать сложность.

Стохастические игры и RL: как обрабатывать случайность в коротких и длинных нардах

2026-07-14

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

Узел случая

Стандартные диаграммы игровых деревьев имеют два типа внутренних узлов: max-узлы (ваш ход — вы выбираете ход, максимизирующий вашу ценность) и min-узлы (ход соперника — он выбирает ход, минимизирующий вашу). Для игр с костями нам нужен третий тип: узел случая.

Узел случая находится между решением одного игрока и решением следующего. Он представляет бросок костей. Ценность узла случая — это не максимум и не минимум по его потомкам, а математическое ожидание по ним, взвешенное по вероятности:

V(chance) = Σ_{dice} P(dice) × V(child(dice))

Для коротких нард кости дают 21 различную комбинацию (15 смешанных пар, каждая с вероятностью 2/36, плюс 6 дублей, каждый с 1/36). Для длинных нард применяются те же 21 комбинации.

Это единственное изменение разносится по всему. В уравнениях Беллмана теперь есть оператор математического ожидания. Градиенты протекают через стохастические переходы. Оценки на основе выборки несут собственную дисперсию даже при фиксированной политике.

Оценка математического ожидания по выборке

Чистое уравнение V(chance) = Σ P(dice) V(child) хорошо в теории, но имеет практическую проблему: V(child) для каждого исхода костей сам является ожиданием по будущей случайности. Рекурсивно ценность любого нетерминального состояния — это ожидание по всем возможным будущим траекториям, а перечислить их комбинаторно невозможно.

Обучение с подкреплением обходит это, заменяя точное ожидание оценкой по выборке. Бросьте кости, посмотрите, что получилось, обращайтесь с этой одной траекторией как с одним сэмплом Монте-Карло, усредняйте множество сэмплов. Это работает, но привносит дисперсию. Один и тот же алгоритм, обученный дважды с разными random seed, может сходиться к слегка разным функциям ценности, особенно при малом объёме данных.

Несколько техник снижают дисперсию:

Антитетический сэмплинг. Когда вы генерируете партии self-play, спаривайте каждую партию с такой, где броски костей инвертированы. У двух партий шум, как правило, гасит друг друга, поэтому объединённая траектория имеет более низкую дисперсию, чем две независимые партии.

Importance sampling. Когда вы оцениваете политику на данных, сгенерированных другой политикой, взвешивайте каждый сэмпл на отношение вероятностей. Полезно для off-policy обучения, где старые данные переиспользуются после обновления политики.

Eligibility traces (TD(λ) при λ > 0). Распределяйте атрибуцию награды на несколько шагов назад с экспоненциальным взвешиванием. Снижает дисперсию по сравнению с TD(0) ценой некоторого смещения.

TD-Gammon использовал TD(λ) с λ=0.7. Современные системы часто используют более высокие λ (0.9–1.0) или чистый Монте-Карло (λ=1.0), когда вычислительный бюджет на обучение позволяет.

Проблема атрибуции награды в играх с костями

Вот тонкий момент: когда стохастическая партия заканчивается, агент получает финальную награду (+1 или -1). Чтобы учиться, ему нужно отнести эту награду к конкретным решениям, принятым ранее в партии. Но в игре с костями исход частично зависит от удачи на костях — вы могли сыграть блестящий ход и всё равно проиграть, потому что соперник трижды подряд выбросил дубль.

Наивное распределение финальной награды пропорционально по всем ходам означает, что агент иногда «наказывает» хорошие ходы и поощряет плохие. С достаточным объёмом данных это смывается (закон больших чисел в итоге догоняет), но обучение замедляется.

Решения:

Equity-обратная связь во время партии. Вместо ожидания терминальной награды вычисляйте equity (ожидаемый исход из текущей позиции) на каждом шаге, используя базовую политику. Агент обновляется в сторону разностей equity, а не сырых исходов. По сути это то, что делает TD: V(s) — это оценка equity, а TD-ошибка — градиент equity.

Bootstrapping на сильных соперниках. Self-play может дрейфовать; добавление партий против фиксированного сильного соперника (или против многих сэмплированных прошлых версий) даёт более стабильный сигнал награды.

Длинные горизонты → терминальные награды. Контр-интуитивно, при очень длинных эпизодах сырые финальные награды становятся менее шумными, потому что дисперсия костей усредняется. Партии в коротких нардах имеют ~50–80 ply; этого достаточно мало, чтобы дисперсия одной партии была заметной.

Глубина поиска и стоимость ply

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

Для детерминированных игр вроде шахмат переход с глубины-1 на глубину-2 умножает стоимость поиска на средний фактор ветвления (~35 для шахмат). Для коротких нард стоимость умножается на 21 (кости) × ~20 (легальных ходов на бросок) = в среднем ~420 за ply. Так что:

ply-0: один прямой проход сети на каждый ход-кандидат. Доли миллисекунды на GPU.
ply-2: перебор 21 броска соперника и его лучшего ответа. ~50–200мс на позицию.
ply-3: ещё один бросок игрока + лучший ход. Сотни мс.
ply-4+: используется редко; стоимость приближается к секундам, а прирост equity мал по сравнению со стоимостью задержки.

Современные движки выбирают глубину под use case. Для real-time UI, показывающего лучшие ходы во время игры, ply-0 или ply-2 — практический потолок. Для глубокого анализа или rollout (Монте-Карло-симуляции многих партий из заданной позиции) обычны ply-3 или глубины rollout по 1296 (=6⁴).

Rollout: золотой стандарт оценки

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

Rollout затратны — K обычно 1296 или больше, каждая партия — 50–80 ply, каждый ply требует оценки сетью. Для одной позиции rollout на 1296 партий может занимать от секунд до минут в зависимости от железа.

Но rollout исключительно полезны:

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

В нашем пайплайне rollout — это то, как мы генерируем обучающие данные: random + self-play + экспертные позиции — все оцениваются rollout-ом, и исход rollout становится supervised-целью для следующего цикла обучения. Цикл — rollout → train → tournament → promote → reclassify, бесконечно повторяемый на одном GPU.

Стохастические игры и кости как исследование

У стохастичности есть положительный побочный эффект для RL: кости дают бесплатное исследование.

В детерминированных играх агент, всегда выбирающий действие с наивысшей ценностью, редко встречает необычные состояния. Чтобы узнать о них, приходится добавлять явный шум исследования — ε-greedy, dirichlet noise и т. п. Это бывает непросто настроить; слишком много шума тратит ёмкость, слишком мало — оставляет агента застрявшим в узких стратегиях.

В играх с костями одна и та же стартовая позиция к 5-му ходу даёт радикально разные состояния просто потому, что кости разные. Агент никогда не видит одну и ту же траекторию дважды. Исследование встроено в среду.

Отчасти поэтому TD-Gammon работал при таком скромном исследовании — кости делали ту работу по исследованию, которую в шахматах пришлось бы делать явному ε-greedy.

Длинные нарды и стохастичность

Длинные нарды разделяют всю стохастическую структуру коротких нард (те же кости, те же узлы случая, то же equity на основе ожидания). Они добавляют две сложности:

Фаза-зависимые функции ценности. Позиция может находиться в фазе blocking, race, X-escaped или O-escaped. Функция ценности резко различается между фазами — race-позиции доминируются pip-счётом, blocking-позиции — структурными приоритетами. Одна сеть может это выучить, но за счёт ёмкости. Мы используем phase-сегментированные сети: одна сеть на фазу, диспетчируется за O(1) по числу шашек на момент оценки.

Трёхуровневая система призов. Mars и koks — это разные состояния, а не просто умноженные финальные награды. Сеть должна научиться играть на эти состояния или избегать их за пределами простого исхода +1/-1. Выходы нашей сети — nested-ordinal вероятности (P(win), P(win ≥ mars), P(win ≥ koks)) — equity вычисляется из этого более богатого распределения.

Эти проектные решения вытекают из фреймворка стохастических игр — они не дополнения, а конкретные его инстанциации.

Куда это вписывается

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

Следующая статья этой серии, TD-Gammon to modern AI, прослеживает исторический путь того, как поле обращалось с этими компромиссами на протяжении 30+ лет.

Если хотите перейти сразу к коду: статья про обучающий пайплайн описывает наш реальный цикл rollout-train-tournament-promote с конкретными числами по уровням глубины и размерам rollout.