Checkers Solved

August 14, 2007

After eighteen years of work, scientists have designed an unbeatable checkers computer.

Podcast: Play in new window

Transcript

BOB HIRSHON (host):
An invincible checkers computer. I’m Bob Hirshon and this is Science Update.

It took eighteen years and hundreds of computers, but a team of scientists has finally solved the game of checkers. Led by computer scientist Jonathan Schaeffer of the University of Alberta in Canada, they’ve made a checkers-playing computer program that can’t possibly lose.

JONATHAN SCHAEFFER (University of Alberta):
So for example, if the computer makes the first move of the game, you have seven different moves. And for each one of those seven moves, the computer has a response ready.

HIRSHON:
In theory, checkers has 500 billion billion possible board positions. But in order to crunch the numbers in less than a lifetime, Schaeffer’s team developed an algorithm that disregards irrelevant positions and choices. He says the algorithm could help other artificial intelligence programs find the best possible strategy for a complex task. I’m Bob Hirshon, for AAAS, the science society.