At last: Mastering Stratego with AI

A newly developed AI agent called “DeepNash” learned to play Stratego, one of the few board games AI has not yet mastered, at a human expert level, researchers report. This represents an “extraordinary result that the Stratego community did not believe would have been possible with current techniques,” say the study’s authors. For many years, the Stratego board game – which tests one’s ability to make relatively slow, deliberative, and logical decisions sequentially – has constituted one of the next frontiers of AI research. An “imperfect” information game (in which some aspect of play is hidden from opponents), Stratego poses key challenges to AI researchers because of the many complex aspects of its structure, including having more possible states than another well-researched imperfect information game: no-limit Texas Hold’em poker. Currently, it is not possible to use imperfect information search techniques to master Stratego. Here, Julien Perolat and colleagues introduce a novel method that allows an AI for learning to play the game. This new method resulted in a bot called DeepNash that achieved human expert-level performance in the most complex variant of the game, Stratego Classic. At the core of DeepNash is a reinforcement learning algorithm, “R-NaD.” To make DeepNash, Perolat and team combined R-NaD with a deep neural network architecture to learn a strategy that plays at a highly competitive level. DeepNash was tested against various state-of-the-art Stratego bots and human expert players. It won against all bots and achieved a highly competitive level of play against human expert Stratego players on Gravon, an internet gaming platform and the largest online platform for Stratego. Notably, say the authors, this performance was achieved without deploying any search methods, a key ingredient for many milestone AI achievements in board games in past.