Skip to content
Tutorials Center
My learning

Topics

Lesson 19 of 46 ยท Adversarial Search

Alpha-Beta Pruning

Understand alpha-beta pruning step by step: alpha and beta bounds, a pruning walkthrough, a Python implementation, move ordering measured with node counts and transposition tables.

Minimax looks at every node of the game tree, but much of that work is wasted. Once you know that one move already guarantees you a score of 6, you do not care how bad some other move is, as long as you know it is worse than 6; there is no need to find out exactly how bad. Alpha-beta pruning turns that observation into an algorithm. It returns exactly the same value and the same best move as minimax, while skipping every branch that provably cannot matter.

In this lesson you will learn what the two bounds, alpha and beta, mean, follow a pruning walkthrough by hand, implement the algorithm, and measure how much the order in which moves are tried changes the savings. Then you will add a transposition table to avoid searching the same position twice.

The idea behind the bounds

During the search, each node carries two numbers that describe what the players have already secured elsewhere in the tree:

  • alpha is the best (highest) value that MAX can already guarantee along the path to this node. It starts at minus infinity.
  • beta is the best (lowest) value that MIN can already guarantee along the path to this node. It starts at plus infinity.

The window (alpha, beta) is the range in which this node's value could still matter. Two rules do the pruning:

  • At a MIN node, if a child makes the value <= alpha, stop looking at the other children. MAX already has a better option higher up and will never let the game reach this node. This is an alpha cut-off.
  • At a MAX node, if a child makes the value >= beta, stop. MIN already has a better option higher up and would never allow this node. This is a beta cut-off.
graph TD
    R["MAX root<br/>alpha = 5 after the first child"] --> A["MIN node A<br/>value 5"]
    R --> B["MIN node B<br/>first leaf = 4"]
    B --> b1["4"]
    B --> b2["12 (pruned)"]
    B --> b3["8 (pruned)"]

Once B's first leaf is 4, B's value is at most 4, which is already below the 5 that MAX can get from A. The leaves 12 and 8 can never change the answer.

A walkthrough on a small tree

Use the same two-ply tree as in the previous lesson: the root is a MAX node with three MIN children. The leaves, left to right, are 6, 9, 5 under A, 4, 12, 8 under B and 7, 10, 6 under C.

  1. Visit A. Its leaves give 6, then 9, then 5. A is a MIN node, so its value is min = 5. Back at the root, alpha becomes 5: MAX can already get 5.
  2. Visit B with window (5, +inf). The first leaf is 4. A MIN node can only go down from there, so B is worth at most 4, below alpha. Prune the leaves 12 and 8.
  3. Visit C with window (5, +inf). Leaf 7 gives an upper bound of 7, which is above alpha, so keep going. Leaf 10 does not lower it. Leaf 6 makes C equal to 6. Alpha becomes 6.
  4. The root value is 6 and the best move is C, exactly what minimax found, but two leaves were never looked at.

Run it and watch.

Python Alpha-beta pruning on a small tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trace shows a cut-off exactly where we predicted: after B's first leaf, 12 and 8 are skipped. The answer is the same, 6, and 7 of 9 leaves were visited.

The algorithm

The implementation is minimax with two extra parameters and two early exits. Here it is for a general game, in pseudocode:

TEXT
alphabeta(state, alpha, beta):
    if state is terminal: return utility(state)
    if MAX to move:
        value = -infinity
        for each child:
            value = max(value, alphabeta(child, alpha, beta))
            alpha = max(alpha, value)
            if alpha >= beta: break      # beta cut-off
        return value
    else:
        value = +infinity
        for each child:
            value = min(value, alphabeta(child, alpha, beta))
            beta = min(beta, value)
            if alpha >= beta: break      # alpha cut-off
        return value

A subtle but important fact: alpha-beta never changes the answer. It only skips work. If you ever see different values from minimax and alpha-beta on the same tree, there is a bug.

Move ordering decides everything

How much does pruning save? That depends entirely on the order in which children are tried.

  • Worst case: the best move is always last. Little or nothing is pruned, and alpha-beta is about as slow as minimax, O(b^m).
  • Best case: the best move is always first. Alpha-beta then examines roughly O(b^(m/2)) nodes. With perfect ordering it can search twice as deep in the same time, which in chess is the difference between a mediocre and a strong program.
  • Random order: about O(b^(3m/4)), in between.

