With most information hidden, the game Stratego had stumped AI–until now

Researchers from Carnegie Mellon, MIT, NYU, and Stanford built Ataraxos, an AI that overcame long-standing barriers in Stratego and beat Pim Niemeijer, widely regarded as the best player ever, 15-1 with four draws and later won 38 of 40 exhibition games. Stratego is challenging because each side has 40 hidden pieces (decillion possible setups), games can run for thousands of moves, and play relies heavily on long-term bluffing and inference - features that defeated prior efforts like DeepNash. Ataraxos achieved this on a modest budget: training used 16 GPUs for about a week (plus a few extra GPUs to train its belief model), far cheaper and faster than previous attempts that required thousands of specialized chips.

The technical advance was combining large-scale self-play (about 163 million games) with a second neural network that forms a belief over the opponent’s hidden piece identities, enabling sample-based forward search before each move instead of enumerating every configuration. The team also used aggressive strategy updates early in training and finer adjustments later to avoid self-play cycling. The result is a calm, methodical style that bluffs effectively without human impulsiveness and produces novel tactics that have already shifted competitive play. The approach generalized to Barrage Stratego, Hanabi, and dou dizhu, and the authors suggest it can inform simplified models of real-world adversarial problems while work continues on interpretability. Paper published in Nature, 2026 (DOI: 10.1038/s41586-026-11036-y).