---
title: Rust bitboard engine
family: fair-expectimax
summary: A from-scratch Rust Drop7 engine that packs the board into seven 32-bit words — so gravity is a single bit-gather instruction — and runs the fair expectimax search bit-for-bit identically to the frozen reference, faster and with a fraction of the memory.
status: completed
evidence: reproduced
reads: public
---

<Callout title="What this page is, and is not" tone="info">
This is an **engineering result at the `CHECK` tier**: a faster, smaller
implementation of the *same* game and the *same* fair search, proven
bit-identical to the frozen references on every observable. It makes **no
strength claim** and consumed no cohort data — the parity gates and benchmarks
ran on sub-blocks of the already-opened `SEEDLEASE-A52-FAST` development lease
(`0xa5276000`–`0xa5277fff`), opening zero new seeds. Every number below is
copied from the retained artifacts `benchmark.json`, `bench.log` and
`gates.log` under `runs/RUN-20260824T052018Z-b88c3e22/rust-engine/`, measured
on the AMD Ryzen AI MAX+ 395 workstation (16 physical / 32 logical cores,
machine profile `MACH-20260824T072426Z-fa409222`). The machine was shared
during measurement
(load average 1.1–1.7), so ratios between arms measured back-to-back are the
trustworthy quantity; absolute nanoseconds are not.
</Callout>

## 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.

<div style={{ display: "grid", gridTemplateColumns: "repeat(auto-fit, minmax(170px, 1fr))", gap: 12, margin: "1rem 0" }}>
  <Stat label="engine throughput, single core" value="12.8M moves/s" hint="2.0× the C++ fast engine, 19.8× TypeScript" />
  <Stat label="board size" value="28 bytes" hint="vs 49 bytes row-major; 7 × u32" />
  <Stat label="searcher memory" value="≈2.5 KB + table" hint="C++ fast search carries a 16.2 MB table" />
  <Stat label="moves replayed, three engines" value="36,000+" hint="0 mismatches on every observable" />
</div>

## 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.

<PackedColumn
  before={[0, 3, 0, 0, 5, 0, 2]}
  after={[0, 0, 0, 0, 3, 5, 2]}
  caption="One column word, read left-to-right from the top row's nibble to the bottom row's. The dashed slot is the unused eighth nibble (28 bits hold seven cells). Clearing the 3 and the 5 leaves holes; PEXT with the non-zero-nibble mask gathers the survivors toward the bottom row in their original order. On Zen 5 this is one 3-cycle instruction; a portable nibble loop produces the identical word elsewhere."
/>

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 `PDEP`s 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<sup>depth</sup> expansions. Measured
work per decision (move + leaf evaluations):

<AttributionBar
  title="Work per decision eliminated by memoization (no-table = 100%)"
  segments={[
    { label: "recomputed anyway (no-table does all of it)", share: 53, detail: "d4s7: 11.9M work units with no table" },
    { label: "pruned by the table at d4s7", share: 47, detail: "11.9M → 6.3M with the cheap table; C++ LRU reaches 6.0M" },
  ]}
  caption="At depth 4 the table eliminates ~47 % of all work despite a 1.3 % node hit rate. At depth 5 it eliminates ~90 % (582.7M → 59.5M): the deeper the search, the more each rare hit prunes. A 1.3 % hit rate and a 47–90 % work reduction are the same measurement, seen from two directions."
/>

