Murray S. Campbell, A. Joseph Hoane, Jr., and Feng-hsiung Hsu
The Deep Blue chess-playing system explores a huge search tree when selecting a move to play, typically examining on the order of 20 to 40 billion positions. Although a relatively complex evaluation function is applied to the leaf positions of this search tree, there is significant possibility of error in the evaluation function values. Incorrect position evaluation can lead to a poor move choice at the root of the search tree. We have developed methods to reduce the susceptibility of Deep Blue to evaluation function errors through the use of selective extensions in alpha-beta search. This paper briefly reviews some of the standard methods employed in game-playing programs to cope with evaluation function errors, and describes some of the techniques used in Deep Blue.