| In 1989, Deep Thought, a Carnegie Mellon chess machine, won the Fredkin Intermediate prize for the first chess program with a rating of over 2500, and the same year won the world computer chess championship. This thesis is a study of selective min-max search based on work done developing the Deep Thought program. This thesis also explores the idea of automatically tuning the evaluation and selective search strategy of a chess program on the basis of a large collection of master level human games.;Chapter 1 provides some background about the basic min-max search strategy used by almost all chess programs since the 1970's, reviews previous attempts at selective min-max search, and gives an overview of the design of Deep Thought. Chapter 2 discusses different ways of automatically tuning the evaluation function of Deep Thought. Chapter 3 discusses the problem of measuring the effectiveness of a given selective min-max search strategy. Different metrics are statistically compared in terms of cost (time) and accuracy. It is shown that, for the domain of chess, the traditional metric based on games between computers does not provide the best time-accuracy tradeoff and cannot be used practically to explore selective search techniques. A metric based on average performance over a large set of positions sampled from the domain is shown to be much more cost effective. This metric is used in Chapter 4 to systematically evaluate a number of selective search heuristics in the domain of chess, most of which are new or have not been evaluated with precision before. These selective search heuristics have each been implemented on Deep Thought, and the implementation trade-offs for these heuristics are also described. Chapter 5 introduces a selective min-max search technique called Equi-Potential Search, which offers the capability of automatically tuning the relative weights of a given set of search heuristics used to guide the selective min-max search. |
