July 20, 2007  Checkers Computer Can't Be Beat

It’s checkmate for checkers.  The 5,000 year old game has been completely solved, and a checkers-playing computer called Chinook cannot be beaten.  That’s according to University of Alberta computer scientists publishing in the latest issue of the journal Science.  

The researchers spent almost two decades going through the 500 billion billion possible checkers positions, which is still an infinitesimally small fraction of the number of chess positions, by the way.  The checkers effort included top players, who helped the research team program checkers rules of thumb into software that categorized moves as successful or unsuccessful.  Then the researchers let the program run, on an average of 50 computers daily.  Some days, the program ran on 200 machines.  While the researchers monitored progress and tweaked the program accordingly.  In fact, Chinook beat humans to win the checkers world championship back in 1994. 

(Computer voice): But it had not yet become perfect.

That process is now done, and the Chinook program has developed into a database that knows the optimal move in any possible checkers situation.  If a human opponent plays a perfect game, he or she can only hope for a tie.