WASHINGTON (Reuters) - The perfect game of checkers ends as a draw, Canadian computer scientists reported on Thursday.

The team at the University of Alberta said they had "solved" checkers, the 5,000-year-old popular board game also known as draughts. Their computer program, Chinook, spent more than 18 years playing out the 500 billion possible positions, they report in the journal Science.
"This paper announces that checkers is now solved: Perfect play by both sides leads to a draw," Jonathan Schaeffer and colleagues wrote in their report.

"That checkers is a draw is not a surprise; grandmaster players have conjectured this for decades."

But no computer program had been able to tackle the game thoroughly.

The researchers said checkers was the most complex game to have been solved - with every possible moved played out -- by a computer. "I think we've raised the bar, and raised it quite a bit, in terms of what can be achieved in computer technology and artificial intelligence," Schaeffer said in a statement.

The board game uses pieces that can move forward one square diagonally and a forced-capture rule.

While many computer programs exist to play games, and can beat humans at such complex games as chess, playing every possible move in a game is a much more difficult problem.
© Copyright 2007 Reuters.