New computer program never loses at checkers

After almost two decades, a dozen University of Alberta researchers using hundreds ofcomputers have created a computer program that always wins or ties at the game of checkers.

Jonathan Schaeffer, chair of the department of computer science at the University of Alberta, was the lead author of a paper about the program, published this week in the journal Science.

"Checkers is now solved: perfect play by both sides leads to a draw," the article says. "This is the most challenging popular game to be solved to date, roughly one million times more complex than Connect Four."

To come up with the solution,500 billion billion possible checkers positions were taken into account.

"Solving this problem is huge, more than a million times bigger than any other optimal problem ever solved before," Schaeffer told CBCNews.ca.

He likened the experience to this: imagine that a human foot equals 50,000 potential checkers positions that foot would have to touch the entire surface of the Earthto come up with the solution to checkers.

Schaeffer started trying to solve the game of checkers in 1989, first consulting masters of the game about their winning strategies. He fed the information into a computer program called Chinook, which used the heuristic approach to the problem, attempting to find out the best solutions via trial and error.

In the mid-1990s, Chinook wasn't a perfect program, sometimes losing at games. But it was still an impressive player, winning the world checkers championship in 1994.

The researchers then tried another method in whichmany computers played game after game, growing smarter after each round anddrawing experience from past games.

The researchers'success will hopefully open people to the concept of solving problems by inventing new techniques to search for the optimal answer, instead of just randomly looking for a needle in a haystack, Schaeffer said.

"Given the effort required to solve checkers, chess will remain unsolved for a long time, barring the invention of new technology. The disk-flipping game of Othello is the next popular game that is likely to be solved, but it will require considerably more resources than were needed to solve checkers," said the article.

Shaeffer is now working on software that can win at poker. It will be tested at the $50,000 man-versus-machine poker match, which takes place next week in conjunction with the Association for the Advancement of Artificial Intelligence conference in Vancouver.