Deep Blue, AlphaGo and poker bots may have dominated their games, but Stratego, a classic military strategy game, resisted AI conquest for years. Now, a team from Carnegie Mellon, MIT, NYU and Stanford has created Ataraxos, which beat the best human player 15 to one with minimal resources.

Each player in Stratego starts with 40 pieces, representing military ranks and bombs, aiming to capture the opponent’s flag. However, opponents only know the location of the pieces, not their identities, until they clash in battle. This hidden information and the game’s extensive possibilities make it a formidable challenge for AI.

‘There’s something super distinctive about Stratego, which is that it is a massive amount of hidden information that unfolds over a very long timescale,’ said Eugene Vinitsky, a researcher at NYU and co-author of the study. In contrast, in some poker games, the hidden information is minimal. However, in Stratego, the pieces’ orders are nearly infinite, making it much harder for AI to predict the game’s outcome.

‘In chess, usually the game lasts 40 moves, but in Stratego, a game can easily last 2,000 moves,’ explained Gabriele Farina, an MIT computer scientist. The game also requires bluffing, adding another layer of complexity. When players bluff too often, their threats become meaningless; when they never bluff, they become predictable. This balancing act stumped earlier AIs like DeepMind’s DeepNash.

The success of AI in cracking the code of Stratego suggests that overcoming complex challenges requires more than just data; it demands creativity and an understanding of intricate dynamics.