Dec 06, 2022 I Paul Seaburn

AI Dominates Humans in Stratego War Game - Is It Ready for a Real War?

The year 2022 marks the 50th anniversary of the debut of Pong – one of the earliest computer games and the first to become a worldwide hit as an arcade and a home video game. Because of the success of Pong, video games proliferated, but most people viewed the computers inside them as platforms or alternatives to boards rather than competitors. That changed when programs were developed to play against human opponents. Success was slow for computers, especially in the ancient warlike strategic board games like chess and Go, or in games of bluff like poker. However, computers eventually mastered those and defeated their masters. Now another traditional warlike strategy game has succumbed to a computer. It is indeed sad and possibly dystopic news because the game is the one which has ‘strategy’ built right into its name – Stratego … a game considered to be more complex than Go. Is it time to admit defeat to computers and turn war strategy over to artificial intelligence?

Is this the end of chess too?

“Stratego is one of the few iconic board games that artificial intelligence (AI) has not yet mastered. It is a game characterized by a twin challenge: It requires long-term strategic thinking as in chess, but it also requires dealing with imperfect information as in poker.”

In a new paper published in the journal Science, the folks at Goggle’s artificial intelligence subsidiary DeepMind unveiled DeepNash, a game-playing artificial intelligence system designed specidfially to play and win at Stratego, the classic board game DeepMind describes as being complex than chess and Go, and “craftier” than poker. The “crafty” part comes from the fact that, like poker, Stratego is a game of “imperfect information” where players cannot directly observe the identities of their opponent's playing pieces (or cards, in the case of poker).

“This is Stratego – not a place, not a time but a battle of wits and skill and strategy.” (From a 1983 commercial)

Stratego is a strategy board game for two players on a board of 10×10 squares. Each player has  40 pieces representing individual officer and soldier ranks in an army – but the pieces are vertical so the insignias are only visible to the player who moves them. The game is a form of the classic ‘Capture the Flag’ -- the object is to find and capture the opponent's flag, or to capture, isolate and surround their pieces so they cannot make any moves. The original Stratego game may have been based on traditional Japanese Military Chess, but the earliest form most similar to the modern version was the French game L'attaque, patented in 1909 and played primarily in France and Great Britain. The American version of Stratego was created by Dutchman Jacques Johan Mogendorff and registered as a trademark in 1942 (80 years ago this year) by the Dutch company Van Perlstein & Roeper Bosch N.V., which coincidentally also produced the first edition of Monopoly. The game was sublicensed to Milton Bradley, which was acquired by Hasbro in 1984. Electronic Stratego was introduced 40 years agon in 1982, but the “electronics” were limited to lighting lights and playing music and sound effects. The traditional two-player non-electronic board game (versions are available for three and four players) has remained basically unchanged.

“The machine learning approaches that work so well on perfect information games, such as DeepMind’s AlphaZero, 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’em poker and requires a human-like capacity once noted by the American writer Jack London: “Life is not always a matter of holding good cards, but sometimes, playing a poor hand well.”

The website explains the challenge faced by developers in creating a program to play Stratego at a human level. Games of bluff are inherently difficult for computers which rely on reliable data to crunch. Stratego players have “imperfect information” in their database, so they must balance all possible outcomes when making a decision. That’s a big challenge in Texas Hold’em poker which ends after just a few decisions, but nearly insurmountable in Stratego which can have hundreds of moves over hours of play with no visible clues as to how each move may affect the final outcome. To computerize chess and Go, programs are input all possible game states and their relationships – a structure known as a “game tree.” DeepMInd’s website says the “game tree complexity” of Stratego is “off the chart” compared with chess, Go and poker. After years of trying and failing with traditional strategies and increasingly more computer horsepower, DeepMind turned to a new approach.

“The technique underpinning DeepNash uses a game-theoretic, model-free deep reinforcement learning method, without search, that learns to master Stratego through self-play from scratch.”

DeepNash (named for Nash equilibrium: a stable state of a system involving the interaction of different participants, in which no participant can gain by a unilateral change of strategy if the strategies of the others remain unchanged) scraps the game tree search approach for a new game-theoretic algorithmic idea called Regularised Nash Dynamics (R-NaD) which directs DeepNash’s AI learning to Nash equilibrium (explained in the research paper). Spoiler alert … it worked. DeepNash beat existing state-of-the-art AI methods in Stratego and achieved a year-to-date (2022) and all-time top-three ranking on the Gravon games platform while competing with human expert players. (A full-length game can be seen here.) Former Stratego World Champion and paper co-author Vincent de Boer, coauthor Vincent de Boer was impressed.

"DeepNash’s level of play surprised me. I had never seen a machine capable of playing Stratego like an experienced human player. After playing against DeepNash myself, I was not surprised that it made it into the top-three of the Gravon ranking. I think it would do very well if they let it participate in the World Championship."

Is this what DeepNash is thinking about?

DeepNash learned a variety of bluffing and decoy tactics – skills that take computer game playing to a level far beyond anything envisioned by the developers of Pong a mere 50 years ago. And yet, at the base level, the games are the same – combat between two players. If DeepNash can defeat a human “general” at a game of war strategy, is it ready to replace generals in real war rooms? Can this AI general command robotic AI soldiers to success on a traditional military battlefield against human soldiers? Do we want Google to be that general?

Do we really want to find out?   

Paul Seaburn

Paul Seaburn is the editor at Mysterious Universe and its most prolific writer. He’s written for TV shows such as "The Tonight Show", "Politically Incorrect" and an award-winning children’s program. He's been published in “The New York Times" and "Huffington Post” and has co-authored numerous collections of trivia, puzzles and humor. His “What in the World!” podcast is a fun look at the latest weird and paranormal news, strange sports stories and odd trivia. Paul likes to add a bit of humor to each MU post he crafts. After all, the mysterious doesn't always have to be serious.

Join MU Plus+ and get exclusive shows and extensions & much more! Subscribe Today!