Saturday, July 9, 2011

Checkers is Solved !

It's nice to know that SOMEthing works perfectly amongst humans:

The abstract of the 2007 paper that announced Checkers is Solved:

The game of checkers has roughly 500 billion billion possible positions (5 × 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as Deep Blue for chess. Solving a game takes this to the next level by replacing the heuristics with perfection.

If you subscibe to Science'", the full paper can be found here::

The Chinook project began in 1989 with the goal of developing a program capable of defeating the human World Checkers Champion. In 1990, Chinook became the first program in any game to win the right to play for a human World Championship. The program lost the Championship match in 1992, but became Champion in 1994. By 1996, it became clear that the program was much stronger than any human, and Chinook was retired.
Checkers has a search space of 5x1020, 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.

No comments: