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

Deep Blue took down Garry Kasparov at chess in 1997, AlphaGo beat Lee Sedol at Go in 2016, and poker bots have been beating professionals for years. But one classic game calledStrategoheld out. Even DeepMind, with its exceptional budget, couldn’t build a machine that reliably beat the best human players.

Now, a team of researchers from Carnegie Mellon, MIT, New York University, and Stanford University has done it. Their AI, called Ataraxos, beat Pim Niemeijer, arguably the bestStrategoplayer of all time, 15 games to one, with four draws. And it took just 16 GPUs and a few thousand dollars to train it.

Hidden armies

InStratego, each player gets 40 pieces representing military ranks, from a marshal down to a spy, plus bombs and a flag. You win by capturing the opponent’s flag. Your opponent knowswhereyour pieces are, but notwhatthey are. Identities are revealed only when two pieces collide in battle—the weaker one is removed, and the identity of the winner is revealed. That makesStrategoan imperfect-information game, just like poker, which computers cracked years ago. “There’s something super distinctive aboutStratego, which is that it is a massive amount of hidden information that unfolds over a very long time scale,” said Eugene Vinitsky, a researcher at NYU and co-author of the study.

In some forms of poker, the hidden information is tiny. In Texas Hold’em, “You only have two hidden cards,” said Gabriele Farina, an MIT computer scientist and another co-author. That leaves just 1,326 possible hands, few enough for a machine to weigh them all. “InStratego, there’s 40 pieces on the board that could be in any order,” Farina said. That’s more than a decillion possible setups. Then there’s the game’s length.

“In chess, usually the game lasts 40 moves, but inStratego, a game can easily last 2,000 moves,” Farina said. On top of that,Strategois a game of bluffing. Sometimes you move a weak piece as if it were a marshal, just to scare the opponent off. When players bluff too often, their threats mean nothing; when they never bluff, they become predictable. That balancing act, the team explains, is what stumped earlier AIs like DeepMind’s DeepNash, introduced in 2022.