Minimax & Alpha-Beta Pruning

Minimax

Two players alternate. MAX wants the highest utility, MIN wants the lowest. Each internal node takes the best value among its children, according to whose turn it is, and the value flows up from the leaves.

Every leaf is examined, so cost is O(b^d) time and O(bd) space for the depth-first version.

Alpha and beta

α is the best value MAX can already guarantee on the path to the root. β is the best value MIN can already guarantee. Together they form a window of values still worth searching.

The moment β ≤ α, the remaining children are irrelevant — the opponent above would never let play reach them. Cut them off.

Why ordering matters

Pruning depends entirely on the order children are examined. With the best move tried first everywhere, the cost drops to O(b^(d/2)) — roughly double the searchable depth for the same work.

With an unlucky ordering, almost nothing is pruned and you are back to plain Minimax. Press Good ordering then Bad ordering on the same leaves — the root value never moves, only the node count does.

Pseudocode

// returns the minimax value of node, searching only the (alpha, beta) window
function alphabeta(node, alpha, beta, maximizing):
    if node is a leaf:
        return utility(node)

    if maximizing:
        value = -INF
        for child in children(node):
            value = max(value, alphabeta(child, alpha, beta, false))
            alpha = max(alpha, value)
            if beta <= alpha: break      // beta cutoff
        return value

    else:
        value = +INF
        for child in children(node):
            value = min(value, alphabeta(child, alpha, beta, true))
            beta = min(beta, value)
            if beta <= alpha: break      // alpha cutoff
        return value

alphabeta(root, -INF, +INF, true)

Points examiners like to test

• Alpha-Beta returns the same value as Minimax. It changes the work, never the answer.
• The condition is β ≤ α — checked after a child returns, not before.
• α never decreases along a path; β never increases.
• A cut at a MAX node is called a beta cutoff; a cut at a MIN node is an alpha cutoff.
• The leftmost path to depth d is always fully explored — nothing can be pruned before the first value comes back.
• Best case O(b^(d/2)), worst case O(b^d), random ordering roughly O(b^(3d/4)).
• Counting questions usually ask for leaf nodes evaluated, not total nodes — read the wording carefully.