CIS310-s09/Notes

From MCIS Wiki

Alpha-Beta Pruning

See the Wikipedia (http://en.wikipedia.org/wiki/Alpha-beta_pruning) for a more comprehensive description.

Test your code by considering the following example (excuse the ASCII art!)

                  10      alpha = - infinity, beta = infinity
                /    \            max level
              10       5     alpha = 10, beta = infinity
                     /    \       min level
alpha = 10          5       x   cutoff because beta changes to 5 which crosses alpha
beta = infinity 

Note that if x is greater than 5, the 5 will win and x doesn't matter. If x is less than 5, then this would change the right tree to be x but since the top level won't change unless the right side is > 10 it won't matter if x < 5. So no matter what x is the result is 10.

Max levels increase alpha, min levels decrease beta.

Instead of using the algorithm in the wikipedia, use two different loops: one for a max (white's move) level and another for a min (black's move) level. This way you don't ever exchange alpha and beta or negate values that come out of the heuristic evaluator.