Approaches

Subgame solving without common knowledge

Can a game-theoretic search that reasons about what the opponent does not know beat determinized search at the same time per move, and how much of that strength survives when the opponent is limited to a small portfolio of strategies?

The mechanism

Expectimax searches each sampled world with full knowledge, so its strategy is fused across worlds the real player cannot tell apart and it never values information. Obscuro (Zhang and Sandholm, 2025) searches instead over an imperfect-information subgame built from a few hundred positions sampled from the searcher's own information set, plus the positions the opponent might believe possible at distance one in the knowledge graph. The searcher's strategy at those distance-one positions is unfrozen and optimised with the rest (KLUSS), the tree grows by one-sided GT-CFR expansion guided by PUCT, and predictive CFR+ solves it with its last iterate. The move is sampled from a purified strategy: at most three actions, and mixing only when the computed strategy is at least as good as the previous turn's estimate. With a material-only leaf that search still scored 55% against the prior state of the art in Fog of War chess, and 82% behind Stockfish's evaluation.

In Stratego the searcher's information set is far too large to enumerate, so the root sample comes from the belief: the counting prior in the first study, the learned belief network afterwards. The opponent's distance-one positions are sampled by drawing the searcher's own hidden pieces as the opponent would see them. Opponent-limited subgame solving (Liu et al., 2023) shrinks the subgame further: OLSS-I weights how the opponent reaches the root by an opponent model, and OLSS-II lets the opponent choose among N whole-game strategies, which with N of one or two was enough in two-player Mahjong.

The plan

1. kluss-vs-expectimax: a Rust searcher with the hand-written leaf and the counting belief against the 16-world depth-2 expectimax cell at 200 ms and 1 s per move, 200 paired games each.
2. opponent-portfolio: OLSS-II with a portfolio of greedy, expectimax and the searcher's own policy at two temperatures, N in 1, 2 and 4, against full KLUSS at 50 ms, 200 ms and 1 s.
3. learned-belief: the belief network as the root sampler for expectimax and for KLUSS, measured by held-out log-likelihood and by paired matches.

Decision rule

The first study promotes the searcher if the per-seed contrast against expectimax has a 95% interval above zero on 200 paired games at a budget of 200 ms or 1 s, with the time per move measured alone on the machine. The portfolio study reports the crossing budget where full KLUSS overtakes OLSS-II; there is no promotion, only the curve. The belief study promotes the learned belief as the default sampler when both its log-likelihood and its paired match against the prior are separated.

What could disprove it

A few hundred sampled positions may not represent an information set of Stratego's size, in which case the equilibrium gap of the subgame stays large and the searcher plays no better than its leaf. The studies record the gap and the sample counts so that a null result names its cause.

Evidence

The first study is complete and the theory's prediction failed as registered. Knowledge-limited subgame solving loses to expectimax at both budgets: the sampled KLUSS searcher (64 worlds, 4 shadows each, one-sided GT-CFR, predictive CFR+) scored 26.8% effective (21.1% to 33.3%) at the 200 ms calibration and 33.5% (27.3% to 40.3%) at 1 s against expectimax with sixteen worlds at depth 2 on 200 paired games each, with both per-seed contrast intervals below zero. The solver converged and visibly priced hidden information (it attacked into Bombs 355 times against expectimax's 643 in the 200 ms cell), but the tree affordable at these budgets over 320 root states is about two plies tall per world, and that loses to focused depth-2 minimax. The belief study is below; the portfolio study is complete.

The portfolio study found no crossing budget in the measured range (report, 2026-09-19). OLSS-II with a portfolio of one strategy (greedy) or two (greedy plus the searcher's own leaf policy at temperature 0.3) beat full KLUSS at equal wall clock at 50 ms (61.0% and 60.5% effective on 200 paired games) and at 200 ms (62.0%), each per-seed contrast interval above zero, and at 1 s the margin narrowed to 55.0% on 100 paired games with the interval covering zero: the reversal predicted at 200 ms did not happen, and the crossing, if it exists, sits above 1 s where both searchers' cost curves turn sharply superlinear. The solved opponent mixture concentrates on one member (92% greedy), so the portfolio's value is turning the subgame single-agent, not covering many styles. The 200 ms portfolio player still lost to expectimax at sixteen worlds and depth 2 (38.0%, contrast minus 0.240 with the interval below zero), against full KLUSS's 26.8% at the same budget: limiting the opponent closes only part of the gap to plain search. The next registration is the wider portfolio (with the cheap expectimax member) at the 1 s budget against expectimax.

The belief study ran first and is negative at the scale it could train (report, record, 2026-09-19): a 6.4-million-parameter belief network on the self-play of thirty small-preset iterations scored 2.29 nats per hidden piece on the replay library's held-out games against the counting prior's 2.10, worse in every phase and for every acting player, and expectimax at 16 worlds and depth 2 that sampled its worlds from the network scored 45.25% against the same expectimax sampling from the prior on 200 paired games, per-seed contrast minus 0.095 with a 95% interval of minus 0.217 to 0.027. The counting prior is the exact posterior while nothing has moved and everything hidden is exchangeable, and a policy thirty iterations old has little else to teach; the study leaves the promotion condition unchanged and hands the retest to the scaled run's checkpoint, through the Searcher bridge and the two measurement scripts now on main. The other two studies are proposed; each is registered by its agent before a game is played.