A nibble-packed column-major Rust engine reproduces fair expectimax bit-for-bit faster than the C++ fast engine
web/content/research/TH-20260824-rust-bitboard-engine-f68fcbfd.mdx and it will appear here. The registered record is shown below.The registered record
Claim
A 28-byte column-major board (7 x u32, 4 bits per cell) makes gravity, disc placement and legality constant-time bit operations (PEXT compaction on Zen 5, portable nibble loop elsewhere); combined with a packed-key open-addressed transposition table and per-thread searchers, the fair expectimax search runs bit-identical to the frozen C++ reference at higher throughput and lower memory, scaling near-linearly to all available cores.
Mechanism
Column nibble packing turns gravity into PEXT(word, expanded-nonzero-mask); occupancy/numbered/covered bitboards are derived with SWAR nibble tests and PDEP scatters; popper detection uses the proven 128-entry run-length table on row/column masks; cover hits are counted for the whole board at once with a 4-way bitboard adder; the leaf, chance stratification, canonicalisation, column order and accumulation order are copied character-for-character from the proven C++ fast engine.
What would prove it wrong
- Any mismatch in the trajectory gate (Rust vs C++ reference playHeadlessMove over leased seeds), the leaf gate (uint64 bit patterns of leaf values), or the search gate (per-column values and chosen actions at fixed depth/strata); or end-to-end throughput at identical work not exceeding the C++ fast engine; or worker-count dependence of chosen actions in complete-depth mode.
Experiments that test it
- Rust bitboard engine: parity gates and throughput benchmark vs TypeScript and C++ enginesrust-engine (drop7-rs cargo crate, std-only) vs C++ fast engine + frozen native reference + TypeScript engine · CHECK · completed
Results recorded against it
The Rust bitboard engine is trace-equivalent to the frozen C++ reference, the proven C++ fast engine, and the TypeScript engine on every observable, and is the fastest of the three. Board representation is seven u32 column words at 4 bits per cell (28 bytes): gravity is a single PEXT bit-gather per column, a row rise is (word << 4) | SOLID, and cover hits are counted board-wide with a 4-way bitboard parallel counter. All parity gates pass with zero mismatches: 3 trajectory arms (512 center + 256 search-policy games vs C++ playHeadlessMove; 256 games vs the TypeScript seededRandom driver) totalling 36,427 moves and 40,286 waves; 150,854 leaf states bit-identical as uint64 patterns; 105 d4s7 and 10 d5s7 roots with bit-identical per-column values and identical actions; the values gate re-run with the transposition table enabled proves cache-independence. Measured on the shared AMD Ryzen AI MAX+ 395 workstation (best-of-N, load 1.1-1.7): single-core engine throughput 12.8M moves/s vs C++ fast 6.5M (1.97x) and TypeScript 0.65M (19.8x); leaf 155.6 ns vs C++ fast 187.5 ns (1.20x); fair search at d4s7 908 ms/decision vs C++ fast 1,071 ms (1.18x) with a 3.1 MB direct-mapped table vs the C++ 16.2 MB LRU; d5s7 7,047 ms at 1M entries vs 7,817 ms (1.11x). Game-level scaling is shared-nothing and near-linear (10.3x on 16 physical cores on the shared machine; 14.1x in a clean run), with identical results at every worker count. A key recorded finding: the transposition table's 1.3% node hit rate is misleading — each hit prunes a whole subtree, so the table eliminates ~47% of work at d4s7 and ~90% at d5s7, and a cheap direct-mapped depth-preferred table captures nearly all of the strict-LRU table's payoff at a fifth of the memory. No strength claim; no new seeds opened.
- ✓Trajectory parity vs C++ reference and TypeScript engine across center, search-policy, and TS-driver arms — observed: 3 arms, 36,427 moves, 40,286 waves, 0 mismatches on board, next disc, score, score delta, wave list, level, moves remaining, terminal/clear/advance flags
- ✓Leaf bit-exactness vs C++ fastFairLeaf as uint64 bit patterns — observed: 150,854 states, 0 mismatches
- ✓Search value/action parity at fixed depth/strata — observed: 105 d4s7 roots (no-table and depth-gated arms) + 10 d5s7 roots, per-column f64 bit patterns and chosen actions identical, 0 mismatches
- ✓Cache independence of the transposition table — observed: values gate re-run with the direct-mapped table enabled: 105 roots, 0 mismatches
- ✓Worker-count independence and determinism — observed: identical move counts, wave counts and mean scores at 1/2/4/8/16/32 game-level workers; each game computed by exactly one worker
- ✓npm test and make test pass; no existing file modified — observed: npm test 137/137 pass; make research-validate OK; all Rust/C++/TS additions live under approaches/fair-expectimax/rust-engine/ and build/rust-engine/
Recorded metrics
- typescript
- 649,471
- cppReference
- 6,799,180
- cppFast
- 6,511,760
- rust
- 12,838,933
- cppFast
- 187.5000
- rust
- 155.6000
- cppBaseline
- 3247.8000
- cppFast
- 1071.5000
- rustNoTable
- 1633.4000
- rustDepthGated64k
- 907.6000
- cppBaseline
- 23992.6000
- cppFast
- 7817.3000
- rustNoTable
- 63325.4000
- rustDepthGated256k
- 7787.9000
- rustDepthGated1M
- 7047.1000
- rustDepthGated4M
- 6748.4000
- nodeHitRateD4S7
- 0.0130
- nodeHitRateD5S7
- 0.0136
- workEliminatedD4S7
- 11.9M -> 6.3M (47%)
- workEliminatedD5S7
- 582.7M -> 59.5M (90%)
- rust
- 129,483,860
- cppFast
- 82,364,000
- rustSearcher
- 2,496
- rustBoard
- 28
- rustTable64k
- 3,145,728
- cppFastTable
- 16,194,304
- CHECK-tier engineering result: proves equivalence and measures speed/memory, but makes no policy-strength claim and advances no benchmark tier.
- Timing measured on a shared workstation (load average 1.1-1.7); ratios between back-to-back arms are the trustworthy quantity, absolute nanoseconds are not.
- The d5s7 arms ran 3 decisions each (1 repeat) because a single d5s7 decision costs 7-63 s; the d4s7 arms ran 21 decisions, best of 3.
- The direct-mapped table's hit rate at d5s7 (748k-825k hits/decision) trails the C++ strict-LRU table (911k); a set-associative table is the recorded reopening direction.
- No GPU, latent-mode, or native-scenario variant: scripted-round and scenario duties stay with the existing engines.