AI Defeats Stratego’s Best Human Player After Training on Just 16 GPUs

Deep Blue defeated Garry Kasparov at chess in 1997, AlphaGo defeated Lee Sedol at Go in 2016, and poker bots have beaten professional players for years. But Stratego remained a challenge—even for DeepMind, despite its extraordinary resources.

Now, researchers from Carnegie Mellon University, MIT, New York University, and Stanford University have developed an AI that can reliably defeat elite human players. Their system, called Ataraxos, beat Pim Niemeyer—likely the greatest Stratego player of all time—with 15 wins, one loss, and four draws.

The result is particularly notable because Ataraxos required only 16 GPUs and a few thousand dollars to train.

Why Stratego Is So Difficult for AI

In Stratego, each player receives 40 pieces representing military ranks ranging from marshal to spy, along with bombs and a flag. The goal is to capture the opponent’s flag.

Players can see where their opponent’s pieces are, but not what those pieces are. A piece’s identity is revealed only when two pieces collide in battle. The weaker piece is eliminated, and the winner’s rank is revealed.

This makes Stratego a poker-like game of imperfect information, but with far more hidden information unfolding over a much longer period of time.

“There’s something very distinctive about it,” said Eugene Vinnitsky, a researcher at New York University and co-author of the study. “Stratego has a huge amount of hidden information that unfolds over very long time scales.”

More Hidden Information Than Poker

Depending on the format of poker, the amount of hidden information can be relatively small. In Texas Hold’em, for example, there are only two hidden cards. That creates 1,326 possible hands—still too many for a machine to weigh individually in every situation.

“In Stratego, there are 40 pieces on the board, and they can be in any order,” said Gabriele Farina, a computer scientist at MIT and another co-author. The game therefore has more than 100,000 possible configurations before accounting for how the position changes during play.

Stratego Games Can Last 2,000 Moves

The length of a game adds another layer of complexity.

“In the case of chess, the game usually takes 40 steps; Stratego can easily last up to 2,000 moves,” Farina said.

Stratego also requires players to bluff. A player might move a weaker piece as if it were a marshal to frighten an opponent. Bluff too often, however, and the threat loses its power. Never bluff, and the strategy becomes predictable.

The research team says this balance between hidden information, long-term planning, and bluffing caused earlier AIs—including DeepMind’s DeepNash, introduced in 2022—to struggle with the game.