Search Control Methods in Deep Blue

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

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.