# AlphaGo and MCTS

Monte Carlo tree search guided by learned policy and value networks — the combination that beat top human Go players.

**Rests on:** Binary Tree Traversal

*Machine Learning · Reinforcement Learning*


## Why learn this

This is the story of how a computer beat the world champion at Go, a board game so complex that every possible arrangement of pieces on the board exceeds the number of atoms in the observable universe. AlphaGo succeeded not by calculating every outcome—which would take longer than the age of the universe—but by combining two ideas: a fast way to guess good moves (a policy network) and a way to judge positions without playing to the end (a value network), wrapped around a search method called Monte Carlo tree search. Understanding this unlocks your path into Reinforcement Learning—the branch of AI where agents learn by trial and error—and shows you how AI systems learn to win games by playing against themselves. You will see how playing millions of games against oneself generates training data, how search plus learned evaluation beats either alone, and why taking more time to think before answering pays off. These are the same principles behind AI agents that plan, call tools, and act in loops.


## The intuition

Imagine you are a chess player with only seconds per move. You cannot calculate every line to the end. Instead, you rely on instinct (which moves look promising) and a quick sense of who is winning. You might try one move, see the opponent's likely reply, then your reply, and so on for a few moves — but you prune the branches that look hopeless and spend more time on the promising ones. AlphaGo does exactly this, but at a scale no human can match. It plays out thousands of imagined games in its 'mind' in a fraction of a second, using its learned intuition to guide where to look and its learned judgment to evaluate the positions it reaches. The key insight: you do not need to see the entire tree of possibilities. You need a smart way to explore the most promising branches and a reliable way to judge when you have gone deep enough. That is Monte Carlo tree search — a way to balance exploring new moves against exploiting the ones that have already worked well in this position.


## An analogy

Think of a detective trying to solve a mystery. The detective has limited time and must decide which leads to chase. Each lead is a move in a game tree. The detective's intuition (policy network) says which leads look most promising based on experience. The detective's judgment (value network) says how close they are to solving the case — or in Go, how likely they are to win from a given board position. The detective does not follow every lead to the end. Instead, they follow a few promising ones, see what happens, and then decide where to focus next. They might even simulate what would happen if they took a wild guess and followed it for a while, then use that outcome to update their beliefs about that lead. That is Monte Carlo tree search: you repeatedly pick a move, play out a random or guided game to the end, and record whether you won. Over many repetitions, you build a statistical picture of which moves lead to victory. This works because of the law of large numbers — with enough samples, the average outcome converges to the true probability of winning. But in Go, the branching factor is so huge (about 200 legal moves at the start) that you cannot just sample randomly. You need guidance — that is where the policy network comes in. It tells you which moves are worth trying, so you don't waste samples on terrible moves. And the value network saves you from having to play each simulation to the very end — it estimates the outcome from the current position, which is much faster. Where the analogy breaks down: a detective can change their mind mid-investigation; MCTS in AlphaGo makes a decision at the root and then commits, though it re-searches each move. Also, the detective's intuition is static; AlphaGo's policy network gets better as it learns from self-play.


## Definition

Monte Carlo tree search guided by learned policy and value networks — a search algorithm that builds a tree of possible moves, simulating games to estimate each move's winning probability, while using neural networks to prioritise which branches to explore and to evaluate positions without playing to the end.


## How it connects

Your library notes that AlphaGo is the narrative bridge from classical ML into modern AI — it is the clearest demonstration of test-time search paying off. It belongs to the Reinforcement Learning family: the agent (AlphaGo) interacts with an environment (the Go board), takes actions (placing stones), and receives a reward at the end (win or lose). It builds on the exploration-exploitation tradeoff — you must try new moves (explore) but also stick with moves that have worked (exploit). The value network uses the principle that the value of a position is related to the rewards it can eventually lead to, forming the mathematical foundation for how the network estimates future success. Q-learning is the simpler cousin: it learns the value of taking an action in a state, but it becomes infeasible at scale — AlphaGo's networks compress that value function into a neural net. The policy network is a direct policy optimisation: it maps a board state directly to a probability distribution over moves.


## The mathematics

