Chinook

James Propp

On the morning of August 15, 1994, mere hours before the world championship checkers match is due to begin, the second-best checkers player in the world has been up for four days straight and is continuing to work on its game.

This "player" is Chinook (pronounced shin-NOOK), a computer program-- or rather a hardware/software amalgam consisting of a huge computer program and the supercomputer it currently resides on. Each without the other would be powerless. Acting in concert, and aided by the human beings who serve as an interface to the outside world, they will have a chance, over the next ten days, of beating the man who is indisputably the best checkers player in the world and probably the best checkers player of all time.

The checkers match, officially called The Second Man vs. Machine World Championship, is being held in a medium-sized hall at the Computer Museum in Boston. At the front of the hall is a raised platform, on which rest two chairs and a green felt table. On the table is a checkerboard, some checkers, a competition clock, and a monitor that will allow the human beings who function as Chinook's eyes and hands to communicate with the program.

The supercomputer itself stands unobtrusively off to the left of the stage. It belongs to a high-performance line of Silicon Graphics machines prophetically named the "Challenge." It weighs 1200 pounds, and is about the size of a large refrigerator. The box's black exterior offers few clues as to what it contains (16 processors and the cooling apparatus required to keep them from overheating); the only hints are the words "Silicon Graphics Challenge XL" on the front of the unit and, beneath those words, a small liquid-crystal display panel. The Chinook program that the machine is running (or might it be more helpful to think of the program as running the machine?) consists of roughly 50,000 lines of code in the C programming language, together with an enormous data-base of codified checkers-knowledge that has been years in the making.

Jonathan Schaeffer, the head of the team that created Chinook, is a 37-year-old computer scientist with a passing resemblance to the comedian and film maker Albert Brooks. He's been working on the project since 1989, as a professor at the University of Edmonton in Alberta, Canada (promoted from Assistant to Full Professor a month ago). He's in the room now, making sure that everything is in order for the start of the match. Also present in the room are three other members of the Chinook team: Martin Bryant, Robert Lake, and Paul Lu, all in their 20's and 30's. Martin is a gregarious Englishman and the best human checkers player on the team. His specialty is the part of the data-base concerned with the opening moves of the game. Robert Lake is quieter and more intense; he's responsible for the endgame data-base. Completing the group is Paul Lu, a friendly fellow whose job is making sure that the computer's sixteen processors collaborate productively on the task of searching for good moves during the intermediate part of the game, when neither Martin's data-base nor Robert's can always be used in deciding what to do next.

Jonathan, Martin, Robert, and Paul have jointly put in tens of thousands of hours creating Chinook. The name itself was Jonathan's idea, and is a pun on the English name for checkers (draughts) -- a "chinook" being a hot dry wind (draft) in the Pacific Northwest. One Canadian newspaper, which should have known better, came quite close to printing the computer program's name as "Shnook"; fortunately, Schaeffer caught the error just in time. To the members of its team, Chinook is not just a joint creation but a teammate; they often use the word "we" in a way that includes Chinook, as in "We think this is the right move."

Also present in the room is a mild-looking retired professor of mathematics. He wears a light blue suit and tie-pin with "Jesus" written on it in colored rhinestones. He doesn't look like the sort of man to acquire a nickname like "The Terrible Tinsley." But Marion Tinsley's benign exterior cloaks a formidable intellect. At age 27, he was the best checkers player in the world, and by all accounts his game has only improved during the forty intervening years. His record is unparalleled in checkers, chess, or any other game of skill.

To get an idea of the embarrassingly wide margin by which Tinsley surpasses his nearest competition, consider his defense of the world title in 1989 against the challenger Paul Davis. Tinsley drew 23 games, won 9, and lost 0. During his forty-year reign, and over the course of over a thousand games of tournament play, Tinsley has lost exactly nine games. It's hard to come up with anyone who has so thoroughly dominated a field of human endeavor for such a long stretch of time.

Relations between Schaeffer and Tinsley seem friendly and relaxed. Jonathan has enormous respect for Marion. "He's amazing," he says. "When I'm 67, I hope I'm capable of the things he's doing." Marion, for his part, wishes Jonathan well. "Chinook is getting better and better; I'm just trying to do my best." And: "I had a dream last night. God said `I love Jonathan too.'" Still, Tinsley, like Schaeffer, hopes to win; for the last few days, he has been saying Psalm 25 ("Let not my enemies triumph over me") with special devotion.

Both men predict a close match, but Tinsley has some causes for anxiety. Chinook has a perfect memory, and in particular, knows every game Tinsley has ever played. What's more, Chinook has analyzed many of these games to figure out the reasons for Tinsley's moves. This means that, in playing Chinook, Tinsley will be in a sense playing himself.

Tinsley also fears that he may get worn down. Chinook is not subject to fatigue as people are, and can play games that go on indefinitely; in fact, Chinook is like a pit bull, and will keep on harrying its opponent as long as its own hide isn't in danger. Schaeffer has promised that in the interests of good sportsmanship, the Chinook team won't drag out games just to wear Tinsley down, and that when a position is reached that looks like it will lead to a draw, the team will offer or agree to a draw, even if Chinook is eager to play on in the hopes of Tinsley making a mistake.

What Tinsley also suspects is that Schaeffer and his collaborators have come up with some surprises for him -- new traps, or "cooks" in checkers terminology. This means that if the computer can lure him into a position that it has analyzed with special thoroughness, it can lead him into a situation where a seemingly good move on Tinsley's part will have hidden but devastating consequences many moves later. Tinsley's suspicions are in fact correct, but they do him no good, since he has no way of knowing where the traps lie.

Local checkers buffs and journalists seem to be the only people in attendance other than the organizers and the participants in the match. The hall seats a few hundred, but only about 35 people are present as the opening ceremonies begin. There were probably more people attending the last world checkers championship that was held in Boston, in 1847. One reason for the small turn-out is the fact that today is a work-day, but a likely contributing factor is the low esteem in which the game of checkers is held nowadays; most people think of it as a game for children or old men, and are surprised to hear that there are international checkers competitions.

One checkers player who does not disparage checkers is chess grandmaster Raymond Keene. Keene is one of the original organizers of the computer checkers championship, and he gives the kickoff speech in the opening ceremony, extolling both the game of checkers and the incredible record of Dr. Tinsley, whom he claims is arguably the most dominant player in the history of any sport. After Keene, other speakers make brief remarks: Marvin Minsky of MIT, Bob Bishop of Silicon Graphics, Tony Buzan of Mind Sports International, David Greshler of the Computer Museum, and David Levy, the international chess master who contributed to the early development of chess-playing programs by offering a prize to the first computer that could beat him. Some of the speakers see, in the present contest, a potential milestone in the history of intelligence on Earth. For all their hype, these slogans about the rivalry between carbon and silicon ring with a certain amount of truth. The supremacy of computers at some traditionally human mental sport will constitute a coming-of-age ceremony in which artificial minds are welcomed into the fraternity of intelligence.

Whether or not one agrees that something fundamental in the relationship between human beings and computers is at stake here, there are prosaic stakes whose value is beyond dispute. The loser of this match will receive only $5,000; the winner will get $8,000, in addition to the glory of victory. Also, if the computer can manage to beat Tinsley, Schaeffer just might be able to collect from the American Checkers Federation on its long-standing offer of a $5,000 prize to the first program that can beat the world champion.

Now it is time for the games to begin. Marvin Minsky, a pioneer in the field of artificial intelligence, is asked to come to the front to draw twice from a special deck of 36 cards. He draws a card, notes what he has drawn, puts the card back, and draws again. The two draws, taken together, determine the first three moves of the game: 9-14, 22-18, and 11-15. This information is announced, and then we are told "Play has begun!" Tinsley and Schaeffer, sitting at the green felt table, shake hands and begin the match.

Versions of checkers have existed since antiquity, but the version that we play in this country can only be reliably traced back a few centuries. There have been world-championship matches since 1847; they became annual around 1934. (Up until then, it was possible for the champion to retain the title for long periods by refusing to play, for any number of excuses.) The game's popularity peaked during the Depression and has gone steadily down since then, but even today, more Americans know the rules of checkers than of chess.

