Monte Carlo Tree Search from Scratch

Monte Carlo Tree Search is a way to decide where to think by counting where thinking has paid off.

It needs no evaluation function, no opening book, and no knowledge of the game beyond its rules. It plays random games, keeps statistics on the moves that led to wins, and grows a tree towards the moves that look best while reserving a little attention for the ones it has not tried enough. This note builds it from the rules of tic-tac-toe up, derives the exploration term instead of quoting it, and measures what each step buys.

The game, in twenty lines#

Everything below needs four operations from a game: list the legal moves, play one, tell whose turn it is, and say who won.

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)]
 
class TicTacToe:
    """Board is a tuple of 9 cells: 0 empty, 1 or 2 for the players."""
    def __init__(self, board=(0,)*9, to_move=1):
        self.board, self.to_move = board, to_move
 
    def moves(self):
        if self.winner() != 0:          # game over: no legal moves
            return []
        return [i for i, c in enumerate(self.board) if c == 0]
 
    def play(self, m):
        b = list(self.board); b[m] = self.to_move
        return TicTacToe(tuple(b), 3 - self.to_move)
 
    def winner(self):
        for a, b, c in LINES:
            if self.board[a] and self.board[a] == self.board[b] == self.board[c]:
                return self.board[a]
        return 0 if 0 in self.board else -1   # -1 = draw, 0 = still playing

The first two lines of moves() look like a formality. They are not; the section on the bug shows what happens without them.

Step 0: a random player and a random playout#

The simplest agent picks a legal move uniformly. The simplest evaluator plays the rest of the game that way and reports who won.

def random_player(state):
    return random.choice(state.moves())
 
def rollout(state):
    """Play uniformly random moves to the end. Return the winner (or -1)."""
    while state.winner() == 0:
        state = state.play(random.choice(state.moves()))
    return state.winner()

Random against random, 1,000 games: the first player wins 558, the second 300, and 142 are drawn. That asymmetry is the baseline everything else is measured against. A single rollout is a terrible estimate of a position. The mean of many rollouts is a noisy but unbiased estimate of one specific thing: how the position fares if both sides play randomly from here.

Step 1: flat Monte Carlo#

Turn the evaluator into a player. For each legal move, run a fixed number of rollouts and pick the move with the best mean score (win = 1, draw = 0.5, loss = 0).

def flat_monte_carlo(state, n=200):
    """Score each move by the mean outcome of random playouts from it."""
    me, best, best_score = state.to_move, None, -1e9
    per_move = n // len(state.moves())
    for m in state.moves():
        score = 0.0
        for _ in range(per_move):
            w = rollout(state.play(m))
            score += 1.0 if w == me else 0.5 if w == -1 else 0.0
        if score > best_score:
            best, best_score = m, score
    return best

With 200 playouts per decision, flat Monte Carlo as the first player beats the random player in 199 of 200 games. Against weak opponents, averaging random futures is already strong.

Two bottlenecks remain. First, the budget is spread evenly: a move that loses in every playout gets as many samples as the best move. Second, the evaluation never stops being random. Flat Monte Carlo answers "how good is this move against a random opponent", and a real opponent is not random. A move that sets a trap the opponent will see may score well on average and lose in practice.

Both fixes are the same idea: spend more samples where they matter, and let the samples build a tree so that deeper decisions stop being random too.

Step 2: the allocation problem, and UCB1#

Treat each move at the root as a slot machine arm with unknown mean reward $\mu_i \in [0, 1]$. After $n_i$ pulls, the sample mean is $\bar{X}_i$. The question is which arm to pull next.

Hoeffding's inequality bounds how far a sample mean of $n$ bounded rewards strays from the truth:

Pick $\varepsilon$ so that the chance of underestimating the arm shrinks as the total number of pulls $t$ grows, say to $t^{-4}$:

Now act optimistically: pull the arm whose plausible upper value is highest.

The first term exploits. The second explores: it is large for arms pulled rarely, and it grows slowly (as $\sqrt{\ln t}$) for every arm that is ignored, so no arm is ever abandoned for good. Auer, Cesa-Bianchi and Fischer (2002) showed this rule's regret grows only logarithmically in $t$. The constant in front of the square root is usually written $c$, and $c = \sqrt{2}$ is exactly the derivation above. Any reward outside $[0, 1]$ breaks the bound, which is why the scores here are 1, 0.5 and 0.

Step 3: UCB applied to trees (UCT)#

Kocsis and Szepesvári (2006) applied UCB1 at every node of a growing game tree, treating each node's children as arms. One iteration has four phases:

The one subtle part is perspective. A node's value must be stored from the viewpoint of the player who chose the move into it, because that is the player who will compare it against its siblings.

class Node:
    def __init__(self, state, parent=None, move=None):
        self.state, self.parent, self.move = state, parent, move
        self.children = []
        self.untried = state.moves()
        self.N = 0          # visits
        self.W = 0.0        # total reward, from the view of the player who moved INTO this node
 
    def ucb1(self, c):
        return self.W / self.N + c * math.sqrt(math.log(self.parent.N) / self.N)
 
