Reference

Research program: search under imperfect information

The thesis of this program is that test-time search is the lever that one workstation can pull. DeepNash used no search at inference. Ataraxos gained about 120 Elo from a thousand belief-sampled rollouts per move on top of networks trained on sixteen H100s for a week (Sokota et al. 2025, Figure 4D and Table 17). This machine has one Radeon 8060S and 32 CPU threads, roughly a thirtieth of an H100 on the GPU side but an engine that plays 84 million random plies per second on the CPU side. The question is how much of the paper's strength search can recover when training compute is scarce, and whether the search can be made simpler and faster with the ideas of opponent-limited subgame solving (Liu et al., ICML 2023) and search without common knowledge (Zhang and Sandholm, Obscuro, 2025).

Every theory below is falsifiable, has an owning study, a decision rule and a compute budget on this machine, and is worked by one delegated agent from registration to filed report. The orchestrator reads summaries, never raw output. The operating contract is agents/README.md in the research repository; this page is the science.

Where the evidence stands

Measured on September 18, 2026 (evidence boundary):

Two facts shape the program. First, the search rung is limited by its leaf and its belief, not by depth: expectimax lost 241 attacks into Bombs in 100 games because the counting prior treats every unmoved hidden piece alike. Second, the training loop collects about 4,100 environment steps per second on the small preset (1,024 environments, 60 seconds per iteration), while the engine alone steps a thousand times faster; the loop is bound by network inference and data movement, not by the game.

Theories

Each theory names the mechanism, the falsifiable prediction, the control and what would disprove it. Ownership is one study per theory under approaches/<name>/studies/.

T1. Knowledge-limited subgame solving beats determinized search at equal time

Mechanism. Expectimax searches every sampled world with full knowledge, so it cannot value information, cannot bluff and suffers strategy fusion. Obscuro's search keeps a sampled set of positions consistent with the searcher's own information (a few hundred), adds the positions the opponent might consider possible at distance one in the knowledge graph, unfreezes the searcher's strategy at those positions (KLUSS), grows the tree with one-sided GT-CFR expansion and solves it with the last iterate of predictive CFR+. The result is a mixed strategy that accounts for what the opponent does not know. In Stratego the sampled set is drawn from the belief (counting prior first, learned belief later), and the opponent's distance-one positions are drawn by sampling the searcher's own hidden pieces as the opponent sees them.

Prediction. With the same hand-written leaf and the same counting belief, a KLUSS searcher with a 200 ms budget beats expectimax at 16 worlds and depth 2 on 200 paired games with the per-seed interval above zero. Obscuro's ablation with a material-only leaf still scored 55% against the prior state of the art, so the search should carry strength even before a learned leaf exists.

Disproof. An interval covering zero at 200 ms and at 1 s. The most likely cause is that Stratego's information sets are too large for a few hundred samples to represent the opponent's belief, in which case the study records the sample sizes and the equilibrium gap and stops.

Study subgame-solving/kluss-vs-expectimax. Rust, CPU only, 8 threads for the arena.

T2. Limiting the opponent to a small portfolio keeps most of the strength at a fraction of the cost

Mechanism. OLSS-II lets the opponent choose among N whole-game strategies; with N of one or two the subgame becomes a single-agent problem and was enough to lift a two-player Mahjong agent (Liu et al. 2023, Table 3). For Stratego the portfolio is greedy, expectimax and the searcher's own policy at two temperatures. OLSS-I limits how the opponent reaches the subgame, which here means weighting the sampled root positions by an opponent model instead of uniformly, the same idea as Obscuro's non-uniform Resolve root distribution.

Prediction. At a 50 ms budget, OLSS-II with N of two beats full KLUSS at the same budget; at 1 s the order reverses. Safety is lost when N is small, and the crossing point is the measurement.

Disproof. OLSS-II never beats KLUSS at any budget, or loses to expectimax at every budget. Depends on T1's code.

Study subgame-solving/opponent-portfolio.

T3. A learned belief is worth more than search depth

Mechanism. Every search here samples hidden configurations. The counting prior ignores where pieces started and how they moved; the Ataraxos belief network (encoder over the observation, decoder over hidden types in row order) approximates the posterior under the self-play policy. Belief quality is measured directly by the log-likelihood of the true hidden types on held-out games and indirectly by the strength of every search that samples from it.

Prediction. A belief network trained on the small preset's self-play scores a higher held-out log-likelihood than the counting prior on the replay library's greedy and expectimax games, and expectimax at 16 worlds sampling from it beats expectimax sampling from the prior on 200 paired games. If the second holds and the first does not, the belief is fitting the searcher's own style and the study says so.

Disproof. No gain in either measure. Requires a Rust or batched Python path to sample from the network inside the arena.

Study subgame-solving/learned-belief.

T4. Update-equivalence search adds strength on this machine, and its coefficients transfer

Mechanism. Ataraxos's search is one more damped self-play update computed for the current position from a thousand belief-sampled rollouts of depth 40 played by the move network, with the two reverse-KL coefficients of training. Table 17 says depth and rollouts trade Elo for time, and that dropping the network KL is catastrophic.

Prediction. On the small preset's checkpoint, search with 200 rollouts at depth 10 beats the network alone on 200 paired games, and 1,000 rollouts at depth 40 beats 200 at depth 10. Setting the network KL to zero loses to the network alone, reproducing the paper's sign.

