2026-10-01
Self-play RL, a belief network and one test-time update beat the most decorated Stratego player 15-1-4, the game's first superhuman result, on a sub-$8,000 training budget.
Imperfect-information games split into two regimes. Poker AIs such as DeepStack and Libratus relied on public-information transformations, but their cost scales with the amount of hidden state: Texas hold'em gives each player only 1,326 starting hands, which is what makes enumeration tractable. Stratego sits at the far end, a 10×10 board with 40 hidden pieces per side and more than 10^33 legal set-ups. DeepMind's DeepNash attacked it with regularized self-play on 1,024 TPU nodes for two to three months, roughly US$3-4.5 million at 2025 prices, yet its 2023 world-championship demo went 19-9 against humans and it lost to most of the highest-ranked players, Pim Niemeijer included. Ataraxos, from a CMU/NYU/Stanford/MIT team, closes the gap for under $8,000.
Three components: a policy-value network trained by self-play, a belief network, and test-time search. Hidden state in Stratego appears at two decision points, so training runs as two interlocking self-play processes. The set-up network is a decoder-only transformer that autoregressively places the 40 pieces in row-major order; the move network is an encoder-only transformer whose policy head emits the full action distribution from a key-query matrix product.
The chronic failure mode of self-play is its feedback loop: overfit to a pattern and the opponent learns it too, and both players lock into an exploitable equilibrium. Ataraxos answers with dynamically damped self-play, annealing regularization strength and update size in coordination: strong regularization with aggressive updates early, weak regularization with small updates late. The set-up network uses maximum entropy, the move network a myopic reverse KL toward the uniform random policy, both on power-law schedules; update size is bounded by a reverse KL to the data-collection policy, PPO-style importance clipping, gradient-norm clipping, and an Adam learning-rate schedule.
Advantage filtering is the counterintuitive piece: gradients are applied only on moves with large advantage magnitude. Training iterations ran 2.5× faster, and sample efficiency and final performance both improved.
The belief network predicts the types of opponent hidden pieces, trained teacher-forced on self-play games, with dropout buying generalization to out-of-distribution human opponents. At search time it serves as a generative model: sample realizations of the hidden state, run depth-limited rollouts for each candidate move with the move network playing both sides, average the value predictions, then apply a single tabular magnetic mirror descent update, with the same reverse KL regularizers, to the current decision only. The evaluation configuration searched 40 plies with 1,000 rollouts at about 1.26 s per move, faster than human play.
The formal evaluation was 20 games against Pim Niemeijer, holder of four world championship titles (tied for most all time), 15 Dutch national championships, two online world championships and more than 600 weeks at world number one: 15 wins, 1 loss, 4 draws, an 85% effective win rate with draws counted half, exact one-sided binomial P < 2.6×10^-4. A 40-game demo at the 2025 World Championship went 38-2-0.
| Matchup | Metric | Result |
| vs Pim, 20 games | Effective win rate | 85% (15-1-4), P < 2.6×10^-4 |
| 2025 World Championship demo, 40 games | Effective win rate | 95% (38-2-0) |
| Barrage, four 50-game series | Series record | Won all four, P < 1.3×10^-5, first superhuman Barrage |
| Hanabi 2-player, max 25 | Mean score | 24.654 ± 0.007, SOTA at every player count |
| Dou dizhu vs PerfectDou | Mean score margin | +0.199 ± 0.015 (+0.350 vs DouZero) |
| Training cost | US dollars | Under 8,000 (DeepNash: 3-4.5 million) |
The sample and compute gap is just as stark. DeepNash consumed about 5.5 billion games and 5-10 trillion training examples; Ataraxos used about 160 million games and 50 billion examples, roughly 30× fewer games and 100× fewer examples at around 1/500 the cost.
The search ablation (Extended Data Table 1, Elo against a fixed reference opponent) is the most instructive table in the paper. Direct sampling from the move network rates 2095; the full search configuration rates 2218. Remove the reverse KL term that anchors search to the move network and Elo collapses to 1733, 362 points below not searching at all. The stated cause: search overfits idiosyncrasies of the move network that fail to generalize to other opponents. Unanchored search amplifies the model's own biases until it plays worse than the network it is built on. Swapping the learned belief model for the uniform-random-policy belief drops Elo from 2218 to 2148, still above no-search.
The play style is distinctive too: about two-thirds of set-ups enclose the Flag in Bombs, with aggressive piece placement and back-corner Flags; its pieces are hard to read, it preserves Scouts longer than humans do, and it fights more bitterly when behind, to the point that some human opponents considered the stalling rude.
First, this is the first rigorously evaluated superhuman Stratego AI, on a budget a university lab can reproduce: the core cost is 16 H100s for one week. Second, the same recipe of self-play plus belief model plus a single search update delivered top results across three game shapes: purely adversarial (Stratego, Barrage), fully cooperative (Hanabi, SOTA at 2-5 players) and mixed cooperative-adversarial (dou dizhu). It reads as a general design pattern rather than per-game tuning. Third, the ablation carries a lesson well beyond games: test-time computation is not free, and search without a regularization anchor can end up worse than no search at all. Anyone treating test-time search as a cure-all should keep that table close.
The authors list their own: history enters through feature engineering rather than temporal learning; stronger spatial-temporal attention or recurrence would improve the belief model, though it brought no out-of-the-box RL gains; search is capped at a single update step, with knowledge-limited subgame solving named as the next step. The evaluation has caveats they also concede: 20 games is a small sample, and the exact binomial test assumes independent, identically distributed games, which real human play is not. No head-to-head with DeepNash took place; DeepMind replied that the DeepNash code is no longer functional. Hanabi and dou dizhu comparisons reuse each paper's own setups rather than a unified re-run, and the direct search-versus-policy comparison comes from the reference-opponent Elo and Barrage, not from the classic-Stratego series against Pim.