exploratory · engineering resultevidence: CHECK tier · no strength claim
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.
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.
whole decision, depth 4 / 5 strata
3.08×
interleaved A/B, one thread
heap allocations per decision
0
reference: ≈15–30 million
moves replayed, both engines
438,020
0 mismatches
leaf values compared bit-for-bit
225,183
0 mismatches
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.
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 %.
Attributed share of one depth-4 / 5-strata decision, original engine
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 3 is dropped into column 1.
1. Place the disc
2. Wave 1 — find the poppers
3. Resolve the covers
4. Gravity, affected columns only
5. Wave 2 — scan again
6. Wave 2 resolves; cascade ends
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:
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.
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.
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.
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.
Ablation — whole depth-4 / 5-strata decision, variants interleaved within each repeat
table view
configuration
speedup
note
transposition table only
1.01×
inside the noise; 5.8× per op on 0.6 % of runtime
fast engine only
1.08×
1.26× on the 20 % that is move application
fast leaf only
2.61×
carries the result
all three
3.08×
slightly super-additive: less allocator contention
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.
gate 1 · anchor
the parameterised slow search vs the frozen depth-4 binary: action, logical work, completed depth, node count, cache hits, cache size
60 moves
0 mismatches
gate 2 · search parity
fast search vs slow search: selected column AND logical work AND completed depth, at nine (depth, strata) configurations up to depth 5 / 7 strata
306 moves, including configurations where the cache evicts on almost every store
0 action, 0 work, 0 depth mismatches
gate 3 · determinism + reflection
repeat call identity; mirrored position gives the mirrored action with identical work
43 moves, 38 asymmetric boards (symmetric boards excluded and counted)
0 mismatches
gate 4 · trajectory
board, next disc, score, score delta, level, moves, terminal flag, board-clear and level-advance flags, and the complete wave list entry by entry
8,288 games · 438,020 moves · 548,263 waves, across a deterministic policy, a depth-3 search and the frozen depth-4 search
0 mismatches
gate 5 · bit-exact leaf
fairLeaf return values as raw 64-bit patterns, not approximately-equal doubles, on states harvested exactly as the search expands them
225,183 real leaf states, plus every table entry
0 mismatches
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.
Measured speedups, both arms in one process, best of three
table view
configuration
speedup
note
whole games, depth 3 / 5 strata
3.01×
435 moves, work/move 54,826
whole games, depth 3 / 7 strata
3.09×
345 moves, work/move 153,759
whole games, depth 4 / 5 strata
2.88×
60 moves
whole games, depth 4 / 7 strata
2.93×
12 moves
per decision, depth 4 / 5 strata
3.10×
3 fixed real roots
per decision, depth 4 / 7 strata
3.19×
3 fixed real roots
per decision, depth 5 / 5 strata
3.15×
3 fixed real roots
per decision, depth 5 / 7 strata
3.23×
3 fixed real roots
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.
1
Leaf memoisationmeasured headroom, deliberately not shipped
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.
finding-13 §8.4
2
First-wave restricted popper scanrejected pending an enforced invariant
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.
finding-13 §8.3
3
Batched simulation: thousands of boards in lockstepproposed — no implementation
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.
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
4
Batched leaf evaluation on the GPUproposed — designated GPU candidate in the hardware plan
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.
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)
5
A learned leaf (NNUE-style) instead of the hand-written onealgorithmic candidate, not a speedup
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.
docs/research/status.md §4–§7
6
Batched board representation in the browserfar horizon — depends on the two entries above
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.
no artifact; the TypeScript engine's latent-board mode already provides the deterministic reveals such a port would be tested against
7
Things that would change the game, and are therefore not speedupsallowed only as registered new candidates
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.
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.
The benchmark contract that defines what counts as a pure speedup:
docs/benchmarks.md.
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.