“Our paper shows how DeepNash can be applied in situations of uncertainty and successfully balance its actions to help solve complex problems,” explains Julien Perolat, lead author of the study. The tool does not try to predict the possible moves an opponent may make, which is the standard approximation in game simulators – because the number of possibilities in the game tree is practically infinite – but instead establishes its own strategy and then adapts it based on how the game pans out. For this reason, the DeepMind team has developed a reinforcement learning algorithm that applies theoretical models based on Nash equilibrium, a theorem developed by American mathematician John Nash, a specialist in game theory.
#RULES FOR STRATEGO GAME SIMULATOR#
These two particular complexities make it impossible to take advantage of previous research to approach a game simulator for Stratego. Perfect information games do not present the same problem, as the chips are in plain sight. On the other hand, any move made on the first turn involves thinking of 10⁶⁶ possible pairs of chip configurations. This is no coincidence: the game has 10⁵³⁵ possible dispositions, considerably more than Texas Hold’em poker, a game of imperfect information with 10¹⁶⁴ possibilities in which players know only what cards they have in their hand and those that are in play, or Go, which has 10³⁶⁰ options. Until now, no-one had managed to develop a tool capable of playing Stratego at the same level as an expert human. DeepMindĭeepMind has a long history in the field, having developed cutting-edge tools to outperform humans in complex, long-term strategy games with perfect information, such as Go (using AphaGo), but also in imperfect information video games, such as StarCraft (using AlphaStar). Each player places their 40 pieces on the board, but does not know how their opponent has ordered theirs. Stratego consists of 12 types of pieces with different attributes. As such, DeepMind decided to set its sights on Stratego, a major challenge for the machine given the lack of information that it must manage during the game. It is a perfect litmus test to study how humans and machines develop and execute game-winning strategies. They offer a controlled environment with precise rules in which the tools can develop their abilities and where it is easy to measure their success: researchers simply have to see if they win the game or not. Game simulators have historically served as a good barometer to measure the effectiveness of computer programs. It also means that winning requires more cunning than in poker – where you don’t know your opponent’s cards either – and players require both intuition and mathematical knowledge.
This uniqueness makes it a more complex game than Go, the 1,000-year-old Asian game whose board allows the tiles to be arranged in more different combinations than there are atoms in the universe. Stratego is characterized by a double challenge: it requires long-term strategic thinking, like chess, but you also need to manage imperfect information, as in poker, because the opponent’s chips are covered at the start of the game and only revealed as it progresses. Marketed by Jumbo Games since the 1960s, though invented before World War I in a very similiar format under the French name L’Attaque, Stratego was one of the few board games not yet mastered by artificial intelligence. The authors of the study believe that the algorithm could be applied in areas such as automatic traffic optimization. This represents a milestone due to the high complexity of the game, which combines elements of strategy, intuition (players do not have all the necessary information available to draw up perfect plans) and even bluffing.
As detailed by a team of DeepMind researchers in an article published on December 1 in the journal Science, DeepNash (as the tool has been christened) is already ranked within the top three players on the specialist Gravon games platform, where it has been competing against human opponents. The UK-based company DeepMind, which has been owned by Google since 2014, has developed an algorithm capable of playing the popular board game Stratego like an expert human player.
0 kommentar(er)
