Alpha-Beta Pruning

algorithm game-theory optimisation

Definition

Alpha-Beta Pruning

Alpha-Beta Pruning is an optimisation technique for the minimax algorithm that reduces the number of nodes evaluated in a search tree by eliminating branches that cannot possibly influence the final decision. It maintains two values during the search: $\alpha$, the lower bound on the score that the maximising player can guarantee, and $\beta$, the upper bound on the score that the minimising player can guarantee.

Mechanism

The Pruning Condition: The algorithm traverses the tree depth-first. At a “max” node, the parameter $\alpha$ is updated; at a “min” node, $\beta$ is updated. A branch is pruned (cutoff) when the condition $\alpha \ge \beta$ is met. This implies that the current sub-tree leads to a result worse than a move already found in a different branch, making further exploration redundant.

Move Ordering: The efficiency of alpha-beta pruning relies heavily on the order in which nodes are examined. If the best moves are evaluated first, the pruning condition is met earlier, maximising performance. Heuristics such as “killer moves” or iterative deepening are often used to improve ordering.

Complexity Analysis

Time Complexity: For a standard minimax search with branching factor $b$ and depth $d$, the time complexity is $O(b^d)$.

• Best Case: With optimal move ordering, the effective branching factor becomes $\sqrt{b}$, reducing the complexity to $O(b^{d/2})$. This effectively allows the algorithm to search twice as deep as standard minimax in the same amount of time.
• Worst Case: If moves are examined in the worst possible order, the algorithm explores every node, reverting to $O(b^d)$.

Space Complexity: The space complexity is typically $O(b\cdot d)$ for a depth-first implementation, as it only requires storing the stack of states along the current path.