Drop7 Research
← Docs

Finding 13 — a semantics-preserving fast engine for the fair expectimax search

docs/exploratory/finding-13-fast-engine.md

Finding 13 — a semantics-preserving fast engine for the fair expectimax search

Status: exploratory, CHECK tier. Engineering result, not a policy result. No score, strength or ranking claim is made anywhere in this document. Namespace: approaches/lifetime-objective/fast-engine/, build output build/fast-engine/. Seed lease: SEEDLEASE-A52-FAST, 0xa52700000xa5277fff. No seed outside that block was opened; the sub-blocks are fixed as constants in corpus.hpp so two programs here can never overlap. No existing file was modified. The frozen reference is compiled as a library from a copy generated into this approach's own build directory with exactly one line — the entry point — renamed; build.sh refuses to build if the diff is anything other than that one line. The four untouched reference sources hash to exactly the values audit-02 pinned:

45e7c223…f97cf  approaches/fair-expectimax/reference/fair-only-depth4.cpp
8828379b…ee1a   approaches/fair-expectimax/reference/fair-only-horizon.cpp
8b4267af…8c89e  src/core/native/public-behavior.hpp
b6dcde5f…3090   src/core/native/engine.hpp

0. Headline

Whole-decision speedup, depth 4 / 5 strata, one thread, interleaved A/B3.08x
Whole real games, depth 3 / 5 strata3.01x
Whole real games, depth 3 / 7 strata3.09x
Whole real games, depth 4 / 5 strata2.88x
Whole real games, depth 4 / 7 strata2.93x
Per decision, depth 5 / 7 strata3.23x
Selected column identicalyes, 306 gated search moves + 438,020 gated engine moves
Logical work identicalyes, at every one of nine (depth, strata) configurations
Completed depth identicalyes
fairLeaf return valueidentical bit pattern, 225,183 real leaf states
Whole-game outcomes on a real 64-game cohortidentical, 704 field comparisons, 0 mismatches (finding-14 §1)

The measured speedup is about 3x, not the 5–10x the brief hoped for, and the reason is structural rather than a failure of effort. 96.1 % of the search's nodes are leaves; after the leaf is made 3.5–3.8x faster it is still 58 % of the remaining time, and the other 41 % is the move application, which is already close to the cost of copying a board and hashing two 32-bit words. Amdahl's bound on this decomposition, with an infinitely fast leaf, is about 5x.

The brief's ranked expectation was wrong about which lead mattered, and the profile says so with numbers. The transposition table — expected to be "very likely the single largest win" — is 5.8x faster per operation, and is worth 0.6 % of a depth-4 decision (1.01x measured on its own), because only 3.9 % of nodes ever touch it. Every one of the four remaining leads was real but small; the win came from the fifth, the leaf.

The strongest equivalence evidence is not in this document. finding-14 §1 re-runs the depth-4 seven-stratum arm on the fast engine over the shared 64-game evaluation cohort and reproduces the unoptimised binary's recorded result exactly — mean score, mean moves, clears per move, reveals per move, occupancy and work per move all identical to every printed digit, and 704 per-game field comparisons with zero mismatches. That is the end-to-end proof; everything in section 4 below is the mechanism behind it.

Depth 5 with seven strata is affordable now, and most of the reason is not this work. See section 6: the 75-hour figure is a worst-case-work projection, and measured work at that configuration is 10.4x lower than worst case. One 64-game cohort costs 19.1 CPU-hours with the fast engine, 38 minutes of wall time on 30 threads.


1. The machine, and an honest warning about every timing number here

AMD RYZEN AI MAX+ 395 w/ Radeon 8060S, 16 cores / 32 threads, 64 MiB L3,
131,167,724 kB RAM, Linux 6.18.35, AMD clang 23.0.0git.
Flags: -O3 -std=c++20 -pthread -Wall -Wextra -Werror.
clang++ only: `make native` still fails on a default GNU-make + GCC host
(`CXX ?= clang++` is inert, and GCC raises a false-positive
-Werror=array-bounds in public-behavior.hpp:442) — audit-02 L1, unfixed here
because fixing it would mean editing an existing file.

This machine was never exclusive. Other agents' jobs (flow-run, corpus-gen, posmode, reveal-sampling, leaf-reweight, d4-rank, play) held the one-minute load average between 14 and 57 throughout, on 32 logical CPUs. The load average is printed next to every measurement.

