Print

Mail

wiki links

Canadians beat checkers after 18 years of research

Canadian researchers report they have solved checkers, developing a program called Chinook that cannot lose in a game popular with young and old alike for more than 1,000 years.

"The program can achieve at least a draw against any opponent, playing either the black or white pieces," the researchers say in this week's online edition of the journal Science.

"Clearly ... the world is not going to be revolutionized" by this, said Jonathan Schaeffer, chairman of the department of computing science at the University of Alberta.

The important thing is the approach, he said. In the past, game-playing programs have used rules of thumb -- which are right most of the time, he said -- to make decisions.

"What we've done is show that you can take nontrivial problems, very large problems, and you can do the same kind of reasoning with perfection. There is no error in the Chinook result. ... Every decision point is 100 percent," he said.

Schaeffer's team started with the end of a game and looked at every possible position with two checkers, on up to 10 checkers, left on the board. Every combination of 10 checkers offers 39 trillion positions for the end of the game, he said. Chinook can calculate them all.

It does not matter how the players make it to 10 checkers left because from that point on, the computer cannot lose, Schaeffer said. For two players who never make a mistake, every game would be a draw, he said.

Schaeffer's proof is what is called a "weakly solved" result. It calculates the result from an initial position -- 10 pieces on the board -- rather than from the beginning of the game.

Could Schaeffer's team produce a "strong solution" by calculating every position from the beginning of a game? Maybe, but there is not enough computer power available, he said. It took more than 18 years to get where they are now.
This story has been viewed 1121 times.