Search Control Methods in Deep Blue

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.