Minimax Visualization | Alpha-Beta Pruning on a Game Tree

The idea: look ahead, assume the opponent is perfect

In a two-player game like tic-tac-toe or chess, one player's gain is the other's loss. Write every possible continuation as a game tree: the root is the position now, each edge is a move, and the levels alternate between the two players. Score the positions at the bottom (the leaves) from our point of view: high is good for us.

A two-level game tree: the MAX root has three MIN children with leaves 3 12 8, 2 4 6 and 14 5 2. The MIN nodes take the smallest leaf (3, 2, 2) and the root takes the largest of those, 3, so the best move is the left one — Leaf scores flow up: MIN nodes take the smallest, the MAX root takes the largest. The root's value is what MAX can force.

We are MAX: on our levels we pick the child with the highest value. The opponent is MIN: it picks the lowest. The value of the root is the best score we can be sure of if the opponent never makes a mistake, and the child that gives it is the best move.

Use the tree select to choose a tree, then press Minimax or Alpha-Beta, or run one of the demos. The tree on the canvas has MAX at the root, three MIN replies (moves A, B, C), MAX again and then 12 leaves: 22 nodes in all.

Minimax is a depth-first search

Minimax computes the values bottom-up with a depth-first search (see Depth-First Search). It goes down the leftmost branch to a leaf, takes its score, and returns it to the parent. A MAX node keeps the largest value its children return (it starts at −∞), a MIN node the smallest (it starts at +∞). When all children are done, the node returns its value to its own parent (Demo 1: plain minimax).

minimax(node):
    if node is a leaf: return score(node)
    if MAX to move:  return max(minimax(c) for c in children)
    else:            return min(minimax(c) for c in children)

Minimax visits every node. With branching factor b and depth d that is about b^d leaves: fine for 12 leaves, hopeless for chess (b ≈ 35).

Alpha and beta

Alpha-beta pruning gets the same root value while skipping parts of the tree that cannot matter. It passes two numbers down the search:

bound	meaning	changed by
α (starts −∞)	the best score MAX can already force on the path to this node	a MAX node, when a child returns more than α
β (starts +∞)	the best (lowest) score MIN can already force on the path	a MIN node, when a child returns less than β

The bounds go down to the children; values come back up. As soon as α ≥ β at a node, the rest of its children are pruned: whatever they hold, one of the two players already has a better choice higher up and will never let play reach here.

The same tree searched with alpha-beta. After the first MIN node returns 3, alpha at the root is 3. The second MIN node sees the leaf 2, so beta becomes 2; alpha 3 is at least beta 2, so its leaves 4 and 6 are pruned and drawn grey — Once MAX can get 3 from the first move, a MIN node that can already hold MAX to 2 needs no more looking at: α = 3 ≥ β = 2.

On the canvas each node shows its value inside and its α and β next to it. A cut turns the tag red with "✂ α≥β", and the pruned children and everything under them go grey (Demo 2: alpha-beta on the same tree). On the mixed-order tree alpha-beta visits 18 of the 22 nodes and still finds value 6 with move C.

alphabeta(node, α, β):
    if node is a leaf: return score(node)
    if MAX to move:
        v = −∞
        for c in children:
            v = max(v, alphabeta(c, α, β));  α = max(α, v)
            if α ≥ β: break          # β cut-off
        return v
    else:
        v = +∞
        for c in children:
            v = min(v, alphabeta(c, α, β));  β = min(β, v)
            if α ≥ β: break          # α cut-off
        return v

Move ordering decides how much is pruned

Alpha-beta only cuts after it has seen a good move. If the best move is searched first, the bounds are tight early and many branches are cut. If the best move comes last, nothing can be cut. The three abstract trees on this page are the same game with the children in a different order:

tree	minimax	alpha-beta
mixed order	22 nodes	18 nodes (4 pruned)
best move first (Demo 3)	22 nodes	15 nodes (7 pruned), the fewest any ordering gives
worst move first (Demo 4)	22 nodes	22 nodes (none pruned)

With perfect ordering alpha-beta looks at about b^d/2 leaves instead of b^d: in the same time it can search about twice as deep. Real engines get close to that with cheap ordering tricks: try captures first, try the move that was best in the previous, shallower search (iterative deepening), and remember moves that caused cut-offs (killer moves).

Tic-tac-toe: blocking a win

The last tree is a real position. X (MAX) is to move with three squares left; O holds squares 3 and 5 and threatens 7. A win for X scores +1, a win for O −1, a draw 0. The tree has 14 positions; games end early when someone gets three in a row. Minimax finds that only square 7 keeps the draw: after 8 or 9, O plays 7 and wins (Demo 5: tic-tac-toe, X blocks O's win). Alpha-beta needs 10 of the 14 positions: once square 7 is known to give 0, a single O win under 8 (or 9) is enough to drop that move.

Full games are far too big to search to the end. Programs stop at a fixed depth and score the position there with an evaluation function (material, mobility, king safety in chess); the abstract leaf scores on this page stand for those. Monte Carlo Tree Search replaces the evaluation function with random play-outs and grows the tree unevenly towards promising moves.

See also N-Queens and CSP Backtracking, two other depth-first searches that cut branches early, and A* Search, which uses a bound of another kind.

What the page leaves out

Depth-limited search and evaluation functions in detail; the negamax form (one function, values negated each level); transposition tables (the same position reached by different move orders); iterative deepening, aspiration windows and principal variation search; quiescence search; games with chance (expectiminimax) and with more than two players.