I4 · Problem Solving and Reasoning: Classical AI

Alpha-Beta Pruning

Alpha-beta pruning is an optimisation of minimax that skips branches which cannot affect the final decision. It tracks two bounds: alpha, the best value MAX can already guarantee, and beta, the best value MIN can already guarantee. When a position's value is proven to be outside the range between them, its remaining children are pruned. It always returns the same move as plain minimax, only faster.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

Minimax looks at every move. But once you have found a reply that refutes a move, why keep examining that move's other replies? Alpha-beta pruning skips them and often lets a program search twice as deep in the same time.

Alpha-beta pruning is an optimisation of minimax that skips branches which cannot affect the final decision. It tracks two bounds: alpha, the best value MAX can already guarantee, and beta, the best value MIN can already guarantee. When a position's value is proven to be outside the range between them, its remaining children are pruned. It always returns the same move as plain minimax, only faster.

In simple words

You are choosing a restaurant with a friend who will pick the dish. At the first restaurant, the worst dish your friend could pick is still decent. At the second, the first dish you check is terrible. You need not look further: your friend could pick that terrible dish, so the second restaurant is already worse than the first.

Overview

  • Alpha-beta pruning speeds up minimax by skipping branches that cannot change the decision.
  • α is the best value MAX can guarantee so far; β is the best value MIN can guarantee.
  • Whenever α ≥ β, the remaining children of a node are pruned.
  • It always returns exactly the same move as full minimax.
  • With good move ordering it examines about b^(d/2) nodes instead of bᵈ, roughly doubling the searchable depth.
  • Chess engines add many enhancements on top of it.

Why it matters

Searching deeper is the main way game programs get stronger. By cutting away provably irrelevant branches, alpha-beta lets the same computer look much further ahead, which was essential for strong chess programs including Deep Blue.

Key terms

Alpha (α)
The highest value MAX is assured of so far along the path.
Beta (β)
The lowest value MIN is assured of so far along the path.
Pruning
Skipping the remaining children of a node because they cannot change the decision.
Cutoff
The moment pruning happens, when α ≥ β.
Move ordering
Examining likely best moves first, which greatly increases pruning.
Transposition table
A cache of positions already evaluated, reached by different move orders.

Types

Alpha-beta pruning works with several enhancements. These types of technique make game search faster still.

1. Alpha (MAX) and beta (MIN) cut-offs

The two kinds of pruning: beta cut-offs at MAX nodes and alpha cut-offs at MIN nodes.

  • How it works: At a MIN node, once a child is worth less than α, MAX will never come here, so the rest is skipped; at a MAX node the same happens when a child exceeds β.
  • Example: If MAX already has a move worth 3 and MIN finds a reply worth 2 in another branch, that branch is abandoned.
  • When to use it: Understand both to trace alpha-beta by hand.

2. Move ordering

Searching the most promising moves first.

  • How it works: Good ordering causes cut-offs early; heuristics include captures first, killer moves and the history heuristic.
  • Example: Trying checks and captures before quiet moves in chess.
  • When to use it: Use it always; it is the difference between b^(d/2) and nearly bᵈ nodes. Iterative deepening supplies a good order from the previous, shallower search.

3. Iterative deepening with transposition tables

Searching to depth 1, 2, 3 and so on, and storing results of positions already seen.

  • How it works: Each shallow search improves move ordering for the next; the transposition table, a hash table, avoids re-searching positions reached by different move orders.
  • Example: A chess engine that always has a best move ready when its time runs out.
  • When to use it: Use them in time-limited games, where you must answer within seconds.

4. Quiescence search

Extending the search beyond the depth limit in unstable positions.

  • How it works: At the limit, only captures and checks are explored further until the position is quiet, avoiding the horizon effect.
  • Example: Not stopping the search in the middle of a queen exchange, where the evaluation would be badly wrong.
  • When to use it: Use it in tactical games where values swing sharply from one move to the next.

5. Null-window and aspiration searches

Searching with a narrow α–β window guessed in advance.

  • How it works: A narrow window causes more cut-offs; if the true value falls outside it, the search is repeated with a wider window. Principal Variation Search uses null windows for most moves.
  • Example: Guessing that the position is worth about +0.3 pawns and searching between +0.1 and +0.5.
  • When to use it: Use these in strong game engines once basic alpha-beta works.

Explained in detail

A small example

