Mastering Atari, Go, chess and shogi by planning with a learned model

The problem it set out to solve

Games have long been used as testbeds for machine learning, but a recurring obstacle is that planning usually depends on knowing how the environment works. To look ahead before acting, a program needs some model of what each action does to the state of the world. In board games that model is normally the rulebook, written in by hand; in video games it is a simulator. MuZero's bet was that this model does not have to be supplied at all. It can be learned from experience, and the same learned machinery can then serve for games as different as Go and an Atari console title.

How it works

MuZero learns a model of its environment and then plans with that model rather than with a hand-written simulator. The algorithm was evaluated on Go, chess and shogi without any knowledge of the game rules^[1]. In other words, nothing in the system tells it which moves are legal or how a position develops; the learned model stands in for the real environment while the system searches over possible futures, and what it learns during training is whatever makes that internal planning produce good decisions.

DeepMind also describes a variant called MuZero Reanalyze, used on Atari. There the learned model was used 90% of the time to re-plan what should have been done in past episodes, so that earlier experience is revisited with the model as it is now rather than only with the model as it was when the data was collected^[2]. A second experiment on Ms. Pac-Man found that planning with 5 to 50 simulations per move improved both learning speed and final performance^[2].

Results

The headline evaluation covered 57 different Atari games, on which the algorithm achieved a new state of the art^[1]. Atari scores in this work are normalized to human testers, whose performance is set at 100%, and training runs used either 200M or 20B frames^[2]. Because the system plans, extra thinking time should translate into strength, and DeepMind reports exactly that on Go: playing strength rises by more than 1000 Elo as time per move goes from one-tenth of a second to 50 seconds^[2]. The same algorithm was evaluated on Go, chess and shogi again without rule knowledge^[1].

Publication and authorship

Schrittwieser et al. first posted the work to arXiv on 19 November 2019 under the title "Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model"^[1]. The arXiv listing gives 12 authors, including David Silver, Thore Graepel, Timothy Lillicrap and Demis Hassabis^[1]. A Nature version appeared in volume 588, pages 604–609, with DOI 10.1038/s41586-020-03051-4^[3]. DeepMind's blog post dated 23 December 2020 presents MuZero as mastering Go, chess, shogi and Atari without being told the rules^[2].

Why it matters

Two features of the work stand out. The first is breadth: one algorithm, with the same structure, handles board games with perfect information and video games with fast, noisy pixels, rather than needing a bespoke design for each. The second is where the knowledge lives. Earlier systems that played board games at a high level depended on a simulator written by people who knew the rules; MuZero moves that burden into a learned model, so the same approach can be pointed at problems where no clean simulator exists.

The scaling with thinking time is the other point of interest. If strength keeps rising as the system is allowed more simulations per move, then the learned model is good enough to be searched in, not merely a by-product of training. That is what makes the framing "planning with a learned model" a description of the method rather than a slogan, and it is why the paper is usually read as a step toward agents that build and use their own models of the world.