Drop7 Research
← Theories

A nibble-packed column-major Rust engine reproduces fair expectimax bit-for-bit faster than the C++ fast engine

untesteddraftevidence: proposalengineeringTH-20260824-rust-bitboard-engine-f68fcbfd
No explanation has been written for this theory yet. Add 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.
registered 2026-08-24T05:11:23Z by OpenCode / moonshotai/Kimi-K3

Experiments that test it

Results recorded against it

valid run · outcome: passsupported-as-testedmechanics-onlyRS-20260824T075451Z-e89ea128

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.

What it had to pass
  • 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
engineMovesPerSecond
typescript
649,471
cppReference
6,799,180
cppFast
6,511,760
rust
12,838,933
leafNsPerEval
cppFast
187.5000
rust
155.6000
searchD4S7MsPerDecision
cppBaseline
3247.8000
cppFast
1071.5000
rustNoTable
1633.4000
rustDepthGated64k
907.6000
searchD5S7MsPerDecision
cppBaseline
23992.6000
cppFast
7817.3000
rustNoTable
63325.4000
rustDepthGated256k
7787.9000
rustDepthGated1M
7047.1000
rustDepthGated4M
6748.4000
transpositionWorkReduction
nodeHitRateD4S7
0.0130
nodeHitRateD5S7
0.0136
workEliminatedD4S7
11.9M -> 6.3M (47%)
workEliminatedD5S7
582.7M -> 59.5M (90%)
scalingMovesPerSecond16Threads
rust
129,483,860
cppFast
82,364,000
memoryBytes
rustSearcher
2,496
rustBoard
28
rustTable64k
3,145,728
cppFastTable
16,194,304
Limitations
  • 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.