Chinook computer checkers champ now king forever

Stan Beer
Friday, 20 July 2007 04:32

Business IT - Technology

It took up to 200 computers working simultaneously since 1989, but computer scientists at the University of Alberta have solved the game of draughts, known in the US as checkers, meaning that humans no longer have any possibility of beating the program called Chinook.

The Chinook program was developed by a team of 10 computer scientists from the University of Alberta and a weather prediction modeller in Australia, who acted as the checkers expert whose knowledge was input to the artificial intelligence program.

Since the project was started in 1989, Chinook has gradually asserted its superiority over human players. It lost in its first attempt at winning the world championship in the 1992 final. However, it won the title in 1994 from Marion Tinsley, a champion who had not been beaten for the title for decades. The project developers say Chinook was retired from competition in 1996 because it was obvious that no human was capable of beating it.

However, it was not until April 29, 2007 that the development team was able to announce that Chinook had completely solved the game of checkers. The program can no longer do worse than achieving a draw even if a perfect game is played against it.

Solving the game meant an average of 50 computers working in parallel had to examine the outcomes of every possible move, a search space of 5 by 10 to the power 20 (5 followed by 20 zeroes). A game of that size was one million times larger than the most complex game solved to date Connect Four.

According to the Chinook website : "Checkers has a search space of 5x10[to power 20], a daunting number. Almost continuously since 1989 (with a gap in the 1997 to 2001 period), dozens of computers have been working around the clock to solve the game. On April 29, 2007, we were pleased to announce that checkers is now solved. From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move. Checkers is the largest game that has been solved to date, more than one million times larger than Connect Four and 100 million times larger than Awari.

"Along the way, the Chinook project produced numerous research publications. Chinook’s winning of the World Man-Machine Championship (three years before the Deep Blue chess match) was a milestone in the history of artificial intelligence research. In 1996 the Guinness Book of World Records recognized Chinook as the  first program to win a human world championship."

Vistors to the Chinook project site can test the validity of the program at http://chinook.cs.ualberta.ca/users/chinook/index.html and can play a game to test their skill at http://www.cs.ualberta.ca/~chinook/play/ .