AI achieves first superhuman Stratego win at a fraction of the compute cost

An artificial intelligence system called Ataraxos has achieved the first superhuman result in the history of Stratego, the classic board wargame whose massive hidden-information structure has kept machines out of the top ranks for decades. The system defeated Pim Niemeijer, the most decorated human player of all time, by a large margin, according to a paper published in Nature by Samuel Sokota, Gabriele Farina and colleagues. Remarkably, the achievement came at a small fraction of the compute and data costs of earlier attempts, suggesting that a general recipe for strategic decision-making under hidden information may finally be at hand.

Stratego has long stood as a stubborn benchmark. The game is played on a 10-by-10 grid with 92 occupiable squares and two lakes, and each player begins with 40 pieces whose identities are concealed from the opponent, arranged secretly on the first four rows. When pieces collide, both are revealed and battle outcomes are typically determined by rank, with equal ranks destroying both pieces.

Victory requires capturing the opponent's Flag or leaving them without legal moves. Because neither player can see the other's pieces, the game involves hidden information on a scale that renders standard reinforcement learning and search approaches ineffective. Even a multimillion-dollar industrial research effort, DeepMind's DeepNash, did not reach the level of top human players.

The scale of the efficiency gain is striking. DeepNash was trained on 1,024 tensor processing unit nodes over roughly two to three months, a run that under 2025 pricing would cost between roughly US$3,000,000 and US$4,500,000. Its training consumed about 5.5 billion games and between 5 trillion and 10 trillion training examples.

Ataraxos, by contrast, trained its reinforcement learning models on 16 NVIDIA H100 graphics processing units for one week and its belief model on 4 such units for 4 days, a run costing less than US$8,000 at 2025 prices. It used about 160 million games and roughly 50 billion training examples — approximately one-thirtieth of the games and one-hundredth of the training examples, and about one-five-hundredth of the compute cost. The authors note that these reductions, combined with the step change in playing strength, indicate markedly greater sample efficiency rather than merely a faster implementation.

At the core of Ataraxos are two interdependent self-play reinforcement learning processes, one for each phase of Stratego. The first phase, in which players privately place their pieces — called set-ups — is handled by one process; the second, in which players alternate moving pieces, is handled by another. The processes learn separately but in tandem: the set-up process generates the initial boards on which the move process trains, and the move process produces the game outcomes used for policy updates.

The team deliberately chose this decomposition over an end-to-end model because a single pipeline would have to accommodate two unrelated tasks. The set-up learner favoured a decoder-only transformer, Monte Carlo estimation of returns and higher learning rates, while the move learner favoured an encoder-only architecture, lambda-based return estimators, an annealed learning-rate schedule and lower regularization temperatures. Training relied on staying close to on-policy data through what the authors call dynamically damped self-play.

Regularization terms were added to the losses — a maximum entropy term for the set-up network and a reverse Kullback–Leibler penalty toward a uniform random policy for the move network — with coefficients annealed according to distinct power laws. The researchers found this regularization behaved somewhat like an energy reserve: annealing too cautiously left the model's playing ability underdeveloped, while annealing too aggressively produced rapid early gains but collapsed the model's entropy, depleting its capacity to learn and often leaving it easy to exploit. Update sizes were controlled with four complementary mechanisms: a reverse Kullback–Leibler penalty to the data collection policy, importance ratio clipping, gradient norm clipping and Adam's learning rate, the last of which was annealed by power law and proved crucial for both rapid early learning and avoiding later plateaus.

One unusual training trick paid double dividends. For moves played during self-play games, Ataraxos trains only on the moves with large estimated advantage magnitudes. This filtering cut wall-clock time per reinforcement learning iteration by a factor of about 2.5 while — in a phenomenon the authors say merits further investigation — actually increasing both sample efficiency with respect to environment queries and asymptotic performance.

