TL;DR
Monte Carlo Tree Search (MCTS) builds a search tree not by exhaustively exploring every possibility (impossible in games like Go, with more legal positions than atoms in the universe), but by running many random or guided simulations and using their outcomes to focus search where it matters most. AlphaZero replaced MCTS’s random rollouts with a neural network’s own value and policy estimates, and replaced hand-crafted evaluation functions with a network trained purely through self-play reinforcement learning — no human game data, no opening books, no endgame tables. MuZero (covered in the companion model-based RL article) later removed even the requirement of knowing the game’s rules. Used in board games (Go, Chess, Shogi), general game-playing research, and combinatorial planning problems beyond games.
The Four-Phase MCTS Loop
graph LR
A[Selection: descend via UCB1/PUCT] --> B[Expansion: add a new node]
B --> C[Simulation: rollout or network estimate]
C --> D[Backpropagation: update the path]
D -->|repeat N times| A
style D fill:#6366f1,color:#fff
Problem Statement
Classical game-tree search (minimax with alpha-beta pruning) needs either a shallow enough tree to search exhaustively or a hand-crafted heuristic evaluation function for positions it can’t search all the way to the end of. Games like Go have a branching factor so large that neither is practical with hand-engineering alone. MCTS solves the search problem by allocating computation adaptively, and AlphaZero solves the evaluation problem by learning what a good position looks like, purely from self-play.
Monte Carlo Tree Search: The Four-Phase Loop
Classic MCTS runs four repeated phases per simulation: selection (walk down the tree toward promising, under-explored nodes), expansion (add a new node), simulation/rollout (play out randomly to the end), and backpropagation (update every node on the path with the outcome).
def mcts_simulation(root, env, n_simulations=800):
for _ in range(n_simulations):
node = root
path = [node]
# Selection: descend via UCB1 until reaching an unexpanded node
while node.is_fully_expanded() and not node.is_terminal():
node = node.select_child_ucb1()
path.append(node)
# Expansion: add one new child
if not node.is_terminal():
node = node.expand()
path.append(node)
# Simulation: random rollout to a terminal outcome
outcome = random_rollout(node.state, env)
# Backpropagation: update visit counts and value estimates up the path
for n in reversed(path):
n.visit_count += 1
n.value_sum += outcome
return root.best_child_by_visit_count()
The node-selection rule (UCB1: value + c * sqrt(log(N_parent) / N_child)) is the same optimism-under-uncertainty idea as the UCB exploration strategy covered in the companion exploration article — favor children that are either promising or under-explored.
AlphaZero: Replacing Rollouts and Heuristics With a Trained Network
Random rollouts are a weak signal — most of a random Go game is noise. AlphaZero (Silver et al., 2017) replaces the rollout phase entirely with a neural network (policy, value) = f(state) that directly estimates both a prior probability over moves and the position’s value, and uses those estimates to guide MCTS’s selection phase instead of blind random play:
def alphazero_mcts_select(node, c_puct=1.5):
best_score, best_child = -float("inf"), None
for action, child in node.children.items():
# PUCT: combines the network's prior with a visit-count exploration bonus
exploration = c_puct * node.prior[action] * math.sqrt(node.visit_count) / (1 + child.visit_count)
score = child.mean_value + exploration
if score > best_score:
best_score, best_child = score, child
return best_child
The network itself is trained entirely through self-play: AlphaZero plays games against itself using the current network-guided MCTS to pick moves, and the resulting game outcomes and MCTS visit-count distributions become the training targets for the next version of the network — a virtuous loop where a better network produces better self-play data, which produces an even better network.
def alphazero_training_loss(network, state, mcts_policy_target, game_outcome):
predicted_policy, predicted_value = network(state)
policy_loss = -torch.sum(mcts_policy_target * torch.log(predicted_policy + 1e-8))
value_loss = F.mse_loss(predicted_value, game_outcome)
return policy_loss + value_loss
Note what the network is trained to predict: not human expert moves (there’s no human data at all), but the outcome of MCTS itself — the network is learning to distill what tree search discovers into a single fast forward pass, so that over training, the network’s raw intuition gets closer and closer to what expensive search would have found.
Comparison Table
| Method | Evaluation Signal | Requires Known Game Rules? | Requires Human Data? |
|---|---|---|---|
| Classic MCTS | Random rollouts | Yes | No |
| AlphaGo (early version) | Hand-crafted features + supervised network on human games | Yes | Yes, initially |
| AlphaZero | Self-play-trained value/policy network, PUCT-guided search | Yes | No |
| MuZero (companion article) | Self-play-trained network over a learned model | No | No |
Applications
- Perfect-information board games — Go, Chess, and Shogi are AlphaZero’s original and best-known domains, reaching superhuman play purely from self-play.
- General game-playing research — the self-play-plus-search loop generalizes to any two-player, perfect-information game without game-specific hand engineering.
- Combinatorial optimization and planning — the same search-guided-by-learned-value pattern has been adapted for problems like chip placement and combinatorial scheduling, where “moves” are structured decisions rather than literal game moves.
- Any domain requiring both a fast intuition and slower deliberate search — the AlphaZero pattern (fast network estimate, refined by tree search when time allows) is a template beyond games for combining learned heuristics with exact search.
Key Learnings
- MCTS’s real innovation is spending computation where it matters — adaptively focusing simulations on promising branches rather than searching uniformly, which is what makes it tractable in enormous search spaces where exhaustive search never could be.
- AlphaZero’s self-play loop is a genuinely closed system: no human data anywhere. The network’s targets come entirely from its own tree search’s outcomes, which is what let it discover playing styles that diverged meaningfully from centuries of human game theory.
- Search and learning are complementary, not competing, tools. The network alone (no search) plays well but not at superhuman level; search alone (no learned priors, i.e., classic MCTS) is far too slow to reach the same depth of understanding — the combination is what produces results neither achieves independently.
References
- Coulom, R. (2006). Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Computers and Games.
- Silver, D. et al. (2016). Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature, 529.
- Silver, D. et al. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm.