Module 4: Game Searches
Alpha-Beta Pruning Examples
Sometimes it helps just to see a few extra examples of an algorithm and alpha-beta pruning seems to especially confuse people! One in-depth example follows (more can be made if they are useful, just let me know!) with an analysis of a slightly changed example after that.
Example 1
Figure out which nodes are pruned on the search tree below using alpha-beta pruning.
Step 1
We start with alpha and beta both set to their initial values: alpha is negative infinity and beta is infinity. We send these values down the tree. Remember, we can never prune the left most node as we need a value to check for beta less than or equal to alpha. For this example, the current step will be shown in red and the older work in grey.
Step 2
We reach a leaf node whose value is 0. Because the parent node is a MAX node, we set the alpha value to be 0.
Step 3
Now we need to finish exploring the leaf node, always seeing if we can prune. In the end, 2 is the best value and the max node sends 2 up to its parent, which then sets BETA to 2 because it is a MIN node.
Step 4
We continue to explore the leaf nodes. Here we see another node valued 2.
Step 5
There is nothing to prune on the node valued 2 on the previous step so we go to the next node. Here we see a 4 and we are able to set ALPHA to 4 because this is a MAX node. Suddenly something might be about to happen!
Step 6
I separated this out from the previous step to highlight what is happening: we do our usual check for beta less than or equal to alpha and suddenly, 2 is less than 4! We can PRUNE! Thus we never see the node labeled -3 and we return from this branch of search.
Step 7
We return all the way to the root node in this case. Remember, alpha and beta are NOT global variables. They are local to the recursion and the good part of returning to the root is we can now set ALPHA locally since the root node is a MAX node. Thus we now have alpha set to 2 and beta remains at infinity.
Step 8
We proceed with the algorithm down the next set of nodes but remember, alpha is now 2 instead of negative infinity. We look for places where beta is less than or equal to alpha. Alas, 3 is not less than 2 so no pruning on this step.
Step 9
Continuing up and down the search tree while checking for beta to be less than or equal to alpha. So far no additional nodes pruned.
Step 10
On the final node in this branch, we are able to set BETA to 1. 1 is indeed less than 2 so we would prune if there were additional nodes to prune on this branch (alas there are not). One final note, since 1 is less than 2, the root node does NOT change its alpha value because it is a max node and 2 is better!
Step 11
We recurse down the final nodes using our alpha of 2 and beta of negative infinity again. After visiting the first set of children on this branch, we are able to set beta to 3 but 3 is not less than or equal to 2 so we do not prune.
Step 12
On this next step, we proceed down the remaining nodes and discover that unfortunately there is no more pruning. In most examples, we would be able to prune more and we could have done more here if we had ordered the nodes differently!
Animation of full algorithm
The sequence of steps above is animated below, if that helps you to visualize the information flow.
Slightly Altered Example
Remember we discuss node ordering in the lectures. If the node with value 1 in step 10 had been found as the left most node in step 8, we could have pruned that whole subtree! That is shown below!
