Rust bitboard engine

Packed cascadeOne wave in three machine views

The recorded wave begins in seven packed column words, derives row-major masks for the explosion, and writes the crack and reveal back before gravity. The loop that repeats these steps is in engine.rs.

On this page

Approach page

Source

lib.rs

Records31

Theories8

A nibble-packed column-major Rust engine reproduces fair expectimax bit-for-bit faster than the C++ fast engine
A centralized deterministic frontier scheduler keeps deep fair search workers busy across columns
A depth-5-distilled, whole-game-evolved NNUE leaf beats the frozen fair leaf inside the same depth-3 search
One Rust search-matrix config reproduces depth, strata, and leaf comparisons locally and on EC2
Klein-Friedmann six-feature linear Q-learning transfers to corrected Hardcore as a survival heuristic, not a scoring policy

Show all 8Show fewer

Experiments12

Show all 12Show fewer

Results11

Show all 11Show fewer

Used by

Playground policies rust-fair-d6-s7 and rust-fair-d7-s7
The analyzer and cluster workflow (RS-20260825T052959Z-57698687)
The KF linear-Q Rust transfer experiment
The pruned-search gameplay pilot

Motivation

Looking ahead means simulating many possible drops before choosing a column. The same small operations repeat throughout the search: move discs, evaluate the resulting board, and check whether an earlier branch already solved it. An unnecessary scan or memory access in those operations repeats too.

The C++ fast engine already stores rows in packed words, and uses certain optimizations to operate on them. When developing this bitboard engine, all of the assumptions were challenged, including whether to pack rows or columns in each 32-bit word.

How it works

Store each column in a machine word. Each cell occupies a four bit nibble, with the bottom cell at the low end. A rise shifts the word and inserts a covered disc. Gravity gathers the surviving nibbles in their existing order. On an x86 build with BMI2 instructions, that gather uses PEXT; other targets use an equivalent portable implementation.

Board representationForty-nine cells in seven registers

Shows how a board position is represented as seven u32 words used by Board, where each column uses 4 bits per cell.

At a leaf, where look-ahead stops and the board is scored, unpack the columns into a row-major byte array. The fair evaluator reads cells and neighbours repeatedly, so this conversion happens once per evaluation. BMI2 builds use PDEP to spread a column's nibbles into bytes. Portable builds now extract those nibbles with direct shifts, avoiding the general-purpose bit-scatter loop. The feature definitions and their floating-point accumulation order stay the same. This makes the portable conversion explicit; a shorter source path alone does not establish fewer machine instructions.

board.rsA byte view suited to the target CPU

Rustlines 250–272

    pub fn to_bytes(&self) -> [u8; CELL_COUNT] {
        let mut out = [0u8; CELL_COUNT];
        for col in 0..BOARD_SIZE {
            #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
            {
                let spread = pdep64(self.cols[col] as u64, 0x0F0F_0F0F_0F0F_0F0F);
                for nibble in 0..BOARD_SIZE {
                    // nibble n of the column word is row (6 - n).
                    out[(BOARD_SIZE - 1 - nibble) * BOARD_SIZE + col] =
                        (spread >> (8 * nibble)) as u8 & 0xF;
                }
            }
            #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
            {
                let word = self.cols[col];
                for nibble in 0..BOARD_SIZE {
                    out[(BOARD_SIZE - 1 - nibble) * BOARD_SIZE + col] =
                        (word >> (4 * nibble)) as u8 & 0xF;
                }
            }
        }
        out
    }

Both architecture paths produce the same row-major cells. The packed columns remain the engine's stored board.

Build a release-support list only when the disc needs one. The leaf estimates whether other discs could clear and shorten a run that is too long for its number. When the run is already short enough, this release term is zero. Checking that condition before scanning neighbours avoids building and discarding a list. Solid covered discs also need only their two strongest neighbouring supports, which can be selected without sorting the full list. Cracked discs retain their sorted multiplication order so their value bits stay unchanged.

leaf.rsCheck whether release support can contribute

