AI finally cracks Stratego, defeating world champion with modest computing power

For decades, artificial intelligence has conquered classic games one by one—chess fell to Deep Blue in 1997, Go to AlphaGo in 2016, and poker bots have dominated professionals for years. Yet Stratego, a deceptively simple board game rooted in incomplete information and tactical deception, remained a holdout—even against DeepMind's well-funded attempts. That changed when a collaborative team from Carnegie Mellon, MIT, New York University, and Stanford developed Ataraxos, an AI that decisively outplayed Pim Niemeijer, widely considered the strongest Stratego player in history, winning 15 games to one with four draws. Remarkably, the system required only 16 GPUs and a budget of a few thousand dollars to train.

Why Stratego resisted AI for so long#

Stratego presents a radically different challenge than its famous game predecessors. Players deploy 40 pieces—military ranks from marshal down to spy, plus bombs and a flag—with victory achieved by capturing an opponent's flag. The crucial twist: while you know where your opponent's pieces are positioned, you never know what they are until pieces clash in combat. This creates a game of imperfect information that unfolds over an extended timeline, resembling poker in structure but vastly more complex.

The scale of hidden information in Stratego dwarfs that of other games machines have conquered. Poker variants like Texas Hold'em involve just two hidden cards, leaving roughly 1,326 possible hands—manageable for algorithmic analysis. In contrast, Stratego's 40 pieces can arrange in more than a decillion different configurations. Combined with typical game lengths stretching to 2,000 moves—compared to chess's usual 40—the computational space becomes exponentially larger. The game also demands mastery of bluffing: moving weak pieces as if they were powerful marshals to mislead opponents, yet maintaining credibility through careful calibration. Too much deception and threats lose meaning; too little and patterns become exploitable.

How Ataraxos succeeded#

This delicate balance of uncertainty and psychological warfare had stumped earlier approaches, including DeepMind's DeepNash system from 2022. The research team, led by computer scientists including Gabriele Farina from MIT and Eugene Vinitsky from NYU, apparently cracked the core dynamics through techniques that required far less computational firepower than industry giants typically deploy. Their approach successfully navigated both the astronomical state space and the strategic subtlety of optimal bluffing.