🎓 Rao-Blackwellized Monte-Carlo

Это математика оценщика вероятности, который используется в Position Equity — оценка вероятности, когда сыгранных партий мало. Исходник — MonteCarloEquity.scala в dicechess-engine-scala (Scala 3, кросс-компилируется в WASM и исполняется в браузере).

---

Что такое один rollout

Rollout — это одна смоделированная партия от текущей позиции до развязки, которую прогоняет движок. Это не реальная сыгранная партия и не один бросок кубиков. Движок из позиции многократно «бросает» 3 кубика, доигрывает вперёд (до maxPlies полуходов) и фиксирует, кто захватил короля.

Цифра «64 rollouts» на панели означает, что текущая оценка усреднена по 64 таким доигровкам (первый батч); дальше счётчик растёт 64 → 128 → … к цели, а доверительный интервал сужается.

---

Rao-Blackwellization: почему «64» достаточно

Наивный Monte-Carlo на каждом rollout получил бы бинарный исход (0 или 1) и усреднял бы их — высокая дисперсия. Наш оценщик вместо этого аналитически интегрирует на каждом полуходе точную вероятность взятия короля по всем 216 комбинациям трёх кубиков (KingCaptureProbability):

survive = 1
для каждого полухода (ходит сторона S):
    p = P(S берёт короля соперника этим броском)   # точно, по всем 216 броскам
    winsOf(S) += survive * p                        # вклад победы — аналитический, не 0/1
    survive   *= (1 - p)                             # масса «дожили дальше»
    перейти в случайное выжившее продолжение         # сэмплируется ход БЕЗ взятия короля

То есть вероятность победы стороны $S$ — это сумма по её полуходам произведения «дожили до сюда» на «берём короля здесь»:

$$P(S\text{ wins})=\sum _{t:S\text{ ходит}}({\prod }_{u<t}(1-p_u))p_t,p_t=\frac{{\text{бросков-со-взятием}}_t}{216}$$

Остаточная масса выживания на горизонте maxPlies → undecided. Три величины whiteWin + blackWin + undecided = 1.

Так как победная масса добавляется аналитически (это и есть Рао-Блэквеллизация), а не как сэмпл Бернулли, дисперсия на один rollout во много раз меньше. Оценщик сам это измеряет:

$$\text{VarianceReduction}=\frac{\bar{p}(1-\bar{p})}{s^2}$$

— во сколько раз дисперсия меньше, чем у наивного 0/1 MC с тем же средним. Значения $>1$ — выигрыш; $+\infty$ — оценка точная (позиция решается на первом броске).

---

Стандартная ошибка и сходимость

Стандартная ошибка оценки White-win:

$$\text{SE}=\sqrt{\frac{s^2}{n}},{\text{CI}}_{95\%}=\hat{p}\pm 1.96\cdot \text{SE}$$

CI сужается как $1/\sqrt{n}$: чтобы уполовинить ошибку, нужно в 4 раза больше rollouts. Дисперсия $s^2$ считается онлайн по алгоритму Уэлфорда (один проход, без хранения всех значений).

rollouts	типичный CI (для $p\approx 0.5$)
64	широкий (≈ ±12 п.п.) — «Low confidence»
~250	≈ ±5 п.п. — обычно уже показываем вердикт
4000	≈ ±1.5 п.п. — уверенно

Поэтому в UI вердикт по кубу показывается только когда ширина CI ≤ MC_VERDICT_MAX_CI_WIDTH (0.1).

---

Пулинг батчей (на стороне клиента)

Движковый estimateEquity — одноразовый: каждый вызов делает фиксированное число rollouts с нуля. Чтобы уточнять прогрессивно без пересчёта, Web Worker зовёт его батчами по 64 (меняя seed) и пулит результаты в pool.ts. Каждый батч — i.i.d. выборка той же позиции, поэтому объединение точное.

Объединённое среднее по всем $N={\sum }_i{n}_i$ rollouts:

$$\bar{p}=\frac{{\sum }_i{n}_i{\hat{p}}_i}{{\sum }_i{n}_i}$$

Объединённая дисперсия — через закон полной дисперсии (внутригрупповая + межгрупповая суммы квадратов):

$$s^2=\frac{\stackrel{\text{within}}{\overbrace{\sum _i(n_i-1)s_i^2}}+\stackrel{\text{between}}{\overbrace{\sum _i{n}_i({\hat{p}}_i-\bar{p}{)}^2}}}{N-1},\text{SE}=\sqrt{\frac{s^2}{N}}$$

где $s_i^2={\text{SE}}_i^2\cdot n_i$ — восстановленная по-rollout-ная дисперсия батча $i$. Так оценка тикает 64 → 128 → …, а CI монотонно стягивается.

---

Отличие от C++-референса

Эта Scala-версия — порт C++-движка (rabestro/dice-chess-engine), но с одним отличием. Референс продвигает rollout в любой сэмплированный ход, включая взятие короля; взятие терминально, поэтому за ним получается доска без короля, по которой (некорректно) играют дальше — второпорядковое смещение. Будучи источником истины по правилам, наш оценщик обусловливает продолжение на выживании: продвигается только через ходы без взятия короля (событие с вероятностью $1-p$, которое уже учтено в survive). Аналитические по-полуходные члены — и значит самопроверка дисперсии — при этом не меняются.

---

Параметры

Параметр	По умолчанию (движок)	В UI	Смысл
rollouts	500	64 на вызов (батч)	жёсткий лимит rollouts
maxPlies	1000	60	горизонт одного rollout
targetError	0.0 (выкл)	—	адаптивная остановка по достижению SE
minRollouts	128	—	минимум до адаптивной остановки
SurvivalEpsilon	1e-5	—	масса выживания, ниже которой rollout считается решённым
MaxRollRetries	64	—	попыток найти бросок с выжившим продолжением

Детерминизм

При фиксированном rollouts/targetError и seed оценка воспроизводима. Путь с дедлайном (для тайм-бюджетного бота) — недетерминированный (зависит от скорости машины), поэтому для тестов не используется.

Связанные заметки

• Position Equity — оценка вероятности — где и как это показывается в UI.
• WebAssembly — почему движок исполняется как WASM в браузере.