---
title: Fast engine
family: lifetime-objective
status: exploratory · engineering result
evidence: CHECK tier · no strength claim
summary: A semantics-preserving reimplementation of the Drop7 move engine and the fair-D4 leaf, proven bit-identical to the frozen reference and measured at about 3× end to end.
---
<Callout title="An engineering result, not a strength result" tone="info">
This is a visual walkthrough of **how** the fast engine gets its speed and
**how** it was proven to be the same game. Every number on this page is copied
from the retained finding
[`finding-13-fast-engine`](/docs/exploratory/finding-13-fast-engine), which
was measured on a heavily shared machine; ratios between two arms measured
back-to-back are the trustworthy quantity, absolute nanoseconds are not. The
fast engine has produced **no score evidence**: it is an engineering result at
the `CHECK` tier, and it makes no claim about playing strength.
</Callout>
## The one-paragraph version
A Drop7 search spends almost all of its time doing two things: applying a
candidate move to a board (place a disc, pop matching discs, crack and reveal
gray discs, let everything fall, repeat) and then scoring the resulting board
with a leaf evaluator. The frozen reference does both correctly but wastefully —
rescanning the board dozens of times per wave, allocating millions of tiny heap
objects per decision, and calling `pow` and `ldexp` in the innermost loop. The
fast engine keeps every rule, every random draw, every floating-point operation
*in the same order*, and removes only the waste. It was then replayed against
the original on hundreds of thousands of moves and required to agree on every
byte.
<div style={{ display: "grid", gridTemplateColumns: "repeat(auto-fit, minmax(160px, 1fr))", gap: 12, margin: "1rem 0" }}>
<Stat label="whole decision, depth 4 / 5 strata" value="3.08×" hint="interleaved A/B, one thread" />
<Stat label="heap allocations per decision" value="0" hint="reference: ≈15–30 million" />
<Stat label="moves replayed, both engines" value="438,020" hint="0 mismatches" />
<Stat label="leaf values compared bit-for-bit" value="225,183" hint="0 mismatches" />
</div>
## Where the time actually goes
Before anything was optimised, the search was instrumented to count what one
depth-4, five-strata decision really does. The shape of the tree is the whole
story: the last ply is always the overwhelming majority of nodes, so the leaf
evaluator is called on 96 % of everything the search touches.
<TreeShape
depth={4}
totalNodes="796,058"
leafCalls="764,899"
leafShare="96.1 %"
interiorKeys="31,159"
caption="Census of one real depth-4 five-strata decision (24 decisions from real games). Only 3.9 % of nodes ever build a transposition key, which caps what any cache optimisation can be worth before it starts."
/>
Multiplying those counts by the measured cost of each primitive attributes the
decision's wall time. The transposition table, which the brief had ranked as
"very likely the single largest win" — is 0.6 %.
<AttributionBar
title="Attributed share of one depth-4 / 5-strata decision, original engine"
segments={[
{ label: "leaf evaluation (fairLeaf)", share: 79.1, detail: "764,899 calls × 970.3 ns" },
{ label: "move application (playMoveSampled)", share: 20.2, detail: "796,081 calls × 238.2 ns" },
{ label: "transposition probe + insert", share: 0.6, detail: "31,159 calls × 187.9 ns" },
]}
caption="Attributed components sum to 937.7 ms against 1,081.8 ms measured; the 13.3 % residual is the search driver itself and is reported rather than distributed. Load average ≈15–22 during these measurements."
/>
## How a move is applied, step by step
Watch one real move resolve. The frames below were generated by the
repository's TypeScript rules engine with a predetermined latent board, so the
reveals are exact, not illustrative. A <Disc n={3} /> is dropped into column 2.
<CascadeAnimation
frames={[
{
cells: "0000000000000000000000000000000000000890000333080",
label: "Place the disc",
highlight: [43],
note: "The 3 falls to the lowest empty cell of column 2.\nNothing else has changed yet.",
},
{
cells: "0000000000000000000000000000000000000890000333080",
label: "Wave 1 — find the poppers",
highlight: [43, 44, 45],
note: "Columns 2–4 of the bottom row form a run of exactly\nthree occupied cells, and all three discs are 3s.",
},
{
cells: "0000000000000000000000000000000000000910000000080",
label: "Resolve the covers",
highlight: [37, 38],
note: "The solid gray above column 3 takes one hit and cracks.\nThe already-cracked gray above column 4 takes its\nsecond hit and reveals a 1. The 3s are then cleared.\n3 discs × 7 points = 21.",
},
{
cells: "0000000000000000000000000000000000000000000091080",
label: "Gravity, affected columns only",
highlight: [44, 45],
note: "Only columns 3 and 4 lost a disc, so only they are\ncompacted. The other five columns are provably\nunchanged and are not touched.",
},
{
cells: "0000000000000000000000000000000000000000000091080",
label: "Wave 2 — scan again",
highlight: [45],
note: "The revealed 1 now stands alone vertically: a run of\nlength one equals its value, so it pops. The cracked\ngray beside it takes a second hit.",
},
{
cells: "0000000000000000000000000000000000000000000040080",
label: "Wave 2 resolves; cascade ends",
highlight: [44],
note: "The second hit reveals a 4. 1 disc × 39 points = 39.\nThe next scan finds no poppers, so the move is over\nwith a score delta of 60 and two chain waves.",
},
]}
caption="The engine resolves every popper in a wave simultaneously, reads cover hits from the pre-clear board, reveals in row-major order, then applies gravity — in exactly this order in both the reference and the fast engine. Each step is one pass through the loop in resolveCascadeFast."
/>
Both engines perform these same steps. What changed is how much work each step
costs:
<MovePipeline
steps={[
{ title: "Place", before: "copy board, scan column", after: "same (already cheap)" },
{ title: "Scan", before: "~1,300 reads per wave", after: "1 pass → 14 masks + bitboard" },
{ title: "Poppers", before: "lineLength ×2 per cell", after: "128-entry run-length table" },
{ title: "Cover hits", before: "all 49 cells checked", after: "only cover bits, built lazily" },
{ title: "Clear + reveal", before: "separate board copy", after: "in place, same order" },
{ title: "Gravity", before: "49-byte board by value", after: "in place, popped columns only" },
{ title: "Score wave", before: "pow(d, 2.5) each wave", after: "table, verified bit-exact" },
{ title: "Waves", before: "heap vector per move", after: "inline sink, no allocation" },
]}
caption="The reference is correct at every step; it simply recomputes from scratch. The fast engine caches what a 7×7 board makes cacheable and never allocates."
/>
## Strategy 1: the board is small enough to be a handful of integers
A row is seven cells, so its occupancy is one of 128 patterns. One pass over the
49 bytes produces seven row masks, seven column masks, and a 49-bit bitboard of
numbered cells packed into a single 64-bit word. Everything the cascade needs
afterwards is a table lookup or a bit operation.
<BitboardScan
cells="0000000000000000000000000000000000000890000333080"
caption="scanBoard: one sweep fills row_mask[7], column_mask[7] and the numbered bitboard. The cover bitboard is deliberately not built here — more than half of applied moves produce no wave and never need it."
/>
## Strategy 2: run lengths come from a table, not a rescan
The reference asks "how long is the contiguous run through this cell?" by
walking left, right, up and down from every numbered cell, on every wave. With
the row mask in hand, the run length of every position in that row is a single
precomputed entry: `kRunLengthTable[mask].length[column]`. The popper test is
then one comparison per numbered cell, visited in the same row-major order as
the reference so the popper list is byte-identical.
<RunLengthLookup
row="0333080"
caption="The bottom row from the animation after the drop. The mask 0111010 indexes the table; positions 1–3 have run length 3, so the three 3s pop. Position 5 is a gray disc and is never a popper. 98 reads replace ~1,300."
/>
## Strategy 3: gravity and covers touch only what changed
Reveals overwrite a cover in place and never create a hole, so a column with no
popper is unchanged by compaction. Gravity therefore runs only on the columns
that lost a disc, and it runs in the same buffer: the destination index never
trails the source, so no second board is needed. Cover resolution iterates the
cover bitboard (typically a dozen cells) instead of all 49, and reads the
pre-clear board exactly as the reference does, which is why the crack-versus-
reveal decision in the animation above is unchanged.
## Strategy 4: nothing in the hot path allocates
The allocation census was the surprise. Per depth-4 decision, the original
engine performed:
| Site | allocations per decision |
| --- | ---: |
| transposition key (52-byte string, over the 15-byte small-string buffer) | 31,159 |
| cache value (list node plus a copy of the key) | 45,486 |
| `MoveResult::waves` vector on every applied move that produced a wave | ≈ 358,000 |
| **two `std::vector<double>` per numbered disc per leaf, in the leaf's release inventory** | **≈ 15–30 million** |
The fast engine performs **zero**. Wave lists go to an inline sink (the search
only ever asks "was there a wave, and how deep was the last one?"), the leaf's
scratch is one reused member, and the transposition key is a fixed 32-byte
packed struct.
<PackedKey caption="Packing is injective on the reachable domain (cells 0–9, next disc 1–7, moves remaining 1–5, depth 1–8), so two states collide in the fast table exactly when their strings collided in the reference — hit, miss, insert and strict-LRU eviction sequences are identical, which is why logical work matches even at depth 5 where the cache evicts on almost every store." />
## Strategy 5: tables for the two libm calls
`scoreForWave(d)` is `floor(7 · d^2.5)` and was a `pow` call per wave; the
leaf's `readiness(cost)` is `ldexp(1, 1 − cost)`. Both became namespace-scope
tables: a plain indexed load, no thread-safe-static guard. Each table entry was
verified against the original expression over its whole reachable range (wave
depths 1–1,087; readiness costs −64–143), and anything beyond the table falls
back to the original call.
## Strategy 6: the leaf, where the 3× actually came from
The leaf rewrite is seven changes, each value-preserving by construction:
dead features removed (13 of 24 were computed and discarded, three `pow` calls
among them); the libm call tabled; the per-disc vectors replaced by stack
arrays, with a sort replaced by an insertion sort that yields the same order
statistic; ~5.5 kB of per-call zero-initialisation replaced by one reused
buffer; line analysis collapsed onto the same 128-pattern run-length idea; six
full-board passes fused into two while preserving the order *within each sum*;
and a term multiplied by a weight of exactly `0.0` removed, with a finiteness
argument that `+0.0` is the additive identity here. Everything that would have
changed a floating-point result — vectorising the dot product, reciprocal
multiplication, split accumulators, `float`, `-ffast-math` — was rejected.
<SpeedupBars
title="Ablation — whole depth-4 / 5-strata decision, variants interleaved within each repeat"
rows={[
{ label: "transposition table only", value: 1.01, note: "inside the noise; 5.8× per op on 0.6 % of runtime" },
{ label: "fast engine only", value: 1.08, note: "1.26× on the 20 % that is move application" },
{ label: "fast leaf only", value: 2.61, note: "carries the result" },
{ label: "all three", value: 3.08, note: "slightly super-additive: less allocator contention" },
]}
caption="24 real decisions, 3 repeats, load ≈22. Worst/best spread within a variant is 1.35–1.74×; nothing finer than that is claimed."
/>
## How it was proven to be the same game
"Faster and the answers still look right" is not a standard this repository
accepts. Five gates replay the same inputs through the frozen reference and the
fast engine and fail on any difference at all.
<GateLadder
gates={[
{
name: "anchor",
compares: "the parameterised slow search vs the frozen depth-4 binary: action, logical work, completed depth, node count, cache hits, cache size",
scope: "60 moves",
result: "0 mismatches",
},
{
name: "search parity",
compares: "fast search vs slow search: selected column AND logical work AND completed depth, at nine (depth, strata) configurations up to depth 5 / 7 strata",
scope: "306 moves, including configurations where the cache evicts on almost every store",
result: "0 action, 0 work, 0 depth mismatches",
},
{
name: "determinism + reflection",
compares: "repeat call identity; mirrored position gives the mirrored action with identical work",
scope: "43 moves, 38 asymmetric boards (symmetric boards excluded and counted)",
result: "0 mismatches",
},
{
name: "trajectory",
compares: "board, next disc, score, score delta, level, moves, terminal flag, board-clear and level-advance flags, and the complete wave list entry by entry",
scope: "8,288 games · 438,020 moves · 548,263 waves, across a deterministic policy, a depth-3 search and the frozen depth-4 search",
result: "0 mismatches",
},
{
name: "bit-exact leaf",
compares: "fairLeaf return values as raw 64-bit patterns, not approximately-equal doubles, on states harvested exactly as the search expands them",
scope: "225,183 real leaf states, plus every table entry",
result: "0 mismatches",
},
]}
caption="The column played is always chosen once from the reference state and handed to both engines, so the trajectory gate isolates engine semantics from policy semantics. The one real defect found during the work (an out-of-bounds read in an early isBoardEmpty) was caught by writing the gate first, before it produced a number."
/>
The end-to-end benchmark asserts, on every configuration, that both arms finish
with the same score, move count and total logical work, and aborts otherwise; a
silent divergence cannot be reported as a speedup.
<SpeedupBars
title="Measured speedups, both arms in one process, best of three"
rows={[
{ label: "whole games, depth 3 / 5 strata", value: 3.01, note: "435 moves, work/move 54,826" },
{ label: "whole games, depth 3 / 7 strata", value: 3.09, note: "345 moves, work/move 153,759" },
{ label: "whole games, depth 4 / 5 strata", value: 2.88, note: "60 moves" },
{ label: "whole games, depth 4 / 7 strata", value: 2.93, note: "12 moves" },
{ label: "per decision, depth 4 / 5 strata", value: 3.1, note: "3 fixed real roots" },
{ label: "per decision, depth 4 / 7 strata", value: 3.19, note: "3 fixed real roots" },
{ label: "per decision, depth 5 / 5 strata", value: 3.15, note: "3 fixed real roots" },
{ label: "per decision, depth 5 / 7 strata", value: 3.23, note: "3 fixed real roots" },
]}
caption="Load average 22–32 throughout. The speedup is flat to slightly rising with depth and strata, as the decomposition predicts: the last ply is always ≈96 % of nodes, so the leaf fraction does not fall as the tree grows."
/>
### What the 3× bought
A 64-game depth-5 / seven-strata cohort was projected at "roughly 75 hours".
Measured work at that configuration is 55,765,609 per move against a worst case
of 582,727,796 — 10.45× lower, because deeper trees are mostly transpositions —
and that correction applies to the unoptimised engine too. On top of it, the
fast engine turns the cohort from about 61.8 CPU-hours into about 19.1: roughly
38 minutes of wall time on 30 threads instead of two hours. The thread count is
arithmetic by analogy, not a measured scaling preflight.
---
## Primer: what could make this game run faster still
Everything below is **proposed**. None of it has an implementation, a gate, or
a measurement in this repository unless the entry says otherwise, and each one
would need its own registered experiment before a number could be quoted.
### First, the ceiling on the current shape
The decomposition above is blunt about its own limit: with the leaf at ~96 % of
nodes, the bound on this decomposition *with an infinitely fast leaf* is about
5×. After the rewrite, the leaf is still 58 % of the remaining time and move
application 41 %. Getting another order of magnitude therefore cannot come from
polishing the same serial loop; it has to come from doing *less* of it, doing it
*wider*, or doing it on different hardware.
<LeverList
levers={[
{
name: "Leaf memoisation",
status: "measured headroom, deliberately not shipped",
what: "264,655 of 764,899 leaf calls in a decision (34.6 %) re-evaluate a state already seen in that decision. fairLeaf is a pure function of (board, next disc, moves remaining), so a memo cannot change its value at any capacity and leaves logical work untouched. It is a cache-semantics change, which the benchmark contract says must be declared, memory-accounted and gated on its own, and its payoff is not obviously positive: a table large enough for the distinct leaf states per decision is ~20 MB per thread, probed 765,000 times, against a 64 MB L3 shared by 30 threads. 34.6 % is the headroom, not the gain.",
evidence: "finding-13 §8.4",
},
{
name: "First-wave restricted popper scan",
status: "rejected pending an enforced invariant",
what: "A board handed to playMove has no poppers (the previous cascade ran to completion), so after a placement only that disc's row and column can pop — 13 candidate cells instead of 49. Exactly equivalent given the invariant, and silently wrong the first time a caller hands the engine an unresolved board. Shippable only with a debug-build cross-check against the full scan, exercised by the gates.",
evidence: "finding-13 §8.3",
},
{
name: "Batched simulation: thousands of boards in lockstep",
status: "proposed: no implementation",
what: "Not for the expectimax hot path, whose tree is irregular and sequential, but for the work search cannot do serially: mass rollouts, corpus generation and training-data throughput. Lay boards out structure-of-arrays (one array per cell, or per bit-plane) so lane b owns board b, and make each cascade wave one vectorised step over every lane — AVX-512 on the CPU (16 cores, 32 threads) or one thread per board on the GPU. Every step in the pipeline above is a bit operation or a table lookup, which is exactly what vectorises. The open costs are divergence (lanes whose cascade has ended idle until the batch settles) and reveal RNG, which must remain bit-compatible with the reference's Mulberry32/stratified draws if the batch engine is to pass the trajectory gate.",
evidence: "docs/hardware/amd-ryzen-halo.md places a full simulator GPU port as a research prototype that must pass transition/RNG parity and beat the CPU end to end",
},
{
name: "Batched leaf evaluation on the GPU",
status: "proposed — designated GPU candidate in the hardware plan",
what: "The leaf is the bottleneck, and a leaf is a fixed function of a 49-cell board: the kind of uniform, data-parallel work a GPU amortises. A search that collects its frontier of leaf states and evaluates them in one batch trades the serial 279 ns per leaf for launch latency plus a per-board kernel. With the current hand-written leaf this would demand a bit-exact floating-point port, which changes summation order on most GPU reductions; it is far more natural once the leaf is a learned evaluator whose semantics the new candidate defines for itself.",
evidence: "gpu-01: PyTorch on ROCm works on this machine's gfx1151 after two documented workarounds, and wins 1.25–5× over the 32-thread CPU for the Drop7-sized policy net depending on batch size (lower bounds, contended host)",
},
{
name: "A learned leaf (NNUE-style) instead of the hand-written one",
status: "algorithmic candidate, not a speedup",
what: "Replacing fairLeaf with a small network is a new policy, not an optimisation. It is judged by whole-game score, not by agreeing with the old leaf. The attraction is that inference is dense linear algebra, which batches on the GPU and would run in a browser via WebGL or WebGPU shaders. The evidence in status.md is the caution: several learned evaluators already found predictive signal but failed to rank sibling moves well enough to beat fair D4. The hard, unsolved part is training, not running.",
evidence: "docs/research/status.md §4–§7",
},
{
name: "Batched board representation in the browser",
status: "far horizon — depends on the two entries above",
what: "The same packed representation (49 cells × 4 bits, masks, run-length table) is small enough to live in a texture or a storage buffer, and the cascade steps are shader-friendly integer ops. A playable browser engine that does a shallow lookahead with a learned leaf is plausible engineering once a leaf worth running exists; it would still be gated the same way: the WebGL port replayed against the TypeScript engine, move for move.",
evidence: "no artifact; the TypeScript engine's latent-board mode already provides the deterministic reveals such a port would be tested against",
},
{
name: "Things that would change the game, and are therefore not speedups",
status: "allowed only as registered new candidates",
what: "Alpha-beta or move ordering (full width at every node is part of what fair D4 is), sharing chance subtrees between sibling columns, skipping the shallow iterative-deepening passes, or raising the transposition capacity so depth 5 never evicts. Each changes logical work or the selected column. They may well be good ideas; they must be tested as policies, with gates that measure score, not equivalence.",
evidence: "finding-13 §8.2; docs/benchmarks.md required correctness gate",
},
]}
/>
<BatchLayout caption="Today the engine walks one cascade on one board. A batched engine would hold thousands of boards column-wise and advance every cascade one step at a time across all lanes; the per-step logic is unchanged, only the loop nesting flips. Divergence (boards that finish early) is the cost to measure." />
<Callout title="How any of these would be admitted" tone="warn">
The same way the fast engine was: a registered theory with a falsification
criterion, a seed lease, gates written before the optimisation, and a replay
against the reference that fails on any difference. A batch or GPU engine that
changed a single reveal draw, a wave order, or a popper list would not be a
faster engine; it would be a different game, and the trajectory gate exists to
say so. Timing claims additionally need an idle machine and a retained system
profile: none of the figures on this page qualify as a clean baseline.
</Callout>
## Reading further
- The full engineering finding, with the census, microbenchmarks, ablation,
gates, memory table and the rejected-ideas list:
[`docs/exploratory/finding-13-fast-engine.md`](/docs/exploratory/finding-13-fast-engine).
- The benchmark contract that defines what counts as a pure speedup:
[`docs/benchmarks.md`](/docs/benchmarks).
- The hardware plan for this workstation, including the CPU-first rule for
exact simulation and the GPU's designated workloads:
[`docs/hardware/amd-ryzen-halo.md`](/docs/hardware/amd-ryzen-halo).