Minimax and Alpha-Beta

In a two-player turn-based game (tic-tac-toe, chess, connect four), minimax picks the best move assuming the opponent also plays perfectly. Alpha-beta gets exactly the same result while exploring far fewer positions.

The game tree

Each node is a position, each edge a move. Levels alternate between the two players:

• ▲ MAX (us) looks for the largest value;
• ▼ MIN (the opponent) looks for the smallest value.

Leaves get their value from an evaluation function: +1 / 0 / −1 for a finished game, or an estimate (material advantage, for instance) when the search stops at a fixed depth.

Minimax

Values are computed bottom-up: a MAX node takes the maximum of its children, a MIN node the minimum. The tree is explored depth-first, left to right.

minimax(node):
    if node is a leaf: return evaluate(node)
    if node is MAX: return max(minimax(c) for each child c)
    else:           return min(minimax(c) for each child c)

Example: the root A (MAX) has three MIN children.

                A (MAX)
       /           |           \
    B (MIN)     C (MIN)     D (MIN)
   /  |  \     /  |  \     /  |  \
  4   9   6   3   7   5   8   2   10

• B = min(4, 9, 6) = 4
• C = min(3, 7, 5) = 3
• D = min(8, 2, 10) = 2
• A = max(4, 3, 2) = 4: the best move leads to B.

Minimax visits every leaf: O(b^d) for a branching factor b and a depth d.

Alpha-beta pruning

Two bounds are passed down the tree:

• α: the best value MAX is already guaranteed on the path (starts at −∞);
• β: the best value MIN is already guaranteed on the path (starts at +∞).

A MAX node updates α, a MIN node updates β. As soon as α ≥ β, the remaining children can no longer change the decision: they are pruned.

The same example with alpha-beta

1. B (α = −∞, β = +∞): we see 4, 9, 6 → B = 4. Back at A, α = 4.
2. C (α = 4, β = +∞): first leaf 3, so β = 3. Since α = 4 ≥ β = 3, we cut: C will be worth at most 3, and A already has an option worth 4. Leaves 7 and 5 are pruned.
3. D (α = 4, β = +∞): leaf 8 → β = 8, no cut. Leaf 2 → β = 2 ≤ α, cut: leaf 10 is pruned.
4. A = 4, as with minimax, but with 3 fewer leaves to evaluate.

Move ordering matters

Alpha-beta prunes more when the best moves are explored first. With perfect ordering, the complexity drops to about O(b^d/2), which allows searching twice as deep in the same time. With bad ordering, nothing is pruned and we are back to O(b^d).

Common pitfalls