Confidently Selecting a Search Heuristic¹

Article type: Research Article

Authors: Anantharaman, T.S.

Affiliations: Tudor Investment Corporation, Greenwich, CT USA

Note: [1] This article is an edited version of Chapter 3 of the author’s Ph.D. thesis, May 1990, Carnegie-Mellon University (Report CMU-CS-90-173). The editing was mainly done in order to make the contribution self-contained and no information has been altered or omitted.

Abstract: This article addresses the problem of determining the best of a number of proposed selective-search heuristics in computer chess. The area is shown to be beset by problems, which may be succinctly expressed by the vast amount of computations required to get standard deviations down to a reasonable level. We consider this level to have been achieved when, say, an estimate of playing strength in USCF rating points with a confidence of 95% is within 20 rating points of computation. A total of 15 techniques have been investigated, leading to the selection of a preferred technique for its accessory advantages. The results suggest that what human Masters and Grand Masters do is not, or no longer, a good yardstick for the evaluation of a computer’s move.

DOI: 10.3233/ICG-1991-14102

Journal: ICGA Journal, vol. 14, no. 1, pp. 3-16, 1991