Rustlines 476–496

        let value = cells[index] as i32;
        let horizontal_excess = horizontal.length[column] as i32 - value;
        let vertical_excess = vertical.length[row] as i32 - value;
        // Release is exactly zero unless the run is longer than the disc's
        // value. Avoid gathering a supporter inventory that cannot be read.
        let horizontal_release = if horizontal_excess > 0 {
            let mut support = [0.0f64; BOARD_SIZE];
            let mut count = 0usize;
            let mut scan_col = horizontal.start[column] as i32;
            while scan_col <= horizontal.end[column] as i32 {
                let supporter = row * BOARD_SIZE + scan_col as usize;
                if supporter != index && scratch.present(supporter) {
                    support[count] = scratch.addition[supporter];
                    count += 1;
                }
                scan_col += 1;
            }
            release_readiness(horizontal_excess, &mut support, count)
        } else {
            0.0
        };

The horizontal support scan runs only when the occupied run exceeds the disc's value. The vertical scan applies the same check.

Check the cache's depth threshold before building a key. A transposition table remembers the value of a position reached through another branch. The threshold is the remaining search depth at that position. Raising it skips shallow cache accesses, including key packing and hashing, while allowing deeper results to be reused. Capacity controls allocated memory separately: raising the threshold does not shrink an already allocated table.

search.rsReject shallow cache work before hashing

Rustlines 428–438

        // The shallow majority never packs a key or executes its three mixes.
        let cache_key = if self.table.accepts_depth(depth) {
            let key = PackedKey::new(state, depth);
            let hash = hash_key(&key);
            if let Some(cached) = self.table.lookup(&key, hash, depth) {
                return Ok(cached);
            }
            Some((key, hash))
        } else {
            None
        };

The search constructs and hashes a packed key only after the table accepts this remaining depth. A cache-free search rejects every depth.

Choose who owns the table. Private tables let workers access their own memory without locks. The optional shared table lets a worker reuse another worker's completed result during the same decision. Slots are grouped into stripes, with one lock protecting each group's full keys and values. A worker tries the lock once; a busy stripe becomes a cache miss, so the worker continues its own search. Two workers can still compute the same subtree before either has published a result. Grouping slots bounds the number of locks, including runtime lock allocations on platforms that need them.

shared_table.rsReuse only a complete matching entry

Rustlines 111–127

    #[inline]
    fn lookup(&mut self, key: &PackedKey, hash: u64, depth: i32) -> Option<f64> {
        if !self.accepts_depth(depth) {
            return None;
        }
        let index = hash as usize & self.storage.mask;
        let stripe = self.storage.stripes[index & self.storage.stripe_mask]
            .try_lock()
            .ok()?;
        let slot = &stripe[index >> self.storage.stripe_shift];
        if slot.depth > 0 && slot.key == *key {
            self.hits += 1;
            Some(slot.value)
        } else {
            None
        }
    }

A nonblocking lookup compares the entire position key while holding its stripe lock. A busy stripe or a different key returns a miss.

Reduce finished tasks in the original order. A central work queue distributes continuation subtrees across workers. Results go into fixed slots, then the coordinator combines them in the same column and chance-sample order as the sequential search. Shared storage is created afresh for each decision, so results cannot survive a change of evaluator or search settings. Private tables remain the default.

The existing gravity and cover-hit diagrams show the packed operations that precede leaf evaluation.

Gravity and riseThe mask moves whole nibbles

word

·0305001

0x00305001

↓ nonzero_flags(word)

flags

·0101001

0x00101001

↓ flags × 0xF

mask

·0F0F00F

0x00f0f00f

↓ pext32(word, mask)

result

·0000351

0x00000351

The 3, 5, and 1 keep their order as the holes disappear.

same gather in the recorded wavec3 0x00000090 → 0x00000009c4 0x00000010 → 0x00000001

The gravity example is the exact three-disc case in the board test. nonzero_flags marks one bit per occupied nibble, multiplying by 0xF selects all four bits, and PEXT gathers the selected nibbles in order. The recorded cascade uses the same operation for 0x90 → 0x09 and 0x10 → 0x01.