This concept rests on probability and statistics — specifically, the idea of estimating an unknown quantity by sampling. In Go, the unknown is: 'What is the probability that I win if I play this move?' You cannot know it exactly without searching the entire game tree, which is impossible. So you estimate it by playing out many imaginary games from this position and counting how often you win. That is a Monte Carlo method — named after the casino, because it relies on randomness. The more games you play, the more accurate your estimate becomes (the law of large numbers). But each game is a full sequence of moves, which is expensive. So you use two tricks: a policy network that suggests which moves to try (so you don't waste time on terrible ones), and a value network that estimates the outcome from the current position (so you don't have to play to the end). The mathematics of the tree search itself is a combination of: (1) selecting the most promising node using a formula that balances exploration and exploitation, (2) expanding the tree by adding a new child node, (3) simulating from that node (or using the value network), and (4) backpropagating the result up the tree to update the win counts. The selection formula, called Upper Confidence Bound applied to Trees (UCT), is: for each child node, compute (win rate) + (a constant) * sqrt(log(parent visits) / child visits). The first term exploits good moves; the second term explores moves that have not been tried often. The constant controls the balance.

For each child node j of a node n, compute:

UCT(n, j) = WinRate(j) + c * sqrt( ln(N(n)) / N(j) )

Where:
- WinRate(j) = Wins(j) / N(j) — the proportion of simulations from node j that ended in a win.
- N(j) — the number of times node j has been visited (simulations that passed through it).
- N(n) — the number of times the parent node n has been visited.
- ln — the natural logarithm.
- c — an exploration constant that balances exploitation and exploration. Typical values are around √2 ≈ 1.414, but AlphaGo used a tuned value (often around 1.4 or 2.0).

AlphaGo's full MCTS modifies this: instead of using just random simulations, it uses a policy network P(s, a) to suggest moves, and a value network V(s) to evaluate leaf nodes. The selection formula then becomes:

Q(s, a) + c * P(s, a) * sqrt( N(parent) ) / (1 + N(s, a) )

Where Q(s, a) is the current win rate estimate for action a in state s, P(s, a) is the prior probability given by the policy network, and N(s, a) is the visit count for that action.


## A worked example

```
Consider a simplified game tree with just two moves from the root: move A and move B. We have already simulated 10 games from the root. Move A has been tried 6 times and won 4 times (win rate 0.667). Move B has been tried 4 times and won 1 time (win rate 0.25). We have a constant 'c' equal to 2. The parent (root) has been visited 10 times.

Step 1: For move A: win rate = 4/6 = 0.667   # We first compute the win rate (exploitation).
Step 2: For move A: exploration = 2 * sqrt(log(10) / 6) = 2 * sqrt(0.383) ≈ 2 * 0.619 = 1.238   # We compute the exploration bonus using the natural log of parent visits divided by child visits, times the constant 2.
Step 3: For move A: UCT = 0.667 + 1.238 = 1.905   # We add exploitation and exploration.
Step 4: For move B: win rate = 1/4 = 0.25   # Same for move B.
Step 5: For move B: exploration = 2 * sqrt(log(10) / 4) = 2 * sqrt(0.576) ≈ 2 * 0.759 = 1.518   # The exploration term is larger because B has been visited fewer times.
Step 6: For move B: UCT = 0.25 + 1.518 = 1.768   # Sum for B.
Step 7: Since 1.905 > 1.768, we select move A for the next simulation.   # Even though B has a lower win rate, the exploration bonus is not high enough to overcome the difference. If c were larger, B might be selected.

Result: Move A is chosen for the next playout. After simulating a game from move A and winning, we would update its win count to 5/7, win rate to 0.714, and recompute the UCT values for the next iteration.
```


## From scratch, in Python

