Alpha Beta Pruning is a method that optimizes the
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
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.
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.
View all Courses