Machine beats man at his own game

US scientists have developed a computer programme that they say can’t lose at the popular board game draughts.

After 18-and-a-half years and sifting through 500 billion billion (a five followed by 20 zeroes) draughts positions, Dr. Jonathan Schaeffer and colleagues of the University of Alberta have built a draughts-playing computer program that cannot be beaten. Completed in late April this year, the program - Chinook - may be played to a draw but will never be defeated.

“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,” said Schaeffer, chair of the U of A Department of Computing Science. “With Chinook, we’ve pushed the envelope about one million times more than anything that’s been done before.”

A self confessed ‘awful’ draughts player, Schaeffer used the knowledge of several draughts experts to programme heuristics (‘rules of thumb’) into a computer software program that captured knowledge of successful and unsuccessful draughts moves.

An average of 50 computers - with more than 200 running at peak times - were used everyday to compute the knowledge necessary to complete Chinook. Now that it is complete, the program no longer needs heuristics - it has become a database of information that ‘knows’ the best move to play in every situation of a game. If Chinook’s opponent also plays perfectly the game would end in a draw.

“We’ve taken the knowledge used in artificial intelligence applications to the extreme by replacing human-understandable heuristics with perfect knowledge,” Schaffer said. “It’s an exciting demonstration of the possibilities that software and hardware are now capable of achieving.”