1993aaai J. Schaeffer, P. Lu, D. Szafron and R. Lake, A Re-examination of Brute-Force Search, Games: Planning and Learning, Chapel Hill, N.C., (AAAI report FS9302), 1993, pp. 51-58. abstract or pdf.

In August 1992, the World Checkers Champion, Dr. Marion Tinsley, defended his title against the computer program Chinook. The best-of- 40-game match was won by Tinsley with 4 wins to the program's 2. This was the first time in history that a program played for a human World Championship. Chinook, with its deep search and endgame databases, has established itself as a Grandmaster checker player. However, the match demonstrated that current brute-force game-playing techniques alone will be insufficient to defeat human champions in games as complex as checkers. This paper re-examines brute-force search and uses anecdotal evidence to argue that there comes a point where additional search is not cost effective. This limit, which we believe we are close to in checkers, becomes an obstacle to further progress. The problems of deep brute-force search described in this paper must be addressed before computers will be dominant in games such as checkers and chess.