ADVERTISEMENT
60-Second Science

Checkers Computer Can't Be Beat

It took more than 18 years, but computer scientists have completely solved the game of chess, with a program that can be tied but never beaten. Steve Mirsky reports.

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. 

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Dinosaurs

Get Total Access to our Digital Anthology

1,200 Articles

Order Now - Just $39! >

X

Email this Article

X