Our version of checkers is only played in the English-speaking world; in the former U.S.S.R., for example, 10-by-10 (or International) checkers is by far more popular than 8-by-8. Even so, the 8-by-8 version is played by two hundred million people around the world, and there are thousands of top-flight players.

People who think that the version of checkers played by school-children is boring have a valid point: when both players are expert, the outcome, more often than not, is a draw. Indeed, it is universally believed that checkers, when played between perfect players, will always lead to a draw. That's why tournaments aren't played by the familiar rules, but employ what is called "restricted play." Under the form of restricted play that governs the Chinook-Tinsley match, the first three moves of the game are determined by lot, from a list of 144 opening sequences. By forcing variety in the opening positions, this convention forces players to explore and master less familiar situations, in which the path to victory (or, failing that, the path to a draw) is not so clear.

Most of these openings preserve the balance of power between the two sides (called Black and White), and usually lead to draws. Other openings -- the so-called "tough openings" -- give one player a significant advantage over the other, and increase the likelihood of non-drawn games. This might seem to pose the risk that a player will lose a match because of poor luck rather than lack of skill, so under this form of restricted play it is mandated that each opening sequence will be played twice, with the two players taking different sides of the opening. Thus, for example, the first game of the match, in which Chinook plays Black, is to be followed by a game with the same three opening moves, but with Chinook playing White. This convention of championship play provides the background for an amusing anecdote, in which a great checkers player, near the beginning of a game, was taking a long time to make some simple moves. Someone asked him, was he taking so long because he was thinking about what he would need to do later in the game? No, he explained; he was thinking about what he would need to do in the next game.

Over the two centuries, checkers players have developed a large literature about what one should do in particular situations, and no checkers player can afford to be ignorant of this accumulated knowledge. This is even true in the endgame, where most of the pieces have been removed from the board and one might naively think that the situation is simple enough to analyze by a brute-force examination of all the possible moves. For instance, there is one infamous endgame position that involves just 3 pieces of each color, in which one player must make 40 accurate moves in order to reach an easily winning position. Even a small deviation from the correct sequence of moves may throw away the victory. More complicated positions, such as 4 pieces against 4, could require 100 accurate moves.

On the other hand, even the voluminous literature on checkers can survey no more than a minute fraction of all the positions that arise during the course of play. Mere encyclopedic knowledge of the literature is not enough; one must also be able to analyze each position, via a combination of intellection and intuition. One also needs to have a high energy level. Checkers games can sometimes be over in an hour, but they can also last four or five hours, and world title competitions typically require players to play 4 games a day. A single day's four games can take ten hours, which is a far more grueling regimen than the six hours a day that is usual in chess competitions.

The popularity of chess, combined with the two games' superficial resemblance, is probably a key reason for checkers' lack of popularity. Don Lafferty, age 61, the second-best human checkers player in the world, thinks that the two games currently attract different sorts of people. "I never met a checkers player I didn't like; they're all even-tempered," he says. "Chess players are egotistical. They think they're intellectuals and that everyone else is beneath them. Checkers players aren't like that." It certainly is true that the top chess players have a kind of charisma that the top checkers players lack. This probably leads to a self-perpetuating lack of interest in checkers.

In fact, checkers can offer the human mind as much scope for effort and accomplishment as chess. Superior alien beings might actually feel that we humans have no business playing a game as complicated as chess -- that human play completely ignores the true complexities of the game, and confines itself to certain pools and shallows where the currents are navigable by our limited minds while the real interest lies elsewhere. Recent computer-aided explorations of chess endgame problems, by Ken Thompson of Bell Laboratories and others, indicate that if one were to play God at chess, the moves He would make, at least in the endgame, might be baffling and enigmatic, and look no more like Bobby Fischer's than like a weekend amateur's.

On the other hand, if God plays checkers, His style of play just possibly might resemble Marion Tinsley's.

Tinsley became the world champion in 1955, while he was still a graduate student in mathematics. Ironically, when Tinsley got his degree in the field of combinatorial theory, he got two job offers: one from the Florida State University in Tallahassee, which he accepted, and the other from the University of Alberta in Edmonton, which is now Schaeffer's home institution. If someone in the dean's office in Edmonton had been more impressed by the fresh Ph.D. from Ohio State, Tinsley and Schaeffer might have wound up at the same university.

In 1958, after three uninterrupted years as champion, Tinsley retired from tournament checkers. Having no serious rivals in the game, he was getting bored, and he wanted to devote more time to his research. He continued to player checkers outside of competitions, and in particular, he served as a kind of mentor to Don Lafferty, a high school math and science teacher from Kentucky. The two men had met during Tinsley's years playing championship checkers, and developed a deep and lasting friendship over the succeeding decade.

It was Lafferty who brought Tinsley back into the checkers world in 1970, after twelve years of retirement. Lafferty says: "I used to be a heavy drinker. And with the way I drank, one drink was too many and a thousand wasn't enough." Tinsley made a deal with Lafferty that he would go back to playing checkers tournaments if Lafferty would cut down on his drinking. Lafferty's adherence to his end of the bargain has, by his own account, been intermittent, but Tinsley's was astounding. "Coming out of retirement was an unusual experience," Tinsley says. With every new game he played, he could feel long-disused mental muscles begin to revive and assume their former power. But, according to Schaeffer, the new Tinsley was no longer the enfant terrible of the 1950's; Tinsley still hated to lose, but he was no longer so keen to win each and every game. He never lost a tournament, but he often would win only the minimum number of games he needed, and then coast. He did not seem to be interested in winning back his title; perhaps he wanted to give others a chance at the glory, for the overall health of the sport. But when you happen to be the best player in the world, you will eventually rise to your level, and Tinsley was once again world champion by 1975. No one had told him that intellectual vigor was supposed to be the province of the young, or if they did, he clearly hadn't taken the admonition to heart; his game had gotten stronger, not weaker, since the 50's. Indeed, both Tinsley and his opponents say that the man's game has improved to this very day.

In describing Tinsley, Schaeffer says, in wry mock-consternation, "This man is not normal." There is no disparagement intended -- only awe, tinged with humor.

How does Tinsley explain his phenomenal performance? He professes not to know. One clue he does offer concerns his motivation. "I'm basically an insecure individual," he says; "I hate to lose." Other checkers players back this up; in watching Tinsley play simultaneous games in exhibition, moving from board to board, they have been struck by the intensity with which Tinsley wants to win not just most of the games, but every single one of them.

The game of checkers is not, according to Tinsley, the most important thing to him; religion is his main passion. He has a daily radio program on biblical topics that is broadcast in the vicinity of Conyers, Georgia, where he has lived since his retirement from Florida State. And indeed on first acquaintance one is likelier to take him for a minister than for a game player with killer instincts. "He's a gentleman," says Paul Lu, the youngest member of the Chinook team.

When Arthur Samuel's program beat a fairly strong Connecticut player in 1962, the press had a field day, and announced that computers were now "better" at checkers than humans. This was a fatally premature announcement -- fatally, because in over-stating the program's accomplishments, the press killed off what might have been a fruitful area of further exploration. In actual fact, the computer won a single isolated game but later lost when it played the human a full match; moreover, the game in which the program prevailed over the human player was not won by the program's cleverness but lost by the human's momentary inattention. (The human, a man named Robert Nealey, made a single, blundering move that completely turned the tide of the game. Perhaps Nealey had forgotten the positions of all the checkers; he was, as it happens, totally blind.) In any case, it should have been clear that Samuel's program, for all its promise, was only the first step towards computer superiority at the game of checkers.

However, journalistic hype held the day, to the point that even now, researchers in the field of artificial intelligence, learning of Schaeffer's interest in computer checkers, often look puzzled and say "But didn't Samuel solve that problem?" This is a source of more than casual irritation to Schaeffer, since the people in AI who evaluate the merits of his funding proposals often know only the popular myths about computer checkers.

In the wake of Samuel's work, interest shifted towards computer chess. Initially, there was great optimism -- for, if a computer learned from its mistakes, couldn't it bootstrap itself up to unlimited levels of ability simply by playing thousands of games against humans, or other computers, or itself?

