Alpha-Beta Pruning Explained: Bounds, Cutoffs and a Complete Game-Tree Trace

Alpha-beta pruning follows the same decision rule as minimax while skipping branches that cannot change the choice. A correct trace keeps MAX's viewpoint fixed, alternates MAX and MIN by level, respects the stated child order, and updates alpha and beta on the right levels. On the tree below, those rules determine the root value, best move, pruned branches, and exact visit counts.

Alpha-beta pruning begins with minimax, not a new decision rule

Consider a finite, deterministic, two-player, zero-sum game with perfect information. Each state is a node, each legal move is an edge, and one level is one ply. Terminal leaves contain utilities from MAX's viewpoint. MAX selects the greatest child value, while MIN selects the smallest. In a depth-limited search, a heuristic can evaluate non-terminal frontier nodes, but the worked tree ends at terminal leaves.

Compactly, V(s)=U(s) for a terminal state, V(s)=max V(child) at MAX, and V(s)=min V(child) at MIN. Alpha-beta pruning uses exactly this minimax decision rule. It merely avoids branches that cannot change the result.

Adversarial search also includes evaluation functions and chance nodes, developed in Game Playing in AI: Minimax and Alpha-Beta Pruning. Alpha-beta pruning questions narrow the task to bound propagation, cutoff safety, and exact visit counts.

Alpha and beta bounds: meaning, updates and cutoff

alpha is the best value MAX can already guarantee along the current root-to-node path, so it is a lower bound. beta is the best value MIN can already guarantee, so it is an upper bound. The root starts with alpha=-infinity and beta=+infinity. Neither symbol necessarily equals the current node's final value.

alphabeta(node, alpha, beta, player):
  if terminal(node): return utility(node)
  if player == MAX:
    value = -infinity
    for child in ordered_children(node):
      value = max(value, alphabeta(child, alpha, beta, MIN))
      alpha = max(alpha, value)
      if alpha >= beta: break
    return value
  value = +infinity
  for child in ordered_children(node):
    value = min(value, alphabeta(child, alpha, beta, MAX))
    beta = min(beta, value)
    if alpha >= beta: break
  return value

Alpha never decreases along a path, beta never increases, and equality is enough for a cutoff. The recursion normally produces a depth-first trace. Minimax Search Algorithm: Two Worked Game Trees, an Alpha-Beta Trace and Exam Traps develops the minimax recurrence, depth-limited backup, and a compact pruning application. Alpha-beta specialists additionally need to follow every bound update, justify each cutoff, and compare visit orders. A pruned leaf is not evaluated and cannot be used later as though the search saw it.

Alpha-beta pruning worked example

Root R is MAX. Its children A and B are MIN. Their MAX children and terminal leaves are A1:[8,2], A2:[9,12], B1:[3,5], and B2:[14,6], always visited left to right.

First compute the full minimax baseline:

• A1=max(8,2)=8, A2=max(9,12)=12, so A=min(8,12)=8.

• B1=max(3,5)=5, B2=max(14,6)=14, so B=min(5,14)=5.

• R=max(8,5)=8, so MAX chooses A.

Now trace alpha-beta. A1 visits 8,2 and returns 8, so MIN node A lowers beta from +infinity to 8. At A2, visiting 9 makes its local MAX value 9. Since 9>=8, leaf 12 is pruned. A returns 8, and R raises alpha from -infinity to 8.

Node B inherits alpha=8. B1 visits 3,5 and returns 5, so B lowers beta from +infinity to 5. Now beta 5<=alpha 8, so the whole B2 subtree, including 14,6, is pruned. B returns 5; R remains max(8,5)=8 and chooses A.

The evaluated leaves are 8,2,9,3,5: 5/8 terminals. The search visits 11/15 total nodes. Pruned terminals are 12,14,6, and the pruned internal node is B2. Both algorithms return 8.

Why alpha-beta cutoffs are safe

At A, MIN already has A1=8. MAX node A2 has reached at least 9, and another child can only keep or raise its value. MIN will never prefer it to the available 8, so the remaining leaf cannot change A.

At the root, MAX already has A=8. MIN node B then finds B1=5, making B at most 5 regardless of B2. That cannot improve MAX's choice over 8, so the remaining branch is irrelevant.

The complete baseline tells us A2=12 and B2=14, but the actual search never discovers those exact values. After a cutoff, the caller may need only the sufficient fact that a node is at least beta or at most alpha.

Move ordering changes efficiency, not the answer

Now use a poor order. Under A, visit A2 first with leaves [12,9], then A1 with [2,8]. Under B, visit B2 first with [6,14], then B1 with [5,3]. Useful bounds arrive too late, so all eight leaves are evaluated. The backups still give A=8, B=5, R=8, and move A.

Trying a promising move first is a search-order heuristic, not a greedy substitute for minimax. Implementations may try a previous principal variation, captures, or domain-specific promising moves first. A transposition table can help with repeated positions, but alpha-beta itself does not require overlapping subproblems.

Alpha-beta pruning complexity and space

Let b be the branching factor and d the depth in plies. Full uniform minimax takes Theta(b^d) terminal work. Alpha-beta has the same worst case under poor ordering, while ideal ordering approaches Theta(b^(d/2)), often allowing roughly twice the depth for a similar leaf budget. See Time Complexity and Asymptotic Notation: Big-O for a notation refresher.

The 5 versus 8 leaves illustrate ordering, not the general proof. Depth-first recursion stores a path proportional to d, plus per-level state and move data. A stored full tree or transposition table changes memory use. Pruning removes search work, not legal moves or minimax alternatives.

Alpha-beta pruning question patterns and traps

Common practice forms ask you to compute the root, mark cuts for a stated order, distinguish leaf visits from total-node visits, complete a trace table, improve ordering, or classify a returned result as exact or merely a bound. GATE CS Exam Preparation provides broader practice across Artificial Intelligence and adjacent CS topics.

Rapid checks from the trace: after A1, A has beta=8; 12 is pruned after 9; after A, root has alpha=8; after B1=5, B2 is pruned; totals are 5 leaves and 11 nodes. For equality, if a MAX node enters with beta=4 and first sees 4, its alpha reaches at least 4, so it may prune remaining children [7,1].

Alpha-beta pruning in the short version

Remember: MAX raises alpha, MIN lowers beta, and either level stops when alpha>=beta. Here the full value is 8, move A, with 5/8 leaves in the favourable order and 8/8 in the poor order.

For a final check, search B before A but preserve every internal order. You visit 3,5,14, prune 6, then visit 8,2,9 and prune 12. That is 6/8 leaves and 13/15 nodes; R still returns 8 and chooses A. GATE Guidance by Sanchit Sir is an optional structured route for placing Artificial Intelligence and other CS topics into a broader preparation sequence.