Alpha-Beta Pruning Simulator

How Alpha-Beta Pruning Simulator works

Alpha-beta pruning computes exactly the same value as minimax while skipping branches that provably cannot change the answer. It carries two bounds down the tree: alpha, the best value MAX can already guarantee somewhere above, and beta, the best value MIN can already guarantee. At a MAX node every child value raises alpha; the moment alpha becomes greater than or equal to beta, MIN would never allow play to reach this node — a better option for MIN already exists elsewhere — so the remaining children are never examined. The mirror rule applies at MIN nodes, where child values lower beta and the cutoff fires on the same comparison. Crucially, the cut branches are not guessed at; the bounds prove they are irrelevant. The saving depends entirely on move ordering. If the best move is searched first at every node, the effective branching factor drops to roughly its square root, letting a search reach about twice the depth in the same time. With the worst ordering, nothing prunes and the cost is identical to plain minimax.

Pseudocode

alphabeta(node, depth, alpha, beta, maximizing):
    if depth == 0 or node is terminal:
        return evaluate(node)

    if maximizing:
        value = -infinity
        for each child of node:
            value = max(value, alphabeta(child, depth-1, alpha, beta, false))
            alpha = max(alpha, value)
            if alpha >= beta:
                break                  // beta cutoff: MIN would avoid this node
        return value
    else:
        value = +infinity
        for each child of node:
            value = min(value, alphabeta(child, depth-1, alpha, beta, true))
            beta = min(beta, value)
            if alpha >= beta:
                break                  // alpha cutoff: MAX would avoid this node
        return value

// Top-level call:
best = alphabeta(root, depth, -infinity, +infinity, true)

Time and space complexity

Time

O(b^d) worst case, O(b^(d/2)) with perfect move ordering

Space

O(d) for the recursion stack

Perfect ordering means every node's best move is tried first, which halves the exponent — the same budget then searches roughly twice as deep. Random ordering gives about O(b^(3d/4)).

Worked example

Depth-2 tree, root is MAX with three children B, C, D (all MIN). B has leaves 3, 12, 8. C has leaves 2, 4, 6. D has leaves 14, 5, 2.

1. Explore BMIN node, no cutoff possible yet. Leaves 3, 12, 8 → B = 3. Root alpha becomes 3.
2. Explore C, first leafC inherits alpha = 3, beta = ∞. First leaf is 2, so C's beta drops to 2. Now alpha(3) ≥ beta(2) → cutoff.
3. Prune CLeaves 4 and 6 are never evaluated. C can only end up ≤ 2, and MAX already has 3, so C is irrelevant regardless of what they hold.
4. Explore D, first leafD inherits alpha = 3. First leaf 14 → beta = 14. 3 ≥ 14 is false, keep going.
5. D, second leafLeaf 5 → beta = 5. Still 3 < 5, no cutoff.
6. D, third leafLeaf 2 → beta = 2. D = 2. Root compares max(3, 2) = 3.

Root value 3, choosing move B — identical to minimax. Two of nine leaves were never evaluated. Had D been ordered before C, more would have pruned.

Common exam mistakes

• Believing pruning changes the result. It cannot — alpha-beta returns exactly the minimax value; only the number of nodes visited differs.
• Cutting off with a strict inequality only. The standard condition is alpha >= beta; using alpha > beta still works but misses valid cutoffs on ties.
• Passing alpha and beta back up the tree. They travel downward as bounds; the value returned upward is the node value, not the bound.
• Updating alpha at MIN nodes or beta at MAX nodes. MAX raises alpha, MIN lowers beta — swapping them breaks the proof and prunes wrongly.
• Ignoring move ordering and then concluding pruning "does not help". With the worst ordering alpha-beta visits every node minimax would.

Frequently asked questions

Related simulators