Here an unforeseen difficulty arose. Human learning is intimately tied up with the human capacity to form new concepts which tie together low-level percepts, and then higher-level concepts to tie together those new mid-level concepts, and so on. This ability to innovate is currently thought to be at the heart of human intelligence, and it has proved to be elusive (frustratingly so, to those who are trying to simulate intelligence on a computer; gratifyingly so, to those who fear that such simulation will rob humankind of its essential dignity). Without this capability -- call it creativity if you like -- computers' ability to play chess in a human fashion seemed to hit a ceiling.

We are so far from understanding the cognitive infrastructure that makes human-style play of games possible in the first place that, ironically, it is not even our failed attempts to mimic creative processes that have led to the advent of the best machine players. The most powerful chess-playing programs are not those that have crude parodies of the human ability to create new concepts but those that take advantage of what machines do best, namely, execute simple actions repeatedly, quickly, and flawlessly -- such as in this case performing massive calculations that consider, one by one, each of the possible courses of action the players can take, and what the results of these courses of actions will be later on in the game. As computers became ever-faster in the '70s and '80s, it became clear that even without a revolution in our understanding of the human mind we would soon have computers that could play a strong game of chess, purely on the strength of their blazing speed, and not because their programs were particularly deep.

A helpful way of picturing the way these programs analyze games is what is called a "game tree." These are diagrams in which the choices open to a player -- "Do I move this checker, that one, or this other one?" -- are modeled by the sort of decisions a person makes when wandering in an unfamiliar area and arriving at an intersection -- "Do I turn left, turn right, or go straight ahead?" To keep the diagram from getting too complicated, the successive moves are envisioned as successive steps from one tier of locations to another. The successive steps in such a diagram (from the first position of a game to all the positions that can succeed it, and thence to all the positions that can succeed those positions) resemble the trunk, branches, and twigs of a tree. These trees are typically drawn with the trunk at the top and the branches and twigs successively further down, so that the passage of time corresponds to moving down the page, as in the reading of text. Starting from any point in the tree, all the different possible future moves constitute a sort of tree unto themselves, which computer scientists call a subtree.

In principle, with infinite computing power, it would be possible to completely solve the game of checkers. Positions in which one of the players has no legal move are losing positions for that player, and a win for his opponent. Positions in which the player whose turn it is to move can move to a winning position are themselves winning positions. Positions in which the player whose turn it is to move can only make move to losing positions is a losing position. By iteratively applying these rules, working from the endgame backwards (that is, starting with the leaves of the game tree and progressing to the branches and trunk) one could in theory classify the positions as wins for one player or the other. Eventually the procedure will terminate when all of the billions of billions of positions that are wins or losses have been recognized as such; at this point, all the not-yet-classified positions can be recognized as being draws.

In practice, this sort of analysis is not possible until one gets to the endgame, where the number of levels in the tree becomes manageable. To resolve this impasse, game-playing programs follow Samuel's lead in making use of "heuristics." These are rules of thumb that neither promise nor deliver perfect performance of a task, but do a decent job in most situations. For instance, one kind of heuristic might be to assign each checkers position a score that gives a rough index of how much it favors the computer, in terms of some general criteria such as the number of pieces that the computer has on the board and the extent to which these pieces control the center. The computer might look at all its different options, calculate the score of each one, and choose the option with the best score.

Naturally, this sort of procedure is only as good as the scoring method chosen; in some sense, it begs the question. Nevertheless, the point of view has been a fruitful one. What Samuel did was devise a program in which the scoring system was subject to revision by the program itself, in accordance with the outcomes of the games it played. The program's initial progress was very impressive. Unfortunately, the program hit a performance ceiling around the time that it beat the Connecticut player. The problem is that Samuel's scoring system used preassigned criteria for the strengths of positions, and only modified the computer's assessment of the relative importance of the different criteria. His program was unable to take into account the subtle ways in which the different criteria might interact with one another; moreover, it did not permit the computer to formulate its own additional criteria, in the way a human player would. These defects in Samuel's program were not the result of deficiencies in his programming skill, but were caused by difficulties inherent in the all attempts to create machine intelligence; these difficulties have plagued subsequent generations of researchers in AI.

When Jonathan Schaeffer came to the University of Edmonton in 1984, the AI community had mostly given up on game-playing as a criterion of machine intelligence, and had focussed its efforts on so-called "expert systems," which, in addition to offering more useful real-world applications than work on games like checkers and chess, also gave researchers an opportunity to focus on the use of heuristics in computers, without having to deal with the extra layer of complexity added by the adversarial nature of games. Those computer scientists who were willing to ignore the fashion and continue to work on games devoted their efforts to chess. Much to the consternation of AI visionaries, progress in computer chess came not from their own efforts to understand the nature of intelligence but from Silicon Valley's success in continually building faster computers. In machine-versus-machine competitions, victory usually went not to the cleverest program but to the fastest one, especially if it ran on hardware that was specifically designed to facilitate the representation of chess positions. The efforts of the chess programmers and their unwitting accomplices the chip designers led to a congenial schedule of communal gratification for the former: every year or two, a new computer champion appeared, a new record was set, and computers pushed still further up through the ranks of the chess-playing world. Today's best chess-playing computers play at the level of weak grandmasters and can beat all but a few hundred chess players in the world.

In the midst of all this exciting progress, Schaeffer began to have second thoughts about the direction he wanted to take his own research. Chess was very exciting, but checkers was a simpler game, in which the massive-computation approach that had proved so successful in chess might be even more successful. It seemed reasonable to hope that a checkers program, that made use of existing ideas in a clever way, might actually have a chance of beating the best human players. Schaeffer began work on Chinook in 1989.

Chinook's strength comes from several different sources. One is that it has a good opening book, encoding much of the accumulated lore of checkers experts, which tells it what it should do at the beginning of a game. Another is its endgame data-base, which has been developed over the last five years by exhaustive analysis of the ramifications of all the different endgame positions; if you describe to Chinook a checkers position involving four black checkers and four white checkers, Chinook can search the endgame data-base and play perfectly. But what about the middle-game, during which it may happen that neither of these data-bases offers Chinook any advice? Here, Chinook makes use of a good evaluation function and its ability to perform deep searches.

The evaluation function is of the same general sort as the scoring system used by Samuel's program, and it has evolved over time based in part on the programmers' knowledge of the game of checkers and in part on the program's experiences in the course of play, but with the difference that the programmers played an active role in the learning process.

However, even a good evaluation function is not very useful unless it is designed with a certain amount of look-ahead. What a program like Chinook does is to examine very many positions that may occur in the medium-term (twenty-move) future of the game. Since the number of possibilities grows exponentially over the course of time, the computer cannot hope to look at all the possibilities, unless it uses some criteria to decide which possibilities are the important ones to look at, or it sets some sort of threshold as to how far into the future it needs to look, or both. At this point, the computer uses its evaluation function as a rough approximation of the strengths of these possible future positions. These heuristic evaluations are a sort of surrogate for the kind of calculations that a computer with infinite resources would do, namely, continue exploring even further into the future.

One might fear that the flaws in the evaluation function, when applied to positions far in the future, would only be magnified by the distance in time between those positions and the present state of the game. Fortunately for Schaeffer and other creators of game-playing programs, the reverse appears to be true: the plethora of possible destinies that a game can have seems to give rise to a sort of smoothing out of the deficiencies of the evaluation function, so that the mixed strategy of combining look-ahead with evaluation functions works even better than the bare evaluation function.

Some of the ideas that were used in the design of Chinook are too technical to describe here, but three of them -- "minimax strategy," "depth-first search," and "alpha-beta pruning" of game trees -- are sufficiently simple in principle that they are worth describing here, to give the reader at least a sample of the sort of ideas that were involved in the creation of Chinook, and to forestall the misconception (all too easily conveyed by the use of terms like "brute-force calculation") that Chinook's successes are nothing but a vindication of dim-witted persistence, carried to novel extremes by the rapidity with which modern integrated circuits can shunt electrons to and fro. (You can get more information here on the minimax heuristic, depth-first search, and alpha-beta pruning).

Using depth-first search and alpha-beta pruning to determine the minimax strategy, Chinook is able to assign a value to the current position and to each of its possible successors. The program, unless overridden by its handlers, will always make the move that has the highest value (except in the opening, where it usually defers to the wisdom of tradition, as embodied in its opening book). Schaeffer writes: "Chinook assesses positions in terms of the value of a checker (100 points). The more positive the number, the better the position is for Chinook; the more negative, the worse. Usually, I start worrying when Chinook is down 20 or more points.... It is important to note that Chinook's assessments are based not on the current position but on the positions it is considering far in the future." A value near zero indicates that a position doesn't offer any appreciable advantage to either player, and will probably lead to a draw.

A final strength of Chinook is that its search strategies for middle-game analysis are eminently suitable for parallel computation. That is, if a computer has several CPU's, each CPU can work on a different subtree, analyzing the ramifications of each possible choice of move. Thus, by adding more processors, one can increase the speed with which the program searches the game tree to any fixed depth. Putting this another way: if the amount of time that the computer can spend in choosing its next move is held fixed (as is the case in tournament play), then parallelization allows the computer to look deeper into the future and make more prudent moves.

The division between the stages of the game is actually not as clear-cut as the preceding descriptions might lead one to think. In deciding opening moves, Chinook will not just trust its opening book, but will do some calculations of its own, using depth-first search. Its forays into the future may lead it to positions that are actually in the endgame data-base, in which case Chinook can make use of the known outcome of these positions (win, lose, or draw) rather than using its heuristic position-evaluation function. All three components -- the openings book, the parallelized search schemes, and the endgame data-base -- must operate smoothly with one another, forming a single analytic juggernaut.

It should be stressed that Schaeffer is, in his own words, only a "rank amateur" at the game of checkers. Even Martin Bryant, the best checkers player on the Chinook team, is only a moderate club-player. Facile paradoxes about getting "something for nothing" notwithstanding, there's nothing strange about a person writing a program that can do a task that he himself cannot, simply by virtue of its blinding speed and its ability to perform tedious calculations without any errors. Sometimes Chinook's handlers need to consult checkers experts to understand the finer points of Chinook's game, as in situations in which Chinook claims it's winning and its handlers don't see why.

It's also not true that a computer can't be creative, at least in the sense of producing results unanticipated by the programmer. Schaeffer writes: "Chinook has consistently shown that on its own, it finds interesting opening innovations, and we do not want to stifle its creativity. However, some opening positions are known by humans to be losing, and Chinook cannot detect these positions under game constraints. To solve this problem, we maintain an anti-book, a library of moves not to make. The anti-book allows Chinook to play its own openings and avoid the positions that are known to be lost." Far from being too straight-laced, early versions of Chinook needed to have their creativity reined in.

Between the Nationals and the World Championship, Chinook played 14 games against Tinsley in an exhibition match in Edmonton. Tinsley won once; all the other games were draws. The lost game was game 10, and move 10 was the critical move on which Tinsley's victory hinged. When Chinook made the move, Tinsley instantly said aloud, in a manner that brings to mind the brash youth of 1946, "You'll regret that." Even now, Schaeffer marvels at that prescient comment. It wasn't until much later -- move 35, in fact -- that Chinook realized that it was in trouble. Clearly, Tinsley knew some things about the game that were well beyond Chinook's sphere of vision.

After the match, Tinsley expressed his thanks to Schaeffer. Most human players, complained Tinsley, played unadventurous games against him; knowing that they were unlikely to beat him, they played conservatively, in order to get a draw. Chinook, however, was not intimidated by Tinsley's reputation; like Tinsley, it played to win, in each and every game. Tinsley said that boldness of the computer made him feel young again.

In 1991, the American Checkers Federation and the English Draughts Association decided not to sanction a Chinook-Tinsley match, on the grounds that computers should not be eligible for the position of world champion checkers player. They decreed that Tinsley would defend his title against the reigning English champion, Derek Oldbury. Tinsley, however, wanted to play Chinook. He could not convince the ACF and the EDA to accept Chinook as the challenger in a match for the world title, and he knew he didn't have the stamina to play both Oldbury and Chinook, and so he stunned the checkers world by resigning as world champion, relinquishing the title to Oldbury. The two organizations tried to convince Tinsley to change his mind, but he stood firm. In August, they awarded him the title of "world champion emeritus," in recognition of his long-standing stature in the checkers world.

No one doubts that Tinsley is still the best player alive. Thus, any match between him and Chinook would be de facto, if not officially, a world championship. In grudging recognition of this, the ACF eventually decided to sanction the match as the First Man versus Machine World Checkers/Draughts Championship.

The Championship was arranged take place in August of 1992 at the Park Lane Hotel in London -- the very same location as the 1986 Kasparov-Karpov World Chess Championship. The players even used the same table. At stake was $10,000, to be split 60-40 (or 50-50, in the event of a tie).

To prepare for the competition, Schaeffer studied published analyses of Tinsley's games, to better exploit weaknesses. Since Tinsley is the best player in the world, and Schaeffer himself is a mediocre player, Chinook itself played a key role in the search for weaknesses in Tinsley's play. Schaeffer also arranged to run Chinook on a new Silicon Graphics multi-processor computer. Tinsley welcomed the prospect of an even worthier adversary than the one he'd played the year before, but he seemed to be confident about the outcome of the match. He had nothing but respect for Schaeffer's skills as a programmer, yet he still felt that he had the upper hand: "Chinook is programmed by Jonathan, but I'm programmed by God."

The first four games led to draws. However, game 1 proved instructive, inasmuch as it emphasized the extremely high level at which Chinook and Tinsley were playing. This was a boring game from the point of view of Chinook and of its human handlers/confidants; the numerical scores of the positions stayed close to zero throughout, right up to the moment when Tinsley agreed to a draw. "However," writes Schaeffer, "some members of the audience thought we had been in serious trouble. Many times in the match, it was obvious that the audience (which included some well-known strong players) did not understand what was transpiring on the board."

The first non-drawn game in the match was Tinsley's win in game 5. Chinook had trusted a published prescription for opening play, which (subsequent to the match) was admitted by its author to be erroneous. Tinsley made the most of this mistake, and pulled into the lead, 1-0.

Chinook's first victory over Tinsley came in game 8. Although he felt upset that his loss had been a "fluke" caused by "enormous fatigue," Tinsley's sense of sportsmanship dictated that he should congratulate the Chinook team, and he did so. Schaeffer and the rest of Chinook team went to dinner after the game to celebrate their victory. This was a moment that the team had been looking forward to for years. Yet, to their surprise, the dinner was "more like a funeral; no one was happy. I'd expected to be jumping up and partying," said Schaeffer. He writes: "How can I explain the sadness that I felt? Perhaps we were sad for Marion. Not only did we all have a lot of respect for him, but we liked him as a person. Perhaps we were sad because this game marked a changing of the guard. After all, we were still members of the human race, and Chinook defeating Tinsley in a single game meant that it may only be a matter of time before computers would be supreme in checkers. I still don't know the answer."

The next decisive game was game 14. Once again, Chinook won, this time pulling into the lead. Once again, Tinsley was frustrated; with its phenomenal memory, Chinook "beat me on my own published play when I'd forgotten it." Schaeffer and team-mate Paul Lu went out for dinner, and this time, they "really celebrated: the sadness of game 8 had been replaced by euphoria." Game 14, like game 4, pointed up the advanced level of the two combatants: after Tinsley resigned, the spectators raced up on stage and congratulated him on obtaining a draw in a difficult game. They didn't see the trap that Chinook had lured him into; only Tinsley and the Chinook team understood what had just happened, so that the spectators, misinterpreting the handshake of Tinsley's resignation, thought they had just seen Tinsley accept an offered draw. It seems that the only players who are qualified to be ringside commentators on a match between players of Tinsley and Chinook's caliber are Tinsley and Chinook themselves.

Disaster struck in game 18: the computer simply froze up at one point, and refused to respond to the operator's attempts to communicate with it. Schaeffer had to forfeit the game on Chinook's behalf, bringing the match to an even 2 wins apiece. Tinsley has suggested that the glitch in game 18 may have been an act of God. "They've never explained it, you know," he told me with a smile.