Disproof. Search does not beat the network alone at any setting. The most likely cause is a value head too weak to rank rollouts, which the study checks by the correlation of predicted and realised outcomes.

Study ataraxos/update-equivalence.

T5. A scaled self-play run on one GPU keeps climbing for days

Mechanism. The pipeline exists and trains without entropy collapse. The smoke run stalled into battleless draws, which the paper avoids with its training-rule draw limit and its advantage filter. The scaled run trains the largest network that keeps an iteration under three minutes, with a checkpoint evaluated against greedy and expectimax every twenty iterations by the arena, and a draw-share diagnostic beside the entropy and clip-rate curves.

Prediction. After 48 hours the move network beats greedy on 200 paired games; after 96 hours it beats expectimax at 16 worlds and depth 2. The Elo-against-time curve is the result whichever way it goes.

Disproof. Elo plateaus below greedy for 24 hours, or the draw share rises above half. The run is the user's to launch; the agent prepares the registration, the command, the checkpoint schedule and the monitors.

Study ataraxos/scaled-run.

T6. The training loop can be made ten times faster on this hardware

Mechanism. Collection runs at 4,100 steps per second on 1,024 environments. Suspects, in order: plane encoding and transfer on every step, the sampling over 10,000 actions on the CPU, unfused attention on ROCm, small batches. The paper's remedies are bf16, on-device state and larger batches. The GPU has 95 GiB of unified memory, so batch size is not the constraint.

Prediction. Profiling names one stage above 40% of wall time; fixing the top two stages reaches 40,000 steps per second on the small preset with identical learning curves over ten iterations from the same seed.

Disproof. No stage dominates and the loop is already within a factor of two of the network's forward-pass cost. Then T5 is planned at the measured speed.

Study pipeline/throughput. Engineering study; its evidence is a measured table, not a match.

T7. World models do not buy sample efficiency here, but their infoset model may buy a belief

Mechanism. NashDreamer (Holeček 2026) learns a centralised recurrent state-space model whose per-player infoset models are trained to reconstruct each player's observations, then trains R-NaD in imagination. Its gain is fewer real environment steps. On this machine environment steps are nearly free and inference is the cost, so the sample-efficiency argument does not apply. What might transfer is the infoset model: a learned belief state trained by the centralised objective rather than by a supervised decoder.

Prediction. The share of wall time spent in the environment during training is under 20% (measured in T6), so imagination cannot help. A NashDreamer-style infoset model trained on the same self-play data scores a held-out hidden-piece log-likelihood within 5% of the Ataraxos belief decoder at equal parameters. If it does, it becomes a second sampler for T3; if not, the direction closes.

Disproof. Environment time above 20%, which would reopen imagination as a lever, or an infoset model far below the decoder. The paper's own limitation, full unrolls from the first move, makes imagination over Stratego's hundreds of plies impractical, and the study says so before spending on it.

Study world-model/infoset-belief. Bounded to one GPU-day.

T8. Regularised Nash dynamics under equal compute

Unchanged from the DeepNash approach page: the R-NaD update against the damped clipped loss at equal wall-clock, registered once T5 has a checkpoint schedule to match.

T9. The placement is worth more than a rung for the weak players

Every engine player draws its forty squares uniformly at random, so a quarter of its games start with the Flag in the front row. Mechanism: a sampler that keeps the Flag back and bombed in, the Scouts forward and the Miners back removes the games that are lost before the first move, and a pool of setups selected by self-play removes more, while both stay random enough not to be read.

Prediction. With the move policy identical in both seats, the structured prior beats uniform setups at 95% for greedy, rollout and expectimax; a pool selected by successive halving beats the prior on opposing setups it never met; neither is more exploitable, by the best single opposing setup the same procedure can find, than the source it replaces. The learned setup network of T5 has to beat the pool to justify its cost.

Disproof. A contrast indistinguishable from zero for the searching players (they already survive bad setups), or a pool whose gain vanishes on held-out opponents. Exploratory numbers are on the approach page.

Studies setups/structured-prior and setups/selection-by-self-play. CPU only.

The synthesis experiment

When T1, T3 and T5 have results, the headline registration is the strongest player each family can produce at 1 s per move on this machine:

Each pair plays 200 paired games. The result decides which search goes into the browser and which direction the next pass scales.

Compute plan

Every time-per-move figure is measured alone on the machine and says so.

Order of work

Wave 0, in parallel, no dependencies: pipeline/run-layout (metrics stream, checkpoints, resumable launcher), pipeline/monitor (the TUI and its plugin library), pipeline/throughput (T6), subgame-solving/kluss-vs-expectimax (T1).

Wave 1, after wave 0 files: ataraxos/scaled-run (T5, needs the run layout and the throughput fixes), subgame-solving/learned-belief (T3, needs the belief bridge), ataraxos/update-equivalence (T4), subgame-solving/opponent-portfolio (T2, needs T1's crate).

setups/structured-prior (T9) has no dependency on the networks and can run beside wave 1 as soon as the kluss crate has merged (both touch the policy registry); setups/selection-by-self-play follows it.

Wave 2: world-model/infoset-belief (T7), deepnash/equal-compute (T8), then the synthesis, played with the best setup source T9 found.

What this program will not do

It will not replicate the paper's 16 H100 weeks, will not claim Elo from smoke presets, will not pool results across rule presets, and will not let a policy see a seed, a hidden type or the arbiter state. A theory that fails is filed as prominently as one that holds, with its curves.