Consequences, stated plainly:

  • Absolute nanosecond figures are inflated by roughly 3x at load 50 relative to load 15. The same unoptimised depth-4 decision measured 3,076 ms at load 51 and 1,082 ms at load 22 — same binary, same 24 positions.
  • Ratios between two arms measured back-to-back in one process are the trustworthy quantity, and every speedup here is such a ratio.
  • A drifting load can fake a speedup, and did. An earlier ablation run measured variants sequentially — all repeats of arm A, then all of arm B — while the background load fell from 51 to 28 over the run. It reported 5.51x for the full stack. Re-run with the variants interleaved inside each repeat, at a steady load of ~22, the same code measures 3.08x. The 5.51x was an artefact of measurement order. This is recorded because it is exactly the kind of number that would otherwise have been published.
  • Even interleaved, the worst/best spread within a variant is 1.35x–1.74x. Nothing below that resolution is claimed.
  • Under docs/benchmarks.md these are not a clean performance baseline and must not enter research/benchmarks/profiles-v1.json.

perf is not installed on this host, so section 2 instruments instead of sampling.


2. Profile of the ORIGINAL hot path

2.1 Census — what a depth-4, five-strata decision actually does

A counting instantiation of the same search driver (CensusSearch; the counters are behind if constexpr and compile away in every other instantiation) over 24 real decisions from real games on lease seeds 0xa5274000+:

Per decisionCountShare of nodes
logical work1,560,979
bestFutureValue nodes796,058100 %
fairLeaf calls764,89996.1 %
playMoveSampled calls796,081
canonicalState calls796,058
dynamicStateKey builds (interior nodes)31,1593.9 %
cache inserts22,743
cache hits8,416
findPoppers scans per applied move1.899

The shape of the tree is the whole story. Any optimisation of the transposition table is capped at a few percent before it starts.

2.2 Microbenchmarks on the real input distribution

Each primitive is timed on exactly the inputs the census says it sees: leaf states harvested by expanding real roots the way the search expands them, interior states likewise, cascade boards likewise. ns per call, load 14.6:

Primitiveoriginalfastratio
fairLeaf970.3278.83.48
playMoveSampled (one applied move)238.2188.61.26
findPoppers52.234.71.50
isBoardEmpty4.61.04.65
board scan + popper extraction vs scan alone33.820.2— †
applyGravity14.328.80.50 ‡
canonicalState10.61.85.78
scoreForWave (pow(d,2.5))below timerbelow timer
transposition probe + insert187.932.55.79

† This row is not an A/B of two implementations; it decomposes the fast path, showing that the one-pass board scan is 20.2 ns and extracting the popper list from it costs a further 13.6 ns. Compare the 52.2 ns of drop7::findPoppers. ‡ Not a fair comparison, and reported as such. The original returns a Board by value and the harness discards it, so the compiler elides the stores; the fast arm must copy a board into a mutable buffer first because it works in place. In the real cascade the fast version has no copy. Read 0.50 as "this microbenchmark cannot measure this", not as a regression.

2.3 Attribution, with the residual shown, not hidden

Census counts × microbenchmark cost, for one depth-4 five-strata decision at load ~15–22:

Componentcallsns/callmsshare of attributed
fairLeaf764,899970.3742.279.1 %
playMoveSampled796,081238.2189.620.2 %
transposition probe + insert31,159187.95.90.6 %
attributed total937.7
measured whole decision1,081.8
unattributed residual144.1 (13.3 %)

The residual is the driver itself — recursion, budget checks, State copies, the iterative-deepening loop — plus the gap between a microbenchmark's streaming access pattern and the search's. It is reported rather than distributed.

The same arithmetic on the fast side: leaf 213.3 ms + move 150.1 ms + table 1.0 ms = 364.4 ms attributed, against 351.8 ms measured. The leaf is now 58 % of the remaining time and the move application 41 %.

2.4 The allocation census nobody had counted

Three of the four confirmed leads are really the same defect — the hot path calls malloc. Per depth-4 five-strata decision, the original performs:

Siteallocations per decision
dynamicStateKey (52-byte string, exceeds the 15-byte SSO buffer)31,159
cacheValue — the list<string> node and its copy of the key45,486
MoveResult::waves vector, on applied moves that produce a wave≈ 358,000
releaseReadiness's two std::vector<double> per numbered disc per leaf≈ 15–30 million

The last row is the one that matters and it is not in the brief's list. It is in public-behavior.hpp's release-inventory loop, two vectors built by push_back for every numbered disc on the board, on every one of 764,899 leaf evaluations. The fast engine performs zero allocations inside a decision.


3. The optimisations, individually and cumulatively

Each is switched independently in one shared search driver (variant-search.hpp, ConfigurableSearch<kFastTable, kFastEngine, kFastLeaf>), so an A/B difference is attributable to the switched storage and nothing else.

3.1 What each switch contains

