Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

general
communitycreator

What is Alpha-Beta Pruning?

Fatima Hasan

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.

We move down, depth first, until we reach the left most leaf node. Here, we have to explore both the leaf nodes to determine the maximum value for max's turn. The maximum value is found to be 4, which is the value that alpha is set at. Now, the node's value, i.e., 4 is used to back track. When we reach node B, the value of beta is updated to become 4 as well.
Now, moving towards the next branch, we reach the leaf node with value 6. The turn is of max, therefore, it will choose the maximum value from its children node. When we explore 6, we realize that the value of alpha will either be 6 or greater than 6. We do not need to explore the other child node since the value of alpha is now greater than beta. So 2 is pruned.
B's node value becomes 4 as it is the minimizer and min(4,6) = 4. This value is passed up and the value of alpha is changed by the maximizer to become 4 as well. Now moving towards the next leaf node, we follow the blue path to reach 2. We need to explore both the branches to find the maximum value for the maximizer, which is 2. This node value is passed up and the minimizer changes beta's value to 2. Now alpha is again greater than beta so the entire right branch is pruned.

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.

RELATED TAGS

general
communitycreator
RELATED COURSES

View all Courses

Keep Exploring