Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 46 ยท Adversarial Search

Expectiminimax and Monte Carlo Tree Search

Handle dice with chance nodes and expectimax, then learn Monte Carlo Tree Search: selection, expansion, simulation, backpropagation and UCB1, built and run live on tic-tac-toe.

Minimax assumes a deterministic game with perfect information: the same move always leads to the same position, and the board shows everything. Many games break that assumption. Backgammon rolls dice. Card games hide the cards. And some games, above all Go, are so wide and so hard to score that a handwritten evaluation function never worked well.

This lesson covers two answers. Expectiminimax (often shortened to expectimax) adds chance nodes to the game tree, so the same search can handle dice. Monte Carlo Tree Search (MCTS) drops the evaluation function altogether and judges moves by playing thousands of random games. MCTS is the idea behind the first programs that beat professional Go players. You will build both, and MCTS will play tic-tac-toe.

Chance nodes

An expectiminimax tree has three kinds of node:

  • MAX nodes, where you choose the move that gives the largest value;
  • MIN nodes, where the opponent chooses the smallest value;
  • chance nodes, where nature moves: a die roll, a shuffled card, a random event.

The value of a chance node is the expected value of its children: the sum of probability times value. For a fair die that is the plain average of the six outcomes.

graph TD
    M["MAX: choose a move"] --> A["Cautious<br/>chance node"]
    M --> B["Bold<br/>chance node"]
    A -- "p = 0.5" --> A1["4"]
    A -- "p = 0.5" --> A2["6"]
    B -- "p = 0.9" --> B1["10"]
    B -- "p = 0.1" --> B2["-20"]

The cautious move is worth 0.5 x 4 + 0.5 x 6 = 5. The bold move is worth 0.9 x 10 + 0.1 x (-20) = 7, so MAX takes the risk.

Treat the chance nodes as MIN nodes instead and you get the worst-case view: cautious is worth 4, bold is worth -20, and MAX plays it safe. Which view is right depends on what you want. Against a real opponent, assuming the worst is sensible. Against dice, which are not out to get you, the average is the right thing to maximize. The program below builds the tree from nested tuples, evaluates it both ways, and then checks the claim by simulation.

Python Expectimax versus worst-case on a small tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The simulation confirms the expected values: the means come out near 4.99 for the cautious move and 6.95 for the bold one, close to 5 and 7. The last two lines show a subtle point. Cubing every number keeps their order (bigger stays bigger), so worst-case search chooses exactly as before. Expectimax changes its mind from bold to cautious, because cubing stretches the gaps and the rare -20 now weighs -8,000 against only 1,000 for the win. Expectimax needs utilities on a meaningful scale, where an outcome twice as good is worth twice as much. Minimax only needs a ranking.

Expectiminimax is also expensive. With a branching factor b, a chance node with n outcomes (21 distinct rolls in backgammon) multiplies the cost of every ply by n, so programs for such games search only a few plies and lean heavily on the evaluation function. And alpha-beta pruning is much harder to apply, because a chance node's value depends on all of its children.

Learning from random games

Now consider a game where the evaluation function is the problem. In Go, a position's value depends on subtle long-range patterns that nobody managed to write down as a fast formula. The idea of Monte Carlo methods is to skip the formula: to estimate how good a position is, play many random games from it and count how often you win. A random game is a rollout (or playout). Single random games are almost worthless, but the average of thousands tells you something real.

Estimating each move separately by flat sampling is wasteful, though. Moves that are clearly bad get as many samples as promising ones. MCTS spends its samples where they matter and builds a search tree that grows towards the interesting lines.

The four phases of MCTS

MCTS repeats four steps as many times as the time budget allows. Each node of the tree stores a visit count and a score.

graph LR
    S["1. Selection<br/>walk down the tree<br/>using UCB1"] --> E["2. Expansion<br/>add one new child"]
    E --> R["3. Simulation<br/>play randomly<br/>to the end"]
    R --> B["4. Backpropagation<br/>update counts and<br/>scores up to the root"]
    B --> S

One MCTS iteration. After the last iteration, the move at the root with the most visits is played.

  1. Selection. Start at the root and repeatedly step to the child that looks most promising, until you reach a node that still has untried moves. "Most promising" is decided by the UCB1 rule below.
  2. Expansion. Add one new child to the tree by trying one untried move.
  3. Simulation. From the new node, play random moves for both sides until the game ends.
  4. Backpropagation. Walk back up to the root and add the result to every node on the path: one more visit, plus a win, draw or loss.

The tree stays lopsided: good moves get deep and well measured, bad moves stay shallow. Because MCTS only needs the rules of the game, it works for any game where you can list the legal moves and decide who won, even if no one knows a good evaluation function.