The explosion bitplanes diagram shows an efficient mechanism for counting hits and double hits for a single wave of a chain reaction.

Explosion waveFour shifts count every adjacent hit

explosion bitboard

popping0x380000000000

↓ four edge-safe shifts

one neighbour mask per direction

up = popping >> 70x7000000000

down = (popping << 7) & BOARD_MASK0x0

left = (popping & NOT_COL0) >> 10x1c0000000000

right = (popping & NOT_COL6) << 10x700000000000

xoradds each cell without carrying into its neighbourandmoves carries into the twos and fours planes

bit-sliced hit count

ones0x6c7000000000

twos0x100000000000

fours0x0

any_hit = ones | twos | foursmulti_hit = twos | fours

solid ∩ exactly one hit

→

c3: 0x83 → 0x90

cracked ∩ any hit

→

c4: 0x93 → 0x10

This is the first wave of the recorded move. The three bottom-row 3s form the explosion mask. Four shifts feed the bitwise counter in clear_wave; its one-hit plane cracks the solid 8, while any hit reveals the cracked 9 as the next recorded value, 1.

Results

The updated search ran 1.07× faster on six constructed root positions over five alternating repeats, with identical completed-search values and actions. The leaf batch also used fewer instructions. The optimization result retains the configuration, every repeat, and the limits of this local measurement.

The portable unpacking rewrite produced no credible standalone speedup. Its nearly unchanged instruction count suggests the compiler already simplified the old constant-mask scatter. The direct shifts remain a clearer expression of the fixed conversion.

The capacity sweep shows diminishing returns: the middle-sized table already removed most of the work saved by the largest tested table. Raising the minimum cached depth lost useful shallow hits without reducing allocated table memory. The default remains private storage with a minimum depth of one.

Cache capacity and search time

Cache from depth 1
Cache from depth 2
Cache from depth 3

The constructed-root cache sweep compares capacity and minimum remaining depth. The recorded timings and memory describe these search configurations, with no game-score comparison.

Notes and sources

Six constructed public roots per repeat, five alternating-order repeats on an interactive Apple M3 Pro. Depth 4, seven chance strata, completed searches with exact value checks. Whiskers show the minimum and maximum repeat times, not confidence intervals. CHECK mechanics evidence; these roots and elapsed times do not measure playing strength. The table view lists the plotted values and their sources.

RS-20260905T193830Z-9733627a

Spec: web/content/figures/rust-cache-capacity.json · 1 source record · kind line

Sharing helped modestly when several workers searched the same decision. At four workers and the shallow cache threshold, it reduced median logical work by 5.2% and retired instructions by 3.9%, with a 1.03× ratio of latency medians. The one-worker shared arms were slightly slower. Both scopes had the same total entry budget; shared storage also needed its bounded lock allowance.

Private and shared search caches

Private
Shared

Private and shared caches are compared at equal total entry capacity across worker counts. Shared-table memory includes its lock allowance; the result records the cost as well as the saved work.

Notes and sources

RS-20260905T193830Z-9733627a

Spec: web/content/figures/rust-shared-cache.json · 1 source record · kind bar

What we learned

A column layout suits gravity, while a byte view suits the fair leaf's repeated cell reads. Avoiding the conversion would require making those reads cheaper elsewhere. The current changes instead preserve the evaluator and remove work that cannot contribute to its answer.

Cache hit rate alone leaves out the size of the subtree saved by each hit. Depth, table capacity, and worker ownership therefore need to be measured together with elapsed time, CPU use, and memory. Shared caching offers another trade-off: more opportunities for reuse, plus lock traffic and contention.

Chess engines suggest further experiments. Stockfish groups entries and uses depth and age when choosing replacements. Its compact signatures and racy multi-field updates have a different correctness contract from the complete key comparisons and synchronized values used here; copying that storage scheme would require changing this engine's exact-value guarantee. See Stockfish's table implementation.

Profile-guided optimization is another unmeasured option: representative execution profiles can guide inlining, code layout, and register allocation. Which of clustered full-key storage or compiler profiling saves more time on the intended CPU remains an open question.

