Simple Algorithm
Artificial Intelligence · Hidden Layer · 24 min

Games: Minimax, Alpha–Beta & MCTS

Planning against an opponent.

Chess has more than 104010^{40} legal positions and a game tree of roughly 1015410^{154} nodes, yet engines look far enough ahead to beat any human. Three ideas make that possible: minimax defines what best play means, alpha–beta proves most of the tree irrelevant without looking at it, and Monte Carlo tree search samples what is still too big to search.

What you’ll learn

  • Define a two-player zero-sum game as a search problem, and compute minimax values by depth-first recursion in O(bm)\order{b^m} time and O(bm)\order{bm} memory.
  • Implement alpha–beta pruning, prove that it returns the minimax value, and count the leaves it examines under perfect and random move ordering.
  • Design cutoff searches with evaluation functions, and explain why expectimax, unlike minimax, depends on the scale of the evaluation.
  • Describe Monte Carlo tree search with the UCB1 selection rule, and how AlphaGo combined it with learned policy and value networks.

Games as search problems

A two-player, turn-taking, deterministic game of perfect information is a search problem with an adversary. It is given by an initial state s0s_0, the player to move ToMove(s)\mathrm{ToMove}(s), the legal moves Actions(s)\mathrm{Actions}(s), a transition model Result(s,a)\mathrm{Result}(s,a), a terminal test and a Utility(s)\mathrm{Utility}(s) for terminal states, written from MAX's point of view. In a zero-sum game MIN's utility is the negative of MAX's, so one number per leaf suffices.