For set-ups, meanwhile, plain Monte Carlo returns proved superior to other advantage estimators, an outcome the team notes is unusual in reinforcement learning, though similar behaviour has been observed in language model reasoning. The second pillar of the system is test-time search, long viewed as a major technical challenge in settings with as much hidden information as Stratego — so much so that DeepNash effectively forwent it. Ataraxos sidesteps the problem with a belief network trained on positions from games played by its final self-play policy, using teacher forcing to predict the true types of the opponent's hidden pieces given the information available to the player.

At each move, the system samples possible game states from the belief network, runs depth-limited rollouts for each candidate move using its move network to simulate both players, and averages network value predictions across the resulting positions. These averages approximate self-play action values regardless of the actual opponent, and are used to update the policy with a tabular step of magnetic mirror descent, regularized by the same two reverse Kullback–Leibler divergences used in training. Because the test-time update is tabular and rests on more accurate advantage estimates, it can safely be more aggressive than training updates.

None of this would have been feasible on modest academic infrastructure without a custom GPU-accelerated simulator written in CUDA C++, designed to reach roughly 10 million board state updates per second. The simulator avoids storing easily recomputed quantities, reconstructing past information states and legal action masks on demand from a circular preallocated GPU-memory buffer, which greatly reduces memory footprint and fragmentation. It minimizes dynamic memory allocations, supports fast resets of board states to non-terminal positions so search can pin simulations to specific states, and lets boards desynchronize as games finish independently, spreading training data across the game's phases.

Custom state machines and a fast diffing algorithm implement competitive play's anti-repetition rules — the two-square rule and the continuous-chasing rule — whose detection requires access to board history. The evaluations went beyond the headline match. Against the five bots of the Stratego Evaluator benchmark — Asmodeus, Celsius, Celsius1.1, Vixen and Peternlewis — Ataraxos won 99, 98, 97, 99 and 98 of 100 games respectively, leading the authors to describe the benchmark as meaningful only as a sanity check.

The team also reached state-of-the-art results in Hanabi, a cooperative game, where with search employed by all players perfect 25-point games rose to 77.53% in the two-player variant, 89.90% in three-player, 88.40% in four-player and 58.05% in five-player, with performance improving monotonically as more players used search. In the Chinese card game dou dizhu, Ataraxos scored 0.199 ± 0.015 against the previous state-of-the-art PerfectDou and 0.350 ± 0.016 against DouZero in role-averaged terms over 10,000 duplicated deals, a new best. The way Ataraxos plays differs tellingly from top humans.

Players observed that it favours aggressive set-ups, high Bombs and back-corner Flags that humans consider difficult to defend, and deploys less predictable structures. In play, its pieces are hard to read, it accepts draws when progressing would carry negative expected value, it preserves Scouts deep into games, and it uses some bluffs sparingly while attempting gambits humans consider altogether too risky. When behind, it stalls and pesters aggressively — tactics some humans consider rude — and players described it as excelling at long-term positional play, defence, playing from an information deficit and converting unfavourable positions into wins or draws.

Success across adversarial, cooperative and team games establishes what the authors call a design pattern for reinforcement learning and search under large amounts of hidden information, a longstanding desideratum of the field. They caution that search gains remain bounded because the procedure mimics a single update step, and that temporal-attention architectures could strengthen the belief model, but they conclude that hidden information is no longer prohibitive for practical AI wherever fast, accurate simulators can be built.

Subject of Research: Reinforcement learning and search algorithms for superhuman play in games with large amounts of hidden information

Article Title: Scalable decision-making for games of imperfect information

Article References: Sokota, S., Vinitsky, E., Hu, H., Fan, Z., Kolter, J. Z., & Farina, G. (2026). Scalable decision-making for games of imperfect information. Nature, 658(8134), 55-59. https://doi.org/10.1038/s41586-026-11036-y

Image Credits: AI Generated

DOI: 10.1038/s41586-026-11036-y

Keywords: Stratego, Ataraxos, imperfect information, reinforcement learning, self-play, test-time search, belief network, transformer, Hanabi, dou dizhu, DeepNash, superhuman AI