Game 18 turned out to be the turning point of the match. Tinsley went on to win both games 25 and 39, making him the winner of the match, 4 games to 2. The London match was very draining for Tinsley, but it was also one of the most exciting checkers matches ever played. When Jonathan Schaeffer put out his hand to Tinsley on behalf of Chinook, to resign the last game, Dr. Tinsley stood up, raised a fist in the air, and shouted, over the thundering applause of the audience, "Three cheers for the human race! -- and that includes Jonathan!"

Schaeffer, describing the games played in London, says "What's amazing about these games is that if you didn't know who was playing, you'd say Tinsley was the computer and the computer was the human." Other checker players concur in this opinion. Chinook and Tinsley play superficially similar games, in that neither one tries to bluff; both attempt to make the best move possible, nothing more nor less. However, continues Schaeffer, "Marion played checkers with a perfect logic and an infallible memory, rarely making mistakes. Chinook played like a young arrogant master who was still maturing, occasionally making the type of mistake that Marion might have made when he was a youth. I would argue that Marion was more a machine that Chinook, and and Chinook was playing more human-like than Marion!"

Fortunately, Schaeffer was on friendly terms with Martin Bryant, the creator of Colossus, the second best checker-playing program in the world. Chinook's strength was its endgame data-base, while Colossus' strength was its opening book. Schaeffer suggested to Bryant that they swap: Chinook would get the openings book, while Colossus would get the 6-piece data-base, containing the definitive analysis of each checkers position involving 6 or fewer pieces. Thus, the Chinook and Colossus that emerged from this exchange were not the same as the earlier versions of the programs that bore the same names; metaphorically, it would be more accurate to view the new hybridized programs as the progeny of a strategic union of two royal families.

Schaeffer also got Silicon Graphics to agree to lend him one of their Challenge supercomputers for the new match. This half-million-dollar machine is one of the most powerful computers of its kind. Schaeffer has likened Chinook to an expert race car driver, whose performance depends on the kind of car he is driving. In the Challenge, Schaeffer had found a first-class vehicle for his driver. With its sixteen CPU's, each of which can perform 150 million instructions per second, Chinook would be able to consider, in a single minute, 12 million possible directions in which the game might evolve. With its gigabyte of built-in memory and 10 gigabytes of disk space, Chinook would have access to pre-computed information about the hundreds of billions of positions that it had studied over the preceding years.

Schaeffer spent the six months preceding the match in Maastricht. working full-time on Chinook, away from all distractions (including his wife and daughter). His collaborators were scattered over Europe and North America: while Jonathan was in the Netherlands, his research associate Robert Lake was in Edmonton, his former masters' student Paul Lu was pursuing his doctorate in Toronto, and Martin was in England.

Meanwhile, machines in Edmonton, California, and Switzerland were helping Chinook by augmenting its endgame data-base, using massive search of the sub-trees associated with different endgame positions. Hundreds of computers throughout the world were recruited for the task of helping the team during the weeks preceding the match. Schaeffer's budget was limited, so he begged and borrowed unused CPU time wherever he could.

The version of Chinook that resulted from all this work is a far better checkers player than the one that came before. In every dimension, the program is vastly superior to what it had been in 1992. Where before its basic depth of look-ahead was 17 moves (21 in the end-game), now it's 19 (23 in the end-game). Its opening book is 12 times larger than in 1992. The 1992 endgame data-base contained a mere 40 billion positions. Now it contains 250 billion positions (5.6 gigabytes of data).

The act of making changes in Chinook gave the program a subtle additional advantage. The old version of Chinook had only played a few hundred games in its career, as opposed to Tinsley, who had played over a thousand. This made it easier for Chinook to study Tinsley's game (and look for weaknesses) than it was for Tinsley to return the compliment. With the advent of the "new improved Chinook," even the few hundred games Chinook had played before lost their relevance. Benoit Marchand, one of Schaeffer's international network of CPU-time providers, said, "If Tinsley studied games by Chinook from a year ago, he wouldn't learn anything." All Tinsley might do to prepare himself for the Second Man versus Machine Checkers Match would be to study the eighty-odd games that the new Chinook would have played by mid-August. Or, if he wanted to get an appreciation of the capabilities of the supercomputer on which Chinook would be running, he could rent "Jurassic Park" or "Terminator" and look at the special effects, many of which were facilitated by computations made on the Challenge XL.

Schaeffer convinced Silicon Graphics to lend him an additional computer, the "Onyx." This machine is not as powerful as the Challenge, but in the event of difficulties with the Challenge, the Onyx would also be capable of running Chinook; the Chinook/Onyx combination plays a good game, although not as good as Chinook/Challenge. Another advantage of having a second computer was that the two together could separate the task of figuring out the right moves from the task of displaying the moves for the benefit of the audience; that way, a bug into the display-program, running on one computer, would not jeopardize the calculations taking place on the other.

Jonathan returned to Edmonton in the beginning of July, and the new version of Chinook began its checkers-playing career. Its first practice match was against Don Lafferty, the second-best human player in the world. Lafferty found the experience educational. In one game, he refused to accept Chinook's offer of a draw, even though Schaeffer assured him that Chinook's analysis guaranteed that he had no chance of a win. "Chinook is probably right, but I don't see it." So he played out the game, until he could see where the draw was. "That's beautiful," he said. "I learned something."

In early August, Chinook entered the Nationals, held in Dallas. Chinook was the only computer entrant, so the outcome of the Nationals would have no effect on Chinook's eligibility, as the premier computer player, to play against Tinsley later in the month in the Man versus Machine championship. Schaeffer was eager for a win in the latter match, so, with the instincts of a hustler, he disabled some of Chinook's new features for the Nationals, the better to keep Tinsley from knowing the new Chinook's full power until the one-on-one match itself began. Even with this handicap, Chinook played on Tinsley's level, and the four games that were played all ended in draws. The U.S. Open led to a 3-way tie between Tinsley, Chinook, and Lafferty. Tie-breaking technicalities were invoked, and the title of U.S. champion was awarded to Lafferty. However, Tinsley was still the emeritus world champion, and Chinook was still the best checkers program, so the Man versus Machine Championship could go ahead as scheduled.

On Tuesday the 9th of August, Jon Schaeffer and Paul Lu arrived in Boston. Rob Lake and Martin Bryant didn't show up until Saturday the 13th; Rob had stopped for a week in New York en route from the U.S. Nationals. Benoit Marchand from Switzerland and Joe Gilberto from Silicon Graphics were also in Boston during the days preceding the match, and they worked hard to get the system configured for optimal performance.

An unexpected complication arose on Saturday the 13th, two days before the start of the match: the room in which the match was to be held had been rented for a wedding for Saturday, so that the Chinook team would be unable to get any work done that day. The bride was not pleased with the schedule conflict either, since the computer, which had already been installed, had to be left in place during the ceremony and reception. Preparations resumed on Sunday morning, and continued until slightly past midnight; Schaeffer had to make an unforeseen expenditure of money to hire security guards to watch over the building after the museum closed for the day. There was a sense of urgency in the team's efforts to get the computer ready for the next day's games. At the same time, the sharing of a common goal made the event exhilarating, and the sharing of take-out Chinese food reinforced the evening's camaraderie. Finally, at around a quarter past midnight, the team felt Chinook was ready, and went home to get some sleep.

But even as they slept, Chinook's agents were helping it further increase its power. Out in California at Livermore National Laboratories, unused computers with nothing to do were running the Chinook program and thinking about checkers positions, most of which probably never had been played and never would be played, at least by human beings. An evangelist friend of Marion Tinsley's once told him that God, in a vision, had instructed him to deliver to Tinsley a message: "Tell My servant that I have moves he never dreamed of." Out in California, on the night of August 14th, computers were dreaming some of these moves. In the morning, half a billion more endgame positions were computed. This information was sent over the phone-lines to Chinook in Boston, and was added to the program's data-base.