MAX chooses between moves A and B; after each, MIN chooses a reply. Under A, MIN's replies lead to values 3, 12 and 8, so MIN would choose 3; A is worth 3, and now α = 3: MAX is assured at least 3. Under B, the first reply examined is worth 2. MIN can therefore hold B to 2 or less. Since 2 is already below the 3 that MAX has from A, MAX will never choose B, whatever B's other replies are. Those replies are pruned. With a third move C whose first reply is 14, MIN might still find something lower, so the search continues there until the bound is decided.

How much it saves

Move orderingPositions examined to depth dEffect
Plain minimaxabout bᵈBaseline
Alpha-beta, random orderabout b^(3d/4)Searches about a third deeper
Alpha-beta, best moves firstabout b^(d/2)Searches about twice as deep

With perfect ordering, alpha-beta examines roughly the square root of the positions minimax would, a result shown by Donald Knuth and Ronald Moore in 1975. In chess, with a branching factor near 35, that is the difference between looking 6 moves ahead and 12. Real programs approach good ordering by trying captures first, remembering moves that caused cutoffs before (killer moves) and using iterative deepening, where the best move from a shallower search is tried first in the deeper one.

Important properties

  • Pruning never changes the result: alpha-beta chooses exactly the move minimax would.
  • The amount pruned depends entirely on move ordering.
  • Transposition tables avoid re-evaluating positions reached by different move orders, which is common in chess.
  • Modern chess engines such as Stockfish still use alpha-beta search, now often combined with neural-network evaluation functions.

The example below runs both algorithms on the same random game tree. They return exactly the same value, but alpha-beta evaluates far fewer leaf positions, even without any special move ordering. In a real game, that saving is spent on searching more moves ahead, which is why alpha-beta, rather than plain minimax, sits at the heart of strong game-playing programs. Its weakness is that, on its own, it still needs an evaluation function for positions it cannot search to the end, and the quality of that function often matters as much as the depth of the search.

How it works

  1. Start the search with α = −∞ and β = +∞.
  2. At MAX nodes, update α to the best child value found so far.
  3. At MIN nodes, update β to the lowest child value found so far.
  4. Whenever α ≥ β, stop examining the remaining children.
  5. Order moves so the most promising are tried first.

In code

alphabeta.py
import math
import random

random.seed(4)
DEPTH, BRANCH = 6, 5
leaves = [random.randint(-20, 20) for _ in range(BRANCH ** DEPTH)]
counter = {"minimax": 0, "alphabeta": 0}

def minimax(index, depth, maximising):
    if depth == 0:
        counter["minimax"] += 1
        return leaves[index]
    vals = [minimax(index * BRANCH + i, depth - 1, not maximising) for i in range(BRANCH)]
    return max(vals) if maximising else min(vals)

def alphabeta(index, depth, alpha, beta, maximising):
    if depth == 0:
        counter["alphabeta"] += 1
        return leaves[index]
    value = -math.inf if maximising else math.inf
    for i in range(BRANCH):
        child = alphabeta(index * BRANCH + i, depth - 1, alpha, beta, not maximising)
        if maximising:
            value, alpha = max(value, child), max(alpha, child)
        else:
            value, beta = min(value, child), min(beta, child)
        if alpha >= beta:
            break  # prune the remaining children
    return value

print("Minimax value:   ", minimax(0, DEPTH, True), " leaves evaluated:", counter["minimax"])
print("Alpha-beta value:", alphabeta(0, DEPTH, -math.inf, math.inf, True), " leaves evaluated:", counter["alphabeta"])

Output

Minimax value:    -10  leaves evaluated: 15625
Alpha-beta value: -10  leaves evaluated: 1439

Try it yourself

The move not worth finishing

MAX compares two moves; after each, MIN replies.

True or false about alpha-beta?

Sort each statement.

  • It returns the same move as minimax

  • It can change which move is chosen

  • It removes the need for an evaluation function in chess

  • Good move ordering increases pruning

Common mistakes

  • Thinking pruning loses accuracy.
  • Ignoring move ordering and getting little pruning.
  • Mixing up when to update alpha and when to update beta.

Check yourself

Question 1

1. When does alpha-beta prune?

Question 2

2. Does alpha-beta ever choose a different move from minimax?

Question 3

3. With perfect move ordering, alpha-beta can search about…

Summary

  • Alpha-beta prunes branches that cannot change minimax's decision.
  • It tracks α for MAX and β for MIN and cuts off when α ≥ β.
  • Good move ordering lets it search about twice as deep with the same result.

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · UC Berkeley CS188: Introduction to Artificial Intelligence