DeepMind AI Topples Experts at Complex Game Stratego

Game-playing AIs that interact with humans are laying important groundwork for real-world applications. From a report: Another game long considered extremely difficult for artificial intelligence (AI) to master has fallen to machines. An AI called DeepNash, made by London-based company DeepMind, has matched expert humans at Stratego, a board game that requires long-term strategic thinking in the face of imperfect information. The achievement, described in Science on 1 December, comes hot on the heels of a study reporting an AI that can play Diplomacy, in which players must negotiate as they cooperate and compete. "The rate at which qualitatively different game features have been conquered -- or mastered to new levels -- by AI in recent years is quite remarkable," says Michael Wellman at the University of Michigan in Ann Arbor, a computer scientist who studies strategic reasoning and game theory. "Stratego and Diplomacy are quite different from each other, and also possess challenging features notably different from games for which analogous milestones have been reached."

Stratego has characteristics that make it much more complicated than chess, Go or poker, all of which have been mastered by AIs (the latter two games in 2015 and 2019). In Stratego, two players place 40 pieces each on a board, but cannot see what their opponent's pieces are. The goal is to take turns moving pieces to eliminate those of the opponent and capture a flag. Stratego's game tree -- the graph of all possible ways in which the game could go -- has 10^535 states, compared with Go's 10^360. In terms of imperfect information at the start of a game, Stratego has 10^66 possible private positions, which dwarfs the 106 such starting situations in two-player Texas hold'em poker. "The sheer complexity of the number of possible outcomes in Stratego means algorithms that perform well on perfect-information games, and even those that work for poker, don't work," says Julien Perolat, a DeepMind researcher based in Paris.

[...] For two weeks in April, DeepNash competed with human Stratego players on online game platform Gravon. After 50 matches, DeepNash was ranked third among all Gravon Stratego players since 2002. "Our work shows that such a complex game as Stratego, involving imperfect information, does not require search techniques to solve it," says team member Karl Tuyls, a DeepMind researcher based in Paris. "This is a really big step forward in AI." "The results are impressive," agrees Noam Brown, a researcher at Meta AI, headquartered in New York City, and a member of the team that in 2019 reported the poker-playing AI Pluribus.

Read more of this story at Slashdot.