At the front of the room is a 47-inch Sony screen, with a rendering of a three-dimensional checkerboard and two colors of checkers. Above the checkerboard on the screen is a realistic presentation of a floating hand, which moves the pieces of both colors. The hand has a wedding ring on its fourth finger; it is actually a digitized version of the hand of the person who wrote the display software for Silicon Graphics' "Reality Centre." At the bottom of the screen, at the lower left, one sees the label "The Reality Centre" along with its somewhat menacing emblem, a rearing shark.

Schaeffer sits upright; Tinsley leans back thoughtfully. Tinsley makes a move, and punches the time clock. (Clocks are not ordinarily used in checkers matches, but this is no ordinary match.) Schaeffer enters the move into the computer, using a small monitor that is tilted away from Tinsley. Time passes. The computer reports its recommendation. Schaeffer makes the move, and punches the time clock. Tinsley thinks. Tinsley makes a move. Tinsley punches the time clock. And so on. Every now and then, something more interesting happens, to enliven the proceedings: for instance, Schaeffer might pour water for himself and Tinsley. Meanwhile, the cooling apparatus in the Challenge makes a loud tuneless humming sound that submerges the audience in a cloud of white noise. One participant likens the process of watching the game proceed to watching paint dry.

But what would one expect? The real action is happening on a microscopic level, in the synapses of Tinsley's brain and in the etched circuitry of the Challenge. No doubt there is a frenzy of activity on that level. We can't see into Tinsley's brain, but the liquid crystal display on the front of the Challenge gives us an intriguing window into Chinook's style of thought. The display shows, bar-graph style, how hard each of the unit's sixteen brains is working at any given moment. Sometimes all of the CPU's are working hard; at others times, just a handful. At first it looks random, but then one realizes that there's a curious rhythm to it. Watching the computer think is fairly relaxing; it's the visual equivalent of the musical bells in Cambridge's Kendall Square subway station near MIT. The sixteen CPU's share the work of analyzing checkers positions by looking at different subtrees of the game tree. Sometimes a position admits only a few legal moves; in those cases, only a couple of the CPU's will be recruited to analyze the consequences of those respective moves. In some subtle way, the patterns on the display reflect the way in which Chinook is repeatedly taking problems that it wants to solve and breaking them down into smaller chunks, which it divides up among its several brains.

Chinook plays an aggressive game. After 23 moves, Schaeffer leaves the table and goes over to confer with his teammates. Chinook is, in its own opinion, ahead by 20 points -- not enough to give it a chance of beating Tinsley (unless the man slips), but enough so that it's unlikely that Tinsley will win either. They discuss the prospect of offering or accepting a draw within the next few moves. Schaeffer, starting to return to the board, tells the others "If you ever think we should offer a draw let me know." Meaning: If it ever looks like the only way we can win is by playing for so long that Tinsley becomes tired and makes a mistake, let's offer him a draw. After all, he is only human. We do not want to win by exhaustion.

More time passes; it's 1:30 PM. Schaeffer and Tinsley both start to get hungry. There was a buffet at 10:00 before the opening ceremony, but neither man had any of it, and the food is long gone now. Schaeffer investigates the possibility of lunch and reports to Tinsley. A member of the Chinook team gets Tinsley a hamburger.

Checkers continue to disappear from the board. At 2:15, Schaeffer says "I think the advantage is illusory." The score has been stable at 18 for several moves. Shortly thereafter: "6 on 6; we're up 22 points."

Finally, on the 30th move the Chinook team accepts Tinsley's offer of a draw, after having turned down the offer several times. Schaeffer and Tinsley shake hands. There is polite applause. It is the end of the first game. There are to be 29 more, in what promises to be a long and difficult match for both players.

Tuesday, the second day of play, saw some technical difficulties with Chinook, but nothing that proved as fatal as in game 18 in 1992. All four games played that day, like the two played the day before, were draws. Schaeffer was nonetheless optimistic. He felt that Tinsley had come close to losing game 2, while Chinook had never been in serious trouble in any of the games played so far. Indeed, in the first two days of play, Chinook never felt Tinsley had a better position than it had.

Tinsley agreed that, for the first six games, the machine's play had been flawless. He began to muse about what it would take to actually win a game off of Chinook. "I have about 10-12 moves to get the computer into trouble," he said; after that, the computer's in-depth searches would lead it into its pre-computed endgame data-base, where Tinsley's own intellect, for all its penetration, could not follow.

Tinsley seemed to be in good spirits, but he had been listless during the games; in particular, he had often forgotten to punch the clock after making a move, with the result that Chinook got to think about its moves on Tinsley's time. This might not require any deep explanations; after all, Tinsley was not used to playing with a tournament clock. But one had to wonder if this was sufficient explanation. Was Tinsley so confident of his ability to think quickly that he didn't care about the clock? Or was something bothering and distracting him?

The next day, these questions were given a horrible answer.

Tinsley's first words on Wednesday morning, after he sat down at the board, were, "I'd like to suggest the unthinkable: let Lafferty finish the match for me." He had had abdominal pains on Tuesday night, and he was afraid that there might be something wrong with him.

The organizers decided to make Wednesday the free day, rather than Thursday as originally scheduled, and Tinsley was sent to a nearby hospital for tests.

He seemed to feel better in the evening, but the next morning he said that he'd been in pain all night and had gotten very little sleep; he was in no condition to play. He resigned the match that morning, without even waiting for the test results to come in. He went back to the hospital, and while he was there the test results came back. The news was bad: Tinsley had a lump around his pancreas. It might be cancer.

Schaeffer was stunned. As a friend of Tinsley's, he was of course concerned for the man's health. And, as a competitor, he was stricken by the sense of an opportunity that had been within his reach and then vanished. "My worst nightmare was that Tinsley would die before we could play him; or, that he'd beat us and then retire from the game. But this is even worse. To come so close..."

When a component malfunctions on a parallel computer, you can yank the part and replace it by another, or transfer the program to a backup machine. Unfortunately, when it comes to human beings, replacing defective parts like pancreases isn't so easy; and known methods for transferring knowledge from one brain to another are arduous and unreliable. Tinsley's internal checkers program is uniquely located in the skull of the person called Marion Tinsley. However, to the extent that anyone on earth has managed to get a copy of Tinsley's program, that person would be Don Lafferty, Tinsley's long-time friend and protegé, and the only human player (other than Tinsley) who has beaten Chinook more than once.

Don Lafferty lives in Kentucky. He used to teach mathematics and physics at the high school level, but he has now retired. Unlike Tinsley, who never married, Lafferty has married three times, and has three daughters, none of whom shares his passion for checkers but two of whom share his passion for pool. He is well over six feet tall, with muscular arms and an incongruous paunch; his hair is gray, and he has a small gray mustache.

Lafferty first met Tinsley in 1955; they've been good friends since the mid-60's. In their debates over the strength of positions and the utility of moves, they have a habitual repartee, with stock lines like "You're right and I'm wrong, like you usually are." They have played hundreds of private, undocumented games together, both at Lafferty's home and at Tinsley's; Lafferty is Tinsley's only real disciple. Lafferty, though, seems to feel that he's not much of a disciple. Of Tinsley he says, "He's tried to help me. I'm not sure how much I've absorbed." And: "If I could remember 10% of what Tinsley taught me, I'd be a better player." Lafferty has never beaten Tinsley in match play.

But what of their hundreds of private little games? Surely Tinsley can't have won or drawn all of those too! Indeed, Lafferty did manage to beat Tinsley in a game. Once. "And it was late at night; Marion was tired," says Lafferty, apologetically.

Lafferty may not be at Tinsley's level, but he's definitely the second best human player in the world. Although he lost to Chinook in 1990 and 1992, and only managed to beat out Chinook in 1994 on the basis of tie-breaking technicalities (which also placed him ahead of Tinsley), he beat Chinook in tournament play in both 1991 and 1993. Lafferty has a good track record against Chinook: in the 72 games that the two have played, Lafferty has had 7 wins, while Chinook has had only 5. But most of these wins were against the old Chinook. How would he fare against the new?

The Chinook team was guardedly optimistic about the match. After all, Lafferty typically lost 3-4 games a year; the new Chinook was playing with a winning streak of well over 100 games. ("We don't make many mistakes," says Paul.) However, 20 games is awfully short for a tournament, and Jonathan was afraid that Chinook's advantage over Lafferty was sufficiently slight that it might not show up in a match that short.

