A Perfect Game of Checkers Will End in a Draw

What will be the result of a game of checkers with no mistakes made by either player? A team at the University of Alberta said they had “solved” checkers: “perfect play by both sides leads to a draw“.

The research published in the journal “Science” says that dozens of computers have been working on solving checkers for more than 18 years by playing out about 39 trillion possible positions!

Jonathan Schaeffer, the chairman of the department of computing science at the University of Alberta said:

Clearly, the world is not going to be revolutionized by this. The important thing is the approach. In the past, game-playing programs have used rules of thumb – which are right most of the time – to make decisions. What we’ve done is show that you can take non-trivial problems, very large problems, and you can do the same kind of reasoning with perfection. There is no error in the Chinook result. … Every decision point is 100%.

This proof is what is called a “weakly solved” result, because it calculates the result from an initial position – 10 pieces on the board – instead of from the beginning of the game. Could it be possible to produce a “strong solution” (calculating every position from the beginning of a game)? “Maybe”, said Schaeffer, “but there is not enough computer power available”.

This breakthrough could encourage others to solve the other games we encounter in life:

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.