Back to Study Material Artificial Intelligence

Alpha beta pruning

Alpha-beta pruning is an optimisation of the minimax algorithm that eliminates branches of the game tree that cannot possibly influence the final decision,...

Alpha beta pruning

Eliminating Irrelevant Branches

Alpha-beta pruning is an optimisation of the minimax algorithm that eliminates branches of the game tree that cannot possibly influence the final decision, without changing the result minimax would return. It maintains two values during the search: alpha, the best value that MAX can guarantee so far along the current path, and beta, the best value that MIN can guarantee so far along the current path. When a MIN node's value falls at or below alpha, MAX would never choose the path leading to that MIN node, so its remaining children can be pruned. Symmetrically, when a MAX node's value rises at or above beta, MIN would never allow that branch, so pruning applies there too.

The efficiency gain from alpha-beta pruning depends on the order in which moves are examined. In the best case, where the best move is always examined first at each node, alpha-beta reduces the number of nodes evaluated from O(b to the power d) to O(b to the power d divided by 2), effectively allowing search to twice the depth compared to plain minimax given the same computation budget. In the worst case, with moves in reverse order, pruning provides no benefit at all. Practical implementations use move-ordering heuristics such as examining captures before quiet moves in chess to approach best-case performance.

Alpha-beta pruning was independently discovered by multiple researchers in the 1950s and 1960s and was formalised mathematically by Knuth and Moore in 1975. It remains fundamental to all high-performance game-playing programs even as neural network evaluation functions have supplemented classical search.

A Worked Example

Imagine MAX is considering a move and the best option found so far gives a value of six, so alpha equals six. While evaluating another branch, MIN finds a child with value four. Since four is less than alpha, MIN would choose this value or lower, making this branch worse than six for MAX. The rest of this branch is pruned without further evaluation.

Exam Tip

When tracing alpha-beta on a game tree in an exam, maintain an explicit alpha and beta value at each node and write the updated values as you descend. Mark pruned subtrees clearly with an X or bracket. A common mistake is pruning at the wrong player's node: remember that alpha cutoffs happen at MIN nodes when the MIN value is less than or equal to alpha, and beta cutoffs happen at MAX nodes when the MAX value is greater than or equal to beta.