A team of researchers at DeepMind Technologies Ltd., has created an AI application called “DeepNash” that is able to play the game Stratego at an expert level. In their paper published in the journal Science, the group describes the unique approach they took to improve the app’s level of play.

Stratego is a two-player board game and is considered to be difficult to master. The goal for each player is to capture their opponent’s flag, which is hidden among their initial 40 game pieces. Each of the game pieces is marked with a power ranking—higher-ranked players defeat lower-ranked players in face-offs. Making the game more difficult is that neither player can see the markings on the opponent’s game pieces until they meet face-to-face.

Prior research has shown that the complexity of the game is higher than that of chess or go, with 10⁵³⁵ possible game scenarios. This level of complexity makes it extremely challenging for computer experts attempting to create Stratego-playing AI systems. In this new effort, the researchers took a different approach, creating an app capable of beating most human and other AI systems.

Game-playing artificial intelligence (AI) systems have advanced to a new frontier. Stratego, the classic board game that’s more complex than chess and Go, and craftier than poker, has now been mastered. Published in Science, we present DeepNash, an AI agent that learned the game from scratch to a human expert level by playing against itself.

DeepNash uses a novel approach, based on game theory and model-free deep reinforcement learning. Its play style converges to a Nash equilibrium, which means its play is very hard for an opponent to exploit. So hard, in fact, that DeepNash has reached an all-time top-three ranking among human experts on the world’s biggest online Stratego platform, Gravon.

Board games have historically been a measure of progress in the field of AI, allowing us to study how humans and machines develop and execute strategies in a controlled environment. Unlike chess and Go, Stratego is a game of imperfect information: players cannot directly observe the identities of their opponent’s pieces.

Deepmind introduces a new research framework for AI agents in simulated environments such as video games that can interact more flexibly and naturally with humans.

AI systems have achieved great success in video games such as Dota or Starcraft, defeating human professional players. This is made possible by precise reward functions that are tuned to optimize game outcomes: Agents were trained using unique wins and losses calculated by computer code. Where such reward functions are possible, AI agents can sometimes achieve superhuman performance.

But often – especially for everyday human behaviors with open-ended outcomes – there is no such precise reward function.