Agent contextRecords and provenance

The current engineering check is EX-20260905-rust-bitboard-improvements-check-c68c07b7, under theory TH-20260905-rust-bitboard-improvements-1c56b072. Its comparator is the Rust implementation at 7adb6b36412b4bbef25623183dac1a905570cd1a. It opens no new gameplay cohort and makes no policy-strength claim.

The current result is RS-20260905T193830Z-9733627a. The comparison summary is artifacts/results/EX-20260905-rust-bitboard-improvements-check-c68c07b7/RUN-20260905T191558Z-f9e6cb1d/summary.json; the machine profile is research/system-profiles/MACH-20260905T191558Z-4a61bc91.json. The host ran macOS on Apple M3 Pro with Chrome, WindowServer, and Codex active. The check serialized its own measurements and paused its own builds and tests; it had no exclusive CPU or affinity guarantee. These are local engineering measurements, with no claim of maximum machine throughput.

The historical packed-engine result is RS-20260824T075451Z-e89ea128, recorded as valid + pass, mechanics-only evidence from the CHECK experiment EX-20260824-rust-engine-parity-throughput-4036a91f. Its timing host was the shared AMD Ryzen AI MAX+ 395 workstation. The result retains metric summaries; its original local files under runs/RUN-20260824T052018Z-b88c3e22/rust-engine/ may be absent from a clean checkout. The historical table below transcribes the result and does not claim that those missing artifacts were regenerated by the current check.

The historical frontier result is RS-20260825T052959Z-1b3ed9a5, recorded as valid + pass, mechanics-only CHECK evidence on a shared 12-logical-CPU arm64 machine. Its theory is TH-20260825-central-frontier-scheduler-e4f547e0.

The search-matrix and resource-planning result is RS-20260825T052959Z-57698687. It covers the bounded launch workflow and allocation-free plans. No EC2 resource was created by that check, and its large-worker plans are not timing measurements.

Agent contextFull results table

Current before/after measurements from RS-20260905T193830Z-9733627a, using the same six constructed roots and five alternating repeats per arm:

Workload	Baseline median seconds	Updated median seconds	Ratio of batch medians	Recorded instruction reduction
Depth 4, seven strata, gate 1, 16,384 entries	12.052394167	11.257799041	1.07058×	4.4384%
Leaf batch, 1.2M calls per repeat	0.604415917	0.516645375	1.16989×	10.6541%
Unpack batch, 1.2M calls per repeat	0.004975042	0.005177292	No credible gain	About 0.059%; effectively unchanged

The depth-4 gate-1 comparison also had a 1.0678604115× median paired speed ratio, with repeat ratios from 1.0582717724× to 1.1158545109×. The table above uses ratios of batch medians.

The complete depth-4 search retained 39,288,466 logical work units in each arm. Its median process CPU time fell from 11.93 to 11.15 seconds. Median retired instructions fell from 222,843,607,698 to 212,952,842,410; the leaf batch fell from 10,346,642,712 to 9,244,298,981. These counts cover the timed process and its harness. They do not imply the same gain on other CPUs or board distributions. The unpack batch's CPU time is near the host's printed timer resolution and cannot support a precise CPU-time claim.

The unpack batch recorded 109,784,960 versus 109,720,197 median instructions. Its source rewrite did not demonstrate a useful instruction saving or a latency improvement. The combined leaf and search measurements support the retained optimization package; they do not isolate the contribution of every changed leaf branch.

The capacity sweep's gate-1 rows, each using five repetitions of six roots:

Entries	Allocated table bytes	Median search seconds	Logical work units
1,024	49,152	13.765320707	47,250,952
16,384	786,432	11.305829207	39,288,466
262,144	12,582,912	10.844751666	38,002,223
No table	0	17.604948875	64,858,647

At four workers, gate 1 and 65,536 aggregate entries, private and shared median decision times were 3.108119542 and 3.017273043 seconds. Median process CPU times were 11.75 and 11.37 seconds. Their table projections were 3,145,728 and 3,186,688 bytes, respectively; the shared difference covers stripes and runtime locks. The corresponding median peak process RSS values were 6,029,312 and 5,537,792 bytes. RSS includes the harness and runtime and is reported separately from the layout projection.

