In his book OneJumpAhead: Challenging Human Supremacy in Checkers, JonathanSchaeffer tells the story of the development of Chinook (the retired world champion of checkers). Chinook advanced to the point where it could beat all the human players in the world but one: Dr. MarionTinsley. The final step, improving Chinook to the point where it could beat the godlike Tinsley probably took more effort than all the steps up to that point.

With a large endgame database covering all the positions with 7-and-fewer (later 8-and-fewer) checkers on the board, the program could search into its endgame database within a few moves of the start of the game. In other words, *the first few moves* would decide the outcome of the game unless the program had bug(s) or MarionTinsley made a mistake later in the game. He was so close to perfect that the Chinook team knew this would never happen unless they could force MarionTinsley into unfamiliar lines of play. Their strategy became, to design an opening book based on all the knowledge they could collect about Tinsley's previous play and study, causing Chinook to *avoid* good moves that they knew Tinsley could parley into a draw (Checkers is drawish). They had moves that they identified (called "gold cooks" and "silver cooks" or something) that they could prove were analysed incorrectly in the literature -- e.g. Chinook with its databases could prove that a supposed drawn position was actually winnable by Chinook. They would then try to lead play to the points where these moves could be used.

If you're interested in man-machine competition (go, checkers, chess, etc.) then OneJumpAhead is an entertaining read. And if you're interested in search algorithms or game-playing engines, JonathanSchaeffer has written some papers in that area that can be found in ResearchIndex:

http://citeseer.nj.nec.com/cs?cs=1&q=schaeffer&co=Expected+Citations&cm=50&cf=Any&ao=Expected+Citations&am=20&af=Any

-- WylieGarvin