def mcts(root_state, iters=1000, c=math.sqrt(2)):
    root = Node(root_state)
    for _ in range(iters):
        node = root
        # 1. Select: descend while the node is fully expanded and not terminal.
        while not node.untried and node.children:
            node = max(node.children, key=lambda ch: ch.ucb1(c))
        # 2. Expand: add one child for an untried move.
        if node.untried:
            m = node.untried.pop(random.randrange(len(node.untried)))
            node.children.append(Node(node.state.play(m), node, m))
            node = node.children[-1]
        # 3. Simulate: random playout from the new node.
        w = rollout(node.state)
        # 4. Backpropagate: credit each node from the view of the player who moved into it.
        while node is not None:
            node.N += 1
            mover = 3 - node.state.to_move
            node.W += 1.0 if w == mover else 0.5 if w == -1 else 0.0
            node = node.parent
    return max(root.children, key=lambda ch: ch.N).move

The final move is the most visited child, not the one with the highest mean. Visits are the more robust statistic: a child with a high mean from five visits is a guess; a child with 600 visits is a conclusion that survived UCB's attempts to look elsewhere.

Step 4: the terminal-node bug#

The first version of this code had moves() return every empty cell, even after someone had won. Nothing crashed. The tree simply kept expanding past finished games, running rollouts from positions in which the winner had already been decided but more stones kept appearing.

Its measured symptoms were subtle enough to miss:

Tic-tac-toe is a draw under perfect play, so the self-play row is the diagnostic. Printing the tree for a losing position showed the cause: a child where O had already completed a row still had grandchildren, and their rollouts credited X with wins in a game X had lost. Terminal states must have no moves. Every MCTS implementation needs a test that checks this.

What the budget buys#

With the fix in place, sweeping the iteration count for MCTS playing second against a random first player (300 games each):

And against a strong opponent, MCTS with $n$ iterations as X against MCTS(1000) as O, 100 games each:

Two things stand out. Fifty iterations is already enough to hold a 1,000-iteration opponent to draws most of the time. And MCTS(1000) still loses occasionally, to random once in 300 games and to MCTS(200) six times in 100. MCTS converges to minimax in the limit, but at any finite budget it is a statistical estimate, and estimates are sometimes wrong. Flat Monte Carlo with 1,000 playouts drew all 100 games against MCTS(1000) as well; in a game this small, the tree's advantage shows up against weak play rather than strong.

Improvements that matter in bigger games#

Tic-tac-toe hides the costs that dominate real games. Four standard improvements address them.

Transpositions. The same position is reached by different move orders. A tree stores it many times and splits its statistics. A table keyed by the position shares them:

table = {}   # (board, to_move) -> [N, W]
 
def stats(state):
    return table.setdefault((state.board, state.to_move), [0, 0.0])

The tree becomes a directed acyclic graph, and backpropagation must decide whether to update shared entries once or once per path. Most implementations update along the path actually taken and accept the small bias.

Rollout policies. Uniform rollouts estimate value against a random opponent. A cheap heuristic policy (take an immediate win, block an immediate loss) makes rollouts closer to real play:

def heuristic_move(state):
    me, opp = state.to_move, 3 - state.to_move
    for m in state.moves():                               # win now if possible
        if state.play(m).winner() == me:
            return m
    for m in state.moves():                               # else block the opponent's win
        b = list(state.board); b[m] = opp
        if TicTacToe(tuple(b), me).winner() == opp:
            return m
    return random.choice(state.moves())

The trade is speed against bias. A rollout policy that is too deterministic makes every rollout identical and the mean worthless. AlphaGo-style systems replace rollouts entirely with a learned value function, which is the step taken in self-play and the arms race.

Progressive widening. In games with hundreds of moves per position, or continuous actions, a node cannot expand every child before descending. Progressive widening allows a node with $N$ visits to hold only about $k N^{\alpha}$ children ($\alpha$ around 0.25 to 0.5), adding new ones as evidence accumulates.

Tuning $c$. $\sqrt{2}$ is the Hoeffding constant for rewards in $[0, 1]$, not a law. Games with long horizons and noisy rollouts usually want smaller $c$; games with deceptive early moves want larger. Tune it by self-play matches, not by intuition.

What to try next#

1. Run the self-play test first: MCTS against itself on a game with a known value (tic-tac-toe is a draw). Any decisive result is a bug.
2. Print the root's children with $N$ and $W/N$ for a handful of tactical positions where the right move is obvious. Check that the obvious move has the most visits.
3. Sweep iterations on a log scale (10, 100, 1,000, 10,000) and plot win rate against a fixed opponent. The curve should rise and flatten; if it falls, perspective is flipped somewhere.
4. Swap uniform rollouts for heuristic_move and repeat the sweep. Measure both strength and iterations per second.
5. Add a transposition table and count unique positions in the tree versus total nodes.
6. Move to Connect Four, where the board is too big for MCTS to solve and the value of $c$ and the rollout policy start to dominate. For hidden cards and imperfect information, the tree has to change shape entirely, which is the subject of the hidden hand.