
AlphaBeta PruningThis is a technique used for optimizing Recursion Trees. You'll know what Recursion Trees are in a minute. Basically, this alphabeta pruning method helps speed up your recursive function tenfold.

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 TreeTake 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 moveselecting 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 subnodes 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 dsubtree. At this point, we know that the current maximum on level 1 is 5 (node c). For the first node in the dsubtree, 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 dsubtree is useless, and we can immediately abandon further pursuits in this subtree. 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 subtrees 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 alphabetapruning. 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.

recursion
index introduction
magic
squares tic
tac toe connect
4 optimizing recursion trees sorting equation generator other problems 

home jokes programming about me resume guest book  