🎓 2-ply Expectimax поверх value-модели

О чём это

Наш первый модельный бот (house|oracle-1) оценивает позицию, но не смотрит вперёд — и потому играет на уровне greedy (~41.5% против aggressive, гейт ≥55% не пройден). Этот документ объясняет, что такое expectimax, почему в Dice Chess он устроен не как в обычных шахматах, во что обойдётся по времени (с замерами) и что конкретно нужно построить, чтобы пробить гейт. Читать можно по частям — первые три раздела концептуальные, дальше идёт инженерия.

Связанные заметки: Что такое LightGBM · 03 Идеи по улучшению алгоритмов · 01 Анализ Монте-Карло против Aggressive

---

1. Зачем это вообще нужно

Текущий OracleStrategy работает так: генерирует все свои легальные ходы под выпавшие кости, оценивает получившуюся позицию value-моделью и берёт ход с максимальной оценкой. Это поиск на 1 полуход (1-ply).

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

Слепота 1-ply: «съел — и не заметил, что срубят в ответ»

Бот видит, что может забрать ладью, оценивает позицию «+5 материала» и радостно ходит. Но он не смотрит, что следующим ходом соперник заберёт его ферзя. С точки зрения 1-ply обе позиции просто «оценка после моего хода» — рекапча в горизонт не попадает.

Именно поэтому 1-ply на материальной оценке ≡ greedy: оба максимизируют материал на один ход вперёд. Никакая, даже идеальная, статическая оценка этого не чинит — нужен просмотр вперёд (lookahead). Самый дешёвый полезный горизонт — 2 полухода: мой ход + лучший ответ соперника. Это и есть цель.

---

2. Что такое expectimax (с нуля)

Minimax — для игр без случайности

В шахматах дерево игры — это чередование:

• на моём узле я выбираю ход, максимизирующий мою оценку → узел MAX;
• на узле соперника он выбирает ход, минимизирующий мою оценку (максимизирует свою) → узел MIN.

Оценка позиции = «спускаемся до листьев, оцениваем, поднимаем обратно, на каждом уровне беря max или min». Это **minimax **.

Chance node — узел случайности

В Dice Chess перед каждым ходом бросают кости. Ход соперника зависит от того, что он выбросит, а этого я в момент своего хода не знаю. В дереве появляется третий тип узла — узел случайности (chance node): у него нет «выбирающего», есть распределение вероятностей по исходам броска.

Expectimax = minimax + узлы случайности

Значение узла случайности — это математическое ожидание (среднее по исходам, взвешенное вероятностями), а не max и не min:

$$V_{\text{chance}}=\sum _{r}P(r)\cdot V(r)$$

Алгоритм, где узлы бывают трёх типов (MAX / MIN / EXPECT), называется expectimax. Это стандартный инструмент для игр с костями/картами (нарды — канонический пример).

Почему именно матожидание, а не «худший случай»

Заманчиво считать, что соперник всегда выбросит самую опасную для нас кость (это был бы minimax по худшему броску). Но это пессимистично и неверно: ход, который «вешает» ферзя, наказуем, только если соперник выбросит кость нужного типа. Матожидание считает ровно вероятность быть наказанным — и это тот самый dice-специфичный сигнал, ради которого всё и затевается.

---

3. Дерево игры в Dice Chess

«2 полухода» в Dice Chess — это три уровня дерева, потому что между моим ходом и ходом соперника вклинивается бросок:

graph TD
    A["MAX — мой ход<br/>(мои кости известны)"] -->|"ход t₁"| C1
    A -->|"ход t₂"| C2
    A -->|"…top-K"| C3["…"]
    C1["EXPECT — бросок соперника<br/>(56 комбинаций, веса 1/3/6)"] -->|"бросок r, P(r)"| M1
    C1 -->|"…"| M2["…"]
    M1["MIN — ответ соперника<br/>(его лучший ход под бросок r)"] -->|"ход u"| L1["Лист:<br/>value-модель<br/>на позиции после endTurn"]
    C2["EXPECT — бросок соперника"] --> M3["MIN"] --> L2["Лист: value-модель"]