UCB1: exploring versus exploiting

Selection has a dilemma. Should the search keep sampling the move with the best win rate so far (exploit), or sample a move it has tried only a few times, which might be better than it looks (explore)? The formula that balances them is UCB1, from the study of multi-armed bandits (slot machines with hidden payout rates):

TEXT
score(child) = wins / visits  +  C * sqrt( ln(parent visits) / visits )

The first term rewards a high win rate. The second grows when a child has few visits compared with its parent, and shrinks as the child is sampled. A common constant is C = 1.41, which is the square root of 2. Rarely tried moves get periodic second chances, but not forever.

You can see the idea without any game. Three slot machines pay out with hidden probabilities 0.30, 0.50 and 0.65. We compare random pulling, a greedy policy that always pulls the arm with the best average so far, and UCB1. For each policy we play 1,000 pulls and average over 20 fixed seeds.

Python UCB1 on a three-armed bandit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the single run, greedy pulled the worst arm 998 times out of 1,000: an early lucky streak convinced it, and it never looked elsewhere. UCB1 spent most of its pulls (844) on the best arm while still checking the others. Over 20 seeds UCB1 averages about 607 wins against about 494 for greedy and about 492 for pure random pulling.

In MCTS, each child of a node is an "arm", and a win in the rollout is a payout. That is exactly why UCB1 works for selection.

MCTS for tic-tac-toe

Tic-tac-toe is small enough to verify the result: a good player never loses. The program below follows the four phases literally. A node stores the board, who moves next, its parent, and visits and score. The score of a node counts results from the point of view of the player who made the move leading to it, because that is the player the parent wants to optimize when choosing among its children. A draw counts as half a win.

Python MCTS plays tic-tac-toe

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the first table. The centre square (4) received 463 of the 2,000 visits and has the best win rate, 0.73. The corners follow, and the edges (1, 3, 5, 7) are the worst, which matches what strong tic-tac-toe players know, yet the program was told none of it. Then the tournaments: with only 10 iterations per move MCTS still loses 4 of 20 games to a random player, with 100 it beats the random player in all 20 games but loses 3 of 10 games to perfect play, and with 1,000 iterations it draws all 10 games against perfect play. More iterations give more accurate statistics, which is the entire mechanism.

Why play the most-visited move, not the best win rate? A child with a great win rate but a handful of visits might be a fluke. The visit count is a robust measure of how much the search trusts a move, because UCB1 keeps returning to children that keep looking good.

Strengths and limits of MCTS

  • No evaluation function needed. Only the rules matter. This is why MCTS conquered Go and is common in general game playing and puzzle solving.
  • Anytime. You can stop after any iteration and play the most-visited move.
  • Selective. The tree grows where the action is, instead of uniformly like depth-limited minimax.
  • Handles chance. Dice are just part of the random rollout.
  • Weak at sharp tactics. A single forced losing line hidden among many plausible moves can be missed, because random rollouts rarely find "only moves". Strong programs replace random rollouts with learned policies and value estimates, which is how AlphaGo-style systems combine this tree search with neural networks.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the value of a chance node in expectiminimax?

    A chance node averages its children, weighted by probability. This is the expected value.
  2. 2. Cubing every utility in a game tree (which keeps the order of the numbers) can change the best move for which algorithm?

    Minimax only compares values, so order-preserving changes do not matter. Expectimax averages values, so the gaps between them matter and its choice can change.
  3. 3. What happens in the simulation phase of MCTS?

    The rollout plays (usually random) moves for both sides to a terminal position; the result is then backpropagated.
  4. 4. In UCB1, what is the purpose of the term sqrt(ln(N) / n)?

    The bonus is large when a child has few visits relative to its parent and shrinks as the child is sampled, balancing exploration and exploitation.
  5. 5. After the iterations finish, which root move does MCTS usually play?

    The visit count is the most robust signal, since a high win rate on very few visits may be luck.

Summary

  • Expectiminimax adds chance nodes whose value is the probability-weighted average of their children; it needs utilities on a meaningful scale.
  • Chance multiplies the branching of the tree, and alpha-beta pruning is harder to apply, so such programs search shallowly.
  • MCTS judges moves with random playouts instead of an evaluation function and builds a lopsided tree: selection, expansion, simulation, backpropagation.
  • UCB1 balances exploiting good moves and exploring rarely tried ones.
  • With more iterations the statistics improve; in the demo 1,000 iterations per move never lost to perfect tic-tac-toe play.
  • MCTS shines when no good evaluation exists, but can miss narrow tactical lines.

Next: Propositional Logic.