Alpha-Beta Pruning

01

The idea

In game trees, not every node needs evaluation. If we know that a move leads to a worse outcome than one already examined, we can skip exploring its children entirely. Alpha-beta pruning implements this by tracking bounds: alpha (the best value the maximiser can guarantee) and beta (the best value the minimiser can guarantee). When beta ≤ alpha, we prune.

The algorithm works by performing a depth-first search through the game tree. At each MAX node, we update alpha with the maximum value seen so far. At each MIN node, we update beta with the minimum value seen so far. If at any point beta becomes less than or equal to alpha, we know the current branch cannot produce a better result than what we have already found, so we stop exploring it.

The effectiveness of alpha-beta pruning depends heavily on move ordering. With perfect ordering (best moves evaluated first), alpha-beta can prune up to half the nodes that minimax would evaluate, effectively doubling the search depth achievable in the same time. With random ordering, the benefit is less pronounced but still significant.

02

The maths

The minimax value V(n) of a node n is defined recursively. For a terminal node, V(n) equals its utility. For a MAX node, V(n) = max(V(c)) over all children c. For a MIN node, V(n) = min(V(c)) over all children c.

Alpha-beta pruning maintains two parameters during search: α represents the best value (highest) that the maximiser can guarantee at the current level or above, and β represents the best value (lowest) that the minimiser can guarantee at the current level or above. Initially, α = -∞ and β = +∞.

At a MAX node, after evaluating a child with value v, we update α = max(α, v). If β ≤ α, we prune the remaining children. At a MIN node, after evaluating a child with value v, we update β = min(β, v). If β ≤ α, we prune the remaining children. The pruning condition β ≤ α is called a cutoff.

With optimal move ordering, the number of nodes evaluated is O(b^(d/2)) instead of O(b^d) for pure minimax, where b is the branching factor and d is the depth. This means we can effectively search twice as deep in the same time, which translates to significantly stronger play in games.

03

Try it

Use the stepper to see how alpha and beta values propagate up the tree and trigger cutoffs. Notice which subtrees are pruned and how move ordering affects the number of nodes evaluated.

04

Where I used it

05

Easy to get wrong

06

Sources

COMP30024 (2022). Adversarial search and game tree algorithms. Formalised in Russell & Norvig, Artificial Intelligence: A Modern Approach (2020), Chapter 5.