A Re-Examination of Brute Force Search

Jonathan Schaeffer, Paul Lu, Duane Szafron, Robert Lake

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


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.