Sequential search timers exclude table allocation. Parallel decision timers include planning, allocation, execution, and reduction; do not compare those two timing definitions as a direct scheduler speed ratio. Counter measurements include the whole process. Chart whiskers show minimum and maximum repeat times, not confidence intervals. All 210 timed processes completed within the registered 1,800-second measurement budget.

Historical packed-engine measurements from RS-20260824T075451Z-e89ea128:

Measurement	TypeScript	C++ reference	C++ fast	Rust packed
Engine moves/s	649,471	6,799,180	6,511,760	12,838,933
Leaf ns/evaluation	not recorded	not recorded	187.5	155.6
Depth 4, seven strata, ms/decision	not recorded	3,247.8	1,071.5	907.6 with 64k entries
Depth 5, seven strata, ms/decision	not recorded	23,992.6	7,817.3	7,047.1 with 1M entries
Engine moves/s, 16 game workers	not recorded	not recorded	82,364,000	129,483,860

The retained result's depth-4 timing used 21 decisions, best of three; depth-5 timing used three decisions in one repeat. The move-throughput game's exact count and the leaf timing's evaluation count are not carried in the retained metric summary. The parity panels below are separate workloads and must not be used as the timing sample counts.

Historical Rust cache arm	Depth 4, seven strata, ms/decision	Depth 5, seven strata, ms/decision
No table	1,633.4	63,325.4
Direct mapped, 64k entries	907.6	not recorded
Direct mapped, 256k entries	not recorded	7,787.9
Direct mapped, 1M entries	not recorded	7,047.1
Direct mapped, 4M entries	not recorded	6,748.4

The same historical result records work falling from 11.9M to 6.3M units at depth 4 (47%) and from 582.7M to 59.5M at depth 5 (90%). Its reported node hit rates are 1.3% and 1.36%, respectively. These summaries describe the original measurement configurations.

Historical allocation	Bytes recorded
Rust board	28
Rust searcher excluding table	2,496
Rust table, 64k entries	3,145,728
C++ fast table	16,194,304

Historical scheduler measurements from RS-20260825T052959Z-1b3ed9a5:

Configuration	Roots per repeat	Repeats	Root median seconds	Frontier median seconds	Recorded speedup	Task-phase busy fraction
Depth 4, seven strata, 12 workers	8	3	4.076978	3.232507	1.2612×	0.9951
Depth 5, seven strata, 12 workers, bounded split	3	3	22.034955	19.410905	1.1352×	0.8823
Depth 5, seven strata, over-expanded split	not separately recorded	not separately recorded	24.959552	24.707506	1.0102×	0.9963

The over-expanded split increased logical work from 381,642,037 to 539,523,663. Its higher worker occupancy did not meet the speed gate.

The historical allocation-free depth-7, seven-stratum plan for 192 workers selected one internal split ply, at most 2,401 frontier tasks, and projected 2,418,377,728 bytes under an 8 GiB guard. The old 16,777,216-entry table per worker was rejected before allocation at 154,618,822,656 bytes. These are plans from RS-20260825T052959Z-57698687, with private tables under that version's layout; the current shared-table layout must be planned again.

Agent contextValidity, gates and limitations

The current leaf regression test compares every feature's raw f64 bits against a preserved test-only copy of the pre-change evaluator on constructed public boards, including sparse positions, dense positions, holes, solids, and cracked discs. The unpacking test compares direct extraction with the original PDEP expansion and scalar cell reads. These mechanics checks do not measure playing strength.

The current result records 40 passing Rust release tests, six C++ leaf comparisons, and six complete depth-4/seven-stratum root comparisons. Native bit parity uses -ffp-contract=off. The C++ trajectory check compared 575 moves across 32 fixtures, and the TypeScript check compared 660 moves across 32 fixtures, with zero mismatches. The root npm suite passed 144 tests with two skips. make -k test passed its native and TypeScript gates but failed the aggregate target on 96 errors for missing historical artifacts. The web build, typecheck, lint and 70 web tests pass. The separate chart library retains one pre-existing stale snapshot assertion (63/64 pass); the route sweep passes 727/728, with /compete lacking local authentication configuration. All eight missing-data render checks pass. These checkout limitations remain disclosed in RS-20260905T193830Z-9733627a.

