Dice Chess Wiki

Оптимизация KingCaptureProbability

5 min read

Оптимизация KingCaptureProbability

Путевая заметка о том, как мы ускоряли KingCaptureProbability (KCP) — горячий путь Monte-Carlo-оценщика. Здесь зафиксировано что отгрузили, что попробовали и откатили, и — главное — почему. Самая ценная часть — отрицательный результат: дисциплина «сначала замерь, потом отгружай» один раз уже спасла нас от регрессии, которая выглядела как очевидное улучшение.

TL;DR

1A + 1B дали честные ~1.7× (точно, bit-for-bit). Вариант A («доска без mailbox») был корректен, но медленнее — откатан. Урок: mailbox — это не лишняя память, а O(1)-индекс поиска фигуры; убрав его, мы заставили код сканировать битборды и потеряли больше, чем сэкономили.

Почему KCP — это горячий путь

KCP отвечает на один вопрос: «с какой вероятностью соперник в свой следующий ход срубит нашего короля (или ферзя)?». Он перебирает все 216 исходов трёх кубиков (сгруппированных в 56 взвешенных мультисетов) и для каждого делает DFS по микроходам — есть ли путь к взятию цели.

Ключевой факт: MonteCarloEquity.singleRollout зовёт kingCaptureProbability на каждом полуходе каждого роллаута. Это и есть аналитический член Рао-Блэквеллизации (см. 🎓 Rao-Blackwellized Monte-Carlo):

Каждое — это один вызов KCP. На один роллаут их maxPlies штук, на оценку — сотни роллаутов. Отсюда вывод: ускорение KCP пропорционально превращается в больше роллаутов за тот же бюджет времени, то есть в более сильного бота и более узкий доверительный интервал.

Сюрприз бенчмарка

На мидгейме (позиция kiwipete) KCP стоил миллисекунды, а не микросекунды (король ~7 мс до оптимизации). Именно это объясняло, почему Monte-Carlo-бот «висел» на дебюте, пока ему не дали тайм-бюджет.

Как мерили

Всё через JMH (mise run bench:quick), отдельный бенчмарк KingCaptureProbabilityBenchmark с @Param по позициям (initial / kiwipete / endgame) × защитник (white / black). Аллокации — через -prof gc. Правило для движка действует жёстко: изменение горячего пути не уходит в main без A/B-замера (см. тесты для корректности и JMH — для скорости).

Что отгрузили (1A + 1B, точно и замерено)

ШагИдеяЗамер (чистый A/B)Корректность
1AВынести расчёт KCP для нулевого полухода из цикла роллаутов — он одинаков для всех роллаутов одной оценки, считаем один раз.меньше повторных вызовов на оценкуgolden bit-for-bit
1BВ captureDFS кодировать оставшийся пул кубиков прямо в int-битах GameFlags (withDiceSlotsOf), без аллокации List/Option на каждый узел DFS.король 6945 → 4344 µs, ферзь 5964 → 3468 µs (≈1.6×)дифф-корпус, tol 1e-12

Совокупно ~1.7×, оба точные (числа не «примерно те же», а бит-в-бит совпадают с эталоном, снятым на pristine-коде). Король считается ровно как ; для ферзя сохраняем документированный лёгкий оверэстимейт (правило максимальной длины микроходов) — намеренно.

Что попробовали и ОТКАТИЛИ — и почему это ценно

Вариант A: makeMove без mailbox. Гипотеза была красивой: профиль показывал ~50 МБ аллокаций на вызов, и казалось, что доминирует клон 64-клеточного массива mailbox, который makeMove копирует на каждом шаге DFS. Идея — не копировать его вообще, а тип фигуры брать прямо из битбордов (pieceAt).

Сделали. Корректно — property-тест подтвердил, что новый путь бит-в-бит эквивалентен настоящему makeMove на всех ветках (тихие ходы, взятия, двойной шаг пешки, взятие на проходе, рокировка, превращение). И всё равно откатили, потому что замер показал регрессию:

Версияkiwipete, µs/op
post-1B (с mailbox)~4100
вариант A (без mailbox)~5400

Урок: mailbox — это не балласт, а O(1)-индекс

mailbox хранит «какая фигура на клетке X» за одно обращение по индексу. Убрав его, мы заставили pieceAt сканировать битборды (~3 раза на узел DFS), чтобы узнать тип фигуры. Этот скан по CPU дороже, чем сэкономленный arraycopy 64 интов. Корректно ≠ быстрее.

И вторая половина урока — где на самом деле те 50 МБ: в них доминируют не клоны mailbox, а копии неизменяемого GameState и List[Move], который generateMoves аллоцирует на каждом узле. То есть гипотеза «виноват mailbox» была опровергнута замером — ровно для этого замер и нужен.

Мораль

  1. Сначала замерь, потом отгружай. Изменение, которое «очевидно быстрее», оказалось медленнее. Без JMH-гейта оно бы уехало в main и тихо замедлило бота.
  2. Профилируй, а не угадывай, что доминирует. «50 МБ» ≠ «виноват mailbox». Аллокации сидели в GameState-копиях и List[Move].
  3. Корректность и скорость — две независимые проверки. Вариант A прошёл property-тест и всё равно был отброшен. Одно не заменяет другое.
  4. Отрицательный результат — это знание. Теперь мы знаем, что mailbox оставлять, а атаковать надо GameState-копии и List[Move].

Что дальше (не сделано, осознанно)

Настоящий выигрыш требует сохранить O(1)-поиск и убрать копирование одновременно. Это уже не быстрый шаг, а рефактор:

  • Вариант B — мутабельная scratch-доска make/undo. mailbox мутируется на месте и откатывается, а не клонируется → O(1)-индекс сохранён И клон убран. Требует property-теста инварианта undo ∘ make = id.
  • Либо убрать List[Move] из generateMoves на горячем пути (трогает MoveGenerator).

Оба варианта оправданы только если выигрыш перевесит сложность и риск. Поскольку 1A + 1B уже дали ~1.7×, на этой точке мы сознательно остановились.

Также отвергнуто (проверкой, не вкусом)

  • Прунинг 56 мультисетов по «лучу-надмножеству». Ложно для паттернов AAB/AAA: гнутые пути слайдера (напр., ферзь b1 → c3 через b3) дают недосчёт. Ни один существующий тест это не ловит — поэтому не трогаем.
  • Транспозиционный кэш для plies ≥ 1. Hit-rate ≈ 0 на случайных блужданиях роллаута.
  • Параллелизм внутри одного вызова. Накладные расходы съедают выигрыш на микросекундных задачах. Параллелить роллауты (уровнем выше) — возможно, но это JVM-only и только после оптимизации аллокаций.

Следы в коде и трекере

Исходник: shared/.../search/KingCaptureProbability.scala, MonteCarloEquity.scala, domain/GameFlags.scala (репозиторий dicechess-engine-scala). Эпик #385; 1A — #386, 1B — #388; вариант A и разбор — #391. 1A + 1B влиты в main.

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

Graph View