```python
import random
import math

# A very small game: a board with only 3 moves.
# We represent a state as a tuple. Each move leads to a new state.
# For simplicity, we'll just use a tree structure.

class Node:
    def __init__(self, state, parent=None, action=None):
        self.state = state          # the game state (here, a string)
        self.parent = parent        # parent node
        self.action = action        # the action that led to this node
        self.children = []          # list of child nodes
        self.visits = 0             # how many times this node was visited
        self.wins = 0               # how many wins from this node
        self.untried_actions = get_legal_actions(state)

    def is_fully_expanded(self):
        return len(self.untried_actions) == 0

    def best_child(self, c=2.0):
        # Use the UCT formula to pick the best child
        best = None
        best_value = -float('inf')
        for child in self.children:
            # UCB1 formula: wins/visits + c * sqrt(log(parent_visits)/visits)
            uct = child.wins / child.visits + c * math.sqrt(math.log(self.visits) / child.visits)
            if uct > best_value:
                best_value = uct
                best = child
        return best

    def expand(self):
        # Take one untried action and add a child node
        action = self.untried_actions.pop()
        next_state = do_action(self.state, action)
        child = Node(next_state, parent=self, action=action)
        self.children.append(child)
        return child

    def update(self, result):
        # result is 1 for win, 0 for loss
        self.visits += 1
        self.wins += result

    def rollout(self):
        # Simulate a random game from this state to the end
        current_state = self.state
        while not is_terminal(current_state):
            action = random.choice(get_legal_actions(current_state))
            current_state = do_action(current_state, action)
        # Return 1 if the player to move at the root wins, else 0
        return 1 if current_state == 'winner' else 0

    def is_terminal(self):
        # In this toy example, any state that starts with 'winner' is terminal
        return self.state.startswith('winner')

# Hard-coded game rules for the toy: states are strings, legal actions are indices.
def get_legal_actions(state):
    # If state is 's0' (root), moves are 0,1,2. Each leads to a new state.
    if state == 's0':
        return [0, 1, 2]
    # For simplicity, any other state has no legal moves (terminal)
    return []

def do_action(state, action):
    # Returns a new state.
    # For this toy, we just encode the action in the state string.
    return 's' + str(action) + '_winner'  # assume always leads to a win for the root player

# Simple: any state that ends with '_winner' means the root player wins.
def is_terminal(state):
    return state.endswith('_winner')

# MCTS main loop
def mcts(root_state, iterations=100):
    root = Node(root_state)
    for i in range(iterations):
        node = root
        # Selection: descend to the most promising leaf that is fully expanded
        while node.is_fully_expanded() and node.children:
            node = node.best_child()
        # Expansion: if not terminal, expand one child
        if not node.is_terminal():
            if not node.is_fully_expanded():
                node = node.expand()
            # Simulation (rollout) from the new node
            result = node.rollout()
        else:
            # If terminal, just use the outcome
            result = 1 if node.state.endswith('_winner') else 0
        # Backpropagation
        while node is not None:
            node.update(result)
            node = node.parent
    
    # Choose the best child (most visited)
    best_child = max(root.children, key=lambda c: c.visits)
    return best_child.action

# Run it
root_state = 's0'
best_move = mcts(root_state, iterations=1000)
print("Best move:", best_move)
```


## The same thing, with a framework

```python
import torch
import torch.nn as nn

class PolicyValueNet(nn.Module):
    def __init__(self, board_size):
        super().__init__()
        self.conv = nn.Conv2d(1, 32, kernel_size=3, padding=1)
        self.policy_head = nn.Linear(32 * board_size * board_size, board_size * board_size)
        self.value_head = nn.Linear(32 * board_size * board_size, 1)

    def forward(self, state):
        # state: (batch, 1, board_size, board_size)
        x = torch.relu(self.conv(state))
        x = x.view(x.size(0), -1)
        policy_logits = self.policy_head(x)
        value = torch.tanh(self.value_head(x))
        return policy_logits, value

# Example usage:
# board_size = 9
# net = PolicyValueNet(board_size)

```


## What the code does

This PyTorch code defines a simple convolutional neural network with two heads: one outputs policy logits (one per board intersection) and the other outputs a single value between -1 and 1 (win/loss estimate). The `forward` method takes a board state as a tensor, passes it through a convolutional layer (to detect patterns), then flattens and feeds it to two separate fully connected layers. This is what AlphaGo's networks look like conceptually.


## Common misconceptions

**AlphaGo just searched every possible move** — AlphaGo must have checked every possible sequence of moves, because it's a computer.

The Go game tree has more possible games than there are atoms in the universe. It is physically impossible to brute-force search even a tiny fraction. AlphaGo's achievement was not blind search but smart search — using learned intuition to guide where to look. In fact: AlphaGo used Monte Carlo tree search, which explores only a tiny fraction of the game tree, guided by a policy network that proposes promising moves and a value network that evaluates positions without playing to the end.

**Monte Carlo means 'random' in a bad way** — Monte Carlo methods are just random guessing, so they can't be very smart.

Randomness is a tool. By simulating many random (or guided) games, you average out the noise and get an estimate of the true winning probability. This is a powerful statistical technique, not a hack. In fact: Monte Carlo methods use randomness to estimate quantities that are too hard to compute exactly. With enough samples, the law of large numbers guarantees the estimate gets close to the true value.

**The value network is just a win/loss predictor** — The value network outputs a 0 or 1 (win or loss), which is all you need.

In Go, the outcome is not binary — it's a score difference (how many stones are captured). Early in the game, a simple 0/1 is too crude. AlphaGo's value network outputs a continuous estimate of the expected outcome, which is much more informative. In fact: The value network predicts the expected outcome (a real number between -1 and 1, or a winning probability) from a board position, allowing the search to compare positions that are not yet decided.

**MCTS is only for board games** — I don't play Go, so this has nothing to do with me.

MCTS is a general-purpose decision-making algorithm. It is used in robotics, operations research, and increasingly in language model reasoning and agentic AI. The core idea — search over actions, guided by learned heuristics — applies anywhere you make sequential decisions. In fact: MCTS is used in many domains beyond games, including autonomous planning, drug discovery, and as a way for LLMs to think through multiple possible responses before answering.


