Minimax search with alpha-beta pruning
Alpha-beta pruning is an optimisation of the Minimax Search algorithm. It limits the search space by culling search paths that cannot contribute to the final result.
Alpha represents the maximum score the maximising player is assured of, Beta the minimum score the minimising player is assured of. If betaalpha, it means a maximising parent node is guaranteed higher score on another branch, or a minimising parent node a lower score on another branch. If this is the case, this branch can be culled and the rest of this node’s children can be skipped.
Alpha-beta pruning is strongly affected by the order in which branches are explored. The sooner the best moves are discovered the sooner worse branches can be discarded. In the optimal case alpha-beta can explore to twice the depth with the same amount of computation as pure minimax.
In the below visualisation, selecting “Optimal Ordering” will reorder the child nodes of each node so that the best node is examined first. This improved ordering of branches will exponentially reduce the number of nodes searched. For this example the whole graph is explored with minimax and ordered perfectly. In practice alpha-beta pruning is often used with a strategy like Iterative deepening depth-first search, where earlier smaller searches can be used to provide a branch ordering for deeper searches.