Rust bitboard engine

The one-paragraph version

A Drop7 board is 49 cells, each holding nothing, a number 1–7, or a gray disc in two states — ten possibilities, which fit in four bits. The reference engines store those cells as 49 bytes and walk them with loops. This engine packs them as seven 32-bit words, one per column, four bits per cell, with the bottom row in the least-significant nibble. That one choice cascades: gravity in a column becomes a single bit-gather instruction, a row rise becomes one shift-and-or per column, and the whole board state is 28 bytes that fit in a handful of registers. On top of that packed core sits the fair expectimax search with a pluggable leaf evaluator and a transposition table that the measurements below drove to a specific, cheap shape. Everything is proven bit-identical to the C++ and TypeScript references before any number was trusted.

Strategy 1: the board is seven integers, and gravity is one instruction

Store a column as a 32-bit word of seven nibbles, with the bottom row in the least-significant nibble. Two invariants make everything cheap:

• A column's height is the popcount of its non-zero nibbles, and a dropped disc lands in the first zero nibble — so a drop is word |= disc << 4*h and a legality check is one mask test against the top nibble.
• Because columns stay bottom-packed, gravity is a stable compaction of non-zero nibbles toward the low end — which is exactly what the BMI2 PEXT instruction does: pext(word, mask) extracts the nibbles selected by mask and packs them, in order, at the bottom.

The row rise is the other place the packing pays: shifting every cell up one row and laying a fresh gray row underneath is (word << 4) | SOLID per column — seven shift-ors replace the reference's 49-cell copy.

Strategy 2: bitboards for the cascade, counted in parallel

Popper detection and cover hits want a different shape — row-major bitboards — and the engine derives them from the column words on each wave with SWAR nibble tests and PDEP scatters (about 70 bit operations, versus the reference's ~1,300 board reads per wave):

• Poppers come from the same 128-entry run-length table the proven C++ fast engine uses: a disc pops when its value equals the contiguous occupied run through it in its row or its column, and the run length is a table lookup on the row/column occupancy mask.
• Cover hits are counted for the whole board at once. The popper bitboard is shifted in the four neighbour directions, and the four resulting bitboards are summed with a bitwise parallel counter (ones/twos/fours planes). A solid gray reveals exactly when its two-or-more-hits plane is set; a cracked gray when any plane is set. No per-cell loop, and the reveal draws are still consumed in ascending row-major order — the order the reference consumes randomness, which is what keeps the streams identical.

Strategy 3: a pluggable leaf, statically dispatched

The search is generic over a Leaf trait, so the fair leaf (ported character-for-character from the proven C++ fastFairLeaf, verified bit-identical on 150,854 real states) is one monomorphised instantiation and a different evaluator costs no branching in the hot path. Because the leaf reads cells many times in row-major order, it works on a byte view of the board that costs seven PDEPs to produce — the engine keeps the packed words for the mechanics, the leaf pays array-load prices for the reads.

Strategy 4: the transposition table, designed by measurement

The fair search carries a transposition table so a state reached two different ways is evaluated once. The C++ fast search uses a packed-key, open-addressed, strict-LRU table. This engine's table was not designed by instinct; two measurements settled its shape, and they are the most interesting numbers on this page.

The node hit rate is a lie. On real decisions, the table's node hit rate is 1.3 % at depth 4 and 1.36 % at depth 5 — which reads as "the table is almost never useful." But a table hit does not save one node; it prunes the entire subtree under that node, about 49^depth expansions. Measured work per decision (move + leaf evaluations):

The expensive part of the table was never the hits — it was the bookkeeping. The C++ table pays for a hash, a probe, and LRU linked-list maintenance on every interior node to earn its hit rate. This engine replaces it with a direct-mapped, depth-preferred table: one slot per hash index, no probe chain, no LRU list, replace-on-collision when the new node is at least as deep. It finds nearly the same hits (27.5k vs the LRU's 29.9k per decision at d4s7) at a lower per-operation cost and a fifth of the memory.

The depth gate exists and was measured: caching only depth ≥ 2 captures the rare deep hits but misses the numerous shallow ones and recovers only ~25 % of the work reduction, so the shipped configuration caches every depth (gate ≥ 1) with the cheap table. The table is a compile-time strategy parameter — the NoTable arm compiles to nothing — and the values gate proves the choice changes no per-column value, only speed and memory.

What happened

All speeds are fixed-work, complete-depth decisions on the same 105 harvested root positions, every arm computing bit-identical per-column values (proven by the gates below). Full data in benchmark.json.

At depth 5 / 7 strata the same arms tell the depth story: the C++ fast search takes 7,817 ms per decision, the Rust cheap table at 256k entries ties it (7,788 ms), and at 1M entries pulls ahead to 7,047 ms (1.11×) — while the no-table arm, doing all 582.7M work units, takes 63,325 ms. Depth 5 is where memoization stops being optional, and where the Rust engine's per-work cost (113 vs 134 ns/work) still wins once the tables are comparably sized.

Thread scaling is shared-nothing: an atomic game cursor, one searcher per worker, no shared mutable state. Whole-game throughput scales 12.6M → 129.5M moves/s from 1 to 16 physical cores (10.3× on the shared machine; a clean run measured 14.1×), with identical move counts, wave counts and scores at every worker count — each game is computed by exactly one worker, deterministically, so worker count never changes a result. This is the mode that maps to a 192-core evaluation instance: 192 searchers with 64k-entry tables cost ~0.6 GB of table memory, against ~3.1 GB for the C++ fast search's tables.

How it was proven to be the same game

Every gate replays identical inputs through the Rust engine and a reference and fails on any difference. The columns in the trajectory gates are chosen once from the reference state and handed to both engines, isolating engine semantics from policy semantics.

What this taught us, and what is still open

• The representation is the win. Packing the board column-wise into seven words turned gravity, drops, rises and legality into single bit operations, and made the whole board small enough to live in registers. That — not any search trick — is where the ~2× engine throughput comes from.
• Measure a cache by the work it eliminates, not the hits it records. A 1.3 % node hit rate sounded like the table was overhead; it was actually eliminating most of the work, because hits prune subtrees. The repository's own fast-engine finding had measured the table's storage cost (0.6 % of runtime) but never its work value; this is the complementary measurement.
• The cheap table beats the careful table. Direct-mapped with depth-preferred replacement finds ~92 % of the strict-LRU table's hits at lower per-operation cost and a fifth of the memory.

Still open: a two- or four-way set-associative table should close the remaining hit-rate gap to the LRU at depth 5 (748k vs 911k hits per decision) without the LRU's bookkeeping; the leaf is within 1.2× of the C++ leaf but not yet faster than it on dense late-game states; and the engine has no GPU or latent-mode variant, so scripted-round and native-scenario duties stay with the existing engines.