Minimax(s)={Utility(s)s terminalmax⁡a Minimax(Result(s,a))MAX to movemin⁡a Minimax(Result(s,a))MIN to move\mathrm{Minimax}(s)=\begin{cases}\mathrm{Utility}(s) & s\text{ terminal}\\ \max_{a}\ \mathrm{Minimax}\big(\mathrm{Result}(s,a)\big) & \text{MAX to move}\\ \min_{a}\ \mathrm{Minimax}\big(\mathrm{Result}(s,a)\big) & \text{MIN to move}\end{cases}
Minimax values back up from the leaves. They are the value of the game under optimal play (Zermelo, 1913): MAX can guarantee at least Minimax(s0)\mathrm{Minimax}(s_0), and MIN can hold MAX to at most that.

A depth-first recursion computes this value by visiting the whole tree: O(bm)\order{b^m} time and O(bm)\order{bm} memory for branching factor bb and maximum depth mm. In chess b≈35b\approx35 and games run to about 100 plies, so the tree has about 35100≈1015435^{100}\approx10^{154} nodes. Exact minimax is out of the question; everything below is about doing less.

Check your understanding

MAX moves, then MIN, then MAX again. The eight leaves, left to right, are 0,4,1,2,6,9,3,50, 4, 1, 2, 6, 9, 3, 5: consecutive pairs share a MAX parent, and consecutive pairs of those share a MIN parent. What is the root's minimax value?

  1. 22
  2. 44
  3. 99
  4. 55
Show the answer

D. 55

The bottom MAX nodes are worth max⁡(0,4)=4\max(0,4)=4, 22, 99 and 55. The MIN nodes take min⁡(4,2)=2\min(4,2)=2 and min⁡(9,5)=5\min(9,5)=5, and the root takes max⁡(2,5)=5\max(2,5)=5.

Alpha–beta pruning

Alpha–beta computes the same value while skipping subtrees that cannot matter. It passes down a window (α,β)(\alpha,\beta): α\alpha is the best value MAX can already guarantee somewhere on the path to the root, and β\beta the best that MIN can guarantee. Once a node's value is proven to lie outside the window, the opponent will never let play reach it, and its remaining children are skipped.

text
function ALPHA-BETA(s, α, β):              # value of s from MAX's point of view
    if TERMINAL(s): return UTILITY(s)
    if TO-MOVE(s) = MAX:
        v ← −∞
        for each a in ACTIONS(s):
            v ← max(v, ALPHA-BETA(RESULT(s, a), α, β))
            if v ≥ β: return v              # MIN above will never allow this: cut
            α ← max(α, v)
        return v
    else:
        v ← +∞
        for each a in ACTIONS(s):
            v ← min(v, ALPHA-BETA(RESULT(s, a), α, β))
            if v ≤ α: return v              # MAX above already has better: cut
            β ← min(β, v)
        return v
# at the root: ALPHA-BETA(s0, −∞, +∞)
DerivationProof sketch, by induction on height
  1. v=max⁡ivi,αi=max⁡(α, r1,…,ri−1)v=\max_i v_i,\qquad \alpha_i=\max\big(\alpha,\,r_1,\dots,r_{i-1}\big)

    Leaves return their exact value. At a MAX node with children c1,…,ckc_1,\dots,c_k, child cic_i is searched with the window (αi,β)(\alpha_i,\beta), where αi≥α\alpha_i\ge\alpha is the running maximum; assume the claim for every child.

  2. r=rj≥β⟹v ≥ vj ≥ rr=r_j\ge\beta\quad\Longrightarrow\quad v\ \ge\ v_j\ \ge\ r

    Cutoff at child jj. If rj≥βr_j\ge\beta, the child failed high, so v≥vj≥rj=r≥βv\ge v_j\ge r_j=r\ge\beta: the node fails high, as claimed.

  3. r>α ⇒ v=r,r≤α ⇒ v=max⁡ivi≤max⁡iri=rr>\alpha\ \Rightarrow\ v=r,\qquad r\le\alpha\ \Rightarrow\ v=\max_iv_i\le\max_ir_i=r

    No cutoff. Each child was exact or failed low (vi≤riv_i\le r_i). If r=max⁡iri>αr=\max_ir_i>\alpha, the first child attaining it beat its own αi\alpha_i, so it is exact, and v=rv=r. If r≤αr\le\alpha, every child failed low and v≤rv\le r. MIN nodes are symmetric.

How much can pruning save? With perfect ordering (the best move first at every node), alpha–beta examines exactly b⌈d/2⌉+b⌊d/2⌋−1b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1 leaves of a uniform depth-dd tree (Knuth & Moore, 1975), about bd/2b^{d/2}: the same time buys twice the depth. With random ordering it examines roughly b3d/4b^{3d/4} for moderate bb, as Knuth and Moore's analysis began to show and Pearl (1982) settled exactly. With the worst ordering it prunes nothing.

Predict before you look

Chess has b≈35b\approx35. With perfect move ordering, what is alpha–beta's effective branching factor, the factor by which the work grows per extra ply on average?

Show the answer

5.9

About bd/2b^{d/2} leaves means a factor of 35≈5.9\sqrt{35}\approx5.9 per ply. A program that could search 6 plies with minimax can search about 12 with perfectly ordered alpha–beta in the same time. Real engines come close to this ideal because iterative deepening supplies good move orders.

Cutoffs, evaluation functions and chance

Real programs stop at a depth limit and apply an evaluation function Eval(s)\mathrm{Eval}(s), an estimate of the minimax value. Classical chess programs used weighted sums of features, Eval(s)=∑iwifi(s)\mathrm{Eval}(s)=\sum_iw_if_i(s), starting from material: pawn 1, knight and bishop 3, rook 5, queen 9. Three refinements matter in practice:

  • Iterative deepening searches to depth 1, 2, 3, … until time runs out; each iteration's best moves order the next one, which is where good move ordering comes from.
  • Transposition tables cache the values of positions reached by different move orders.
  • Quiescence search extends the search through unstable positions, such as pending captures, so that Eval\mathrm{Eval} is applied only to quiet ones. This softens the horizon effect, where a loss is pushed just past the depth limit.

Games with dice add chance nodes. Expectimax replaces the min of a deterministic opponent with an expectation over outcomes rr at chance nodes:

V(s)=∑rP(r) V(Result(s,r)).V(s)=\sum_rP(r)\,V\big(\mathrm{Result}(s,r)\big).
Check your understanding

A program's evaluation function, always positive, is replaced by its cube, Eval3\mathrm{Eval}^3. Which decisions can change?

  1. Neither minimax nor expectimax decisions
  2. Both minimax and expectimax decisions
  3. Expectimax decisions, but not minimax decisions
  4. Minimax decisions, but not expectimax decisions
Show the answer

C. Expectimax decisions, but not minimax decisions

Cubing positive numbers is strictly increasing, so every max and min picks the same child and minimax is unaffected. But averages are not preserved: 12(13+53)=63>12(33+33)=27\tfrac12(1^3+5^3)=63>\tfrac12(3^3+3^3)=27, although 12(1+5)=12(3+3)\tfrac12(1+5)=\tfrac12(3+3). Expectimax can therefore change its choices.

Monte Carlo tree search

Go has about 250 legal moves per position, and for decades nobody could write a good evaluation function for it. Monte Carlo tree search needs neither exhaustive width nor a hand-written evaluation. It grows an asymmetric tree by repeated simulation, keeping a visit count NN and a total reward WW at each node, and estimates a position's value by the average result of games played out from it.

text
function MCTS(root, budget):
    while budget remains:
        node ← root
        while node is fully expanded and not terminal:     # 1. selection
            node ← the child maximizing UCB1 (below)
        if node is not terminal:
            node ← ADD-UNTRIED-CHILD(node)                  # 2. expansion
        z ← PLAYOUT(node)                  # 3. simulation: random moves to the end
        for each n on the path from node up to root:       # 4. backpropagation
            N(n) ← N(n) + 1
            W(n) ← W(n) + reward of z for the player who moved into n
    return the root move with the most visits
choose the child j maximizingWjNj+cln⁡NNj\text{choose the child } j \text{ maximizing}\qquad \frac{W_j}{N_j}+c\sqrt{\frac{\ln N}{N_j}}
UCT (Kocsis & Szepesvári, 2006) applies the UCB1 rule at every node: the child's average reward (exploitation) plus a bonus for rarely tried children (exploration), where NN is the parent's visit count. For rewards in [0,1][0,1], UCB1 uses c=2c=\sqrt2.

Every node is a multi-armed bandit: its moves are arms with unknown payoffs, and the search must balance the move that looks best against learning about the others, the exploration–exploitation tradeoff. UCB1 keeps the number of plays of each inferior arm logarithmic in the total, so its regret grows only like ln⁡n\ln n (Auer, Cesa-Bianchi & Fischer, 2002). UCT inherits a consistency guarantee: as the iterations grow, the probability of choosing a suboptimal move at the root tends to zero. MCTS is also anytime: it can be stopped whenever the clock says so.

Learned evaluation: from AlphaGo to AlphaZero

MCTS with random playouts lifted computer Go to strong amateur level by the late 2000s. AlphaGo (Silver et al., 2016) added deep convolutional networks:

  • a policy network p(a∣s)p(a\mid s), trained by supervised learning on expert games and then improved by self-play with policy gradients, supplies prior probabilities that focus the search on a few plausible moves;
  • a value network v(s)v(s), trained by regression on self-play outcomes, estimates who wins from a position; at the leaves AlphaGo mixed its estimate with the result of a fast rollout.

AlphaGo beat the European champion Fan Hui 5–0 in 2015 and Lee Sedol 4–1 in March 2016.

a⋆=arg max⁡a[ Q(s,a)+c P(s,a) N(s)1+N(s,a) ]a^\star=\argmax_a\Big[\,Q(s,a)+c\,P(s,a)\,\frac{\sqrt{N(s)}}{1+N(s,a)}\,\Big]
The "PUCT" selection rule of AlphaGo Zero and AlphaZero: the network's prior P(s,a)P(s,a) shapes the exploration bonus, and Q(s,a)Q(s,a) averages value-network estimates from the subtree instead of rollout results.

AlphaGo Zero (2017) dropped human data and rollouts. A single residual network outputs both pp and vv and is trained only from self-play: MCTS visit counts become the policy targets, since the search plays better than the raw network, and game outcomes become the value targets. AlphaZero (2018) applied the same algorithm, largely unchanged, to chess, shogi and Go, and beat the champion programs Stockfish (chess) and Elmo (shogi), as well as a three-day version of AlphaGo Zero.

Key takeaways

  • Minimax defines optimal play in two-player zero-sum games; depth-first minimax costs O(bm)\order{b^m} time and O(bm)\order{bm} memory.
  • Alpha–beta returns exactly the minimax value while skipping subtrees outside the window (α,β)(\alpha,\beta); with perfect ordering it examines b⌈d/2⌉+b⌊d/2⌋−1b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1 leaves, doubling the reachable depth, and with random ordering about b3d/4b^{3d/4}.
  • Cutoff search applies an evaluation function at the depth limit; iterative deepening, transposition tables and quiescence search make it work. Expectimax handles chance, but needs evaluations proportional to expected utility.
  • Monte Carlo tree search grows an asymmetric tree by simulation, choosing moves at every node with the UCB1 bandit rule (UCT).
  • AlphaGo combined MCTS with policy and value networks; AlphaGo Zero and AlphaZero learned both from self-play alone.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

With perfect move ordering, how many leaves does alpha–beta examine in a uniform game tree with b=10b=10 and d=6d=6?

  1. 1,0001{,}000
  2. 1,9991{,}999
  3. 10,00010{,}000
  4. 1,000,0001{,}000{,}000
Show the answer

B. 1,9991{,}999

Knuth and Moore's formula gives b⌈d/2⌉+b⌊d/2⌋−1=103+103−1=1,999b^{\lceil d/2\rceil}+b^{\lfloor d/2\rfloor}-1=10^3+10^3-1=1{,}999, against 10610^6 for minimax: one proof that MAX can reach the value plus one that MIN can hold MAX to it, sharing a single leaf.

Question 2

Roughly how many leaves does alpha–beta examine in a uniform tree when moves are searched in random order, for moderate bb?

  1. About bd/2b^{d/2}
  2. About bd/4b^{d/4}
  3. About b3d/4b^{3d/4}
  4. About bd/2b^d/2
Show the answer

C. About b3d/4b^{3d/4}

Random ordering lands between the best case bd/2b^{d/2} and the worst case bdb^d, at about b3d/4b^{3d/4} for moderate bb; Pearl (1982) gave the exact growth rate. Good ordering is worth a great deal, which is why engines invest so much in it.

Question 3

During alpha–beta, a MIN node sees α=5\alpha=5 (MAX already has a move worth 5 higher up), and its first child returns 3. What happens?

  1. The MIN node keeps searching, since a later child might be worth even less
  2. The MIN node stops: its value is at most 3, so MAX will never choose it
  3. The MIN node sets β=5\beta=5 and continues
  4. The whole search restarts with a narrower window
Show the answer

B. The MIN node stops: its value is at most 3, so MAX will never choose it

MIN can already hold MAX to 3 here, below the 5 that MAX has secured elsewhere, so this node cannot affect the root's decision. Its remaining children are pruned; the returned 3 is an upper bound on its true value.

Question 4

In UCT, a move is never selected while its parent keeps being visited. What happens to its exploration bonus ln⁡N(s)/N(s,a)\sqrt{\ln N(s)/N(s,a)}?

  1. It grows without bound, slowly, so the move is eventually tried again
  2. It shrinks to zero, so the move is abandoned
  3. It stays constant
  4. It becomes negative
Show the answer

A. It grows without bound, slowly, so the move is eventually tried again

N(s,a)N(s,a) is frozen while ln⁡N(s)\ln N(s) keeps growing, so the bonus eventually overtakes the leading move's average plus bonus. UCB1 therefore never abandons a move for good, which is what makes its estimates, and UCT's, converge.

Question 5

What did AlphaGo Zero (2017) remove relative to the original AlphaGo (2016)?

  1. Monte Carlo tree search
  2. Self-play training
  3. The value estimate
  4. Human game data and random rollouts
Show the answer

D. Human game data and random rollouts

AlphaGo Zero trained a single network with policy and value heads purely by self-play, starting from random play, and evaluated leaves with the value head alone. MCTS remained at its core, both for playing and for generating training targets.

Go deeper

Further reading

  • S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 5.
  • D. E. Knuth & R. W. Moore, "An analysis of alpha-beta pruning," Artificial Intelligence 6(4) (1975), 293–326.
  • L. Kocsis & C. Szepesvári, "Bandit based Monte-Carlo planning," Proceedings of ECML (2006).
  • D. Silver et al., "Mastering the game of Go with deep neural networks and tree search," Nature 529 (2016), 484–489.