{"id":766,"date":"2023-10-28T04:20:05","date_gmt":"2023-10-28T04:20:05","guid":{"rendered":"https:\/\/todaysainews.com\/index.php\/2023\/10\/28\/mastering-stratego-the-classic-game-of-imperfect-information-2\/"},"modified":"2025-04-27T07:32:35","modified_gmt":"2025-04-27T07:32:35","slug":"mastering-stratego-the-classic-game-of-imperfect-information-2","status":"publish","type":"post","link":"https:\/\/todaysainews.com\/index.php\/2023\/10\/28\/mastering-stratego-the-classic-game-of-imperfect-information-2\/","title":{"rendered":"Mastering Stratego, the classic game of imperfect information"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
\n

Research<\/p>\n

\n
Published<\/dt>\n
\n
Authors<\/dt>\n
\n

Julien Perolat, Bart De Vylder, Daniel Hennes, Eugene Tarassov, Florian Strub and Karl Tuyls<\/p>\n<\/dd>\n<\/dl>\n

\n<\/section><\/div>\n\"\"\n <\/picture>\n<\/p><\/div>\n
\n

DeepNash learns to play Stratego from scratch by combining game theory and model-free deep RL<\/b><\/p>\n

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

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\u2019s biggest online Stratego platform, Gravon.<\/p>\n

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.<\/p>\n

This complexity has meant that other AI-based Stratego systems have struggled to get beyond amateur level. It also means that a very successful AI technique called \u201cgame tree search\u201d, previously used to master many games of perfect information, is not sufficiently scalable for Stratego. For this reason, DeepNash goes far beyond game tree search altogether.<\/p>\n

The value of mastering Stratego goes beyond gaming. In pursuit of our mission of solving intelligence to advance science and benefit humanity, we need to build advanced AI systems that can operate in complex, real-world situations with limited information of other agents and people. Our paper shows how DeepNash can be applied in situations of uncertainty and successfully balance outcomes to help solve complex problems.<\/p>\n

Getting to know Stratego<\/h2>\n

Stratego is a turn-based, capture-the-flag game. It\u2019s a game of bluff and tactics, of information gathering and subtle manoeuvring. And it\u2019s a zero-sum game, so any gain by one player represents a loss of the same magnitude for their opponent.<\/p>\n

Stratego is challenging for AI, in part, because it\u2019s a game of imperfect information. Both players start by arranging their 40 playing pieces in whatever starting formation they like, initially hidden from one another as the game begins. Since both players don’t have access to the same knowledge, they need to balance all possible outcomes when making a decision \u2013 providing a challenging benchmark for studying strategic interactions. The types of pieces and their rankings are shown below.<\/p>\n<\/div>\n

\n

Left:<\/b> The piece rankings. In battles, higher-ranking pieces win, except the 10 (Marshal) loses when attacked by a Spy, and Bombs always win except when captured by a Miner.
Middle:<\/b> A possible starting formation. Notice how the Flag is tucked away safely at the back, flanked by protective Bombs. The two pale blue areas are \u201clakes\u201d and are never entered.
Right:<\/b> A game in play, showing Blue\u2019s Spy capturing Red\u2019s 10.<\/p>\n<\/figcaption><\/figure>\n

\n

Information is hard won in Stratego. The identity of an opponent’s piece is typically revealed only when it meets the other player on the battlefield. This is in stark contrast to games of perfect information such as chess or Go, in which the location and identity of every piece is known to both players.<\/p>\n

The machine learning approaches that work so well on perfect information games, such as DeepMind\u2019s AlphaZero<\/a>, are not easily transferred to Stratego. The need to make decisions with imperfect information, and the potential to bluff, makes Stratego more akin to Texas hold\u2019em poker and requires a human-like capacity once noted by the American writer Jack London: \u201cLife is not always a matter of holding good cards, but sometimes, playing a poor hand well.\u201d<\/p>\n

The AI techniques that work so well in games like Texas hold\u2019em don\u2019t transfer to Stratego, however, because of the sheer length of the game \u2013 often hundreds of moves before a player wins. Reasoning in Stratego must be done over a large number of sequential actions with no obvious insight into how each action contributes to the final outcome.<\/p>\n

Finally, the number of possible game states (expressed as \u201cgame tree complexity\u201d) is off the chart compared with chess, Go and poker, making it incredibly difficult to solve. This is what excited us about Stratego, and why it has represented a decades-long challenge to the AI community.<\/p>\n<\/div>\n

\n

The scale of the differences between chess, poker, Go, and Stratego.<\/p>\n<\/figcaption><\/figure>\n

\n

Seeking an equilibrium<\/h2>\n

DeepNash employs a novel approach based on a combination of game theory and model-free deep reinforcement learning. \u201cModel-free\u201d means DeepNash is not attempting to explicitly model its opponent\u2019s private game-state during the game. In the early stages of the game in particular, when DeepNash knows little about its opponent\u2019s pieces, such modelling would be ineffective, if not impossible.<\/p>\n

And because the game tree complexity of Stratego is so vast, DeepNash cannot employ a stalwart approach of AI-based gaming \u2013 Monte Carlo tree search. Tree search has been a key ingredient of many landmark achievements in AI for less complex board games, and poker.<\/p>\n

Instead, DeepNash is powered by a new game-theoretic algorithmic idea that we’re calling Regularised Nash Dynamics (R-NaD). Working at an unparalleled scale, R-NaD steers DeepNash\u2019s learning behaviour towards what\u2019s known as a Nash equilibrium (dive into the technical details in our paper).<\/a><\/p>\n

Game-playing behaviour that results in a Nash equilibrium is unexploitable over time. If a person or machine played perfectly unexploitable Stratego, the worst win rate they could achieve would be 50%, and only if facing a similarly perfect opponent.<\/p>\n

In matches against the best Stratego bots \u2013 including several winners of the Computer Stratego World Championship \u2013 DeepNash\u2019s win rate topped 97%, and was frequently 100%. Against the top expert human players on the Gravon games platform, DeepNash achieved a win rate of 84%, earning it an all-time top-three ranking.<\/p>\n

Expect the unexpected<\/h2>\n

To achieve these results, DeepNash demonstrated some remarkable behaviours both during its initial piece-deployment phase and in the gameplay phase. To become hard to exploit, DeepNash developed an unpredictable strategy. This means creating initial deployments varied enough to prevent its opponent spotting patterns over a series of games. And during the game phase, DeepNash randomises between seemingly equivalent actions to prevent exploitable tendencies.<\/p>\n

Stratego players strive to be unpredictable, so there\u2019s value in keeping information hidden. DeepNash demonstrates how it values information in quite striking ways. In the example below, against a human player, DeepNash (blue) sacrificed, among other pieces, a 7 (Major) and an 8 (Colonel) early in the game and as a result was able to locate the opponent\u2019s 10 (Marshal), 9 (General), an 8 and two 7\u2019s.<\/p>\n<\/div>\n

\n

In this early game situation, DeepNash (blue) has already located many of its opponent\u2019s most powerful pieces, while keeping its own key pieces secret.<\/p>\n<\/figcaption><\/figure>\n

\n

These efforts left DeepNash at a significant material disadvantage; it lost a 7 and an 8 while its human opponent preserved all their pieces ranked 7 and above. Nevertheless, having solid intel on its opponent\u2019s top brass, DeepNash evaluated its winning chances at 70% \u2013 and it won.<\/p>\n

The art of the bluff<\/h2>\n

As in poker, a good Stratego player must sometimes represent strength, even when weak. DeepNash learned a variety of such bluffing tactics. In the example below, DeepNash uses a 2 (a weak Scout, unknown to its opponent) as if it were a high-ranking piece, pursuing its opponent\u2019s known 8. The human opponent decides the pursuer is most likely a 10, and so attempts to lure it into an ambush by their Spy. This tactic by DeepNash, risking only a minor piece, succeeds in flushing out and eliminating its opponent\u2019s Spy, a critical piece.<\/p>\n<\/div>\n

\n

The human player (red) is convinced the unknown piece chasing their 8 must be DeepNash\u2019s 10 (note: DeepNash had already lost its only 9).<\/p>\n<\/figcaption><\/figure>\n

\n

See more by watching these four videos of full-length games played by DeepNash against (anonymised) human experts: Game 1<\/a>, Game 2<\/a>, Game 3<\/a>, Game 4.<\/a><\/p>\n<\/div>\n

\n
\n

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. But after playing against DeepNash myself, I wasn\u2019t 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.<\/p>\n<\/blockquote>

\n

Vincent de Boer, paper co-author and former Stratego World Champion<\/p>\n<\/figcaption><\/figure>\n

\n

Future directions<\/h2>\n

While we developed DeepNash for the highly defined world of Stratego, our novel R-NaD method can be directly applied to other two-player zero-sum games of both perfect or imperfect information. R-NaD has the potential to generalise far beyond two-player gaming settings to address large-scale real-world problems, which are often characterised by imperfect information and astronomical state spaces.<\/p>\n

We also hope R-NaD can help unlock new applications of AI in domains that feature a large number of human or AI participants with different goals that might not have information about the intention of others or what\u2019s occurring in their environment, such as in the large-scale optimisation of traffic management to reduce driver journey times and the associated vehicle emissions.<\/p>\n

In creating a generalisable AI system that\u2019s robust in the face of uncertainty, we hope to bring the problem-solving capabilities of AI further into our inherently unpredictable world.<\/p>\n

Learn more about DeepNash by reading our paper in Science<\/a>.<\/p>\n

For researchers interested in giving R-NaD a try or working with our newly proposed method, we\u2019ve open-sourced our code<\/a>.<\/p>\n<\/div>\n