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 Jonathan Schaeffer, who is a computer scientist at the University of Alberta. Schaeffer is best known as the creator of Chinook, 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 Grady Booch's talk or Jeannette Wing'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 One Jump Ahead, 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 ( Chinook page | wikipedia page), 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), reinvigorated 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, Tiger Woods, and even Lance Armstrong 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 loved doing AI, 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. -----