reviewed by: Ted Pedersen
During its tournament lifetime from 1989 until 1996, Chinook was a remarkably successful checkers playing program that defeated many of the world's finest players. In One Jump Ahead, Jonathan Schaeffer presents an eyewitness account of Chinook's 6-year playing career. It is an extraordinary book because Shaeffer's feelings about Chinook are much deeper than those of simply a project leader; he is a loving and ambitious father who pushes his creation to increasingly demanding levels of play. Although Chinook lays claim to the man-machine world championship in checkers, its story does not have a happy ending. This is a tale worth telling, and Schaeffer does so with honesty and a sense of fun.
Schaeffer's quest to build a world champion checkers program was rooted in his frustration with his chess playing program Phoenix. By the late 1980s he had spent more than a decade working on Phoenix. While it was improving steadily, it was apparent that well-staffed and generously funded projects had an insurmountable advantage, and that Phoenix, while very good, would never be the best (The success of IBM's Deep Blue just a few years later suggests that Shaeffer's instincts and timing were just about right.)
When asked by a colleague about the status of computer chess, Schaeffer had the same hazy set of reactions as most AI researchers: Arthur Samual, IBM mainframes, learning, maybe solved? A little research showed that checkers was not close to being solved and that Samuel's work, although seminal, largely concerned overcoming the computing limitations of his day. There was quite a bit of work left to be done with computer checkers, but nobody seemed to be doing it. Schaeffer had found an arena in which he felt he could build a world champion.
Development of Chinook began in 1989. It improved quickly, placing second in the U.S. national championship in 1990. This sudden rise attracted the attention of the reigning world champion, Marion Tinsley. One of the pleasures of reading One Jump Ahead is coming to know this fascinating man. Schaeffer portrays him warmly, as a quirky and charming man of deep religious conviction who also happens to be a nearly unbeatable checkers player. In a career of 40 years, he lost at most 10 times. Rarely challenged and often bored by human players, he became a friend and advisor to Schaeffer, hoping that Chinook would one day become a worthy opponent. And in fact, Tinsley got his wish more quickly than he might have expected.
In 1992, Chinook and Tinsley played a 40 game match for the man-machine world championship in checkers. The dramatic re-creation of this event is the high point of One Jump Ahead. Chinook took an early lead in the match. Incredibly, this was the first time that Tinsley had trailed in a match in more than 30 years. However, Tinsley ultimately triumphed, winning four games to two, with the rest of the games ending in draws. Schaeffer quotes Tinsley at the end of the match exclaiming: "Three cheers for human beings-and that includes Jonathan!"
This is a splendid moment in the book. Tinsley has won narrowly and recognizes that this "man-machine" competition was a human event, and he pays tribute to a challenging adversary. It leaves the reader with a warm feeling of unity and respect for all involved. Tinsley generously agreed to a rematch and the reader expects that Chinook will experience the same rise from defeat as Deep Blue, reclaiming a man-machine title in a second, hotly contested match. Sadly this is not quite how it happened.
The frustration of the near victory against Tinsley exacerbated tension within the Chinook team. An original member left the project after questioning the wisdom of rapidly incorporating a more extensive database of opening moves into Chinook. Schaeffer presents this painful event candidly, and to his credit he reprints both sides of the e-mail exchange that led to this parting.
The rematch that took place in 1994 engendered little public interest. After six draws, Tinsley resigned the match and the man-machine championship because of ill health. Don Lafferty, a world-championship-caliber player and close friend of Tinsley, agreed to finish the 40-game match, which ended in a draw.
This was followed by a distressing fight over the title of man-machine checkers world champion. Schaeffer believed that Tinsley had resigned his title to Chinook and that it should now be considered world champion. An official of the governing body of checkers in the United States disagreed. Letters were fired back and forth, and again Schaeffer lets both sides make their case in their own words by reprinting numerous excerpts.
If the lack of recognition bestowed on Chinook weren't enough, Tinsley's health fails and he dies less than a year after the 1994 rematch. There is no human heir apparent and none likely because the number of bright young players is distressingly small. The book ends with Schaeffer's admission that his enthusiasm for checkers has waned and Chinook is retired: a bittersweet ending to a remarkable story. One Jump Ahead is written for the educated layperson and includes accessible discussions of computer-game-playing concepts. It describes the intricacies of creating an evaluation function and the crucial role of opening books and endgame databases in both computer checkers and chess. It also does a nice job of introducing alpha-beta search to non-computer scientists.
The book has a number of technical sub-plots that computer scientists will find especially interesting. Perhaps the most engaging surrounds the creation and expansion of Chinook's endgame database. The value of such a resource is that it identifies whether a position with the given number of pieces (or less) is won, lost, or drawn. Chinook began with a four-piece database that was soon expanded to five through the volunteer efforts of Ken Thompson, who makes numerous cameo appearances throughout the book. By the end of its playing days, Chinook had an eight-piece endgame database that consisted of more than 444 billion positions.
Schaeffer does not use One Jump Ahead as a platform to promote AI; in fact, he appears reluctant to suggest that Chinook represents AI. Early in the book he argues that Chinook represents AI because it creates the illusion of intelligence. It is able to impress people by playing checkers very well, and people agree that this is something that can be ascribed to intelligence. This is not an overwhelming argument, but then Schaeffer does not make strong claims about the contributions of Chinook to AI. He points to some specific contributions to endgame databases and search algorithms but admits that Chinook, like most other programs that aspire to AI, suffered from the knowledge acquisition bottleneck and that manually augmenting it with human-generated knowledge was the key to its success.
One Jump Ahead is a dramatic and gripping book that does a great service to the game of checkers. It entices the reader to get out a checkerboard and play a game or two, or at least follow some of the positions described in the book. Best of all, despite being in retirement, a nontournament version of Chinook is available for friendly games on the World Wide Web (www.cs.ualberta.ca/~chinook). This version uses a six-piece endgame database and is a formidable foe.
University of Alberta