Completed searches must retain identical legal-column values and actions. Different cache settings can change realized work counts, especially when shared-table access depends on scheduling. A fixed work limit can therefore stop configurations at different depths. Claims about unchanged bounded-work fallback require the same cache configuration.

Every shared-table entry belongs to one decision with one parameter set and one deterministic leaf definition. A hit compares the full packed board, next disc, moves until rise, and remaining depth. Terminal states return before lookup. The hash only selects a slot. All workers must produce the same leaf value for the same public state; each worker's scratch memory is private. A shared table does not persist across games or evaluator changes.

The exact comparison covers the canonical search view and its established column order. The inherited floating-point leaf accumulation and tied-action rules are preserved; this check does not establish bitwise reflection equivalence of independently evaluated raw, mirrored boards.

The original packed-engine result records these separate parity panels:

Historical check	Scope recorded	Mismatches recorded
C++ and TypeScript trajectories	512 center-policy games, 256 search-policy games, 256 TypeScript-driver games; 36,427 moves and 40,286 waves	0
Fair leaf	150,854 states	0
Search values and actions	105 depth-4/seven-stratum roots and 10 depth-5/seven-stratum roots	0
Cache independence	105 depth-4/seven-stratum roots with the direct-mapped table	0

These are recorded outcomes from RS-20260824T075451Z-e89ea128. The frontier record separately retains exact root/frontier values, actions, and completed-task counts on its diagnostic roots. It also reports missing historical artifacts that prevented the aggregate validation target from finishing in that checkout, and native floating-point contraction that required -ffp-contract=off for exact parity on arm64. Those limitations are preserved in RS-20260825T052959Z-1b3ed9a5.

The engine has no GPU, latent-mode, or native-scenario variant. Scripted-round and scenario work continues to use the existing engines. A simpler leaf, selective search, or ordinary chess alpha-beta pruning would change the algorithm and needs a separate protocol; Drop7 chance outcomes are averaged.

Agent contextSource files

The source browser below lists this std-only crate. The current control flow is in src/board.rs, src/leaf.rs, src/search.rs, src/shared_table.rs, and src/parallel.rs under approaches/fair-expectimax/rust-engine/.

The analyzer accepts the following cache controls:

Option	Meaning
`--tt-from-depth N`	Cache only nodes with at least N remaining decision plies; this does not change allocated capacity.
`--cache N`	Entries per worker with private scope; total entries with shared scope. Capacity rounds up to a power of two.
`--tt-scope private`	Each worker owns its table; the default.
`--tt-scope shared`	Workers share one fresh table for this decision.
`--threads N`	Worker count; compare scopes at equal total capacity as well as equal wall budget.
`--max-host-bytes N`	Reject a table and frontier plan above the configured memory allowance before allocating it.

For sequential cache experiments, bench search --tt gate2 --tt-capacity N sets the depth threshold and entry count; --tt none disables caching. analyze emits cache scope, threshold, entry count, and projected memory in its plan and decision output.

./build.sh selects target-cpu=native. The trajectory, leaf, and search gates compare against the emitters under cpp/ and the TypeScript driver under ts/. bench_all.sh is the original timing harness; the optimization-check harness follows the current registered comparison.

The bounded matrix workflow is documented in cluster/README.md. Its allocation-free plan is available before any upload or launch. A live cloud run needs its own registered experiment, resource lease, and operator budget.

Agent contextScoring mode

The engine preserves corrected five-move Hardcore scoring, including the 17,000-point rise award. Historical mechanics checks opened no new leased seeds: the original packed-engine experiment used the already-opened SEEDLEASE-A52-FAST diagnostic sub-blocks and probe block documented in its protocol. The current optimization check also opens no new gameplay cohort. Timing improvements do not establish an improvement in mean game score.