Monday, 24 September 2012

The Worst (Research) Day of My Life (Part 3)

In previous posts, I described the agony of August 22 in 1992 and 1994. But August 22 was not quite finished with me. In 1995 I started writing a book on the Chinook story (eventually published as One Jump Ahead in 1997, the predecessor to the 2009 edition). I signed a publishing contract and then...

… work began in earnest on the book. I had lots that I wanted to say, and the words seemed to effortlessly flow from my mind to the printed page. But there was one chapter (or more precisely, part of a chapter) that I kept avoiding, one story that I just couldn’t find the inner strength to write. Every time I tried to compose the words, I felt a deep sense of unease and would put it off to another day. Eventually another day came. It was the last chapter; I had to write it.

[August 22, 1992.] Game 18 of the 1992 Tinsley match. Infamous game 18. Forfeit.

I can vividly remember every detail of the closing moments of that game. I remember the stage, the board, Tinsley, the audience. I remember daydreaming about a possible win—going up three wins to one in the match—and then the abrupt reality check as Chinook revised its assessment downward to a draw. I remember being angry with my disappointment at the likely draw outcome. I remember the surge of adrenalin that I felt when it dawned on me that there might be a problem with Chinook. I remember the horror as I helplessly watched my much-loved creation forfeit. But most of all I remember the whispers. I remember the murmur from the audience as spectators talked to each other in hushed tones. “Why isn’t the program moving?” Someone in the audience said exactly those words, just loud enough that I could hear them. Those words, barely rising above the din, became permanently etched in my mind.

I can recall the sound in the room slowly rising as more spectators started whispering, wondering what was going on. It was like an orchestra, which reached a crescendo the moment Chinook’s flag fell signaling a forfeit. During all of this I can still recall—no, feel—the sense of helplessness that overcame me as I sat on the stage with 200 pairs of eyes staring at me with confused and concerned expressions. I can recall so much of those final minutes. It’s all indelibly seared on my brain.

Then the nightmares started. The first one came two months after returning home from London. I would relive the final minutes of game 18 in all its excruciating detail. Most of all I remembered the whispers, the murmurs: “Why isn’t the program moving?” I would awake with a start, with my heart racing and my breathing rapid and shallow. I had great trouble falling back asleep. The nightmares happened several times a month. I don’t know what triggered them or why they were so intense. All I knew was that game 18 had a profound impact on my subconscious psyche.

When it came time to write One Jump Ahead, I found it difficult to turn my feelings about game 18 into words. Eventually, I had to do it. I sat down at my desk, took a few deep breaths and forced myself to confront my emotions. What seemed like a few minutes later, I paused to get a coffee. To my surprise I had somehow managed to write many pages of text. The floodgates had opened, and words just kept coming. I finished the first draft of the text that day, and it went through very little editing to reach its final published form (unlike most other chapters).

Since that day my nightmare hasn’t reappeared; I’m cured! Writing that fateful text turned out to be therapeutic for me. I wish I had known that when I started work on the book; game 18 would have been the first chapter I wrote, not the last.

The Worst (Research) Day of My Life (Part 2)

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...

Sunday, 9 September 2012

The Bittersweet Week

The start of the Fall academic term has always been a bittersweet experience for me. It is the end of what usually has been a glorious summer (especially the research and holiday components) and the start of conforming to a regular routine (teaching and administration). So, it is with a tinge of remorse and a pang of anticipation that I confront the first week of classes.

As a professor:
Bitter: The end of the so-called “four month summer”. (See my July 15 posting.)
Sweet: Seeing all the excited first-year students wandering the campus, full of pride at starting university.
Bitter: The loss of the freedom to come and go when I please. Typically my calendar would now start filling up with a host of teaching duties and administrative meetings.
Sweet: Teaching again. Although I love teaching, I always feel a bit nervous at the first class of the term. By the end of the class, I am always invigorated.
Bitter: The clogged roads that lead to/from the University in the morning/afternoon rush hours.
Sweet: Meeting new graduate students who, until now, have been a collection of online admission documentation.
Bitter: The long lineups for food in SUB during lunch hour.
Sweet: Talking to new students and realizing how talented they are. Was my generation as talented when we entered university?
Bitter: The annual NSERC research grant application cycle begins. The application itself is only a few pages, but it seems to consume an enormous amount of time getting it just right.
Sweet: Wait! I don’t have to apply to NSERC this year. Whew!

Bitter: The end of the summer festivals in Edmonton.
Sweet: Anticipation of the fall. I love a long autumn, especially when the leaves change color. I regret that in Edmonton the colorful leaves do not stay on the tree long enough.
Bitter: My weekend runs through the green spaces of Edmonton are numbered.
Sweet: Our dog finally stops shedding.
Bitter: My daughter, Rebecca, returns to her University studies at UBC.
Sweet: My daughter, Rebecca, returns to her University studies at UBC.

As the new Dean:
Bitter: My two months of reflection and information gathering on the Faculty of Science is over.
Sweet: Now it is time to start delivering.