Fri, July 20, 2007
Taking the fun out of checkers
EDMONTON -- It's taken dozens of computers humming away for almost 18 years, but a University of Alberta team has finally solved every possible game of checkers and concluded that as long as no mistakes are made, the game will end in a draw.
The popular game may be simple to play, but it holds a potential 500 billion billion positions. That's one million times more complicated than any other game solved before, says Jonathan Schaeffer, the computer science professor who began the project in 1989.
"In hindsight, it was ludicrous. Why tackle something a million times bigger?" said the wiry-haired academic. "Maybe there's a little bit of craziness there."
The team did trim down the number of positions examined. If a move in a certain position would lead to a win, the computer wouldn't look at other possible moves from that position that may lead to a draw or loss.
Schaeffer's proof was to be published in the academic journal Science yesterday. Schaeffer says that while the discovery is exciting from a computer science perspective, it shouldn't change how humans play the game.
More Newspaper Article on Friday and links: Posted by Richard Beckwith on USAcheckers.com forum
Here are some on-line article links. (Thanks to Pal Bucker for many of these.) I also spoke with LA Times, NY Times, Chicago Tribune, and COSMOS (Australian Magazine). I have a few more thoughts in Player's Rep Corner.
The New York times
The Los Angeles Times
Canadian Broadcast Corporation
The National Post (Canada)
ACF Player Rep