Reports · 2026-09-18

Knowledge-limited subgame solving loses to expectimax at both budgets

The searcher is the order-1 KLUSS construction of Obscuro (Zhang and Sandholm, 2025) with sampling in place of enumeration. At each move it draws 64 worlds from the counting belief, adds 4 shadow states per world that resample the searcher's own hidden pieces as the opponent would see them, grows the sampled subgame by one-sided GT-CFR expansion guided by PUCT, solves it with predictive CFR+, and plays the purified last iterate of the strategy at the real root information set. The leaf, the belief and the rules are identical to expectimax's; only the shape of the search differs. The implementation is the armies-solve crate, registered as kluss, with the full parameter list in server/docs/search.md.

Calibration and cost

The bench (cargo run --release -p armies-solve --bin bench, one thread, twenty random middlegame positions, other jobs sharing the machine) gave the registered budgets: 5,000 expansions at 219 ms per move (168 ms on a quieter repeat) and 10,000 at 822 ms (1,024 ms quieter). Time grows faster than linearly in the expansion budget because every CFR sweep walks the whole grown tree; 20,000 expansions already costs 4.9 s per move and 50,000 costs 40 s. In the arena the two cells measured 415 ms and 1,592 ms per kluss move against expectimax's 6.4 ms and 6.0 ms: opening positions branch more than the bench's middlegame ones, so the in-game cost runs about twice the bench figure, and in both cells kluss was the more expensive player by two orders of magnitude.

What the games show

Both cells played 200 games. The 200 ms cell ended 192 by Flag capture, 7 with a side out of moves and 1 at the battleless limit; the 1 s cell ended 191 by Flag capture and 9 with a side out of moves, so kluss did not lose by stalling and the games look like ordinary Stratego. The score rose from 26.8% to 33.5% when the budget doubled, so the search is on a rising part of its curve; the registrations answer only the two measured budgets.

The diagnostic trace says the solver itself worked. The root value moved by 0.0005 on average over the last fifth of the sweeps (measured on twenty middlegame positions at both budgets with cargo run --release -p armies-solve --bin trace), so predictive CFR+ had converged on the grown tree, and the root strategy kept 2.4 to 2.5 actions alive on average: the mixing the method exists for is present. The information accounting is visible in the games, too: across the 200 games of the 200 ms cell kluss attacked into Bombs 355 times against expectimax's 643, and at the 1 s cell 420 against 581, so the searcher does price what the opponent might believe. What it cannot afford is depth: 5,000 to 10,000 expansions spread over 320 root states leave each world's line about two plies tall, where expectimax concentrates its whole node budget on sixteen worlds with alpha-beta cut-offs. The subgame equilibrium on a shallow tree loses to plain tactics on a deeper one, which is the disproof the study registered for: a few hundred samples over Stratego's information sets leave the search too thin at these budgets.

Replays from the library: kluss as Red at 1 s, as Blue at 1 s, as Red at 200 ms and as Blue at 200 ms.

What this means for the portfolio and belief studies

The portfolio study (T2) now starts from a weaker full KLUSS than expected: if limiting the opponent to one or two strategies lets the same budget grow a deeper tree, the 50 ms crossing the theory predicts may sit below 200 ms, and the interesting comparison moves down in budget. The belief study (T3) matters more, not less: kluss loses fewer pieces to hidden Bombs than expectimax even with the counting prior, so a belief that knows where Bombs live should pay a subgame solver at least as directly as it pays expectimax. And the smoke observations behind this run (ten-game plumbing checks, not evidence) hint that purification may be costing strength at small budgets: with purify 1 kluss scored 5 of 10 against greedy, with the registered purify 3 it scored 2.5 of 10; the ablation is a candidate for a future registration.

Run records: 200 ms cell, 1 s cell.

cd server && cargo run --release -p armies-solve --bin bench
cd server && cargo run --release -p armies-arena --bin matchup -- --red 'kluss 200ms=kluss:{"samples":64,"shadows":4,"expansions":5000,"cfr_every":64}' --blue 'expectimax:{"samples":16,"depth":2}' --games 200 --seed 0 --rules training --threads 8 --record-dir ../research/runs/516cedd8-8bf2-4ae8-b287-c0ab50ce019c/records --out ../research/runs/516cedd8-8bf2-4ae8-b287-c0ab50ce019c/matchup.json --tag 516cedd8-8bf2-4ae8-b287-c0ab50ce019c
cd server && cargo run --release -p armies-arena --bin matchup -- --red 'kluss 1s=kluss:{"samples":64,"shadows":4,"expansions":10000,"cfr_every":64}' --blue 'expectimax:{"samples":16,"depth":2}' --games 200 --seed 0 --rules training --threads 8 --record-dir ../research/runs/05d831b0-d37b-4f03-8930-49fc8541340a/records --out ../research/runs/05d831b0-d37b-4f03-8930-49fc8541340a/matchup.json --tag 05d831b0-d37b-4f03-8930-49fc8541340a
cd research && python3 scripts/build_kluss_assets.py && just records