Minimax and Alpha-Beta Pruning: Searching Games Without Visiting Every Move

← Back to Blog & Articles

Minimax lets a program choose moves in two-player games by assuming both sides play as well as they can. Alpha-beta pruning keeps the same answer while skipping large parts of the search.

The minimax idea

Represent the game as a tree of positions. One player, MAX, wants the highest score. The other, MIN, wants the lowest. Leaf positions get a score from the rules of the game or from an evaluation function. Scores then travel up the tree: MAX nodes take the largest child value, and MIN nodes take the smallest. At the root, MAX picks the move leading to the best guaranteed outcome.

What pruning adds

Alpha-beta tracks two numbers during the search. Alpha is the best value MAX can already guarantee on the current path. Beta is the best value MIN can already guarantee. When alpha becomes greater than or equal to beta, the rest of that branch cannot change the final decision, so the search stops exploring it.

function alphabeta(node, depth, alpha, beta, maximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)
    if maximizing:
        for child in children(node):
            alpha = max(alpha, alphabeta(child, depth - 1, alpha, beta, false))
            if alpha >= beta: break
        return alpha
    else:
        for child in children(node):
            beta = min(beta, alphabeta(child, depth - 1, alpha, beta, true))
            if alpha >= beta: break
        return beta

Why ordering matters

Pruning returns exactly the same result as plain minimax. How much work it saves depends on move ordering. With the best possible ordering, the search examines roughly the square root of the nodes, which lets you search about twice as deep in the same time. With poor ordering it saves little.

Limits

Alpha-beta still struggles when the branching factor is very large or when a good evaluation function is hard to write. Games like Go led researchers toward Monte Carlo tree search, which estimates move quality from simulated playouts.

Continue with the book

Explore the full treatment, worked examples, and exercises in The AI Algorithms Compendium.