The winning rate against humans is 84%. DeepMind AI reaches the level of human experts in Western chess for the first time

DeepMind has made new achievements in the field of game AI, this time in Western chess.

#In the field of AI games, the progress of artificial intelligence is often demonstrated through board games. Board games can measure and evaluate how humans and machines develop and execute strategies in controlled environments. For decades, the ability to plan ahead has been key to AI's success in perfect-information games like chess, checkers, shogi, and Go, as well as imperfect-information games like poker and Scotland Yard.

Stratego has become one of the next frontiers of AI research. A visualization of the game’s stages and mechanics is shown below in 1a. The game faces two challenges.

First, Stratego’s game tree has 10,535 possible states, which is more than the well-studied imperfect information games Unrestricted Texas Hold’em (10,164 possible states) and Go (10,360 possible states) ).

Second, acting in a given environment in Stratego requires reasoning over 1066 possible deployments for each player at the start of the game, whereas poker only has 103 possible pairs of hands. Perfect information games such as Go and chess do not have a private deployment phase, thus avoiding the complexity of this challenge in Stratego.

Currently, it is not possible to use model-based SOTA perfect information planning technology, nor to use imperfect information search technology that decomposes the game into independent situations.

For these reasons, Stratego provides a challenging benchmark for studying large-scale policy interactions. Like most board games, Stratego tests our ability to make relatively slow, thoughtful and logical decisions in a sequential manner. And because the structure of the game is very complex, the AI ​​research community has made little progress, and the artificial intelligence can only reach the level of human amateur players. Therefore, developing an agent to learn end-to-end strategies to make optimal decisions under Stratego's imperfect information, starting from scratch and without human demonstration data, remains one of the major challenges in AI research.

Recently, in a latest paper from DeepMind, researchers proposed DeepNash, an agent that learns Stratego self-game in a model-free way without human demonstration. DeepNask defeated previous SOTA AI agents and achieved the level of expert human players in the game's most complex variant, Stratego Classic.

Paper address: https://arxiv.org/pdf/2206.15378.pdf.

The core of DeepNash is a structured, model-free reinforcement learning algorithm, which researchers call Regularized Nash Dynamics (R-NaD). DeepNash combines R-NaD with a deep neural network architecture and converges to a Nash equilibrium, meaning it learns to compete under incentives and is robust to competitors trying to exploit it.

Figure 1 b below is a high-level overview of the DeepNash method. The researchers systematically compared its performance with various SOTA Stratego robots and human players on the Gravon gaming platform. The results show that DeepNash defeated all current SOTA robots with a winning rate of more than 97% and competed fiercely with human players. It ranked in the top 3 in the rankings in 2022 and in each period, with a winning rate of 84%.

Researchers said that for the first time, an AI algorithm can reach the level of human experts in complex board games without deploying any search methods in the learning algorithm. , it is also the first time that AI has achieved human expert level in the Stratego game.

Method Overview

DeepNash uses an end-to-end learning strategy to run Stratego and strategically place chess pieces on the board at the beginning of the game (see Figure 1a). During the game-play phase, The researchers used integrated deep RL and game theory methods. The agent aims to learn an approximate Nash equilibrium through self-play.

This research uses orthogonal paths without search, and proposes a new method that combines model-free reinforcement learning in self-game with game theory algorithm ideas-regularized Nash dynamics (RNaD) combined.

The model-free part means that the research does not establish an explicit opponent model to track the possible states of the opponent. The game theory part is based on the idea that based on the reinforcement learning method, they guide the agent to learn Behavior moves toward a Nash equilibrium. The main advantage of this compositional approach is that there is no need to explicitly mock private state from public state. An additional complex challenge is to combine this model-free reinforcement learning approach with R-NaD to enable self-play in chess to compete with human expert players, something that has not been achieved so far. This combined DeepNash method is shown in Figure 1b above.

Regularized Nash Dynamics Algorithm

The R-NaD learning algorithm used in DeepNash is based on the idea of ​​regularization to achieve convergence. R-NaD relies on three A key step, as shown in Figure 2b below:

DeepNash consists of three components: (1) Core training component R-NaD ; (2) fine-tuning the learning strategy to reduce the residual probability of the model taking highly unlikely actions, and (3) post-processing at test time to filter out low-probability actions and correct errors.

DeepNash’s network consists of the following components: a U-Net backbone with residual blocks and skip connections, and four heads. The first DeepNash head outputs the value function as a scalar, while the remaining three heads encode the agent policy by outputting a probability distribution of its actions during deployment and gameplay. The structure of this observation tensor is shown in Figure 3:

Experimental results

DeepNash also interacts with several existing Some Stratego computer programs have been evaluated: Probe won the Computer Stratego World Championship three of the years (2007, 2008, 2010); Master of the Flag won the championship in 2009; Demon of Ignorance is Stratego's Open source implementation; Asmodeus, Celsius, Celsius1.1, PeternLewis and Vixen were programs submitted to the Australian University Programming Competition in 2012, which PeternLewis won.

As shown in Table 1, DeepNash won the vast majority of games against all these agents, even though DeepNash had no adversarial training and only used self-game.

Figure 4a below illustrates some of the frequently repeated deployment methods in DeepNash; Figure 4b shows DeepNash (blue square) on the chess piece A situation where the center is behind (losing 7 and 8) but ahead in terms of information, because the red side's opponent has 10, 9, 8 and two 7s. The second example in Figure 4c shows DeepNash having an opportunity to capture the opponent's 6 with its 9, but this move was not considered, probably because DeepNash believed that protecting the identity of the 9 was considered more important than the material gain.

In Figure 5a below, the researchers demonstrate positive bluffing, where players pretend that the value of the piece is higher than it actually is. value. DeepNash chases the opponent's 8 with the unknown piece Scout (2) and pretends it is a 10. The opponent thinks the piece might be a 10 and guides it next to the Spy (where the 10 can be captured). However, in order to capture this piece, the opponent's Spy lost to DeepNash's Scout.

The second type of bluffing is negative bluffing, as shown in Figure 5b below. It is the opposite of active bluffing, where the player pretends that the piece is worth less than it actually is.

Figure 5c below shows a more complex bluff, where DeepNash brings its undisclosed Scout (2) close to the opponent's 10, which could be interpreted as a Spy. This strategy actually allows Blue to capture Red's 5 with 7 a few moves later, thus gaining material, preventing 5 from capturing Scout (2), and revealing that it is not actually a Spy.

The above is the detailed content of The winning rate against humans is 84%. DeepMind AI reaches the level of human experts in Western chess for the first time. For more information, please follow other related articles on the PHP Chinese website!