The short answer is: Yes he did! His result was announced in Science magazine in the September 14, 2007 issue, after his solution was completed and verified on April 29, 2007. You can read about it online here or on the Chinook website at the University of Alberta in Edmonton, Canada. You can also see that Ed Gilbert, Gil Dodgen, and Ed Trice were of some (minor) assistance. We independently verified the databases that the Chinook team built were, in fact, correct. Gil and I verified the 8-piece databases in 2001, before Schaeffer started on his 9- and 10-piece database builds. Ed Gilbert verified his 9- and 10-piece databases some time in 2004. The Chinook team was nice enough to mention us on their web page in the Thank You section.

A natural follow-up question is, if checkers is solved, why am I solving checkers databases?

I don't have the goal to duplicate Schaeffer's work, or solve the game of checkers myself as a side project. I am doing something different that is extending the work of my former programming colleague, Gil Dodgen. Gil is an interesting character. His majors in college were Piano and French (which he holds Masters' degrees in) yet he is a very highly skilled C-programmer. More remarkably, he is a self-taught programmer with no formal training in the field.

Gil was the true pioneer of Perfect Play Databases for the game of checkers. When he computed checkers endgames for the first time in 1992 for his checkers program (with the rather mundane name of "Checkers 3.0") he solved how long it would take each win or loss to play out to completion. Even the Chinook program written by Schaeffer and his team from the University of Alberta did not have access to this information. The Chinook databases stored only the so-called Game-Theoretical Value of the position. That is, the only information in their database is whether each position is a win, loss, or a draw.

Why only store the minimal information? That's a long discussion point. The abridged version is that such data can be compressed very highly (the Game-Theoretical Value database that Gil and I computed for 8 pieces contained more than 30 positions per byte, on average. See this link for more information) and it is ideally suited for probing by a checkers program at run-time. As the checkers program searches, it can make use of the information in the database, avoiding losses and draws, and striving for wins, even though still a long distance away.

But, once you enter into a "winning position" over-the-board, the Game-Theoretical Value database is of little use regarding how best to proceed. Take a look at the position below:


Counting the play by both sides, red will win after 253 moves. Computed by Dodgen and Trice, 2003.

The position shown above is the longest win computed using the Perfect Play Lookup database. With optimal play by both sides, red to move cannot win for a staggering 253 moves! In 2003, two different checkers programs were given the winning side to play against the Perfect Play Lookup database. The Perfect Play Lookup database was able to postpone the loss by continually making the "longest losing" move in its database for every move made by the opponent. When given the side with the winning position, it was able to defeat both of the programs rather convincingly, winning much faster than 253 moves when they failed to make the best defensive play according to the database.

If such amazing play is possible for 7-pieces on the board, how much more interesting are the most difficult 8-, 9-, and 10-piece perfect play positions?! This is what interests me the most: computing the Perfect Play for larger databases. The problem is, the technology has been lacking, and the length of time required to compute the more cumbersome Perfect Play data was previously impractical.

Enter Liquid Nitrogen Overclocking! With such amazing computational power now available (systems up to 5.0 GHz in speed in early 2010) it reduces the length of time to less than one year (with some parallel implementations using as many as 4 processing cores). With a pair of these computational workhorses, I will solve the 10-piece Pefect Play Databases by some time in 2011.