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 called Stratego held out — until now.
A team of researchers from Carnegie Mellon, MIT, New York University, and Stanford University has built Ataraxos, an AI that beat Pim Niemeijer, arguably the best Stratego player of all time, 15 games to one, with four draws. Remarkably, it took just 16 GPUs and a few thousand dollars to train.
In Stratego, 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 knows where your pieces are, but not what they are. Identities are revealed only when two pieces collide in battle.
That makes Stratego an imperfect-information game, like poker, but on a much larger scale. "There's something super distinctive about Stratego, which is that it is a massive amount of hidden information that unfolds over a very long time scale," said NYU researcher Eugene Vinitsky, a co-author of the study.
In Texas Hold'em poker, there are only two hidden cards, leaving 1,326 possible hands. In Stratego, there are 40 pieces on the board that could be in any order — more than a decillion possible setups. And while chess games typically last 40 moves, Stratego games can easily last 2,000 moves.
The key breakthrough was adding a second neural network that guesses the identity of hidden pieces, allowing Ataraxos to reason about incomplete information over long time horizons.