AI AI-01.07
Monte Carlo Tree Search and AlphaGo
Selection, expansion, simulation and backpropagation, the UCT formula, and how AlphaGo combined tree search with policy and value networks.
The big idea
Alpha-beta search needs two things that Go does not offer: a manageable branching factor and a reliable way to score a position. A Go board has around 250 legal moves per turn, and even strong players struggle to say who is ahead in the middle of a game. For decades the best Go programs played at amateur level.
Monte Carlo Tree SearchA search algorithm that grows a game tree selectively, guided by statistics from many simulated games, balancing moves that look good with moves that are under-explored. (MCTS) changes the question. Instead of asking "what is this position worth?", it asks "if I play this move and the game continues, how often do I win?", and it answers by playing the game out many times. It spends those simulations unevenly: most go to moves that look promising, a few go to moves that have not been tried much, just in case.
Think of choosing a restaurant in a new city. You keep going back to the place that has been best so far, but every so often you try somewhere new, because one bad meal is not enough evidence to rule a place out. The more often you have been somewhere, the more you trust your opinion of it. MCTS makes that intuition precise with one formula.
How it works
Each node in the MCTS tree stores two numbers: how many simulations passed through it (visits, ) and how many of those the player who moved there won (wins, ). The search repeats a four-phase cycle thousands of times:
1. Selection
Start at the root (the current position) and walk down the tree. At each node, pick the child with the highest UCT score (step 5 below explains it) until you reach a node that still has untried moves, or the end of the game.
2. Expansion
Add one child for an untried move. The tree grows by one node per iteration, and only along paths the search has chosen to explore. That is how MCTS copes with 250 moves per turn: bad moves get a node or two and are then mostly ignored.
3. Simulation
From the new node, play the game to the end quickly, choosing moves at random or with a cheap rule of thumb. This is a rolloutA fast simulated game from a position to the end, used to estimate who is likely to win. Also called a playout.. One rollout is a very noisy estimate, but thousands of them average out, and they need no knowledge of the game beyond its rules.
4. Backpropagation
Walk back up the path to the root. Every node on it gets one more visit, and a win (or half a win for a draw) if the result was good for the player who made the move into that node. The counts now reflect one more game.
5. The UCT formula: explore or exploit
At each step of selection, MCTS uses UCTUpper Confidence bounds applied to Trees: choose the child maximizing w/n + c * sqrt(ln N / n), the win rate plus an exploration bonus that shrinks with visits. (Upper Confidence bounds applied to Trees) to choose the child with the highest
where is the parent's visit count and is a constant, often around . The first term is exploitation: the win rate so far. The second is exploration: a bonus that is large when a child has few visits and shrinks as it gets more. It also grows slowly with , so no move is ever abandoned for good.
Work through Figure 2 with and . Move A: plus , total 1.45. Move B: . Move C: . C has the worst record but the least evidence, so it gets another look. If it loses again, its win rate and bonus both fall and A takes over.
6. Choosing the actual move
When the time budget runs out, MCTS plays the root child with the most visits, not the highest win rate. Visit counts are the robust signal: a move with a 100 percent win rate after 2 visits is a lucky guess, while a move visited 1,600 times has earned the search's trust.
Try it
There is no lab for this lesson; the code below is MCTS in about 50 lines, playing tic-tac-toe from an empty board with 5,000 iterations:
import math, random
LINES = [(0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6),
(1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)]
def winner(b):
for i, j, k in LINES:
if b[i] != "." and b[i] == b[j] == b[k]:
return b[i]
return "draw" if "." not in b else None
def moves(b):
return [i for i, c in enumerate(b) if c == "."]
class Node:
def __init__(self, board, player, parent=None):
self.board, self.player, self.parent = board, player, parent
self.children, self.untried = {}, moves(board)
self.visits, self.wins = 0, 0.0 # wins for the player who moved here
def uct(child, parent, c=1.4):
explore = c * math.sqrt(math.log(parent.visits) / child.visits)
return child.wins / child.visits + explore
def mcts(board, player, iterations, rng):
root = Node(board, player)
for _ in range(iterations):
node = root
# 1. Selection: descend by UCT while the node is fully expanded
while not node.untried and node.children:
node = max(node.children.values(), key=lambda ch: uct(ch, node))
# 2. Expansion: add one untried move as a new child
if node.untried and not winner(node.board):
m = node.untried.pop(rng.randrange(len(node.untried)))
b = node.board[:m] + node.player + node.board[m + 1:]
nxt = "O" if node.player == "X" else "X"
node.children[m] = node = Node(b, nxt, node)
# 3. Simulation: random playout to the end of the game
b, p = node.board, node.player
while not winner(b):
m = rng.choice(moves(b))
b, p = b[:m] + p + b[m + 1:], "O" if p == "X" else "X"
w = winner(b)
# 4. Backpropagation: update counts on the way back to the root
while node.parent:
mover = node.parent.player
node.visits += 1
node.wins += 1 if w == mover else 0.5 if w == "draw" else 0
node = node.parent
root.visits += 1
return root
root = mcts("." * 9, "X", 5000, random.Random(7))
for m, ch in sorted(root.children.items(), key=lambda kv: -kv[1].visits):
print(f"square {m}: visits {ch.visits:5}, score {ch.wins / ch.visits:.2f}")Output
square 4: visits 1608, score 0.74
square 8: visits 614, score 0.68
square 2: visits 612, score 0.67
square 6: visits 608, score 0.67
square 0: visits 430, score 0.64
square 3: visits 386, score 0.63
square 7: visits 288, score 0.60
square 5: visits 284, score 0.60
square 1: visits 170, score 0.53 The search puts 1,608 of its 5,000 simulations into the centre square (4), then roughly 600 each into three of the corners, and the fewest into the edges (squares 1, 3, 5 and 7). That is the classic ranking of tic-tac-toe openings, found without any knowledge of strategy, only rules and random games. The scores are high (0.53 to 0.74) because random playouts are poor defence: random opponents lose a lot. That bias is the weakness the next section fixes.
Things to try if you run it yourself:
- Change the iterations from 5,000 to 100 and see the ranking become noisy.
- Set
c=0inuct. With no exploration bonus, the search pours nearly all 5,000 simulations into whichever move got lucky early, which for some seeds is a corner rather than the centre. - Change the random seed: the counts move, but the centre stays on top.
Going deeper
AlphaGo: networks that guide the search
Random rollouts are cheap but dumb, and with 250 moves per turn the tree still grows slowly. AlphaGo kept the MCTS loop and added two deep neural networks, trained first on human expert games and then by playing against itself:
- A policy networkA neural network that takes a position and outputs a probability for each legal move, an estimate of which moves a strong player would choose. looks at a position and gives a probability for each move. Selection uses it as a prior, so strong-looking moves are explored first and most of the 250 moves are barely touched. This narrows the breadth of the search.
- A value networkA neural network that takes a position and outputs an estimate of the probability of winning from it. looks at a position and estimates the chance of winning. It replaces or supplements the rollout at the leaf, so the search does not need to play every game to the end. This cuts the depth of the search.
The selection rule changes accordingly: the exploration bonus for a move is scaled by the policy network's probability, so the search explores where the network thinks good moves are. Later systems in the same line (AlphaGo Zero and AlphaZero) dropped human games and rollouts entirely, learning both networks from self-play alone, and the same algorithm learned chess and shogi as well as Go.
Search and learning, together
The combination is the lesson. The networks give fast intuition that is usually right; the search checks that intuition by looking ahead, and its improved move choices become training targets that make the networks better. The same pattern, a learned model proposing and a search verifying, shows up in modern systems far from board games, including methods that sample several reasoning paths from a language model and search over them.
Where MCTS works and where it struggles
MCTS needs no evaluation function, can be stopped at any time with a usable answer, and grows the tree asymmetrically toward what matters. It struggles in sharp tactical positions where a single narrow line decides the game: random rollouts rarely find it, which is why alpha-beta remained stronger in chess until learned networks were added. MCTS also extends to games with chance and hidden information, and to planning problems such as scheduling, where a "playout" is a quick simulated plan.
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Alpha-beta plus evaluation | Moderate branching and a good evaluation function, sharp tactics (chess) | Huge branching factors and positions that are hard to score (Go) |
| MCTS with random rollouts | No domain knowledge beyond the rules; anytime answers | Rollouts are weak and noisy; needs very many simulations |
| MCTS with policy and value networks | Superhuman play in Go, chess and shogi; strong priors focus the search | Expensive training; networks can have blind spots the search must catch |
Common mistakes
- Picking the final move by win rate instead of visit count. A rarely visited move with a lucky record is not reliable.
- Setting the exploration constant to zero. The search then stops checking moves that started badly and can miss the best one.
- Backing up wins from a single player's point of view at every level. Each node's wins must be counted for the player who moved into it.
- Treating the score from random rollouts as a true win probability. It is the win rate against random play, which is biased.
In the wild
Google DeepMind
AlphaGo (opens in a new tab)DeepMind describes Go as a long-standing grand challenge, with about 10 to the power of 170 possible board configurations, where the strongest programs had only reached amateur level. AlphaGo combined deep neural networks with search: a policy network that selects the next move and a value network that predicts the winner, trained first on thousands of expert games and then by playing against versions of itself. It beat European champion Fan Hui 5-0 in October 2015 and Lee Sedol 4-1 in Seoul in March 2016, including the unexpected Move 37 in game two. Those are exactly the two networks that steer the MCTS loop in this lesson.
Check yourself
-
What are the four phases of one MCTS iteration, in order?
Show answer
B. Selection, expansion, simulation, backpropagation Walk down the tree (selection), add a node (expansion), play out a game (simulation), then update counts on the path (backpropagation).
-
In the UCT formula, what happens to a child's exploration bonus as its visit count grows?
Show answer
B. It shrinks The bonus is c * sqrt(ln N / n). As n grows the bonus shrinks, so well-tested moves are judged mainly on their win rate.
-
After the search, move X has 3 visits and 3 wins; move Y has 900 visits and 560 wins. Which should MCTS play?
Show answer
B. Y, because it has the most visits Visit counts are the robust choice. Three lucky wins are weak evidence; the search sent 900 simulations to Y because it kept looking good.
-
In AlphaGo, what did the policy network contribute to the search?
Show answer
B. Priors that focused exploration on promising moves, narrowing the breadth The policy network's move probabilities steer selection toward strong-looking moves, so most of the roughly 250 legal moves get little attention.
-
Why did MCTS succeed in Go where alpha-beta had struggled?
Show answer
B. MCTS needs no handcrafted evaluation and grows the tree selectively despite huge branching Rollouts (and later a learned value network) replace the missing evaluation function, and selective growth copes with the branching factor.
Recap
- MCTS repeats selection, expansion, simulation and backpropagation, growing the tree where it matters.
- Each node keeps visits and wins; UCT adds an exploration bonus that shrinks with visits.
- The final move is the root child with the most visits.
- AlphaGo added a policy network (which moves to consider) and a value network (who is winning) to MCTS.
- Learned intuition plus explicit search is a pattern that reaches well beyond games.