O1 — transposition table (fast-search.hpp). The reference keys an std::unordered_map<std::string, CacheEntry> with a 52-byte string rebuilt at every interior node — one malloc/free per interior node — and keeps LRU order in a parallel std::list<std::string>, a second allocation plus a second 52-byte copy per insert. Replaced by a 32-byte packed key (49 cells × 4 bits, plus next disc, moves remaining and depth), an open-addressed table with linear probing and backward-shift deletion, and an intrusive doubly linked LRU over slot indices. A decision starts with an empty cache — the reference gets that by constructing a fresh SearchContext; here it is an epoch bump, O(1), so there is no multi-megabyte memset per decision. Equivalence: the packing is injective on the reachable domain (cells 0–9, next disc 1–7, moves remaining 1–5, depth 1–8; gate-leaf checks the cell bound on every state it sees), so two states collide here exactly when their strings collide there, and eviction is still strict LRU at the same declared capacity. Hit, miss, insert and eviction sequences are therefore identical — which is why work counts are identical, including at depth 5 where the cache does evict.

O2 — scoreForWave and readiness tables (fast-engine.hpp). drop7::scoreForWave calls std::pow(double, 2.5) once per cascade wave; cfpi::detail::readiness calls std::ldexp several times per numbered disc per leaf. Both become table lookups at namespace scope, so the hot path is an indexed load with no thread-safe-static guard. The wave table has 1,024 entries with the original expression retained as the fallback beyond it — far above the depth-20 cascade observed in real play, and above anything reachable at all, since every wave clears at least one of 49 discs. Every entry is verified against floor(7.0 * pow(d, 2.5)) and every readiness value bit-compared against ldexp.

O3 — popper detection (fast-engine.hpp). drop7::findPoppers calls lineLength twice per numbered cell, and lineLength rescans up to seven cells in each of two directions — on the order of 1,300 board reads per wave, recomputed from scratch every wave. Replaced by one board pass producing seven row occupancy masks, seven column occupancy masks and a bitboard of numbered cells, after which each cell's run length is a 128-entry table lookup. The popper list comes out in the identical row-major order.

O4 — gravity and cover resolution. applyGravity returned a 49-byte Board by value on every wave; it is now in place, and only on the columns that actually lost a disc — reveals overwrite a cover without creating a hole, so a column with no popper is provably unchanged by compaction. The cover-resolution scan iterates a cover bitboard instead of all 49 cells, and that bitboard is built lazily, because most applied moves resolve with no wave at all (1.899 popper scans per move means ~0.9 waves) and never need it.

O5 — wave sink. MoveResult::waves is a std::vector<Wave> allocated per applied move for data the search never reads; playMove itself consults only empty() and back().depth. The search now passes MinimalWaveSink, which records exactly those two facts. Trajectory consumers get the complete list through FullWaveSink, which stores it inline and throws rather than truncating.

O7 — the leaf (fast-leaf.hpp), seven changes:

  • L1, dead computation. fairLeaf reads 13 of PhaseFeatures' 24 fields; audit-02 M5 measured the discarded set at ≥13.2 % of leaf time. Removed wholesale, because each discarded feature has its own accumulator and nothing retained depends on it: placementInventory (a full seven-column placement simulation), raiseCoveredRow + findPoppers (an entire extra popper scan per leaf), the low-cap column loop, cover_altitude_debt, and the rise-urgency block — which between them contain three std::pow calls per leaf whose results are multiplied by nothing.
  • L2, libm. readiness's ldexp becomes the O2 table.
  • L3, allocation. The two std::vector<double> support buffers per numbered disc become stack arrays (see 2.4). releaseReadiness reads one order statistic of the sorted values, a property of the multiset and not of the sort, so a descending insertion sort is value-identical to std::sort.
  • L4, layout. std::array<DiscAnalysis, 49> was ~4.3 kB zero-initialised per leaf; LineAnalysis's six 49-entry int arrays another 1.2 kB with four fill(-1) sweeps. Both gone; the leaf's scratch is one reused ~2.4 kB member.
  • L5, run-length table. A board row is seven cells, so its occupancy is one of 128 patterns and every position's run length, start and end follow from that pattern alone. analyzeLines' two scanning sweeps and its six arrays collapse into two 7-entry mask arrays plus a 2,688-byte lookup table.
  • L6, pass fusion. Six of the leaf's passes iterated all 49 cells. The fair-only horizon's own column loop has the same bounds and order as the occupancy/heights loop, and its board sweep the same bounds and order as the main per-cell sweep, and their accumulators are disjoint from everything else, so both are folded in — two whole board passes disappear while the order within each sum is preserved exactly. The remaining passes (adjacent_ones, runs of twos, cover exposure) iterate bitboards of the relevant cells — typically 5, 3 and 13 cells — instead of 49 each.
  • L7, the zero-weighted term. kRoughnessWeight is 0.0 and the leaf computed column roughness on every evaluation and multiplied it by zero. Both the feature and the term are removed. The argument: roughness is a sum of six absolute integer height differences, so it is finite on every board and 0.0 * roughness is exactly +0.0; result starts at +0.0 and can never become -0.0 (round-to-nearest returns +0.0 for any exact cancellation, and +0.0 + -0.0 is +0.0), so result += +0.0 is the identity. Verified empirically by re-running the bit-exact gate on all 225,183 corpus leaves after the removal: 0 mismatches. (This lead was contributed by the coordinator mid-task; it had been deliberately kept in until the finiteness argument was checked. Its measured cost after L6 was six integer subtractions inside a loop that runs anyway — below this machine's resolution.)

3.2 In-leaf profile

Cumulative cost of each leaf stage, measured with an if constexpr early return that compiles away in the shipped leaf, on 8,000 real leaf states, load 21.4:

Stagecumulative nsmarginal ns
frozen fairLeaf, for scale824.1
1 occupancy masks, heights, rise pressure, danger height34.234.2
2 + per-cell sweep: direct potential, height load, covered/low-number height risk134.4100.2
3 + release inventory171.637.2
4 + adjacent ones171.60.1
5 + runs of twos177.65.9
6 + cover exposure — full leaf218.941.4
7 (identical code to 6 after the L6 fold)217.8−1.1

Row 7 is the same code as row 6; its −1.1 ns marginal is a direct read of this machine's noise floor, ±0.5 % at this stage size and much worse at high load. An earlier run of the same table at load 54 produced marginals of −196 ns and −40 ns, i.e. it was not resolvable at all; that is why the stage table is reported only from the low-load run.

3.3 Ablation: whole depth-4 / 5-strata decision

24 real decisions, 3 repeats, variants interleaved within each repeat, load ~22:

Variantbest msworst msspreadspeedup
baseline (all original)1,081.831,877.531.74x1.00
O1 fast table only1,069.471,448.691.35x1.01
O3–O5 fast engine only1,003.211,730.871.73x1.08
O2/O7 fast leaf only414.64699.121.69x2.61
O1 + engine1,012.501,596.041.58x1.07
O1 + engine + leaf (all)351.81526.751.50x3.08

Reading this table honestly:

  • The leaf carries essentially the whole result: 2.61 of the 3.08.
  • The table on its own is 1.01x — indistinguishable from nothing, and inside the spread. Its 5.79x per-operation improvement lands on 0.6 % of the runtime, and its 4.4 MB of arrays displace hot leaf data from cache, which is why it does not even show its arithmetic share. It is kept because at depth 5 the cache actually evicts and the reference's list<string> churn grows with it, and because it removes the last per-node allocation.
  • The engine on its own is 1.08x, which is what a 1.26x improvement on 20 % of the runtime predicts.
  • 2.61 × 1.08 × 1.01 = 2.85, against 3.08 measured; the composition is slightly super-additive because removing the leaf's allocations also removes allocator contention with the engine's.

4. The equivalence gates

All gates exit non-zero on any mismatch.

4A. Anchor — the comparator really is the comparator

SlowSearch (slow-search.hpp) is a literal transcription of fair-only-depth4.cpp's driver with depth, strata, terminal utility, work bound and cache bound exposed as parameters, built exclusively from unmodified frozen primitives. This is what licenses using it as the semantic anchor at configurations the frozen binary cannot itself run.

SlowSearch(default) vs frozen chooseDepth4Action: 60 moves compared, 0 mismatches on action, logical work, completed depth, node count, cache-hit count and cache size.

4B. Search parity — action AND work AND completed depth

FastSearch vs SlowSearch, every move of every probe game:

depthstratamovesaction mismatcheswork mismatchesdepth mismatcheswork/move (both arms)
155000070
25500002,221
27500004,615
355000060,800
3750000174,013
45100001,383,207
47100004,377,375
55300019,025,731
57300052,398,525
total306000

Work-count identity is not optional. Work is the fixed-cost currency every comparison in this repository is denominated in; a version that reached the same column having done less logical work would be a different algorithm, not a faster one. Note the depth-5 rows in particular: there the declared cache capacity (200,000) is far below the worst case (6,007,498 entries at seven strata), so eviction happens on essentially every store — and the two arms still agree exactly, which is the strongest available evidence that the open-addressed LRU reproduces the list<string> LRU's eviction order.

4C. Determinism and reflection

43 moves; 0 repeat mismatches (identical action, work, nodes and cache hits on a second call); 0 mirror-equivalence mismatches (fast and frozen-primitive searches give the same action, work and completed depth on the mirrored position); 0 reflection mismatches on 38 asymmetric boards (action == 6 - action and identical work); 5 symmetric boards excluded.

One honest note on the reflection property. On a horizontally symmetric board the mirror is the board, so canonicalisation returns the same canonical state and the deterministic kColumnOrder tie-break returns the same column rather than its reflection; action == 6 - action then holds only for column 3. The frozen reference behaves identically — its self-test uses an asymmetric fixture — so this is a property of the policy, not a defect introduced here. The gate excludes symmetric boards from the 6 - action check, counts them, and separately requires fast and slow to agree on the mirrored position, which is the actual equivalence question.

4D. Trajectory — engines identical move for move

Both engines are driven through the same game with the same column, chosen once from the reference state and handed to both, so the gate isolates engine semantics from policy semantics. Compared every move: board, next disc, score, score delta, level, moves remaining, moves played, terminal flag, board-clear flag, level-advance flag, and the complete wave list (depth, cleared, revealed, points) entry by entry.

PolicySeedsGamesMovesWavesMismatches
centerFirstMove, full games0xa52700000xa5270fff4,09687,21260,6320
depth-3 five-strata search, full games0xa52710000xa5271fff4,096346,594482,0160
frozen fair depth-4, 45-move cap0xa52760000xa527605f964,2145,6150
total8,288438,020548,2630

The depth-4 arm is 96 seeds rather than 4,096 because a 4,096-seed frozen depth-4 arm is several CPU-days on this contended host; the depth-3 arm supplies the 4,096-seed breadth with search-quality (long, tall-board) states. The column is handed to both engines either way, so every arm is a valid engine test; what the smaller depth-4 arm buys less of is state distribution, not validity.

4E. Bit-exact leaf

frozen::fairLeaf and fast::fastFairLeaf compared as raw uint64 bit patterns — not as approximately-equal doubles — over states harvested by expanding real roots at every iterative-deepening ply exactly the way the search expands them:

wave-score table: depths 1..1,087 checked against floor(7*pow(d,2.5)), 0 mismatches (spot values 7, 39, 109, 224, 391, 617; d=20 → 12,521) readiness table: costs −64..143 bit-compared against ldexp(1.0, 1-cost), 0 mismatches leaf corpus: 125 real roots expanded, 225,183 leaf states compared leaf bit-pattern mismatches: 0 cell-domain violations (cell > 15): 0 terminal path identical: yes

This gate was re-run after every change to the leaf — after the bitboard rewrite, after the L6 pass fusion, and after the L7 roughness removal — and reported zero mismatches each time. That is a claim about the leaf, not about the process: the one real defect found during this work (section 8.5) was caught by reading the code, not by the gate, and the only gate that ever failed was the reflection check in 4C, which turned out to be the gate being wrong about symmetric boards rather than the engine.


5. End-to-end on real games

Paired whole games, seeds 0xa5275000+, both arms in one process, three repeats, best of. The benchmark asserts on every configuration that the two arms end with the same score, same move count and same total logical work, and aborts if they do not — a silent divergence cannot be reported as a speedup.

Configarmbest sms/movemoveswork/movespeedupidenticalload
d3, 5 stratabaseline28.31065.0843554,8261.00yes31.9
fast9.41421.6443554,8263.01yes31.9
d3, 7 stratabaseline65.669190.35345153,7591.00yes31.7
fast21.22161.51345153,7593.09yes31.7
d4, 5 stratabaseline67.0551,117.59601,487,6301.00yes28.8
fast23.243387.39601,487,6302.88yes28.8
d4, 7 stratabaseline47.8473,987.26126,142,4301.00yes29.6
fast16.3091,359.09126,142,4302.93yes29.6

Cache capacity 60,000 entries at five strata (the frozen value, worst case 45,430, never binds) and 200,000 at depth-4 seven strata (worst case 122,598, never binds). Game counts differ per configuration because a depth-4 seven-stratum game is ~4 s per move on this host; the move counts are the honest, reported unit.

Measured work per move agrees closely with finding-05's independent figures — 54,826 vs 54,429 at d3s5 and 153,759 vs 156,834 at d3s7 — which is a useful third-party check that this driver really is the same algorithm.

Per-decision probes on three fixed real roots, three repeats, both arms:

Configwork/decisionbaseline msfast msbaseline ns/workfast ns/workspeedupload
d4, 5 strata1,315,860697.9225.1530.4171.13.1028.9
d4, 7 strata3,295,3152,903.9910.9881.2276.43.1926.9
d5, 5 strata21,358,80811,864.03,765.1555.5176.33.1524.3
d5, 7 strata55,765,60930,340.29,379.2544.1168.23.2322.0

The speedup is flat to slightly increasing with depth and strata, which is what the decomposition predicts: the leaf fraction does not fall as the tree grows, because the last ply is always ~96 % of the nodes.


6. Does depth 5 with seven strata become affordable?

Yes — and the arithmetic says most of the reason is a cost-model correction, not this engine.

6.1 Reproducing the brief's 75 hours

The brief states worst-case work of 582,727,796 per move at depth 5 with seven strata, projecting to "roughly 75 hours for one 64-game cohort". That figure is reproducible exactly:

worst-case iterative work, branches b = 7 columns x 7 strata = 49:
  sum_{d=1..5} [ sum_{l=1..d} 49^l + 49^d ]
  = 98 + 4,851 + 237,748 + 11,649,701 + 570,835,398
  = 582,727,796                                        (matches the brief)

cohort = 64 games x 114.66 mean moves               (finding-05's d4s7 mean)
       = 7,338.24 decisions
total  = 582,727,796 x 7,338.24 = 4.2761e12 work units

cost per work unit, ORIGINAL engine, at the heavy contention that prevailed
earlier in this session:  3,076.199 ms / 1,560,979 work = 1,970.7 ns

4.2761e12 x 1,970.7e-9 s = 8.428e6 s = 2,341 CPU-hours
                                     / 30 threads = 78.0 wall-hours

So "roughly 75 hours" is worst-case work × the original engine's contended rate ÷ 30 threads. Both inputs are pessimistic.

6.2 Measured work is 10.4x below worst case

Depth-5 seven-stratum work was measured directly, twice, on disjoint real roots: 52,398,525 per move (search-parity gate, 3 moves) and 55,765,609 per decision (probe, 3 roots). Take the larger, 55,765,609.

582,727,796 / 55,765,609 = 10.45x

The transposition table is why: the deeper the tree, the more of it is transpositions. The same effect is visible at depth 4 (worst case 11,892,398, measured 3.3–6.1 million). This correction is not a contribution of this work — it applies equally to the unoptimised engine — but it is the larger of the two factors and the projection is wrong without it.

6.3 The measured cost of one 64-game depth-5 seven-stratum cohort

decisions = 64 games x 114.66 mean moves = 7,338.24

unoptimised engine:  7,338.24 x 30.3402 s = 222,640 s = 61.8 CPU-hours
                                                      = 2.06 h on 30 threads
fast engine:         7,338.24 x  9.3792 s =  68,825 s = 19.1 CPU-hours
                                                      = 0.64 h on 30 threads
                                                      = 38 minutes
Modelwork/moveCPU-hourswall hours, 30 threads
brief's projection (worst-case work, contended original engine)582,727,7962,34178.0
unoptimised engine, measured work and rate55,765,60961.82.06
fast engine, measured work and rate55,765,60919.10.64

The experiment the evidence most wants next is reachable either way. The engineering contribution is the 3.23x — it turns a two-hour cohort into a 38-minute one, which is the difference between "an afternoon per configuration" and "sweep the configuration space".

6.4 What this projection assumes, stated so it can be attacked

  • 114.66 mean moves is finding-05's measured depth-4 seven-stratum figure, used as the closest available anchor. A depth-5 policy that is genuinely stronger will survive longer and cost proportionally more: at 150 mean moves the fast cohort is 25.0 CPU-hours / 50 minutes; at 200 it is 33.3 CPU-hours / 67 minutes. The projection is therefore optimistic in exactly the case where the experiment succeeds.
  • Three real roots. Work per decision varies by ±40 % with board state; the two independent depth-5 seven-stratum measurements differed by 6 %.
  • Cache capacity 200,000 entries, against a worst case of 6,007,498 at this configuration. The cache therefore evicts, and measured work is a function of that declared cap. A different cap is a different configuration with different work — this must be frozen and declared in the experiment's manifest, exactly as docs/benchmarks.md requires. Both arms used the same cap and agreed exactly.
  • Contended machine, load ~22. On an idle machine both arms speed up together; the 3.23x ratio is the contention-robust part.
  • 30 threads is assumed by analogy with finding-05's runs, not measured here. No parallel scaling preflight was performed.

7. Memory

referencefast
Transposition storage, 60,000-entry capacity~15.4 MB at capacity, ~5.8 MB at the 22,743 entries actually used (estimated: ~256 B/entry across a map node, a heap string, a list node and a second heap string)4,648,576 B, fixed, preallocated (77.5 B/slot: 56 B entry + 4 B index + 4 B epoch stamp, at 2x slot over-provisioning)
Transposition storage, 200,000-entry capacity~51 MB at capacity16,194,304 B, fixed
Cache occupancy at d4s522,743 of 60,000 = 37.9 %identical, by construction
Allocations inside one decision~15–30 million (section 2.4)0 (every buffer is preallocated at construction; the only allocation the fast search can make is the exception object if the work bound is hit)
Leaf scratch~5.5 kB zero-initialised per leaf call (≈4.2 GB of writes per depth-4 decision)one reused ~2.4 kB member per search object
Process peak resident, both arms in one process, d4s518,096,128 B
Process peak resident, d4s7 (200,000-entry cache)50,892,800 B
Process peak resident, d5s7 probe (200,000-entry cache)77,742,080 B
Process peak resident, profile (six search objects + corpora)62,476,288 B

The reference figures marked "estimated" are derived from the libstdc++ node layouts, not measured; the fast figures are reported by the table itself. At 30 threads the fast engine's 16.2 MB table at depth 5 is 486 MB of resident transposition storage, comfortable on a 131 GB host but not comfortable in a 64 MB L3, which is one reason the table's measured benefit is small.


8. Rejected, and why — the part that matters most

Every idea below was considered and not shipped, because each would have turned an engineering result into an untested policy change. This repository has already been bitten once by an unstated configuration assumption — a work bound sized for five strata silently degraded a seven-stratum depth-4 search to depth 3 and produced a wrong scientific conclusion (finding-05). The list is long on purpose.

8.1 Rejected because they change floating-point results

IdeaWhy rejected
Vectorise or re-associate fairLeaf's 19-term dot productChanges the summation order, changes the returned double, changes action ranking. The order is pinned to the TypeScript reference for parity.
Replace x / moves_remaining in rise_pressure with x * (1.0/moves_remaining)Reciprocal-multiply is not division. Seven different doubles per leaf.
Multiple partial accumulators in the leaf's per-cell sums, to break the dependency chainClassic, effective, and changes every sum.
float for the addition / release / support arraysHalves the leaf's memory traffic and changes every value.
-march=native, -ffast-math, -ffp-contract=fastWould change FP codegen for the frozen reference too, since it is compiled into the same translation unit. That is worse than useless: it would make the comparator disagree with the repository's own build/fair-depth4 while this document's gate still passed.
Constant-fold elevation*elevation*edge_multiplier into a 49-entry tableNot attempted. acc += e*e*edge is one statement, so clang may contract it to an FMA, and a table lookup cannot reproduce an FMA's single rounding. The gate would catch it, but after L6 the upside is small and the failure mode is silent-if-untested.

8.2 Rejected because they change work, depth, or the action

IdeaWhy rejected
Alpha-beta, move ordering, or root width limitsFull width at every node is part of what fair D4 is (audit-02 I1). Any pruning changes work and can change the column.
Share chance subtrees between sibling columnsChanges work and the sampled scenarios. New candidate.
Skip the depth-1 and depth-2 iterative-deepening passes when the work bound provably cannot bindChanges work, and removes the completed-depth fallback that makes a work-limited decision consistent rather than partial.
Raise the transposition capacity so depth 5 never evictsChanges cache semantics and therefore work. It is a legitimate configuration choice that must be declared per configuration, not smuggled in as an optimisation. Both arms in sections 5 and 6 use the same declared cap.

8.3 Rejected because they rest on an unchecked invariant

IdeaWhy rejected
First-wave restricted popper scan. A board handed to playMove provably has no poppers (the previous cascade ran to completion), so after placing a disc only that disc's row and column can pop — 13 candidate cells instead of 49.Exactly equivalent given the invariant, and the invariant is nowhere enforced. It would be correct today and silently wrong the first time any caller hands the engine an unresolved board. If wanted, it must ship with a debug-build cross-check against the full scan, exercised by the gates.
isBoardEmpty as "the bottom row is empty", valid because gravity keeps every board settledSame objection, for ~4 ns.
Deriving vertical run length from column height, valid for the same reasonSame objection.

8.4 Measured, provably value-preserving, and deliberately not taken

Leaf memoisation. The census counts how often the same leaf state is evaluated more than once inside one decision: 264,655 of 764,899 leaf calls, 34.6 %. fairLeaf is a pure function of (board, next disc, moves remaining), so — unlike the search's own transposition table — a leaf memo cannot change its value at any capacity; hit rate would affect speed only. Work counts would also be unchanged, because work is incremented in evaluateLeaf before the value is produced. By the letter of docs/benchmarks.md it is a pure optimisation: it changes no random event, no completed depth, no logical work, no floating-point ranking and no selected column.

It is not shipped anyway, for two reasons.

  1. It is a cache-semantics change, and docs/benchmarks.md requires a comparison to freeze and declare "per-decision depth, work, action width, chance samples, random-domain derivation, cache semantics, and model bytes". It needs its own declaration, its own memory accounting and its own gate — not a footnote in an engineering finding.
  2. Its payoff is unmeasured and not obviously positive. A table large enough for ~500,000 distinct leaf states per decision is ~20 MB per thread; probing it 765,000 times per decision is 765,000 random accesses that would evict the leaf's own working set from a 64 MB L3 shared with 30 sibling threads. This document already shows the transposition table's 4.4 MB doing exactly that (section 3.3). 34.6 % is the headroom, not the gain.

Recorded here so a follow-up can decide with the number in hand.

8.5 A bug caught by writing the gate first

The first isBoardEmptyFast read seven uint64 words out of a 49-byte std::array — a seven-byte out-of-bounds read — and masked the wrong end of the final word. It was replaced before it ever produced a number. Recorded because it is precisely the defect that a "it's faster and the answers still look right" workflow does not catch.


9. Limitations

  • Not a clean performance baseline. Section 1. Nothing here may be promoted into research/benchmarks/profiles-v1.json or compared with a timing from another machine or another load.
  • The trajectory gate's frozen depth-4 arm is 96 seeds × 45 moves, not 4,096 seeds; the 4,096-seed breadth comes from the deterministic arm and a depth-3 search arm. Section 4D explains why this is still a valid engine test and what it buys less of.
  • The search-parity grid is deep but not wide: 50 moves per configuration at depths 1–3, 10 at depth 4, 3 at depth 5. Depth-5 parity rests on three decisions — each of which is tens of millions of work units, so it is strong evidence per decision and thin evidence across positions.
  • No PILOT/SCREEN/STANDARD cohort was run and no strength claim is made. The fast engine has not produced a single point of score evidence.
  • Two of the three trajectory arms (center, d3fast) were run on the build immediately preceding the L7 roughness removal. That change is confined to fastFairLeaf and cannot affect engine mechanics; the leaf's bit-exactness after it is separately gated on all 225,183 corpus leaves, and the depth-4 arm ran on the final build.
  • Section 6's 55,765,609 work/move for depth 5 at seven strata was measured at a declared cache capacity of 200,000 entries. Capacity changes work by up to 2.2x at that configuration without changing any decision; see finding-14 §3. Never compare work across capacities.
  • The 30-thread figures in section 6 are arithmetic, not measurement. No parallel scaling preflight was run, as docs/benchmarks.md §"Using the operating system well" requires before a throughput claim.
  • A contribution record under research/contributions/ is owed and not written. This work package was constrained to create files only under approaches/lifetime-objective/fast-engine/ and docs/exploratory/, and research/ belongs to a concurrent contributor. The coordinator must add it before this is done under AGENTS.md.

10. Reproduce

./approaches/lifetime-objective/fast-engine/build.sh          # clang++ only
B=./build/fast-engine

# Gates
$B/gate-leaf       --games 3 --max-moves 45 --leaves 500000 --per-root 600
$B/gate-search     --anchor-games 2 --anchor-moves 30 --parity-games 2 \
                   --parity-moves 25 --reflect-games 2 --reflect-moves 20 \
                   --grid 1x5,2x5,2x7,3x5,3x7
$B/gate-search     --anchor-games 1 --anchor-moves 1 --parity-games 1 \
                   --parity-moves 10 --reflect-games 1 --reflect-moves 1 \
                   --grid 4x5,4x7
$B/gate-search     --anchor-games 1 --anchor-moves 1 --parity-games 1 \
                   --parity-moves 3 --reflect-games 1 --reflect-moves 1 \
                   --grid 5x5,5x7
$B/gate-trajectory --policy center --games 4096 --threads 8
$B/gate-trajectory --policy d3fast --games 4096 --threads 8 --seed-start 0xa5271000
$B/gate-trajectory --policy d4     --games 96   --threads 8 --max-moves 45 \
                   --seed-start 0xa5276000

# Profile, in-leaf profile and ablation
$B/profile      --games 2 --max-moves 30 --decisions 24 --repeats 3
$B/leafprofile  --games 1 --max-moves 25 --leaves 8000 --reps 60

# End to end and the depth-5 price
$B/bench --mode ab --grid 3x5,3x7 --games 4 --max-moves 2000 --repeats 3 --cache 60000
$B/bench --mode ab --grid 4x5     --games 2 --max-moves 30   --repeats 3 --cache 60000
$B/bench --mode ab --grid 4x7     --games 1 --max-moves 12   --repeats 3 --cache 200000
for d in "4 5" "4 7" "5 5" "5 7"; do set -- $d;
  $B/bench --mode probe --probe-depth $1 --probe-strata $2 --decisions 3 \
           --repeats 3 --probe-baseline 1 --cache 200000; done

Every one of these exits non-zero on any mismatch. Repeat the timing commands on an exclusive machine before quoting any absolute number from this document.

These documents are written for researchers. For the same ideas in plain language, with animations, start at how the game works and the concepts primer; every term is defined in the glossary.