« New Year's Resolutions | Main | Donations welcome! »
January 01, 2005
Alpha-beta Pruning
The idea behind alpha-beta pruning is that instead of looking for good moves, we look for “good-enough” moves. Originally, “good-enough” is negative infinity. This lower bound is the beta. At this point, any move is good for Sean. However, once Sean finds better moves, this beta increases. Sean doesn’t need moves worse than what he already found. He doesn’t need to find their exact values (examine them fully) to decide that these moves are inferior.
Good moves for Sean, are bad for Vlad. Sean’s lower bound becomes Vlad’s upper bound - the alpha. If Vlad finds a move better than alpha (than the beta comes bigger than alpha), the position cannot result from optimal play and no longer needs to be searched. This is called an alpha-beta cutoff.
The only “interesting” moves are the ones which have the values between alpha and beta. As the search progresses, the “window” between the beta and value becomes smaller. Alpha-beta pruning saves a lot of the search and typically reduces the effective branching factor to its square root - hence, doubling the depth of the search.
Another bonus of alpha-beta pruning is that it has a decent move to return even after an incomplete search. However, efficiency of the algorithm heavily depends on how fast we find moves which turn out to be good (so we achieve cutoffs quickly). Some moves just “look” better than others - thus it would make sense to search them first. This concept is called ordering heuristics, but more on this later.
Posted by Oleg Ivrii at January 1, 2005 05:03 PM