DeepMind AI Topples Experts at Complex Game Stratego 21
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.
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.
Stratego no let's play Global Thermo-Nuclear War! (Score:2)
Stratego no let's play Global Thermo-Nuclear War!
Re: (Score:2)
I always preferred Nuclear War [kuratedkorner.com] to Chess or Diplomacy.
Re: (Score:2)
For classic board games, can't beat good ol' Risk.
Ironically, on the old Risk map the territory that we call Russia today is called Ukraine on the board instead...there is no Russia in Risk game. Perhaps that's really what caused Vlad to lose his marbles and embark on this self-destructive enterprise.
(still can't pronounce Kamchatka...)
Re: (Score:2)
Else, unless you put some several hampers on what the AI can do and see, my money is on the bot. The bots cheat man. Especially those in UT2k4
Topless? (Score:2)
Re: (Score:2)
Nope, I too was almost interested in this story.
Neat but, (Score:1)
Re: (Score:2)
To really be fair, same power *supply* constraints as a human: Shoves burrito in to front of computer, then pours some water after that.
Re: (Score:2)
Re: (Score:2)
Well sure, if you want to overclock; but the hardware may not last as long.
Re:Neat but, (Score:5, Insightful)
Re: (Score:2)
We solved this problem by throwing lots of math and computing power at it.
This is neat, prolly has some stuff for those in the biz to chew on, but nothing I am really going to see use of in day to day life.
Maybe if it was efficient enough to be PCIE add in card for my PCs. All the tech world is going to using it for is analyzing data for ads.
Re: (Score:2)
The end result is just a computer program, with all the training baked in. You can literally copypaste it to run in, without having to redo all the training.
Stratego! (Score:2)
One of my favorite childhood board games. Now I can throw it back in the faces of those chess-player snobs. Hear that Carlsen!
Can't wait to find out that Battleship is the most complex of all
Re: Stratego! (Score:2)
I was thinking the same thing. I had no idea the game was so mathematically complicated. It doesn't seem much more so than chess when you're playing.
Re: (Score:2)
Stratego would be like chess, except each player gets to place his pieces where he wants on his side of the board while keeping the identity of each piece hidden from the opponent.
Re: (Score:2)
No wonder that it is much more complex.
Re: Stratego! (Score:3)
Re: (Score:1)
I was thinking the same thing. I had no idea the game was so mathematically complicated. It doesn't seem much more so than chess when you're playing.
Chess has more ranged pieces and more structure. And because pawns can move the structure has some flexibility. One of the more difficult-to-master aspects of chess is understanding and deciding when to change that structure.
A big step forward : AI winning another game (Score:1)
Why go for the cheap media attention instead of something like cancer detection?
It's like a company boasting they achieved a great number of followers on social media as their big achievement this year.