In particular, Schaeffer was concerned that the match would have too many drawn games. To prevent this, he suggested to Lafferty that they play 10 different openings (20 games) with 3 chosen by Chinook, 3 chosen by Lafferty, and 4 chosen by random draw. Lafferty wisely refused. He suspected that Chinook had prepared some traps, or "cooks," along certain lines of play, and that Schaeffer was hoping to trick him with some of Chinook's pre-computed innovations. As a compromise, Schaeffer said "Let's use the tough deck." That is, he wanted to remove from the deck all the opening positions that preserved the balance of power between the two sides, and play only those games in which one of the players starts out with a significant material advantage and a sizeable chance of getting an actual win. Again, Lafferty said no, and Schaeffer backed off: random selection from a full deck of 144 openings would be used throughout. The organizers of the match gave final approval for the substitution on Thursday night: Lafferty would play Chinook in a 20-game match in a contest over a $10,000 pot, to be split 60-40 (or 50-50 in the event of a tie).

Lafferty would come to this new contest with an advantage that Tinsley had not possessed, because Lafferty had had a chance to play 18 games against the new Chinook the month before, and had undoubtedly learned much about Chinook from playing these games. (If Schaeffer had known that there was a chance that Chinook and Lafferty would be pitted against each other that same summer in tournament play, he would never have given the great checkers-player the advantage of seeing the new Chinook in action.) Furthermore, Chinook had not analyzed its past games with Lafferty in the way that it had pored over its older self's games with Tinsley; nor, to Schaeffer's great frustration, had he brought with him any computer-readable records of the games that Chinook and Lafferty had played, so he had no way of studying those games and giving Chinook a chance to analyze Lafferty's style of play to look for hidden weaknesses.

On the other hand, Lafferty had not expected to play a tournament at all, and would have to rev up his intellectual engines awfully fast.

The organizers would have liked to see Lafferty fly in on Thursday night and begin playing on Friday, but he had already made plans and appointments for Friday that he was unwilling or unable to change. Instead, he left for Boston early Saturday morning. He was exhausted when he arrived, but he had agreed to play two games on Saturday afternoon, and so he did. Despite his fatigue, Lafferty managed to draw both games.

Gone now was the four-foot display screen that had been rented for the start of the match with Tinsley. Gone, too, was the excitement. Martin Bryant explained, "We're going through the motions, but our heart's not in it. We didn't come here to win the title; we came here to play Tinsley." Chinook's performance against Tinsley was the data point that they, as scientists, had wanted to obtain; Tinsley's game had been the Everest that they, as explorers, had wanted to scale.

When Lafferty came back to the match on Monday morning, he still looked tired, but not as much as he had on Saturday. His style of play was careful and conservative; unlike Tinsley, who had tried to beat Chinook in every game, Lafferty seemed content to aim for draws. By the end of Monday, the match with Lafferty stood exactly where the match with Tinsley had left off: six games, all drawn.

Monday's events weren't quite as undramatic as the score made it sound, at least as far as the Chinook team was concerned; in game 6, hardware problems developed with the Challenge, and most of that game was played on the Onyx. Fortunately, Chinook was still able to hold its own. But more hardware troubles, and more serious repercussions, awaited the Chinook team. The trouble began again in the second game played on Tuesday, when once again the Challenge began to have problems and once again the Chinook team switched to the Onyx. Unfortunately, the game being played was not as safe as game 6 had been, and on the twelfth move of game 8, Chinook found itself in a difficult position. Unbeknownst at the time to Chinook and its programmers, that position is in the published checkers literature; with a more extensive openings book, Chinook would have been able to make the right move without thinking at all. Instead, Chinook did its limited look-ahead, its alpha-beta pruning. Unfortunately, the program was running on the Onyx, whose depth of look-ahead was less than that of the Challenge. Not seeing any long-term threat to its position, Chinook/Onyx chose to move so as to win some material from Lafferty. This decision turned out to be a mistake, as it soon gave Lafferty control over the center of the board. Lafferty exploited this mistake to the hilt, forcing Chinook to resign after 62 moves.

This was Chinook's first loss in 149 consecutive games. It was, in fact, the first time that the new, improved Chinook had ever lost a game.

Schaeffer, speaking to a reporter from the Boston Globe, said "We felt like a boa constrictor was attacking us, and we slowly realized we had lost." Don Lafferty was calm in his appraisal. "Chinook doesn't weigh things properly in this sort of situation. I've won three games against Chinook this way." That is, Chinook could see the immediate advantage of capturing its opponent's checkers, but issues of control of the board were subtler and not altogether within its range of understanding.

Chinook's revenge was not long in coming. The hardware problems with the Challenge were fixed after game 9 ended in a draw, and during game 10 (the last game of the day), Chinook/Challenge was able to make use a pre-computed "cook" -- one of the little surprises the Chinook team had prepared for Tinsley. Lafferty played correctly for a while, but at one point he made the wrong move. Three moves after his mistake, he gave a visible start as the realization of what he had done hit him. At this point, Chinook knew Lafferty had no chance of winning or even drawing, but Lafferty didn't know this, at least not for certain; he began to take a very long time on his moves, hoping to find a way to extricate himself from his difficulties. Eventually, he lost the game not because he had no available moves or because he'd resigned, but because the amount of time he was spending thinking about his moves caused him to run out of time on the clock. Lafferty said he lost to Chinook because he was tired and overlooked something he should have seen, but he did not stint on praise of the program: "Chinook played a great game." The match now stood even at one game apiece.

If the organizers had hopes that the excitement of Monday was an indication of more excitement to come, they were disappointed; all four of Tuesday's games were quick draws, The NBC reporter who came to the match on Wednesday told Lafferty "Come on, put up your dukes; we want to see some blood." But Lafferty was not to be swayed from his plan of caution. He stuck to safe, published lines of play, even when a departure into less familiar territory might have given him a chance at a win. In game 14, as he saw yet another draw with Lafferty inexorably taking shape, Schaeffer considered the possibility of doing some impromptu "brain surgery" on Chinook, to make it into a bolder player, so that it would make some moves whose unorthodoxy would throw Lafferty off course. He conferred privately with the rest of the team about how he might do this. Unfortunately, it turned out to be a tricky business, and not just a 5-minute fix, as he'd originally hoped. He ended up not making any changes in Chinook, for that game or for later games. Win, lose, or (most likely) draw, Chinook would be allowed to go on doing exactly what it had been doing so far.

Games 15, 16, 17, and 18 were draws, just like the four preceding games. Lafferty looked tired after the day's games, but it seemed clear that he had the energy to play the same sort of cautious game for one more day and tie up the match.

The next morning, when the players showed up, there was one small surprise for them: one of the checkers was missing from the board. The cleaning staff looked everywhere around the stage, but could not find the missing piece. Eventually, Don Lafferty brought up an extra set of his own, which he and Schaeffer would use to continue the match.

All Schaeffer's hopes were now pinned on the choice of the opening moves of games 19 and 20. With a well-balanced opening that favored neither side, it seemed likely that Lafferty would be able to draw both games. However, if the opening was sufficiently lopsided, then Lafferty's abilities to find draws would be severely tested and might be found wanting. In that case, Chinook might be able to win one game and draw the other, winning the match.

Alas, the opening that was picked for games 19 and 20, drawn by Raymond Keene and Tony Buzan, was one of the better-balanced openings, so there was little Schaeffer could do. Game 19 ended in a draw.

Game 20 seemed to offer more hope: Chinook took a gamble and made a move that the checkers books call "inferior" but which Chinook had analyzed and thought was actually good. Chinook gave up a checker. Lafferty had the chance of giving up a checker, too, returning the game to published lines of play, or holding onto his material advantage and faring forth into the unknown. Lafferty thought for 20 minutes before making his move. He returned the checker. From that point, the outcome of the game was not in serious question: an easy draw for both of these expert players.

