Google’s AI learns to play strategy board game, quickly becomes one of world’s top players

Google’s artificial intelligence bot “DeepNash” has learned to play Stratego – one of the few board games AI had not mastered – and has reached an all-time top-three ranking among human experts.

Previous studies have shown that AI can train itself to learn games like chess and Go from scratch, and even master them and win over human opponents.

However, Stratego posed a challenge to AI since it is more complex and relies on imperfect information – one where players cannot directly observe the identities of their opponent’s pieces.

Stratego is a turn-based game of bluff and tactics that involves information gathering and subtle maneuvering, in which any gain by one player is a loss of the same magnitude for their opponent.

It is particularly challenging for AI to master, say researchers, including Karl Tuyls from Google’s DeepMind, since the game involves making decisions based on imperfect information and the potential to bluff.

“In Stratego, players cannot directly observe the identity of the opponent’s pieces, unlike in well known board games like Chess or Go. As a result the AI methods that worked well on such games, like AlphaZero – relying heavily on search – are not easily transferable to Stratego,” Dr Tuyls, one of the authors of the study from DeepMind, explained.

Players apply strategy and reasoning over a series of sequential actions with no obvious insight into how each of these would contribute to the final outcome.

They would need to “balance all possible outcomes when making a decision,” scientists explained, adding that the number of potential states – ten to the power of 535 – is also “off the chart” compared with chess, Go, and poker.

The game tests a player’s ability to make relatively slow, deliberative, and logical decisions sequentially.

All these factors, researchers said, made it difficult for the AI community to master Stratego.

In a new study, published in the journal Science last week, scientists reported a bot called DeepNash that has achieved human expert-level performance in the most complex variant of the game, Stratego Classic.

They tested DeepNash against various state-of-the-art Stratego bots as well as human expert players.

The bot won against all the bots with which it played 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.

DeepNash developed an “unpredictable strategy” to win, scientists say, adding that its initial deployments varied significantly to prevent its opponent recognising the AI’s patterns over a series of games.

The AI bot even learned to bluff its opponent, using weaker pieces as if they were high-ranking ones, the study noted.

“The level of play of DeepNash surprised me. I had never heard of an artificial Stratego player that came close to the level needed to win a match against an experienced human player,” study co-author Vincent de Boer said in a statement.

“But after playing against DeepNash myself, I wasn’t surprised by the top-3 ranking it later achieved on the Gravon platform. I expect it would do very well if allowed to participate in the human World Championships,” he said.

Scientists believed the findings from the study can lead to several real-world multiagent problems that deal with astronomical numbers of states and characterised by imperfect information that is currently out of reach for state-of-the-art AI methods.

“Many applications can be found in this larger class of games, including crowd and traffic modeling, smart grid, auction design, and market problems,” researchers wrote in the study.