Ataraxos Beats a Stratego Champion by Searching Over Beliefs, Not Just Moves

A multi-university research team has reported a superhuman result in Stratego, a board game whose difficulty comes less from the number of legal moves than from what neither player can see. Its system, Ataraxos, defeated Pim Niemeijer in a 20-game match with 15 wins, one loss, and four draws, according to the peer-reviewed Nature paper published on September 30.

The Hacker News link to Ars Technica’s report had 198 points and 19 comments when checked at 1:03 p.m. Malaysia time on October 3. That is a useful attention signal, but the paper is the evidence. Its central contribution is a practical way to combine self-play, a learned model of hidden information, and test-time search without enumerating every possible private board.

What happened

Stratego begins with each player arranging 40 concealed pieces. A piece’s identity is normally revealed only when combat occurs. The game therefore asks a player to infer what the opponent probably has, preserve several explanations at once, and choose moves that remain useful when those explanations are wrong.

Ataraxos separates setup selection from move selection. Two transformer-based policies learn those phases through interdependent self-play. A third transformer, the belief network, is trained to predict the hidden identities of opposing pieces from the information a player could legitimately observe.

At decision time, the belief network samples plausible complete states. The move policy rolls out candidate actions from those samples, averages the resulting value estimates, and makes a controlled policy update before choosing a move. The system is not reading the hidden board. It is searching over a learned distribution of boards that could explain the visible history.

The paper reports that the reinforcement-learning run used 16 Nvidia H100 GPUs for one week, while belief-model training used four H100s for four days. It also reports 163 million completed self-play games, 208 billion environment steps, and roughly 10 million simulated board-state updates per second in the custom CUDA engine.

Why it matters

Many widely discussed test-time reasoning systems operate in domains where the current state is fully specified: a proof, a source tree, or a chess board. Real decisions are often different. A security system does not know an attacker’s intent, a support agent does not know which facts a customer omitted, and a robot sees only part of its environment.

Ataraxos shows one disciplined pattern for those cases. First learn a policy from experience. Then learn a separate model of the missing state. At inference time, sample several plausible states rather than committing to one guess, evaluate actions across them, and update conservatively.

That pattern is more interesting than the headline victory. The belief network can be wrong, but a distribution of hypotheses gives search a way to express uncertainty. It also makes the failure mode inspectable: researchers can study calibration, out-of-distribution opponents, and sensitivity to the sampled boards instead of treating uncertainty as an unobserved property inside one policy.

Evidence

The paper says Ataraxos used roughly one five-hundredth of the compute cost, one thirtieth of the self-play games, and one hundredth of the training examples of the prior DeepNash work under the authors’ comparison. Those ratios should be read as paper-reported estimates, not as a neutral cloud invoice. Hardware, implementation, and accounting choices affect any such comparison.

The authors attribute much of the efficiency to decomposition and engineering. Setup and play use different transformer forms because they are different tasks. Training keeps only moves with large estimated advantage magnitude for some updates; the paper says this reduced wall-clock time per reinforcement-learning iteration by about 2.5 times while improving sample efficiency. The CUDA simulator avoids storing quantities that can be reconstructed and supports fast resets for search.

The human match is stronger evidence than evaluation only against the system’s own training distribution. Niemeijer could choose unfamiliar setups and play styles. The belief model used dropout during training partly to generalize beyond the final self-play policy. Still, one match against one elite opponent is not a population study, and the paper does not prove that the method transfers cleanly to unrelated hidden-information tasks.

Practical takeaway

Teams building agents under uncertainty can borrow four design questions without borrowing the game system itself:

1. What is hidden? Separate unknown state from ordinary prediction error.
2. Can the unknown state be modeled explicitly? Generate several plausible explanations rather than a single story.
3. How will actions be tested across those explanations? An action that wins only under one fragile guess may be worse than a robust option.
4. How will belief quality be measured? Track calibration and recovery when observations contradict the model.

The architecture also argues for modularity. A policy and a belief model have different training targets. Keeping them separate makes it easier to test whether poor decisions come from bad action values or bad assumptions about hidden state.

Limitations

Stratego supplies stable rules, a fast simulator, exact outcomes, and unlimited self-play. Most business and scientific environments supply none of those advantages. Their hidden states may change while an agent reasons, feedback may arrive late, and simulation may encode the same blind spots as the model.

The belief network is trained on trajectories from Ataraxos’s final policy. Unusual opponents can therefore move the game away from its familiar distribution. Search also inherits the move network’s value errors. Sampling more possible boards does not help if the model assigns very low probability to the true one or evaluates all of them badly.

Ataraxos is best read as a research result about scalable decision-making in one difficult imperfect-information game. It is not proof that more inference compute automatically solves uncertainty. Its useful lesson is narrower: represent uncertainty explicitly, test actions across multiple plausible worlds, and engineer the simulator and update rule as carefully as the neural network.