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:-
Eg: yellow wins in the following game.
 

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:-

 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.