## In short

AlphaGo beat the world champion by combining neural networks with Monte Carlo tree search. The policy network proposes promising moves, the value network estimates the chance of winning from a position, and MCTS uses these to efficiently explore the game tree, balancing exploration and exploitation. The key lesson: search plus learned evaluation beats either alone. Self-play generated the training data that no human corpus could provide. This idea now influences LLM reasoning, agentic planning, and test-time computation.


## Where this is used

AlphaGo's MCTS is not just a historical curiosity — it is the foundation for several active areas of AI.

**In modern game-playing AI:** DeepMind's successors (AlphaZero, MuZero) use exactly the same combination of neural networks and MCTS, but they learn everything from self-play without any human data. MuZero even learns the environment model itself — it does not need the rules of the game. This approach has been applied to chess, shogi, and Atari games, achieving superhuman performance. In robotics, similar tree search methods plan physical movements.

**In large language models (LLMs):** The idea of search over possible continuations is used in decoding strategies. For example, 'beam search' explores multiple token sequences, and more recent methods like 'tree of thoughts' or 'self-consistency' sample multiple reasoning paths and vote. AlphaGo's core lesson — that you can spend more computation at test time to get better answers — has directly inspired methods like 'chain-of-thought' with multiple attempts, where the model tries several reasoning paths and picks the most consistent one. There is also research into using MCTS to guide LLM reasoning: at each step, the model proposes several possible next sentences (like the policy network), evaluates which are more promising (like the value network), and explores a tree of thoughts. This has been used for mathematical problem solving and code generation.

**In small language models on devices:** Small models suffer from limited capacity, but they can compensate by doing more search at test time. For instance, a small model can use MCTS to explore multiple possible next tokens, evaluate them with a quick heuristic, and choose the best one. This is important for on-device AI where you cannot run huge models but you can run more computation per token. Techniques like 'speculative decoding' also involve a small model proposing candidates and a larger model verifying — a form of search.

**In retrieval-augmented generation (RAG):** RAG systems retrieve documents to ground the LLM's answer. MCTS can be used to decide which documents to retrieve and in what order. For example, an agentic RAG system can treat each retrieval step as an action, use a reward model to evaluate the usefulness of the retrieved chunks, and search over different retrieval plans. This improves answer quality by exploring multiple possible document sets before committing.

**In agentic systems that plan and call tools:** These are the most direct heirs to AlphaGo. An AI agent has a goal, a set of tools (like calculators, web searches, code interpreters), and must decide a sequence of actions. MCTS provides a principled way to plan: at each step, the agent (via an LLM) proposes several possible next actions (policy), simulates what would happen if it took them (using a world model or a model of the tool's output), and evaluates the likely outcome (value network). It then backpropagates the expected success to choose the best plan. Companies like Google DeepMind have used such methods to build agents that can browse the web, book flights, or write code. The key advantage is that the agent can 'think' many steps ahead before acting.

**In everyday applied machine learning:** Beyond LLMs, MCTS is used in: hyperparameter optimisation (treating the choice of hyperparameters as a game tree), in drug discovery (searching over molecular structures), in network routing, and in recommendation systems (exploring the sequence of recommendations). In fraud detection, MCTS can explore sequences of transactions to decide which are likely fraudulent.

**What a developer actually writes:** For a simple application, a developer might use a library like `pymcts` or implement a simple MCTS loop as shown above. For neural-guided MCTS, they would implement a custom training loop in PyTorch: generate games by self-play (the learner plays against itself using MCTS), store the game records, train the policy and value networks on that data, and repeat. The training loop looks like: (1) run many MCTS self-play games, (2) store each state + MCTS visit counts (as a teaching signal for the policy) and the game outcome (as the value target), (3) train the networks to match those targets, (4) repeat. The difficult part is debugging the balance between exploration and exploitation, and ensuring the neural networks are good enough to guide the search — if the policy is wrong, search wastes time; if the value is wrong, the search can misjudge positions.

**What breaks when it's done badly:** The most common failure is when the exploration constant is set too high or too low. Too high, and the search spends forever exploring bad moves; too low, and it gets stuck on a local optimum. Another failure is when the value network is untrained, causing the search to make poor decisions. In LLM-guided MCTS, the LLM's policy might be biased, leading the search to over-explore certain patterns. Debugging MCTS is notoriously hard because the algorithm is stochastic and has many interacting parts.


---

Read this on the web: https://basavapurushottam.com/learn-ai/alphago-and-mcts
