Feat(perfect-db): Integrate Malom PerfectDB 3v3 flying endgame sector into Rust/TGF search

[calcitem]

Summary

Add exact endgame play to Sanmill's Rust/TGF engine by integrating the Malom
Perfect Database (Gévay & Danner), beginning with a single embedded sector for
the 3v3 flying endgame (std_3_3_0_0.sec2, ~616 KB). The reader can be ported
from the C++ PerfectDB that already exists on the master branch
(src/perfect/). Board symmetry is handled internally by the DB's hashing, so it
comes "for free" with this integration.

This issue also documents a careful study of the NMM_LLM project, because that
project independently demonstrated the value of an exact 3v3 table and several
other ideas worth discussing openly. The analysis below is meant as a constructive
comparison of two legitimate design points, not a judgement of either.

---

Background: a deep look at NMM_LLM's approach

NMM_LLM is a well-engineered, ~25k-line Python Nine Men's Morris engine with a
web GUI, a learning layer, and an LLM commentary layer. Reading its code and its
excellent AI_INTERNALS.md was genuinely instructive. The points below are an
honest assessment of what it does and how it maps (or does not map) onto Sanmill's
constraints.

1. A complete, textbook search stack

ai/game_ai.py implements essentially the full modern alpha-beta toolkit:
negamax + alpha-beta, iterative deepening with time budgets, a Zobrist
transposition table with depth-preferred replacement, two killer moves per ply, a
history heuristic (depth² increments), PVS/NegaScout, Late Move Reductions (last
~60% of moves at depth ≥ 4, with captures and opponent-mill-blocking squares
excluded from reduction), aspiration windows, quiescence search over captures, and
selective search extensions (own mill threat or opponent fork → +1 ply). It also
probes its endgame table and a learned full-game DB from inside the search.

This is a clean, complete implementation and a good reference for what a full
stack looks like. Importantly for Sanmill, though, some of these techniques are
not universally beneficial — see "Lessons already learned" below.

2. A large, knowledge-rich static evaluator

The standout characteristic is ai/heuristics.py: ~2,784 lines. evaluate()
computes on the order of 40 features per leaf (each typically once per side):
closed mills, blocked pieces, two-configs, double-mill pivots, mobility, mill
threats, positional/cross-node value, cycling-mill setups, fork threats,
encirclement/herding, near-blocked "squeeze" pressure, mill-wrapping, fly
asymmetry, open-mill domination, sealed two-configs, assembly gradients (step
1–4), one-config approach, locked-mill penalties, interpose/perp-block,
convergence clusters (with bipartite matching), and more — all phase-weighted
(place/move/fly). On top of that, tactical_move_bonus() adds ~30 root-only move
bonuses, and _placement_chain_scan() performs a 4-ply forward scan inside the
evaluation path.

This is impressive domain knowledge, and in NMM_LLM's context it is a reasonable
choice:

• The engine targets a human-facing teaching/UX experience. The same features that
  drive the score also serve as explanations ("this move sets up a cycling
  mill", surfaced via the bonus breakdown and the LLM layer). A rich evaluator is
  partly a narration layer, not only a strength layer.
• Python's node throughput is comparatively low, so the marginal search depth
  bought by a leaner evaluator is smaller; investing in per-node knowledge is a
  rational trade at that throughput.

It is worth noting transparently that the git history (B-1 … B-64) shows this
path carries a real maintenance cost: a number of commits fix interactions
between heuristics (e.g. capping fly-phase mobility so fly-entry doesn't score
negatively; restoring a convergence term when a mill closes; detecting
"cycling-capture self-unblock"). The authors handled these carefully — the point
is simply that a large evaluator has a large surface area of subtle interactions.

3. An exact 3v3 retrograde endgame table (the most transferable idea)

ai/endgame_solved_db.py + tools/build_endgame_db.py retrograde-solve all
3v3 flying positions into an exact WDL table. The engineering is tidy:

• Combinatorial number system encoding: C(24,3) × C(21,3) × 2 = 5,383,840
  positions, packed at 2 bits/slot → ~1.3 MB total.
• D4 dihedral symmetry reduces the solve to ~1/8 of positions (canonical
  bitmask-minimum class), with a final fill pass so runtime lookups need no
  canonicalization.
• The table is probed inside negamax and returns an exact ±(INF − depth).

This validated, for us, that an exact 3v3 verdict is high-leverage and cleanly
separable. Sanmill can take the idea and go one step further by using the
already-solved Malom database rather than self-solving (details below).

4. Reusable D4 symmetry engineering

ai/board_symmetry.py provides canonicalization + inverse-transform helpers
(canonical_board_str, canonical_sequence, SYM_INVERSE) shared across the
endgame table, the trajectory DB, and the opening book — a clean "store canonical,
query 8 equivalents, inverse-transform the move back" pattern. This is a good
template for any persisted book/learning data.

5. Learning subsystems and opening variety

TrajectoryDB indexes games by move-prefix and nudges scores by win/loss deltas
(with a hard-ban sentinel for user-flagged blunders); FullGameDB stores learned
outcomes; OpeningBook.select_opening() uses UCB1 with temperature-weighted
sampling for opening variety. These are primarily UX / human-engagement
features (variety, adaptivity, teaching) rather than raw strength, and they are
nicely done for that purpose.

6. LLM commentary layer

mills_llm.py / coordinator.py provide natural-language commentary and an
optional "override" suggestion path. (Sanmill also has LLM-related code; in both
projects the experience depends heavily on the underlying model maturing.)

7. The core architectural trade-off

NMM_LLM sits at the "heavy knowledge, moderate search" design point, which fits
Python + a teaching/UX product. Sanmill sits at the "light evaluation, very fast
deep search" point, which fits a monomorphized Rust engine doing millions of
nodes/sec. For reference, Sanmill's static evaluator is roughly:

value = mobility_diff + 5·(in_hand_diff + on_board_diff + removals_diff) plus a
mills-piece-count term in the relevant placing variant and a game-over branch
(crates/tgf-mill/src/rules/evaluation.rs, game_impls.rs).

Both are valid; they optimize different objectives under different runtimes. The
key takeaway for Sanmill is not "port NMM_LLM's evaluator", but "borrow the
separable, exact parts (endgame table, symmetry pattern) and keep our evaluator
lean so search stays fast."

---

What this means for Sanmill

• Adopt the highest-leverage, zero-hot-path-cost idea: exact endgame knowledge.
  Instead of self-solving, integrate the already-exact Malom database — the C++
  reader was previously in this repo on master (src/perfect/).
• Start with one sector (std_3_3_0_0.sec2, ~616 KB) to prove the full
  pipeline (format → index/symmetry mapping → probe → search short-circuit).
• Do not migrate the heavy evaluator. In a deep-search Rust engine, most of
  those features are (a) redundant with what search already discovers and (b) a
  large per-node cost that would reduce nps and likely weaken play. Tactics
  belong in search; the evaluator stays lean.

Sector naming (Malom standard): std_<WB>_<BB>_<WH>_<BH>.sec2 → std_3_3_0_0 is
3-vs-3 on board, none in hand = the flying endgame.

---

Proposed approach (PerfectDB, single sector first)

1. Port the PerfectDB reader (not the solver) from master:src/perfect/
   (perfect_sector.*, perfect_sec_val.*, perfect_hash.*,
   perfect_sector_graph.*, plus the perfect_api.* / perfect_adaptor.* glue).
   For a single-sector probe we only need the subset that decodes a .sec2 sector
   and answers a value/WDL query.
2. Prefer a pure-Rust reader for the one sector to keep the workspace Rust-only
   and avoid a C++ build dependency; fall back to a thin FFI shim only if
   reimplementing the format is impractical.
3. Embed std_3_3_0_0.sec2 as a build asset (or wire an optional-download loader
   mirroring master's UX), and expose probe(state) -> Option<Wdl> (plus best
   continuation if available).
4. Wire the probe into the searcher's existing 3v3 fly-endgame branch: on a hit,
   return the exact verdict and short-circuit; on a miss, fall through to normal
   search.

---

Important notes & caveats

• Symmetry is internal to the DB. Malom canonicalizes via the board symmetry
  group; we must map a Sanmill MillState into the DB's canonical index correctly
  and must not add a parallel symmetry layer for this feature. This mapping is the
  main correctness risk — cover it with tests, using master:src/perfect/ as the
  reference of truth.
• Index / encoding mapping. Malom has its own square indexing and
  side-to-move / in-hand conventions; the port must translate Sanmill's square
  layout, side_to_move, and on-board/in-hand counts exactly.
• Scope = reader, not solver. We read a precomputed sector; we do not
  regenerate the database.
• Variant guard. PerfectDB is standard-rules only. The probe must be a no-op
  for non-standard variants (diagonal lines, board-full rules, Lasker, etc.).
• No hot-path regression. The probe guard for non-hitting positions must be
  cheap enough that normal search nps is unaffected.

---

Out of scope / lessons already learned

• Killer moves / history heuristic (depth²). Already tried in Sanmill and
  regressed throughput — Mill's rules are simple and the bookkeeping cost
  outweighed the ordering benefit. Do not reintroduce (even though NMM_LLM uses
  them effectively at Python throughput; this is exactly a design-point difference).
• Semantic move-ordering buckets (e.g. "block opponent's last escape square",
  "block interconnected double mills"). Interesting, but suspected to hurt nps
  given how cheap each node already is. Any such change must be proven by a
  self-play / benchmark A/B — which requires the self-play harness to be solid
  first. Treated as a gated follow-up, not part of this issue.
• Porting the heavy evaluator. Out of scope by design (see analysis above).
• LLM commentary layer. Sanmill already has LLM code; experience is mediocre
  until the model side matures. Out of scope here.

---

Tasks

Phase 0 — Prerequisites

• Write a short internal note on the .sec2 format and Malom indexing (sourced from master:src/perfect/)

Phase 1 — PerfectDB reader port

• Extract the minimal .sec2 reader path from master:src/perfect/ (sector decode + value query)
• Implement a pure-Rust single-sector reader (preferred), or an FFI shim if reimplementation is impractical
• Implement MillState → Malom canonical index mapping (square layout, side-to-move, in-hand/on-board counts)
• Unit-test the index mapping against known positions, cross-checked with master

Phase 2 — Embed sector & probe API

• Embed std_3_3_0_0.sec2 as a build asset (or wire the optional loader)
• Expose probe(state) -> Option<Wdl> (+ best move if available), with a standard-rules-only variant guard
• Memory-map / cache the sector so probing is allocation-free on the hot path

Phase 3 — Search integration

• Probe in the searcher's 3v3 fly-endgame branch; on hit, return exact verdict and short-circuit
• Ensure graceful misses (out-of-sector / unsupported variant) fall back to normal search
• Confirm no nps regression on non-hitting positions

Phase 4 — Validation

• Correctness: exact-DB self-play in pure 3v3 should always draw
• Spot-check several known 3v3 W/D/L positions against the DB verdict
• Benchmark before/after with cargo run -p tgf-cli -- bench and tests/perf_baseline.toml

Phase 5 — Docs

• Document the PerfectDB probe contract in docs/FRAMEWORK_API.md / engine docs
• Note the standard-rules-only limitation and the optional full-DB download path

Follow-ups (separate issues)

• Evaluate additional sectors (e.g. 3v4 / 4v3) once the single-sector pipeline is proven
• Complete the self-play harness, then A/B-test any semantic move-ordering ideas (gated on measured nps)

---

Acknowledgments

• Gábor E. Gévay and Gábor Danner — the Malom Perfect Database and the
  paper Calculating Ultra-Strong and Extended Solutions for Nine Men's Morris,
  Morabaraba, and Lasker Morris.
• The NMM_LLM project and its author — for a clear, well-documented
  demonstration of an exact 3v3 retrograde table, clean D4 symmetry engineering,
  and a thorough write-up (AI_INTERNALS.md) that made this comparison easy and
  enjoyable to do.