🎲 Оптимизация пула кубиков: zero-allocation в LegalMovesFilter и TurnGenerator

Путевая заметка об устранении аллокаций в куче (heap allocations) на критических путях движка: валидации максимальной длины хода (LegalMovesFilter) и исчерпывающей генерации путей полного хода (TurnGenerator).

Рефакторинг решил задачу #275 и был отгружен в PR #626.

TL;DR

Замена операций над стандартным List[Int] (diff, contains, isEmpty, withDicePool) на побитовую арифметику в 32-битном opaque-типе GameFlags дала чистый прирост в 1.4× – 2.05× по времени выполнения и сняла нагрузку с GC на всех горячих путях поиска и валидации.

---

🔍 В чём была проблема

В Dice Chess каждый ход состоит из броска до 3 кубиков и цепочки из 1–3 микроходов. По Правилу максимальной длины серии (Maximum Micro-moves Rule):

• Игрок обязан выбрать ход, являющийся частью самой длинной достижимой последовательности микроходов из доступных кубиков.
• Исключение: взятие короля соперника (мат/победа) легально при любой длине.

Для вычисления легальных ходов LegalMovesFilter рекурсивно исследует дерево микроходов. Аналогично, TurnGenerator выполняет DFS для генерации всех полных серий ходов для ботов и UI.

Бутылочное горлышко: аллокации List[Int]

Метаданные состояния (GameState) упакованы в 29-битный Int (GameFlags): активный цвет, права на рокировку, маска битых полей на проходе (en passant), счётчик полуходов и 3 слота под значения кубиков (по 3 бита на слот).

Однако на горячем пути в LegalMovesFilter и TurnGenerator код регулярно вызывал:

// До оптимизации:
val pool = state.dicePool // Аллокация List[Int] через List.newBuilder
 
if pool.contains(PieceType.King.diceValue) && pool.contains(PieceType.Rook.diceValue) then
  val afterCastle = pool.diff(List(6, 4)) // Аллокация двух списков + результат diff
  val next = state.makeMove(move).withDicePool(afterCastle) // Распаковка списка обратно в биты
 
val afterMove = pool.diff(List(moverType.diceValue)) // Аллокация списка при КАЖДОМ микроходе
val next = state.makeMove(move).withDicePool(afterMove)

На каждом узле рекурсивного дерева создавались промежуточные объекты List, вызывался diff (создающий новые списки) и выполнялись лишние преобразования List ↔ Int. В глубоких позициях (например, kiwipete с тысячами путей) это создавало гигантское давление на сборщик мусора (GC pressure).

---

💡 Решение: побитовые операции над GameFlags

В GameFlags уже была реализована битовая раскладка слотов кубиков (биты 13–21):

• Бит 13–15 (3 бита): Слот кубика #1 (0 = пуст, 1–6 = грань)
• Бит 16–18 (3 бита): Слот кубика #2
• Бит 19–21 (3 бита): Слот кубика #3

Ранее в рамках оптимизации KingCaptureProbability (KCP) для GameFlags были добавлены быстрые inline-методы:

• isDicePoolEmpty: Boolean — быстрая маска (flags & 0x1FE000) == 0.
• containsDie(die: Int): Boolean — сравнение со слотами без массивов и списков.
• removeDie(die: Int): GameFlags — очистка первого найденного слота через побитовое AND NOT.
• withDiceSlotsOf(src: GameFlags): GameFlags — копирование только битов кубиков из одного GameFlags в другой за 2 побитовые операции (AND/OR).

Что изменили в коде:

1. Models.scala: Добавили удобный inline-хелпер на GameState:

   inline def withDiceSlotsOf(src: GameFlags): GameState =
     copy(flags = flags.withDiceSlotsOf(src))

2. LegalMovesFilter.scala: Заменили все аллокации списков в maxSequenceLength и filterMaximalMoves:

   // Рокировка (расходует кубики Короля 6 и Ладьи 4):
   if state.flags.containsDie(6) && state.flags.containsDie(4) then
     val survived = state.flags.removeDie(6).removeDie(4)
     val next     = state.makeMove(move).withDiceSlotsOf(survived)
     val depth    = 2 + maxSequenceLength(next)
     if depth > best then best = depth
    
   // Обычный ход:
   val survived = state.flags.removeDie(moverType.diceValue)
   val next     = state.makeMove(move).withDiceSlotsOf(survived)
   val depth    = 1 + maxSequenceLength(next)
   if depth > best then best = depth