By tying the match, Chinook was able to hold onto the title that it had won when Tinsley resigned from the match; it was now the "Man vs. Machine Champion of the World." It was the first time a computer had won a world championship. But the way in which this title had been won left a bitter taste in Schaeffer's mouth, and when the two players finished game 20 and agreed to a draw, Jonathan was too disappointed to remember to shake Don's hand.

The closing ceremony was short. Lafferty said very few words. For his part, Schaeffer talked about how useful it had been to be able to run Chinook on as powerful a machine as the Challenge: "We love the hardware; we'd love to keep it." But there was little chance of that. Computers like the Challenge cost a large sum of money, and money is something Dr. Schaeffer has to go to a lot of trouble to get a hold of. After all, who cares about a sport like checkers?

Don Lafferty plans to get some rest. Then, he'll probably get back to work on a building that he's got under construction on a property that he's building. Derek Oldbury, the former world champion, died in July of 1994; Lafferty will undoubtedly win the title if he tries for it. Tinsley is hoping that he will.

Tinsley himself is to return to Georgia on August 25th, and begin radiation treatment for the lump, which has been diagnosed as a treatable pancreatic cancer. He'll get a small amount of money for his participation in the match -- but Tinsley didn't take on Chinook because of the money involved. Before his illness was diagnosed, he had said that he planned to spend less time on checkers after the match and to return to his early researches in combinatorial theory. Assuming he prevails against his cancer, he will probably continue to play checkers, if only for his own pleasure; his role model, after all, is Asa Long, "the iron man with the iron lines," who is in his nineties now and still playing. Still, Tinsley is mortal, and will die someday -- and when he does, a huge mass of uncommunicated understanding about the game of checkers will disappear with him. It is unlikely that any player of his stature will arise any time soon. Indeed, it is possible that the success of Chinook (and other programs like Chinook, yet to be written) will have an inhibiting effect on future generations of potential checkers players, and discourage people from developing the kind of expertise that Tinsley developed over the course of his career. If that is the case, then Tinsley will turn out to be not only the greatest player of our time, or the greatest human player up until our time, but the greatest human player of all time, both into the past and into the future.

The share of the prize money that goes to the Chinook team will partly go towards covering Schaeffer's teammates' living expenses. The tournament organizers weren't covering anyone's expenses other than his, so he had to pay for their food and lodgings out of grant money. All funds spent on living expenses was money that couldn't be spent on Chinook, so some of the team members tried to save the project money by staying with friends in the Boston area.

Schaeffer thinks it's inevitable that Chinook will become stronger than Tinsley, if work on Chinook continues. But if Tinsley dies, or retires from the game, the whole point of the project will disappear. Even if Chinook manages to beat Lafferty in tournament play a year or two hence, there will always be the nagging question: yes, but is Chinook now good enough that it could have beaten Tinsley? If Schaeffer's fears come true, this question will remain forever unanswered. As Schaeffer had said at the start of the match: "Win or lose, this may be the end of the project."

Still, even if the motive behind the project may disappear, projects like Schaeffer's don't stop on a dime, as long as there are dimes left in the project's piggy-bank. During the coming year, work will continue, and the endgame data-base will grow in size to 450 billion positions. Then, however, they'll be out of disk space, and without new money, there'll be no chance of getting more room for Chinook's mind to expand in.

Even if Chinook's career as a tournament player turns out to be over, the program may have an interesting second career, adjudicating positions in tournament play. In fact, Chinook has already served in this capacity at the U.S. Nationals; two players who suspected that the current position was a draw agreed to consult Chinook to find out its verdict. Perhaps this once-fiery contender will retire from playing the game competitively and lead a more sober existence as a judge.

Silicon Graphics Incorporated will continue to build faster machines. Will it bankroll more work on Chinook, and more Man vs. Machine matches? SGI is a commercial enterprise, so the answer to that question is in part going to be decided in the marketplace. The pioneering supercomputer company Thinking Machines coincidentally filed for bankruptcy on the first day of the match against Tinsley; no company can afford to rest on its laurels. Silicon Graphics may at some point decide that it can't afford to fund checkers matches.

I asked Jonathan if he thought he might switch over to the game of International Checkers, played on a 10-by-10 board. This game is widely played outside the U.S.A., and for higher stakes than our brand of checkers; for instance, the world championship was recently played for an amount equivalent to $50,000. Jonathan shook his head. A program to play International Checkers at a world championship level would have to be an order of magnitude more powerful than Chinook. He doesn't have it in him to do the work that would be required. "I've just spent the last six months away from family to work on Chinook. I have a wife and a two-year-old daughter. I don't know if you know what two-year-old daughters are like. But I wouldn't do that again, for any reason."

Paul Lu will return to Toronto. Paul will get serious about his dissertation, which deals with parallel computation, but not with checkers.

Martin Bryant will go back to England, where he works as a programmer. The new Colossus runs on a PC, and is available commercially. Martin will probably keep on tinkering with his program; a new version will be launched in the first few weeks after his return home. Meanwhile, will Jonathan try to go commercial with Chinook, as Martin did with Colossus? Probably not. Schaeffer isn't willing to spend the time it takes to make Chinook easier to use. Even Martin has had trouble at times mastering Chinook's little quirks; for instance, he had some difficulty with Chinook on Wednesday night. "Bloody hell, Jonathan," he exclaimed good-naturedly on Thursday, after the end of the match, "can't you make the thing a bit friendlier?"

Robert Lake wasn't as visibly disappointed by the outcome of the match as the other members of the team. For him, August 25 was a memorable day for totally different reasons: Chinook's endgame data-base finally reached the size of 250 billion positions. Robert will take a 3-day break from Chinook until Sunday night, when he returns to Alberta. On Monday morning, he'll be back at work, augmenting the data-base.

And Jonathan? I remember the end of game 18, when Jonathan's wife Stephanie and their daughter Rebecca were on hand. I had a chance to talk with Stephanie briefly about their home life. She and Jonathan have, in addition to Rebecca, two dogs, two cats, one horse, and one Chinook. She described Chinook as the least affectionate member of the household.

Looking forward to the prospect of life without Chinook, Jonathan told Stephanie, "You'll have a husband again." Stephanie was eagerly awaiting his return to family life, but had wished the results of the match to be more definitive. "I was hoping he'd win so he could get it out of his system and go on to other things," she told me.

Meanwhile, Rebecca went exploring the room, and climbed up onto the stage, near the monitor that allowed her father to contact Chinook. At the end of year, Chinook will have one third of a trillion positions in its data-base (it now has only one fourth of a trillion). Meanwhile, Rebecca will continue to use a new word every day, and will learn many more than she uses. She already knows the words "checkers" and "data-base," and has learned to frown when the latter word is said.

Rebecca wanted to take one of the checkers from the hall with her. Her mother pulled it out of her clenched fist and put it back on the table. Then she counted, to make sure they were all present. Yes. Twenty-four checkers, none missing, all accounted for.

Jonathan led his daughter away from the stage. Halfway towards the exit, he picked her up by the waist and swung her towards the high ceiling, with her blonde strands of hair dangling downward, ending in ringlets that echo her father's darker, tighter curls. "You monkey you!" he said.

Postscript

That same month, Ron King (who is now the human champion at checkers) challenged Chinook for the man-machine championship, and Schaeffer agreed. Unfortunately, the money needed to fund the match has not been forthcoming, and there are currently no plans to hold the match.

Chinook is now in retirement from professional checkers, though it does still play a devastating amateur game (no longer on an SGI Challenge, though!).

Acknowledgements

Readers interested in getting more (and more reliable) information about Chinook should not miss Jonathan Schaeffer's engaging account One Jump Ahead: Challenging Human Supremacy in Checkers, published by Springer-Verlag in 1997.

This article is copyrighted by James Propp, 1997. Readers are free to transmit this article but not to modify it in any way without the author's express permission.

James Propp was an Associate Professor of Mathematics at the Massachusetts Institute of Technology. When this article was published on ACJ Extra in 1997, he was writing a book on Fermat's Last Theorem for the general reading public. You may visit and challenge Chinook via the web.

This page last modified on 28 April 2018.
Copyright (c) 1995-2018 Christopher F. Chabris. All rights reserved.