Adversarial Search: Minimax & Alpha-Beta — Algorithms Course

What you'll learn

Games like chess and tic-tac-toe are search problems with a twist: an opponent picks moves to hurt you. Minimax plays optimally against a perfect adversary, and alpha-beta pruning lets it search far deeper by skipping moves that can't matter.

By the end you'll be able to:

Model a game as a game tree
Compute optimal play with minimax
Speed it up with alpha-beta pruning

Game trees

Alternating turns form a tree: you (MAX) want the highest score, the opponent (MIN) the lowest. Leaves are terminal positions scored by an evaluation function. Values propagate up — MAX levels take the maximum of their children, MIN levels the minimum:

A minimax game tree

MAX3

↑ picks the larger child

MIN3

MIN2

↑ each picks the smaller child

Leaf scores (from evaluate)

MIN nodes pick the smallest child; MAX picks the largest. Here the root's best guaranteed score is 3.

Minimax

Minimax is a recursion that assumes both players play perfectly: maximize on your turn, minimize on the opponent's. It explores the whole tree to depth d with branching factor b — O(bᵈ):

Language

minimax.py

def minimax(state, maximizing):
    if is_terminal(state):
        return evaluate(state)
    if maximizing:
        return max(minimax(c, False) for c in children(state))
    else:
        return min(minimax(c, True) for c in children(state))

Evaluation & depth limits

Real games are far too big to search to the end, so we stop at a fixed depth and apply a heuristic evaluation function that scores non-terminal positions (in chess: material, king safety, mobility). Deeper search plus a better evaluator makes a stronger player — the engine's whole art.

Alpha-beta pruning

Minimax explores moves it doesn't need to. Alpha-beta carries two bounds — α (best MAX can already guarantee) and β (best MIN can already guarantee). When α ≥ β, the remaining children of a node can't change the outcome, so they're pruned. The answer is identical to minimax, but with good move ordering the cost drops to O(b^{d/2}) — effectively doubling the searchable depth:

Language

alphabeta.py

def alphabeta(state, alpha, beta, maximizing):
    if is_terminal(state):
        return evaluate(state)
    if maximizing:
        value = float("-inf")
        for c in children(state):
            value = max(value, alphabeta(c, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break                      # beta cutoff — prune the rest
        return value
    else:
        value = float("inf")
        for c in children(state):
            value = min(value, alphabeta(c, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break                      # alpha cutoff
        return value

Tip

Move ordering is everything for alpha-beta: searching likely-best moves first triggers cutoffs sooner. Engines order with heuristics, past results, and iterative deepening — turning the theoretical O(b^{d/2}) into reality.

Key idea

Alpha-beta returns exactly the minimax value — it only skips branches that provably can't affect it. It's the backbone of classical game engines, from tic-tac-toe to world-champion chess programs.

Recap & quick check

Key takeaways

Game trees alternate MAX (you) and MIN (opponent) levels; leaves are scored by evaluate().
Minimax maximizes on your turn and minimizes on the opponent's — O(bᵈ).
Real engines cut off at a depth limit and use a heuristic evaluation function.
Alpha-beta prunes branches that can't change the result, giving the same answer faster.
With good move ordering, alpha-beta reaches O(b^(d/2)) — twice the depth.

Quick check

1. In minimax, what does the MIN player do?

2. What does alpha-beta pruning guarantee about the result?

3. Why do real game engines use a depth limit and evaluation function?

4. With good move ordering, alpha-beta's complexity approaches:

Search complete. Now the richest arena in algorithms: graphs. Next up: Module 24 — Graph Representations & Traversal.