One of the most elegant of all AI search algorithms is alpha-beta pruning. The idea, similar to branch-and-bound, is that the minimax value of the root of a game tree can be determined without examining all the nodes at the search frontier.
Only the labeled nodes are generated by the algorithm, with the heavy black lines indicating pruning. At the square node MAX is to move, while at the circular nodes it MIN’s turn.
The search proceeds depth-first to minimize the memory required, and only evaluates a node when necessary. First node and f are statically evaluated at 4 and 5, respectively, and their minimum value, 4 is backed up to their parent node d. Node h is then evaluated at 3, and hence the value of its parent node g must be less than or equal to 3, since it is the minimum of 3 and the unknown value of its right child. Thus, we level node g as <=3. The value of node c must be 4 then, because it is the maximum of 4 and a value that is less than or equal to 3. Since we have determined the minimax value of node c, we do not need to evaluate or even generate the brother of node h.
Similarly, after evaluating nodes k and l at 6 and 7 respectively, the backed up value of their parent node j is 6, the minimum of these values. This tells us that the minimax value of node I must be greater than or equal to 6 since it is the maximum of 6 and the unknown value of its right child. Since the value of node b is the minimum of 4 and a value that is greater than or equal to 6, it must be 4 and hence we achieve another cut off. The right half of the tree shows an example of deep pruning.
After evaluating the left half of the tree, we know that the value of the root node a is greater than or equal to 4, the minimax value of node b. Once node q is equated at 1, the value of its parent node 9 must be less than or equal to 1. Since the value of the root is greater than or equal to 2.
Moreover, since the value of node m is the minimum of the value of node n and its brother, and node n has a value less than or equal to 2, the value of node m must also be less than or equal to 2. This causes the brother of node n to be pruned, since the value of the root node a is greater than or equal to 4. Thus, we computed the minimax value of the root of the tree to be 4, by generating only seven of sixteen leaf nodes in this area.
Since alpha-beta pruning performs a minimax search while pruning much of the tree, its effect is to allow a deeper search with the same amount of computation. This raises the question of how much does alpha-beta improve performance. The best way to characterize the efficiency of a pruning algorithm is in terms of its effective branching factor.
The effective branching factor is the dth root of the frontier nodes that must be evaluated in a search to depth d, in the limit of large d. The efficiency of alpha-beta pruning depends upon the order in which nodes are encountered at the search frontier. For any set of frontier node values, there exists same ordering of the values such that alpha-beta will not perform any cut offs at all. In that case, the effective branching factor is reduced from b to b^1/2., the square root of the brute-force branching factor.
Another way of viewing the perfect ordering case is that for the same amount of computation, one can search twice as deep as with alpha-beta pruning as without since the search tree grows exponentially with depth, doubling the search horizon is a dramatic improvement. In between worst-possible ordering and perfect ordering is random ordering, which is the average case.
Under random ordering of the frontier nodes, alpha-beta pruning reduces the effective branching factor approximately b3/4. This means that one can search 4/3 as deep with alpha-beta, yielding as 33% improvement in search depth. In practice, however, the effective branching factor of alpha-beta is closer to the best case of b1/2 due to node ordering.
The idea of node ordering is that instead of generating the tree left to right, we can reorder the tree based on static evaluations of the interior nodes. In other words, the children of MAX nodes are expanded in decreasing order of their static values, while the children of MIN nodes are expanded in increasing order of their static values.