In a previous
post (August 27), I
related the story of August 22, 1992, when the checkers program Chinook
forfeited a critical game in the World Checkers Championship. We went on to
lose that match by a narrow margin, but I will always be haunted by the “what
if” question.
In 1994,
Chinook met Tinsley again in a rematch for the World title. The venue was the
Computer Museum in Boston (since moved to Silicon Valley). After six drawn
games, Tinsley resigned the match and the title to Chinook. He was not feeling
well (he claimed it was a case of “Chinookitis”) and did not want to continue
playing. Yes, we were now the world champion, but we achieved this milestone in
the worst way possible. A match was hastily arranged with Don Lafferty, the
second strongest human player in the world. Don was open about his match
strategy: play cautiously and wait for the computer to make a mistake. His
strategy seemed to be working.
August 22 would prove to be a fateful day in 1994. The following
comes from my book One Jump Ahead
(Springer-Verlag, 2009).
Monday,
August 22, had four more games. Rob was operating Chinook in the first game while I was in
the next room being interviewed live by an Edmonton radio station. The
interview was nearing the end when the door burst open and Rob yelled, “The
Challenge has crashed!” [Chinook was running on an SGI Challenge computer.] The door slammed shut, and he was gone.
Yes,
thousands of people back home were treated to Rob’s background vocals. The
Challenge computer was dead and couldn’t be restarted. As in London we had a
backup machine available. The backup had fewer processors (four instead of
sixteen) and less memory (256 megabytes instead of 1,024). I quickly started Chinook running, set up the board position,
and computed our next move. Rob finished operating the game without further
incident. Paul and I tried to revive the Challenge. We sent out a call to Joe
Gilberto [the computer hardware expert], and he was on-site within the hour.
The spectators missed out on quite a spectacle. While Rob finished the game on
the backup computer, Joe performed surgery on the Challenge, removing its vital
organs one by one, trying to isolate the offending component. How many more
victims of Chinookitis would there be?
After an
extended pause to see whether the Challenge was usable again (it wasn’t) we
began game eight using the backup computer. Twenty minutes later Joe told me
he’d found the problem: one of the sixteen computers in the Challenge was
faulty. He replaced it and was able to start the computer successfully. I
restarted Chinook and fed
it the current game position. Over the next few moves I had this version of Chinook mirror what was happening on the
backup computer, convincing me that Joe had indeed found the problem and the
computer was one-hundred percent again.
Chinookitis struck one more time
that day. Don’s ninth move surprised us— it wasn’t in our book and involved Don
sacrificing a checker. Finally, we had an interesting game. Chinook did a deep search, grabbed the
checker, and returned a +25 score. These were the most dangerous types of
positions for Chinook: we had the checker, but Don had the positional
advantage. We got into trouble in this very type of position against Tinsley in
the [1994] U.S. championship, and we had lost or almost lost similar positions
against Tinsley at Tupelo in 1990 and Lafferty in the 1992 Southern States
event. I was scared.
On move 12
the advantage dropped to equality (-4), but this didn’t look right…. The slow,
steady slide to reality began. Move 14, -27. Move 17, -67. Move 19, -143. I resigned.
Don was the hero of the day. When I was interviewed by the Boston Globe, my
reaction to the game was, “We felt like a boa constrictor was attacking us, and
we slowly realized we had lost.”
Our
incredible streak had come to an end. When was our last loss? Game ten against
Martin Bryant’s Colossus program
over a year ago. Since then we hadn’t lost in the last forty-four games of the Colossus match, twelve games against [Grandmaster
Derek] Oldbury, forty-eight against commercial programs (practice matches in
Maastricht), eighteen in the first Lafferty match, thirty-two in the Southern
States championship, thirty-two in the U.S. championship, six in the Tinsley
match, and finally, the first seven games of the second Lafferty match. An astounding
total of 199 consecutive games—almost all against grandmaster opposition. Okay,
so maybe I should ignore the 1993 games and the practice games against other
computer programs. That still meant that the “new” Chinook had gone 107 games without a loss.
Is it really
necessary for me to describe how I felt as I watched my offspring thrash around
in its death agony? Things had gone from bad to worse to awful. By defeating
Lafferty in this match, there was the hope of salvaging something from the
Boston debacle. Now there was a real danger that we were going to lose the
match. I wanted to go home.
The media
trumpeted the resounding victory for man over machine. Oliver Strimpel,
executive director of the Computer Museum, summarized the satisfaction that
many felt about Lafferty’s victory: “[It] shows
that knowledge and experience still count for an awful lot against the brute
strength of a computer, which follows rules without imagination or intuition.”
After the
game, I took Steph and Rebecca to the adjoining McDonalds for a late lunch (for
the record, Rebecca chose the restaurant). It was the longest lunch I’d ever
experienced. I had nothing to say; I was alone in my depression. Steph wisely
kept quiet. Rob and Martin’s lunch was no better. Rob Lake writes:
“This was the
first morning I recall in Boston that we had poor weather. It was overcast and
pouring rain. During the drive into Boston, I recall thinking what a gloomy day
this was. It only added to the lackluster feeling all of us were experiencing
from Tinsley’s withdrawal the previous week.
“Anyway,
somehow in a sadistic way, it seemed appropriate that Chinook should lose that morning. After
all, what else could possibly go wrong for us in Boston? Here we are, fending
off the hounds on the Internet accusing us of poor sportsmanship for taking the
title from a sick old man, and with only twelve games remaining, now found
ourselves down one game and in danger of losing to Lafferty. Never mind the
title we have and that we were originally playing Tinsley for the World
Checkers Championship. We can’t even beat Lafferty. We’ll be making [artificial
intelligence] history, but not the way we intended...
“After the loss it was time to go
for lunch. It was still raining fairly hard. Martin and I decided to go for
lunch at the Dunkin’ Donuts down the street. I just wanted to get away from Don
for a bit—I was annoyed at him for the illegal-move incident the day before and
now we had just lost a game to him. With only six chances left on the strong
side, I felt it was extremely unlikely we would win a game from him. I thought
Dunkin’ Donuts would be a good place to go since it was hopefully far enough
away in this wet weather that Don wouldn’t come there. I couldn’t think of a more
depressing moment and I was wondering what could happen next to make things
worse. While I was occupied with my thoughts, I noticed the coincidence that
this loss occurred exactly two years to the day of our infamous game 18 forfeit
to Tinsley. If we ever have another match, we should set August 22 as a rest
day. I’m not superstitious, but why take chances?
“As I was
sitting with Martin having my sandwich, who should enter... Don Lafferty! He
walked up to Martin and myself and asked if he could join us. Of course we
couldn’t refuse, but the question I was just asking myself had been answered.
We ended up having lunch together and chatting for about 30 minutes. I don’t
remember anything about what we talked about as my mind was only half in the
conversation. I then excused myself under the pretext that I wanted to do some
database work. On my way back to the Computer Museum, I noticed the skies were
beginning to clear. Well, at least now things are looking less depressing...
Might as well see what happens with the games this afternoon.”
I will never again play a
competitive game of checkers on August 22.
There are two interesting
postscripts to this game. First, Don later revealed that the sacrifice was a
Tinsley line specially prepared for Boston. It turned out to be a known line
from the early 1900s, but I think he was counting on its surprise value (i.e.,
it wasn’t in [the book] Basic Checkers). Second, I found out why we lost this
game. In October, 1994, Warren Smith of NEC asked to use Chinook for a research project, and I
obliged by sending him the code. Two weeks later Warren reported that he
thought he had found a bug in the program. He was right. After round one of the
U.S. championship match with Tinsley [a few weeks before the World Championship
match], I “fixed” Chinook. Recall that I found two problems. The second one I
fixed correctly. The first, well, I goofed. I included code to test whether two
conditions were true. The code tested whether either one was true, not both. It
was as simple as an “or” condition that should have been an “and.” I spent a
lot of time testing Chinook in Maastricht. I get back to Canada and have to fix two bugs. What
do I do? Fix one and introduce another. And since things were so hectic then, I
didn’t adequately test my change. I paid dearly for my simple mistake.
And if this wasn't bad enough, August 22 wasn't quite finished
with me...
No comments:
Post a Comment