A team of researchers from Carnegie Mellon, MIT, New York University, and Stanford University has developed an artificial intelligence system that reliably defeats the best human players in the board game Stratego. The AI, named Ataraxos, achieved a 15-to-one victory record against Pim Niemeijer, who is considered the best Stratego player of all time, with four additional draws. This breakthrough marks a significant milestone, as previous attempts by major tech companies to solve the game had failed.
Stratego is an imperfect-information game where each player controls 40 pieces representing military ranks, ranging from a marshal down to a spy, along with bombs and a flag. The objective is to capture the opponent's flag. Unlike chess or Go, where the board state is fully visible, Stratego players know the location of their opponent's pieces but not their identities. Identities are only revealed when two pieces collide in battle; the weaker piece is removed, and the winner's rank is disclosed.
The game has historically stumped computer systems despite advances in other areas. Deep Blue defeated Garry Kasparov at chess in 1997, and AlphaGo beat Lee Sedol at Go in 2016. Poker bots have also consistently outperformed professional humans for years. However, even DeepMind, which operates with an exceptional budget, was unable to build a machine that could reliably beat top human Stratego players. The new Ataraxos system required only 16 GPUs and a few thousand dollars to train.
Eugene Vinitsky, a researcher at New York University and co-author of the study, noted that Stratego is distinctive because it involves a massive amount of hidden information that unfolds over a very long time scale. This characteristic made the game particularly challenging for AI development compared to other imperfect-information games like poker, which computers cracked years ago.