Computer scientist creates invincible Checkers game

Computer scientists at the University of Alberta claim to have built a checkers playing computer programme that is invincible.

Washington, July 20 : Computer scientists at the University of Alberta claim to have built a checkers playing computer programme that is invincible.

According to Dr. Jonathan Schaeffer, who developed the game after spending 18 and a half years and sifting through 500 billion billion (a five followed by 20 zeroes) checkers positions, the game, named Chinook, can be played to a draw, but can 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. With Chinook, we've pushed the envelope about one million times more than anything that's been done before," said Dr. Schaeffer, chair of the U of A Department of Computing Science.

Dr. Schaeffer, who describes himself as an "awful" checkers player, said he created Chinook to exploit the superior processing and memory capabilities of computers and determine the best way to incorporate artificial intelligence principals in order to play checkers.

With the help of some top-level checkers players, Dr. Schaeffer programmed heuristics ("rules of thumb") into a computer software program that captured knowledge of successful and unsuccessful checkers 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.

Then he and his team let the program run, while they painstakingly monitored, fixed, tweaked, and updated it as it went.

According to Dr. Schaeffer, now that it is complete, the program would no longer need 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, said Dr. Schaeffer.

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

"This is a tremendous achievement-a truly significant advance in artificial intelligence," added Dr. Jaap van den Herik, editor, International Computer Games Journal.

The results of the research appear in today's issue of the journal Science.

ANI