Skip to content

A Perfect Game of Checkers Will End in a Draw

July 20, 2007

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.

Advertisements
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: