Fast engine
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.
On this page
- Depth x chance-exactness factorial: the fifth ply at five and at seven strata, with an end-to-end reproduction control (2026-08-21)
- Depth x chance-exactness factorial: the fifth ply at five and at seven strata, with an end-to-end reproduction control (2026-08-21)
- Rust bitboard engine: parity gates and throughput benchmark vs TypeScript and C++ engines
Summary
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.
Runtime profile
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.
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 %.
table view
| component | share | detail |
|---|---|---|
| leaf evaluation (fairLeaf) | 79.1% | 764,899 calls × 970.3 ns |
| move application (playMoveSampled) | 20.2% | 796,081 calls × 238.2 ns |
| transposition probe + insert | 0.6% | 31,159 calls × 187.9 ns |
Move pipeline
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 is dropped into column 2.
Both engines perform these same steps. What changed is how much work each step costs:
Packed board state
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.
Run-length lookup
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.
Incremental gravity and cover updates
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.
Allocation-free hot path
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.
Math lookup tables
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.
Optimized leaf evaluator
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.
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 |
Parity validation
"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.
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.
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 |
Search impact
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.
Further optimization
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.
Current bottleneck
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.
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. - 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.
RecordsTheories, experiments and results that reference this directory
Claim: With seven chance strata (one stratum per disc value, so every individual chance marginal is exact), adding a fifth ply of look-ahead to the fair expectimax search raises mean score on the shared 64-game development cohort by a paired margin whose one-sided 95% whole-game bootstrap lower bound is above zero, as the third-to-fourth ply does (+86,172 with a lower bound of +26,468, finding-05). With five strata, where the third-to-fourth ply gradient is absent (-7,723, not significant), no fourth-to-fifth ply gradient is expected either. Depth and chance-estimator exactness are therefore complements, and the fourth ply is not a special stopping point.
This theory is currently mixed at the public-development (a cohort for deciding what to try next, not confirmation) level.
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.
This theory is currently untested at the proposal (no games played) level.
It compares fast-engine-parameterized-fair-search, depth 5 (arms d5s7 and d5s5) against the recorded depth-4 arms on the same seeds (d4s7 = runs/RUN-A51D-s7confirm/fresh-s7.json, d4s5 = runs/RUN-A51D-s7confirm/fresh-s5.json), plus a same-cohort fast-engine reproduction of d4s7 as the control at the STANDARD (a 64-game paired development cohort) level, using previously-evaluated-development data.
partial run outcome: fail The run was partial and the outcome was fail (public-development (a cohort for deciding what to try next, not confirmation)). Read the result.
partial run outcome: inconclusive The run was partial and the outcome was inconclusive (public-development (a cohort for deciding what to try next, not confirmation)). Read the result.
It compares rust-engine (drop7-rs cargo crate, std-only) against C++ fast engine + frozen native reference + TypeScript engine at the CHECK (mechanics checks only, no games played) level, using no-gameplay data.
valid run outcome: pass The run was valid and the outcome was pass (mechanics-only (checks only, no games played)). Read the result.
The run was partial; the outcome was fail, at the public-development (a cohort for deciding what to try next, not confirmation) level. Of 6 preregistered checks, 3 passed and 2 failed.
The fifth ply buys nothing at either chance resolution, and the earlier interim reading that it was actively harmful is withdrawn. Complete leg, 64 of 64 games: depth 5 at five strata scores 288,704 against depth 4 at five strata's 297,327, a paired -8,624 with a one-sided 95% whole-game bootstrap lower bound of -55,134 and W-T-L 33-0-31, for 23.29x the logical work per move. That is a wash, not a reversal. Partial leg, 16 of 64 games and still running: depth 5 at seven strata is -1,581 against the depth-4 seven-stratum control (95% lower bound -173,154, W-T-L 7-0-9) at 34.32x the work, and +16,622 against depth 3 at seven strata (95% lower bound -130,027, W-T-L 8-0-8) at 1,084.78x the work. At a fixed stratum count, depth 3 -> 4 -> 5 does not separate. READ THIS BEFORE QUOTING THE MEANS: the eye-catching gap between the 398,498 of d4s7 and the 288,704 of d5s5 is a chance-samples effect and not a depth effect, because those two arms differ in both factors; the correct paired depth contrasts at fixed chance resolution are d5s5 - d4s5 = -8,624 and d5s7 - d4s7 = -1,581, both indistinguishable from zero, and the correct paired stratum contrast at fixed depth is finding-05's d4s7 - d4s5 = +101,171. The interim slice reported in finding-15 section 2.2 (-268,611 over 8 paired games) was completion-order biased against depth 5 exactly as that section warned; at 16 games the bias is gone and the delta is -1,581. The engine control is clean and is the other retained result here: the fast engine's depth-4 seven-stratum arm reproduces the recorded unoptimised arm over 64 paired games x 11 fields with 0 mismatches, and the depth-5 five-stratum arm reproduces the recorded 32-game unoptimised arm over 32 paired games x 11 fields with 0 mismatches across two binaries and two different cache capacities. Every arm audited 0 incomplete decisions at its requested depth, 0 censored games and 0 score-decomposition identity failures. Flow rates fall with depth at five strata (1.9387 clears and 1.0651 reveals per move against depth 4's 1.9489 and 1.0697, and against the 2.400 and 1.400 indefinite survival needs), so nothing here moves toward the target.
Technical recordLimitations recorded with the result
- PARTIAL ARM: the depth-5 seven-stratum arm holds 16 of 64 games and was still executing (process 127323) when this result was written. Every seven-stratum number here is over those 16 paired games and none of them can decide the primary gate. The frozen snapshot assessed is runs/RUN-20260821T060358Z-895d0a79/d5s7-partial-16games.json; the live artifact will be rewritten to 32 games and beyond and will no longer match this record's hash.
- The 16 finished games are the cohort's first 16 seeds (0xa51d1000-0xa51d100f) because the runner completes whole 16-game chunks, so they are a fixed block rather than a random subset; they are paired seed-for-seed against comparators recorded on exactly those seeds, which is what makes the paired delta fair even though the 16-game mean is not an estimate of the arm's 64-game mean.
- 64 paired games with a score standard deviation of 38-64% of the mean; at this sample size a true depth effect smaller than roughly 55,000 points cannot be resolved, so 'no gradient' means 'no gradient this cohort can see', not 'exactly zero'.
- The cohort 0xa51d1000-0xa51d103f was opened by finding-05 and is permanently development data. This is a diagnostic comparison at STANDARD tier; it is not a freeze gate and can never become confirmation evidence.
- The depth-5 arms declare a 200,000-entry transposition cache and the depth-4 comparators 60,000. Capacity provably cannot change play (verified three ways in finding-15 section 3, including whole-game agreement across two binaries) but work per move is not comparable across capacities and each figure must be read with its capacity.
- The experiment record was written after the runs, by a different agent than the one that executed them. The comparison rule predates the arms and is implemented in analyze.py, but this is retroactive registration and not a preregistration; the amendment on the experiment record says so.
- Wall-clock figures are not timing-grade: the machine carried a one-minute load average of 12-63 from other agents' jobs throughout. Scores, moves and logical work are deterministic and unaffected.
- This rejects the exact configurations tested - depth 5 at five and seven strata, this leaf, this terminal utility, these work bounds. It does not show that no five-ply search can help. finding-15 section 5 names two mechanisms that would predict exactly this outcome (the terminal utility has no death-depth shaping, and the leaf is an uncalibrated potential); neither was tested here.
- Cost model correction, recorded because it changes what is affordable rather than what is true: the 78-wall-hour projection that once cancelled this experiment used worst-case iterative-deepening work. Measured work at depth 5 with seven strata is about 10x below that bound, and the arms ran in hours.
The run was partial; the outcome was inconclusive, at the public-development (a cohort for deciding what to try next, not confirmation) level. Of 6 preregistered checks, 3 passed and 2 failed.
SUPERSEDES RS-20260821T181917Z-9a34ba02, which assessed this experiment when the depth-5 seven-stratum arm held 16 games. The arm was stopped by the repository owner's decision at the 32-game chunk boundary and will not be resumed, so its analysis is now FINAL even though the cohort is partial: 32 of 64 planned games, every one of them a whole game, 0 censored, 0 score-decomposition identity failures, 0 incomplete decisions, minimum completed depth 5. The old record remains committed history and is not edited. THE HEADLINE IS A CORRECTION, NOT AN UPDATE. The previous record read the fifth ply as 'does not separate'. That reading was a NON-MEASUREMENT REPORTED AS A NULL. Doubling the sample from 16 to 32 games moved the depth-5-minus-depth-4 seven-stratum contrast from -1,581 to +23,367 and its median from -39,660 to +18,820 - THE SIGN FLIPPED - which is what a quantity being estimated far below its detection floor looks like. By chunk the paired mean is -1,581 on the first 16 seeds and +48,315 on the second 16. Do NOT replace the old reading with 'depth 5 helps': +23,367 is equally unsupported. The one-sided 95% bootstrap lower bound is -83,046 and the contrast's detection floor at n=32 is 107,988, so the estimate sits at 22% of the smallest effect this cohort could have resolved. The correct statement is that THE FOURTH-TO-FIFTH PLY CONTRAST AT SEVEN STRATA WAS NEVER MEASURED, in either record. THE POWER ANALYSIS IS THE MOST USEFUL THING THIS EXPERIMENT PRODUCED. Detection floor, taken as 1.645 x sd / sqrt(n), the smallest true effect whose one-sided 95% bound would clear zero: d4s7-d4s5 +101,171 against a floor of 55,192 (n=64); d4s7-d3s7 +86,172 against 61,457 (n=64); d5s5-d4s5 -8,624 against 47,052 (n=64); d5s7-d4s7 +23,367 against 107,988 (n=32). EVERY SIGNIFICANT RESULT IN THIS FACTORIAL IS ABOVE ITS FLOOR AND EVERY NULL IS BELOW IT - the factorial separated the contrasts it had the power to separate and nothing else. Resolving the observed +23,367 needs about 684 paired games; finishing to the planned 64 would have left a standard error near 46,400 against a 23,367 estimate, still a non-measurement. That is the justification for the stop: the contrast is not answerable at any affordable cohort size, so the marginal machine-day buys no information. The variance is structural, not fixable by tidier running: the five largest single-seed paired deltas are -1,002,862, +958,985, -678,455, +592,546 and -577,069, so individual games swing by more than twice the cohort mean. WHAT IS ACTUALLY MEASURED HERE, and it is the same lesson from the other side: at depth 5, going from five to seven strata is worth +123,613 with a lower bound of +32,575, W-T-L 19-0-13 - SIGNIFICANT, and comfortably above its 95,207 floor - for 5.85x the work. The chance-exactness axis pays at depth 5 exactly as it pays at depth 4 (+101,171 [+47,447] there). The previous record's warning therefore survives and is strengthened: the eye-catching gap between d4s7's 398,498 and d5s5's 288,704 is a CHANCE-SAMPLES effect, not a depth effect, and both stratum contrasts are now significant while no depth contrast is. The engine controls are unchanged and clean: the fast engine's depth-4 arm reproduces the recorded unoptimised arm over 704 field comparisons with 0 mismatches, and the depth-5 five-stratum arm reproduces its recorded 32-game predecessor over 352 comparisons with 0 mismatches across two binaries and two cache capacities.
Technical recordLimitations recorded with the result
- SUPERSESSION: this record replaces RS-20260821T181917Z-9a34ba02 for the same experiment. That record was written and committed when the depth-5 seven-stratum arm held 16 games, and its central depth claim reversed sign when the sample doubled. It is left byte-unchanged, because this repository has no precedent for annotating a committed result in place; the relationship is carried here and by the theory record's evidenceRefs. Quote this record, not its predecessor.
- PARTIAL BUT FINAL: 32 of 64 planned games. The run validity stays partial because the planned cohort was not completed; the analysis is nevertheless final, because the stop was a decision and the arm will not be resumed. These are different things and the record keeps them apart deliberately.
- THE PRIMARY CONTRAST IS UNMEASURED, not null. Neither -1,581 at n=16 nor +23,367 at n=32 is evidence about the fifth ply at seven strata. Anyone quoting either number as a finding is quoting noise.
- The 32 games are the cohort's first two 16-seed blocks, a fixed prefix rather than a random subset, because the runner completes whole chunks. They are paired seed-for-seed against comparators recorded on exactly those seeds, which is what keeps the paired delta fair; the arm's 32-game mean is not an estimate of a 64-game mean.
- The detection floors are a normal approximation (1.645*sd/sqrt(n)) applied to heavy-tailed paired deltas with sample skewness between -0.30 and +0.92. They are planning quantities, accurate to roughly the 1-5% by which they differ from the percentile bootstrap the tooling reports, not exact power guarantees.
- The 684-game and 13-wall-day figures assume the observed effect size is the true one and that throughput matches this run's 1,647 s per game at 14 threads. Throughput varied 2.3x between the two chunks under other agents' load, so the wall estimate spans roughly 8-18 days. If the true effect is smaller than +23,367 the required cohort grows quadratically.
- The one significant new result, d5s7 - d5s5 at +123,613 [+32,575], rests on 32 games rather than 64 and on an arm that was stopped; it is a stratum contrast at fixed depth 5 and should be replicated on a fresh block before it is leaned on.
- The cohort 0xa51d1000-0xa51d103f was opened by finding-05 and is permanently development data. STANDARD tier, diagnostic only, never a freeze gate and never confirmation evidence.
- The depth-5 arms declare a 200,000-entry transposition cache and the depth-4 comparators 60,000. Capacity provably cannot change play but work per move is not comparable across capacities.
- The experiment record was written after the runs, by a different agent than the one that executed them; its amendment says so. The comparison rule predates the arms.
- This still rejects nothing about five-ply search in general - only these depths, this leaf, this terminal utility, these work bounds. The two mechanisms named in finding-15 section 5 remain untested, and a flat-and-unmeasurable depth axis is consistent with both.
- Nothing here moves the ceiling. The best arm on this cohort is 411,874 on 32 games against the 1,050,000 the frozen qualification protocol requires, and every game ended.
The run was valid; the outcome was pass, at the mechanics-only (checks only, no games played) level. Of 6 preregistered checks, 6 passed and 0 failed.
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.
Technical recordLimitations recorded with the result
- 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.
Agent contextSource files, operational notes and how to reproduce
Directory: approaches/lifetime-objective/fast-engine