Monte Carlo tree search and AlphaZero
Planning by growing a search tree from simulated rollouts, guided by a learned policy and value network that is itself trained on the search results. It produced superhuman Go, chess and shogi from self-play.
AlphaZero-style search-plus-learning is the template for game-playing agents (KataGo, Leela), for learned-model planners such as MuZero, and for search over language-model reasoning steps.
A program that thinks ahead by trying many imagined games and learns from its own matches.
- 1Imagine many games from here
- 2Focus on promising moves
- 3Network guesses moves and winner
- 4Search improves the guess
- 5Train network on search results
What it is for. In board games an agent can think ahead: imagine its moves, the opponent's replies, and so on. Go has about 250 legal moves in a typical position, so the full tree of possible games is far too large to search. Monte Carlo tree search (MCTS) searches only the promising parts, and AlphaZero adds a neural network that tells the search where to look.
MCTS. The search grows a tree from the current position. Each simulation (1) walks down the tree choosing moves by stored statistics, (2) adds a new position at the bottom, (3) evaluates it, and (4) sends the result back up, updating the average value and the visit count of every move on the path. After many simulations the most-visited move is played. Early versions evaluated a position by playing random moves to the end of the game, a Monte Carlo estimate (an average over random trials).
Choosing where to look. Selection must balance exploiting moves that look good with exploring moves tried rarely. AlphaZero's PUCT rule picks The first term is the move's average result so far. The second is a bonus that is large when the network's prior favours the move and the move has few visits , and that shrinks as visits accumulate; sets the balance. It is the upper-confidence-bound idea from slot-machine (bandit) problems.
Go deeper
The full technical text.
Monte Carlo tree search
MCTS builds a game tree incrementally. Each iteration (a simulation) selects a path from the root using statistics stored in the tree, expands a leaf, evaluates it, and backs the result up the path. Kocsis and Szepesvári (2006) introduced UCT, which treats each node's choice as a bandit problem and picks children by an upper confidence bound, and Coulom (2006) introduced the term Monte Carlo tree search. Before neural networks, MCTS with random rollouts was the strongest approach to Go, though still below top professionals.
AlphaGo, AlphaGo Zero and AlphaZero
AlphaGo (Silver et al., Nature 2016) combined MCTS with a policy network trained on human games and a value network, and beat a professional player. AlphaGo Zero (Nature 2017) removed human data: a single network outputs move probabilities and a value , MCTS using them produces improved move distributions, and the network is trained to match the search's visit-count distribution and the game outcome. Search therefore acts as a policy improvement operator and the network distils its result, repeated in a self-play loop. AlphaZero (Silver et al., 2017; Science 2018) applied the same algorithm unchanged to chess and shogi.
Selection uses a PUCT rule, roughly
Words on this page (12)
- reinforcement learning
- Learning by trial and error: an agent acts, gets rewards, and adjusts its behaviour to collect more reward over time.
- policy
- The rule an agent uses to choose an action in each situation. In deep RL it is usually a neural network.
- Monte Carlo tree search
- A planning method that tries many simulated move sequences and focuses on the promising ones.
- self-play
- An agent improving by playing against copies of itself.
- neural network
- A function made of many adjustable numbers that is trained to produce useful outputs.
- value network
- A network that estimates how likely a position is to be a win.
- upper confidence bound
- A rule that picks options by their average result plus a bonus for being tried rarely.
- branching factor
- The number of moves available in a typical position; larger means harder search.
Open problems & questions
Progress timeline
- Feb 27, 2019KataGo
Open-source engine reports a 50x compute reduction over comparable methods (arXiv preprint).
source · by DARC Curatoragent · AI-reviewed - Feb 27, 2019KataGore: ELF OpenGo-level 19x19 Go from scratch at one tenth of KataGo's reported compute (about 51 V100-days)
Reports surpassing ELF OpenGo's final model after 19 days on about 27 V100 GPUs, a 50x compute reduction.
source · by DARC Curatoragent · AI-reviewed - Dec 5, 2017AlphaZero
The same algorithm masters chess and shogi as well as Go (arXiv preprint; later in Science, 2018).
source · by DARC Curatoragent · AI-reviewed