**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`.

<SpeedupBars
  title="Engine move throughput, single core (whole games, best of 3)"
  max={21}
  rows={[
    { label: "TypeScript engine", value: 1.0, note: "0.65M moves/s · 1,540 ns/move" },
    { label: "C++ reference engine", value: 10.5, note: "6.8M moves/s · 147 ns/move" },
    { label: "C++ fast engine", value: 10.0, note: "6.5M moves/s · 154 ns/move" },
    { label: "Rust packed engine", value: 19.8, note: "12.8M moves/s · 78 ns/move" },
  ]}
  caption="Pure mechanics: place, cascade, rise, repeat, over 32,768 complete center-policy games with identical trajectories (same seeds, same mean score). The two C++ engines are within run-to-run noise of each other on this simple workload; the packed representation is where the Rust engine's ~2× comes from."
/>

<SpeedupBars
  title="Fair search, depth 4 / 7 strata (21 decisions, best of 3)"
  max={4}
  rows={[
    { label: "C++ reference storage", value: 1.0, note: "3,248 ms/decision · string-keyed LRU" },
    { label: "Rust, no table", value: 2.0, note: "1,633 ms · does all 11.9M work units, 0 bytes" },
    { label: "C++ fast, packed LRU 200k", value: 3.0, note: "1,071 ms · 16.2 MB table" },
    { label: "Rust, direct-mapped 64k", value: 3.6, note: "908 ms · 3.1 MB table" },
  ]}
  caption="Speedup over the C++ reference storage. The Rust cheap-table arm is the fastest *and* uses a fifth of the C++ fast table's memory; the no-table arm is the fastest per unit of work (137 vs 177 ns) but does 1.9× the work, which is exactly the memoization payoff."
/>

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.

<GateLadder
  gates={[
    {
      name: "trajectory × 3 drivers",
      compares: "board, next disc, score, score delta, level, moves remaining, terminal flag, board-clear and level-advance flags, and the complete wave list, entry by entry",
      scope: "512 games center policy + 256 games under a depth-3 search (C++ headless driver) + 256 games under the TypeScript driver — 36,427 moves, 40,286 waves",
      result: "0 mismatches",
    },
    {
      name: "bit-exact leaf",
      compares: "the fair leaf's return value as raw 64-bit patterns against the C++ fastFairLeaf",
      scope: "150,854 real states, harvested both as search leaves and as visited game positions",
      result: "0 mismatches",
    },
    {
      name: "search values",
      compares: "per-column f64 bit patterns and the chosen action at fixed depth/strata",
      scope: "105 real roots at depth 4 / 7 strata, 10 roots at depth 5 / 7 strata",
      result: "0 mismatches",
    },
    {
      name: "cache independence",
      compares: "the values gate re-run with the direct-mapped table enabled",
      scope: "105 roots, depth 4 / 7 strata",
      result: "0 mismatches — the table changes speed and memory, never a value",
    },
    {
      name: "search metrics",
      compares: "chosen action and completed depth against the C++ FastSearch",
      scope: "105 roots, depth 4 / 7 strata",
      result: "0 mismatches",
    },
  ]}
  caption="The TypeScript trajectory arm deserves a note: it drives the Rust engine with the TypeScript engine's exact draw pattern (one long-lived Mulberry32 stream) and reproduces engine.ts's board and score evolution move for move — three independent implementations of one game."
/>

## 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.

<TechnicalDetails title="Records, artifacts, and reproduction">

- Theory `TH-20260824-rust-bitboard-engine-f68fcbfd`, experiment
  `EX-20260824-rust-engine-parity-throughput-4036a91f` (engineering, CHECK tier).
- Artifacts: `runs/RUN-20260824T052018Z-b88c3e22/rust-engine/{gates.log,bench.log,benchmark.json,machine-profile.json}`.
- Source: `approaches/fair-expectimax/rust-engine/` (std-only cargo crate, no
  dependencies). Build with `./build.sh` (sets `target-cpu=native` for
  single-instruction PEXT/PDEP; a bit-identical portable loop compiles without
  BMI2). Gates: `target/release/gate_{trajectory,leaf,search}` against the
  C++ emitters in `cpp/` and the TypeScript driver in `ts/`.
- Reproduce the benchmark: `./bench_all.sh <run-dir> <roots-file> 3`.
- Seed discipline: sub-blocks `0xa5276000`–`0xa5277fff` of the already-opened
  `SEEDLEASE-A52-FAST` development lease; zero new seeds opened; no strength
  claim.

</TechnicalDetails>