Формально, если $V$ — оценка с моей точки зрения, а $\text{eval}$ — dice-free value-модель на позиции-листе:

$$\text{best}=\underset{t\in T(s,r_0)}{\max }\underset{Q(s,t)=\text{ценность моего хода }t}{\underbrace{\sum _{r}P(r)\underset{u\in T(s_t^{\prime },r)}{\min }\text{eval}(s_t^{\prime }\cdot u)}}$$

где:

• $r_0$ — мои кости в корне (известны, поэтому там нет узла случайности — важная деталь для стоимости, см. далее);
• $s_t^{\prime }=\text{endTurn}(s\cdot t)$ — позиция после моего хода $t$: ходит соперник, кости очищены;
• $r$ пробегает 56 комбинаций костей соперника с вероятностями $P(r)=w(r)/216$, где вес $w(r)\in \{1,3,6\}$ ( таблица уже посчитана в KingCaptureProbability.weightedRolls);
• соперник выбирает $u$, минимизируя мою оценку;
• терминалы: если мой $t$ рубит короля → $Q=+\infty$ (TerminalWinScore); если ответ соперника рубит моего короля → этот лист $=-\infty$.

Почему лист — именно dice-free модель

Лист — это позиция после endTurn(), где кости уже очищены. Наша dice-free модель обучалась ровно на таких позициях (только материал, без костей) — то есть train/serve совпадают. Кости живут явно в узле случайности над листом, а не внутри оценки. См. про две модели в Что такое LightGBM.

---

4. Почему «в лоб» нельзя: замеры ветвления

Число легальных ходов-путей в Dice Chess огромно. Я прогнал TurnGenerator.generateAllLegalTurnPaths по всем 56 комбинациям костей на двух позициях:

Позиция	min	медиана	среднее	max
стартовая	0	4	200	3376
миттельшпиль	8	423	817	4728

Распределение сильно скошено: медиана много меньше среднего (несколько «жирных» бросков дают тысячи путей). Для миттельшпиля типичное ветвление — сотни ходов.

Наивный полный expectimax:

$$N_{\text{мои}}\times 56\times N_{\text{опп}}\approx 800\times 56\times 800\approx 36\text{млн листьев на один ход}$$

Это часы на один ход — нежизнеспособно.

---

5. Три рычага, которые делают это реальным

1. В корне мои кости известны → там один бросок, а не 56. Узел случайности есть только у соперника (одно «×56», не два).
2. Top-K отсечение моих ходов. Пред-ранжировать мои ~800 ходов дешёвым 1-ply (материал или сама модель) и разворачивать вглубь только топ K≈8–12. Это убирает главный множитель. Тот же приём уже применяется в MonteCarloSearch (MaxCandidates = 16) и предлагался для MCTS в 03 Идеи по улучшению алгоритмов (раздел 1).
3. Батчинг ONNX. Сейчас onnxEval делает один session.run на позицию. Если собрать все листья узла в один тензор $[B\times 7]$ и прогнать разом — крошечная 5-деревьевая регрессия жуёт сотни тысяч строк за ~100 мс, а per-call JNI-оверхед исчезает.

С этими рычагами реальная цена на ход:

• генерация ответов соперника: $K\times 56$ вызовов generateAllLegalTurnPaths (по одному броску, ~50–100 мкс каждый) ≈ 50–80 мс;
• батч-оценка листьев ≈ ~100 мс;
• итого ~150–250 мс/ход.

Этого хватает и для Арены (400 партий ≈ 20–30 мин), и с большим запасом для лобби (Unlimited = 120 с/ход).

Узел случайности не отсекается

В отличие от moves, chance node — это ожидание, его нельзя «обрезать» без смещения оценки. Но там всего 56 взвешенных исходов, и таблица готова. При желании можно семплировать подмножество (Monte-Carlo expectimax) — но 56 достаточно дёшевы, чтобы брать их точно. Ср. раздел 3 в 03 Идеи по улучшению алгоритмов.

