What is Alpha-Beta Pruning?

Alpha Beta Pruning is a method that optimizes the Minimax algorithmUsed in decision making and game theory to increase the winning chances of a player. The number of states to be visited by the minimax algorithm are exponential, which shoots up the time complexity. Some of the branchesmaybe a leaf node or an entire subtree of the decision tree are useless, and the same result can be achieved if they were never visited. Therefore, Alpha Beta Pruning cuts off these useless branches and, in best-case, cuts back the exponent to half.

If you do not know the working of the minimax algorithm, study it as a prerequisite so you can understand it better.

Alpha Beta Pruning relieved its name because it uses two parameters called alpha and beta to make the decision of pruning branches.

–> Alpha is used and updated only by the Maximizer and it represents the maximum value found so far. The initial value is set to -∞. The value of alpha is passed down to children node, but the actual node values are passed up while backtracking.

–> Beta is used and updated only by the Minimizer and it represents the minimum value found. The initial value is ∞. Again, the value of beta is passed down to the children node, but actual node values are used to backtrack.

The condition used by alpha beta pruning to prune the useless branches is: alpha >= beta

Example

The values of alpha and beta are passed down until they reach a leaf node – their new value is decided by whichever player’s turn it is. The minimum value is chosen if it is min’s turn and the maximum value chosen if it is max’s turn.

Explaining the alpha beta inequality

If we look at the last image, when we are exploring the sub tree of C, after having explored the left branch, we can see that the value of node C will be 2 or less since it is the minimizer’s turn. However, node A will choose the greatest value among its children nodes and, since we have already explored the sub tree of B, will give it a value of 4. So, when A has a choice between 4 and <=2, it will definitely choose 4, which we do not need to find the actual value of node C. Instead, we can assume it to be 2 and we will reach the same final answer.