Alpha-Beta Pruning

This is a technique used for optimizing Recursion Trees. You'll know what Recursion Trees are in a minute. Basically, this alpha-beta pruning method helps speed up your recursive function ten-fold.

Formidable though this term may seem, the concept is fairly straightforward. And it has the effect of nullifying much of the Limitations of Recursion we discussed earlier. First, you should understand what a Recursion Tree is.

Recursion Tree

Take the case of Connect 4. At the beginning of the game, there are 7 possible moves. This can be represented as:-

For each of the 7 given possible moves, there are 7 possible moves.

This is a Recursion Tree. Level 0 corresponds to the topmost level (which is a call to the move-selecting function). Level 1 is deeper than level 0, level 3 is deeper than level 2, etc. (as you can see). Node 1 would occur first, then node 2, then node 3 and so on. On a given level, the nodes occur from left to right (or so we'll assume).

For the sake of making it simpler to explain, assume that the Recursion is allowed only to a depth of 2, i.e., only till level 2. At level 2, the function calculates a goodness value based on the position of the coins, advantage, etc. [Which I haven't discussed.] So, we have something like this:-

The values at the bottom are the goodness values for the given move. So, now, what will the value of 'a' be? The negative of the maximum of the 7 values, i.e., negative of 19, -19. So, a = -19. Suppose we've calculated the values of a, b and c and now we're on node d. Assume a(-19), b(-2), c(5). Suppose d has sub-nodes with values 3, -4, 10, 20, -18, 3, and 10. After the sweep through these nodes, d would have a value of -20.

Notice at this point that the value of -20 is useless to us, since c has the greatest value of 5, and hence, by no means will -20 be the maximum goodness value.

Consider the entry into the d-subtree. At this point, we know that the current maximum on level 1 is 5 (node c). For the first node in the d-subtree, we obtain a value of 3. We now know that the maximum value on this level 2 cannot be less than 3. Following me? And hence, the goodness value of the node d can by no means be greater than -3. Which is less than 5. So, the d-subtree is useless, and we can immediately abandon further pursuits in this sub-tree.

We have thus saved checking 6 nodes. Suppose the recursive depth was 4, i.e., recurse till level 4, then we save checking 6x7x7 nodes - quite a bit of time is saved. Did you get the point?

Summary. When checking a given node, if the maximum goodness value of the current level is greater than the negative of the goodness value of one of the node's children, then the node can be abandoned. Equivalently, when the goodness value of a given node is greater than the negative of the maximum goodness value in the level above, then the rest of the sibling nodes need not be checked.

Using this method, a lot of time is saved and a lot of useless sub-trees are avoided. This method of "cutting off branches" is called Pruning (derived from the gardening term). Don't ask me what 'alpha' & 'beta' are supposed to mean in alpha-beta-pruning. All I know is it works. And it works wonderfully.

I noticed that my game of Connect 4 increased in speed by over 12 times. Moreover, increasing the depth does not significantly increase the time taken. It doesn't seem exponential anymore! This method is applicable to all recursive functions which return a goodness value. So you can even use it with Tic Tac Toe. It doesn't need too much of a modification to implement. Go ahead, try it!

And that concludes this wonderful tutorial.