---

6. Что переиспользуем, что писать

Инфраструктура почти вся уже есть в движке:

Уже есть	Роль в expectimax
SearchScoring.scorePath(state, path, evalFn)	точка врезки: leaf evalFn заменяется на рекурсивную expectimax-оценку
KingCaptureProbability.weightedRolls	готовая таблица 56 взвешенных бросков (1/3/6, Σ=216) = узел случайности
TurnGenerator.generateAllLegalTurnPaths	ходы соперника на каждый бросок
Evaluator.evaluateMaterial	дешёвый порядок для top-M ответов соперника
state.withDicePool / .endTurn() / TerminalWinScore	механика костей и терминалов
MonteCarloSearch	живой образец стохастического поиска в этом же дереве

Новое (объём — примерно день работы, сложность средняя):

1. Сделать weightedRolls публичной (вынести в отдельный DiceRolls) — тривиально.
2. onnxEvalBatch(states): Array[Int] на OnnxEvalSearch — тензор $[B\times 7]$, парс $[B\times 1]$. Мелко-средне.
3. ExpectimaxOnnxSearch (jvm-only, как OnnxEvalSearch): рекурсия MAX→EXPECT→MIN с top-K/top-M и материальным порядком. Аккуратно с: перспективой (соперник минимизирует мою оценку), терминалами на обоих плаях, пасами (пустой список ходов → соперник пасует, сторона снова флипается). Ядро ~100–150 строк.
4. Гард по времени: реализовать контракт TimeBudgetedSearch (он уже есть) — из-за хвоста ветвления (max 4728!) нужен per-move дедлайн, иначе патологический бросок раздует один ход.
5. Тесты: позиция «не вешай ферзя», где 1-ply ошибается, а 2-ply нет (регресс-тест на саму слепоту); симметрия; терминалы.
6. Арена vs aggressive/greedy + замер мс/ход.

---

7. Ожидаемая отдача и риски

• Прогноз силы. 1-ply материал = greedy ≈ 41.5%. 2-ply чинит слепоту к рекапче — против aggressive (тоже без просмотра вперёд) просмотр на 1 плай при равной оценке обычно даёт явный скачок. Ожидаю ~55–65%, гейт скорее пройдёт — но не гарантирую: стохастика разбавляет ценность просмотра (смягчается тем, что берём матожидание, а не худший бросок).
• Риск train/serve. Лист обязан быть dice-free моделью на позиции после endTurn() — ровно то, на чём модель обучалась. Уже так, менять не нужно.
• Хвост ветвления. max доходит до 4728 путей на бросок — без per-move дедлайна один ход может «взорваться». Отсюда обязательность пункта 4.
• Дешёвый параллельный эксперимент (не замена, а быстрая проверка перед стройкой): 1-ply в корне на * dice-conditioned* модели (обучена на позиция+кости, ~62.6%) — почти бесплатно, но лукахеда не даёт и слепоту к рекапче не лечит. Полезно как замер; основной рычаг под гейт — всё же 2-ply.

---

8. Следующие шаги

1. Изучить этот документ (можно не спеша).
2. Завести issue в dicechess-engine-scala с планом из раздела 6, разложенным на PR-шаги: DiceRolls (публичная таблица) → onnxEvalBatch → ExpectimaxOnnxSearch + тесты → арена-замер.
3. Реализовать, прогнать арену, сравнить с гейтом.
4. Если проходит — обучить oracle-2 на этой основе и выкатить в лобби (паттерн из 00 Bots — Overview / приватного репо house-bots).

Как это ложится в общую картину

Это первый шаг к «AlphaZero-подобной» связке «оценка + поиск»: слабая оценка с поиском бьёт сильную оценку без поиска. Следующий естественный уровень — MCTS с той же value-моделью вместо роллаутов (см. идеи в 03 Идеи по улучшению алгоритмов), но 2-ply expectimax — самый дешёвый способ проверить гипотезу и пробить гейт.