3. TurnGenerator.scala:

   • Убрали передачу параметра pool: List[Int] по всей цепочке методов (generatePathsSinglePass, processMove, handleCastling, handleNormalMove).
   • Заменили проверку уменьшения размера списка на прямую проверку наличия кубика:

   val dieValue = moverType.diceValue
   require(
     state.flags.containsDie(dieValue),
     s"CRITICAL: Dice pool ${state.dicePool} does not contain die $dieValue!"
   )
   val survived = state.flags.removeDie(dieValue)
   val next     = state.makeMove(move).withDiceSlotsOf(survived)

---

📊 Результаты замеров (JMH Benchmarks)

Замеры проводились на JDK 26 (Apple Silicon, macOS) с конфигурацией -wi 3 -i 5 -f 1.

1. LegalMovesFilterBenchmark.filterMaximalMoves (Average Time — меньше = лучше)

Кубики	Позиция	До (main)	После (#275)	Ускорение	Сокращение времени
1,2,3	initial	63.79 µs	36.49 µs	1.75×	-42.8%
1,2,3	kiwipete	795.50 µs	469.16 µs	1.70×	-41.0%
1,2,3	endgame	1.31 µs	0.79 µs	1.66×	-39.7%
1,2,3	castling	3.65 µs	2.08 µs	1.76×	-43.2%
1,2,3	promotion	2.75 µs	1.39 µs	1.98×	-49.4%
4,5,6	kiwipete	96.06 µs	54.92 µs	1.75×	-42.8%
4,5,6	castling	5.87 µs	3.06 µs	1.92×	-47.9%
1,1,1	initial	364.06 µs	237.91 µs	1.53×	-34.7%
1,1,1	castling	379.67 µs	225.89 µs	1.68×	-40.5%
6,4,2	kiwipete	109.56 µs	59.00 µs	1.86×	-46.2%
6,4,2	castling	5.75 µs	2.80 µs	2.05×	-51.3%

2. TurnGeneratorBenchmark.forEachLegalTurnPath (Average Time — меньше = лучше)

Пул кубиков	Позиция	До (main)	После (#275)	Ускорение	Сокращение времени
1,2	initial	9.67 µs	6.03 µs	1.60×	-37.6%
1,2	kiwipete	14.74 µs	9.59 µs	1.54×	-35.0%
1,2,3	initial	41.03 µs	25.44 µs	1.61×	-38.0%
1,2,3	kiwipete	510.82 µs	350.05 µs	1.46×	-31.5%
1,2,3	castling	2.03 µs	1.21 µs	1.68×	-40.3%
1,2,3	promotion	1.50 µs	0.86 µs	1.74×	-42.5%

---

🎯 Влияние на экосистему

Кому и как помогла эта оптимизация:

1. Expectimax и 2-ply ONNX-боты (oracle-2, oracle-3, ExpectimaxSearch): В Expectimax на каждом полуходе перебираются 56 исходов кубиков и генерируются ответы соперника через TurnGenerator. За один ход бота TurnGenerator вызывается сотни раз. Ускорение на 30–40% позволяет боту анализировать заметно больше вариантов за фиксированный тайм-бюджет.

2. Monte-Carlo бот (MonteCarloSearch / MonteCarloEquity): В случайных роллаутах на каждом полуходе вызывается TurnGenerator. Увеличение пропускной способности напрямую транслируется в большее число симуляций и более высокую силу игры.

3. Web UI (dicechess-analytics-ui / Scala.js & Wasm): При каждом клике пользователя по фигуре вызывается LegalMovesFilter.filterMaximalMoves для подсветки легальных ходов. Двукратное ускорение делает интерфейс максимально отзывчивым даже на мобильных устройствах.

---

🧠 Выводы и уроки

1. Не конструируйте коллекции на горячем пути. Даже маленький List(die) или вызов .diff в рекурсии глубиной 3 с ветвлением порождает миллионы короткоживущих объектов в секунду, перегружая GC.
2. Используйте битовую упаковку до конца. Если состояние уже упаковано в 32-битный Int (GameFlags), все манипуляции с ним должны оставаться внутри этого Int, не распаковываясь в высокоуровневые структуры до самого выхода наружу (к FEN или JSON).
3. Строгий A/B-бенчмаркинг обязателен. Измерение до и после изменений гарантирует отсутствие регрессий и даёт точные цифры для документации и релиз-ноутов.