TITLE: SIGCSE Day 3: Jonathan Schaeffer and the Chinook Story
AUTHOR: Eugene Wallingford
DATE: March 12, 2007 12:34 PM
DESC: 
-----
BODY:
The last session at SIGCSE was the luncheon keynote address by
<A HREF="http://www.cs.ualberta.ca/~jonathan/">
   Jonathan Schaeffer</A>,
who is a computer scientist at the
<A HREF="http://www.cs.ualberta.ca/">
   University of Alberta</A>.
Schaeffer is best known as the creator of
<A HREF="http://www.cs.ualberta.ca/~chinook/">
   Chinook</A>,
a computer program that in the mid 1990s became the second best
checker player in the history of the universe and that, within
three to five months, will solve the game completely.  If you
visit Chinook's page, you can even play a game!

I'm not going to write the sort of entry that I wrote about
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-03.html#e2007-03-09T21_11_10.htm">
   Grady Booch</A>'s
talk or
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-03.html#e2007-03-09T16_02_48.htm">
   Jeannette Wing</A>'s
talk, because frankly I couldn't do it justice.  Schaeffer told
us the story of creating Chinook, from the time he decided to
make an assault on checkers, through Chinook's rise and
monumental battles with world champion Marion Tinsley, up to
today.  What you need to do is to go read
<A HREF="http://www.cs.ualberta.ca/~jonathan/OJA/oja.html">
   One Jump Ahead</A>,
Schaeffer's book that tells the story of Chinook up to 1997 in
much more detail.  Don't worry if you aren't a computer scientist;
the book is aimed at a non-technical audience, and in this I
think Schaeffer succeeds.  In his talk, he said that writing the
book was the hardest thing he has ever done -- harder than creating
Chinook itself! -- because of the burden of trying to make his story
interesting and understandable to the general reader.

If you are a CS professor of student, you'll still learn a lot
from the book.  Even though it is non-technical, Schaeffer does
a pretty good job introducing the technical challenges that faced
his team, from writing software to play the game in parallel
across as many processors as he could muster, to building
databases of the endgame positions so that the program could
play endings perfectly.  (A couple of these databases are large
by today's standards.  Just try to recall how large a billion
billion entry table must have seemed in 1994!)  He also helps to
us feel what he must have felt when non-intellectual problems
arose, such as a power failure in the lab that had been computing
a database for weeks, or mix-up at the hotel where Chinook was
playing its world championship match that resulted in oven-like
temperatures in the playing room.  This snafu may account for one
of Chinook's losses in that match.

As a computer scientist, what I found most compelling about the
talk was reading about the dreams, goals, and daily routine of
a regular computer scientist.  Schaeffer is clearly a bright and
talented guy, but he tells his story as one of an Everyman --
a guy with a big ego who obsessively pursued a research goal, whose
goal came to have as much of a human element as a technical one.
He has added to our body of knowledge, as well as our lore.  I
think that non-technical readers can appreciate the human intrigue
in the Chinook-versus-Tinsley story as well.  It's a thriller of
a sort, with no violence in its path.

I knew a bit about checkers before I read the book.  Back in
college, I was trying to get my roommate to join me in an
campus-wide chess tournament that would play out over several
weeks.  I was a chessplayer, but he was only casual, so he
decided one way to add a bit of spice was for both of us to
enter the checkers part of the same tournament.  Neither of us
know much about checkers other than how to move the pieces.
The dutiful students that we were, we went to Bracken Library
and checked out several books on checkers strategy and studied
them before the tournament.  That's where I learned that checkers
has a much narrower search space than chess, and that many of its
critical variations are incredibly narrow and also incredibly
deep.  This helped me to appreciate how Tinsley, the human
champion, once computed a variation over 40 moves long at the
table while playing Chinook.  (Schaeffer did a wonderful job
explaining the fear this struck in him and his team:  How can
we beat this guy?  He's more of a machine than our program!)

That said, knowing how to play checkers will help as you read the
book, but it's not essential.  If you do know, dig out a checkers
board and play along with some of the game scores as you read.
To me, that added to the fun.

Reading the book is worth the effort only to learn about Chinook's
nemesis, Marion Tinsley
(<A HREF="http://www.cs.ualberta.ca/~chinook/people/Tinsley.php">
    Chinook page</A>
|
<A HREF="http://en.wikipedia.org/wiki/Marion_Tinsley">
    wikipedia page</A>),
the 20th-century checkers player (and math Ph.D. from Ohio State)
who until the time of his death was the best checkers player in
the world, almost certainly the best checkers player in history,
and in many ways unparalleled by any competitor in any other game
or sport I know of.  Until his first match against Chinook, Tinsley
lost only 3 games in 42 years.  He retired through the 1960s because
he was so much better than his competition that competition was no
fun.  The appearance of Chinook on the scene, rather than bothering
or worrying him (as it did most in the checkers establishment, and
as the appearance of master-level chess programs did at first in
the chess world), <EM>reinvigorated</EM> Tinsley, as it now gave
him opponent that played at his level and, even better, had no
fear of him.  By Tinsley's standard, guys like Michael Jordan,
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2007-01.html#e2007-01-15T11_45_37.htm">
   Tiger Woods</A>,
and even
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2006-11.html#e2006-11-07T16_37_17.htm">
   Lance Armstrong</A>
are just part of the pack in their respective sports.  Armstrong's
prolonged dominance of the Tour de France is close, but Tinsley
won every match he played and nearly every game, not just in the
single premiere event each year.

The book is good, but the keynote talk was compelling in its own
way.  Schaeffer isn't the sort of electric speaker that holds his
audience by force of personality.  He really seemed like a regular
guy, but one telling the story of his own passions, in a way that
gripped even someone who knew the ending all the way to the end.
(His t-shirt with pivotal game positions on both front and back was
a nice bit of showmanship!)  And one story that I don't remember
from the book was even better in person:  He talked about how he
used lie in bed next to his wife and fantasize... about Marion
Tinsley, and beating him, and how hard that would be.  One night
his wife looked over and asked, "Are you thinking about him again?"

Seeing this talk reminded me of why I love AI and
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2005-06.html#e2005-06-06T17_04_28.htm">
   loved doing AI</A>,
and why I love being a computer scientist.  There is great passion
in being a scientist and programmer, tackling a seemingly
insurmountable problem and doggedly fighting it to the end, through
little triumphs and little setbacks along the way.  Two thumbs up
to the SIGCSE committee for its choice.  This was a great way to
end SIGCSE 2007, which I think was one of the better SIGCSEs in
recent years.
-----