In practice nobody knows the best move in advance, so programs use cheap guesses: try captures first, try the move that was best at the previous (shallower) search, try "killer" moves that caused cut-offs at the same depth elsewhere. In tic-tac-toe, a good guess is to try the centre first, then corners, then edges.

Measuring the effect

On a random game tree you can control ordering exactly, because you can compute each child's true value and sort by it. The program below builds a random tree with branching factor 6 and depth 6 (46,656 leaves) and counts the leaves examined by alpha-beta under three orderings: best child first, random order, and worst child first.

Python Move ordering and leaves examined

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every ordering reports the same value (22), as it must. But look at the leaf counts. With the best move first, only 431 of the 46,656 leaves (0.9%) are examined, exactly the theoretical 2 * b^(d/2) - 1. A random order examines 4,687 (10%), still a big saving, and the worst order examines 37,542 (80.5%), so almost nothing is pruned. This is why serious game programs spend as much effort on move ordering as on the search itself.

Alpha-beta on tic-tac-toe

Now apply it to a real game. The program compares four searches of the whole game from the empty board: plain minimax, alpha-beta in natural square order, alpha-beta with a hand-made ordering (centre, corners, edges), and alpha-beta with a transposition table (described next).

Python Node counts: minimax, alpha-beta and transposition tables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four searches agree that the value is 0. Minimax looks at all 549,946 nodes. Alpha-beta in natural order needs 18,297 nodes (3.3% of minimax), and the centre-first ordering cuts that to 7,275 (1.3%). Adding the transposition table brings the search down to 1,981 nodes, with only 890 positions stored: about 280 times fewer nodes than plain minimax, with exactly the same answer.

Warning: Alpha-beta assumes you search to a fixed depth with exact utilities (or evaluation scores). If you combine it with a transposition table, store whether a value is exact, a lower bound or an upper bound, as the code does. Treating a bound as an exact value is a classic bug that returns wrong moves.

Transposition tables

The game tree contains the same position many times, reached by different move orders (recall 5,478 distinct tic-tac-toe positions against 549,946 tree nodes). A transposition table is a hash map from position to the result of searching it. When the search reaches a position it has seen before, it reuses the stored value instead of searching again.

Because alpha-beta often stops early, a stored value is not always the exact minimax value; it may only be a bound. Each entry therefore stores a flag:

  • exact: the value is the true minimax value in the window searched.
  • lower: a beta cut-off happened, so the true value is at least this.
  • upper: no move raised alpha, so the true value is at most this.

Real engines also store the search depth (a deeper search result is more reliable than a shallow one), the best move found (a superb guess for move ordering next time) and use a hash of the board such as Zobrist hashing rather than the board itself. The table has a fixed size, so old entries are replaced.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does alpha represent during alpha-beta search?

    Alpha is MAX's best guaranteed score so far along the path (it starts at minus infinity). Beta is the lowest score MIN can guarantee (it starts at plus infinity).
  2. 2. How does the result of alpha-beta search compare with minimax?

    Pruning only skips branches that cannot change the result, so the minimax value is always preserved.
  3. 3. With perfect move ordering, roughly how many nodes does alpha-beta examine for branching factor b and depth m?

    Perfect ordering lets alpha-beta search about twice as deep as minimax in the same time, since b^(m/2) is the square root of b^m.
  4. 4. Why does a transposition table help in games like chess or tic-tac-toe?

    Transpositions are common, so remembering what was already searched avoids repeating large subtrees.
  5. 5. Why do transposition table entries need a flag (exact, lower, upper)?

    A value found inside a window can be exact, or it can fail low or fail high. Using a bound as if it were exact gives wrong results.

Summary

  • Alpha-beta pruning returns the same value as minimax while skipping branches that cannot affect the decision.
  • Alpha is MAX's guaranteed lower bound and beta is MIN's guaranteed upper bound; when alpha >= beta the remaining children are pruned.
  • The savings depend on move ordering: from nothing in the worst case to about b^(m/2) nodes in the best case, which doubles the searchable depth.
  • Cheap ordering heuristics (captures first, previous best move, killer moves, centre first) capture much of the benefit.
  • A transposition table stores each position's result with an exact, lower or upper flag, avoiding repeated work on repeated positions.
  • Even so, deep games need depth limits and evaluation functions, covered next.

Next: Evaluation Functions and Depth-Limited Search.