Scientists Write Perfect Checkers Program

It might not seem like much, but Canadian scientists have created a computer program that can always win at checkers.   Yet behind that is a much bigger achievement.   The team behind theprogram have written about it in Science, and lead author Jonathan Schaeffer, who is also chair of the department of computer science at the University of Alberta, wrote   “This was a huge computational problem to solve – more than a million times bigger than anything that had ever been solvedbefore.”   Schaeffer began his quest in 1989, feeding data from checkers champions into a program called Chinook, whose heuristic approach used trial and error to discover the bestsolutions.   It was largely successful, winning the world’s checkers championships in 1994, but it wasn’t perfect; Chinook could still lose. So the scientists abandoned the heuristicapproach, and instead used literally hundreds of computers to run through game after game until there was enough information that the computer knew what move to make in any game situation – andthere are about 500 billion billion possible positions. Every game is now won by Chinook.   Checkers is by far the biggest game yet solved by computer, about a million times more complex thanConnect 4. However, don’t expect any team to move on and crack chess anytime soon. It has roughly a billion billion billion billion billion possible positions – far beyond thecapabilities of current computers.