Alpha-Beta Pruning

The Core Idea

Many subtrees of the minimax game tree cannot possibly affect the root value. Alpha-beta pruning identifies and skips these subtrees without changing the minimax result.

Named for two bounds maintained during search: - α (alpha): best value found so far for MAX (lower bound on MAX’s value along current path) - β (beta): best value found so far for MIN (upper bound on MIN’s value along current path)

Pruning condition: if at any point α ≥ β, stop searching the current subtree.

Algorithm

function ALPHA-BETA-SEARCH(game, state) returns action
    player ← TO-MOVE(state)
    value, move ← MAX-VALUE(game, state, -∞, +∞)
    return move

function MAX-VALUE(game, state, α, β) returns (utility, move)
    if IS-TERMINAL(state) then return UTILITY(state, player), null
    v ← -∞
    for each a in ACTIONS(state) do
        v2, a2 ← MIN-VALUE(game, RESULT(state, a), α, β)
        if v2 > v then v, move ← v2, a
        if v ≥ β then return v, move    -- β cutoff (prune)
        α ← max(α, v)
    return v, move

function MIN-VALUE(game, state, α, β) returns (utility, move)
    if IS-TERMINAL(state) then return UTILITY(state, player), null
    v ← +∞
    for each a in ACTIONS(state) do
        v2, a2 ← MAX-VALUE(game, RESULT(state, a), α, β)
        if v2 < v then v, move ← v2, a
        if v ≤ α then return v, move    -- α cutoff (prune)
        β ← min(β, v)
    return v, move

Why the Cutoffs Work

β-cutoff (in MAX-VALUE)

If v ≥ β: the current MAX value already exceeds what MIN would allow. MIN has a better move elsewhere (which gives β). So MIN will never reach this MAX node → prune.

α-cutoff (in MIN-VALUE)

If v ≤ α: the current MIN value already falls below what MAX would allow. MAX has a better move elsewhere (which gives α). So MAX will never reach this MIN node → prune.

Analogy

Like a chess player thinking: “I already have a move that guarantees +3. If this line gives my opponent a move leading to -2 for me, I can stop analyzing this line — I won’t play here.”

Effectiveness: Move Ordering

Best case (perfect ordering — best moves examined first):

Time complexity: O(b^(m/2)) instead of O(b^m)

Alpha-beta can search twice as deep as plain minimax in the same time!

Average case (random ordering):

Time complexity: O(b^(3m/4))

Worst case (reverse ordering — worst moves first):

No pruning — same as minimax: O(b^m)

Move ordering heuristics: 1. Killer move: try moves that caused cutoffs in sibling subtrees first 2. History heuristic: prefer moves that caused cutoffs in earlier search 3. Transposition table: cache already-evaluated positions to avoid re-search

Worked Example

         MAX (root)
        /          \
      MIN           MIN
     /   \         /   \
    3    12        8     ?

After evaluating left MIN subtree: MIN=3. α at root = 3.

Right MIN starts evaluating 8. Since 8 > α=3, continue (might find smaller values).

If next subtree under right MIN gave us value 2: MIN updates to min(8,2)=2. Since 2 < α=3, MAX at root will never choose this branch → prune any remaining children of right MIN.

Properties

Practical Impact for Chess

Chess: b≈35, m≈80. - Minimax: 35^80 ≈ 10^123 nodes - Alpha-beta (average): 35^60 ≈ 10^93 nodes - Alpha-beta (best case): 35^40 ≈ 10^62 nodes

Still intractable without depth limits! Alpha-beta enables deeper search but must be combined with heuristic evaluation (file 4).

Iterative Deepening Alpha-Beta

In practice, use iterative deepening with alpha-beta: 1. Search to depth 1, get best move 2. Search to depth 2, update best move 3. Continue until time limit

Benefits: - Always have a move ready (even if search is interrupted) - Deeper searches use shallow results for move ordering → better pruning - Shallow searches are cheap (< 1% of total time at each depth)