Games: Minimax, Alpha–Beta & MCTS
Planning against an opponent.
Chess has more than legal positions and a game tree of roughly 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 time and 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 , the player to move , the legal moves , a transition model , a terminal test and a 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.
A depth-first recursion computes this value by visiting the whole tree: time and memory for branching factor and maximum depth . In chess and games run to about 100 plies, so the tree has about nodes. Exact minimax is out of the question; everything below is about doing less.
MAX moves, then MIN, then MAX again. The eight leaves, left to right, are : consecutive pairs share a MAX parent, and consecutive pairs of those share a MIN parent. What is the root's minimax value?
Show the answer
D.
The bottom MAX nodes are worth , , and . The MIN nodes take and , and the root takes .
Alpha–beta pruning
Alpha–beta computes the same value while skipping subtrees that cannot matter. It passes down a window : is the best value MAX can already guarantee somewhere on the path to the root, and 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.
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, −∞, +∞)Leaves return their exact value. At a MAX node with children , child is searched with the window , where is the running maximum; assume the claim for every child.
Cutoff at child . If , the child failed high, so : the node fails high, as claimed.
No cutoff. Each child was exact or failed low (). If , the first child attaining it beat its own , so it is exact, and . If , every child failed low and . MIN nodes are symmetric.
How much can pruning save? With perfect ordering (the best move first at every node), alpha–beta examines exactly leaves of a uniform depth- tree (Knuth & Moore, 1975), about : the same time buys twice the depth. With random ordering it examines roughly for moderate , as Knuth and Moore's analysis began to show and Pearl (1982) settled exactly. With the worst ordering it prunes nothing.
Chess has . 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 leaves means a factor of 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 , an estimate of the minimax value. Classical chess programs used weighted sums of features, , 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 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 at chance nodes:
A program's evaluation function, always positive, is replaced by its cube, . Which decisions can change?
- Neither minimax nor expectimax decisions
- Both minimax and expectimax decisions
- Expectimax decisions, but not minimax decisions
- 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: , although . 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 and a total reward at each node, and estimates a position's value by the average result of games played out from it.
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 visitsEvery 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 (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 , 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 , 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.
AlphaGo Zero (2017) dropped human data and rollouts. A single residual network outputs both and 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 time and memory.
- Alpha–beta returns exactly the minimax value while skipping subtrees outside the window ; with perfect ordering it examines leaves, doubling the reachable depth, and with random ordering about .
- 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.
With perfect move ordering, how many leaves does alpha–beta examine in a uniform game tree with and ?
Show the answer
B.
Knuth and Moore's formula gives , against for minimax: one proof that MAX can reach the value plus one that MIN can hold MAX to it, sharing a single leaf.
Roughly how many leaves does alpha–beta examine in a uniform tree when moves are searched in random order, for moderate ?
- About
- About
- About
- About
Show the answer
C. About
Random ordering lands between the best case and the worst case , at about for moderate ; Pearl (1982) gave the exact growth rate. Good ordering is worth a great deal, which is why engines invest so much in it.
During alpha–beta, a MIN node sees (MAX already has a move worth 5 higher up), and its first child returns 3. What happens?
- The MIN node keeps searching, since a later child might be worth even less
- The MIN node stops: its value is at most 3, so MAX will never choose it
- The MIN node sets and continues
- 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.
In UCT, a move is never selected while its parent keeps being visited. What happens to its exploration bonus ?
- It grows without bound, slowly, so the move is eventually tried again
- It shrinks to zero, so the move is abandoned
- It stays constant
- It becomes negative
Show the answer
A. It grows without bound, slowly, so the move is eventually tried again
is frozen while 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.
What did AlphaGo Zero (2017) remove relative to the original AlphaGo (2016)?
- Monte Carlo tree search
- Self-play training
- The value estimate
- 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
- Alpha–Beta Pruning in Depth · Move ordering and the √ speedup in the best case.
- Monte Carlo Tree Search & UCT · Bandits at every node: UCB1 and its regret bound.
- AlphaGo & AlphaZero · When search meets learned value and policy networks.
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.