Computer Program Solves the Game of Checkers!

Researchers in Edmonton, Alberta have launched a simple computer program that claims to have "solved" the game of checkers.

Apparently "Chinook", the checker-playing computer program, cannot lose in a game that has been played by young and old for hundreds of years. Tests have shown the very best a player can do while playing against the computer is a draw.

While Chinook is unlikely to start a technological revolution, the steps that were taken to overcome such an improbable obstacle is most interesting. In the past, game-playing programs had used a common sense approach in making all decisions. The common sense approach worked most of the time, though these decisions were flawed enough to give players some chance of beating the computer. (Source: usatoday.com)

The chairman of the department of computing science at the University of Alberta, Jonathan Schaeffer, reported that the reason his staff programmed Chinook to be so flawless was to show the world that complex situations can be solved using the logical reasoning of technology. Schaeffer and his team of researchers created Chinook's thinking process by studying the end of a checker game with only one checker left on the board. They then looked at every possible combination with two checkers left on the board, then three checkers, all the way up to ten checkers left on the board. (Source: news.yahoo.com)

Schaeffer and his team discovered that every combination of ten checkers offers thirty-nine trillion possible positioning strategies that will eventually lead to the end of the game.

Chinook has the ability to calculate them all!

It does not matter how the players make it to ten checkers remaining on the board, because from that point on, the computer cannot lose. Even if the human player never makes a single error, the best he or she can hope for is a draw. (Source: news.yahoo.com)

Chinook has even defeated the current "World Champion of Chess" Vladimir Kramnik. The defeat of Kramnik prompted many newspaper headlines to proclaim, "Checkers is solved!"

Schaeffer's proof is what is called a "weakly solved" result. It calculates the result from an initial position (in Schaefer's case, from ten pieces on the board) rather than from the beginning of the game.

Could Schaeffer and his team produce a "strong solution" by calculating every checker position from the beginning of a game? Possibly, but Schaeffer believes that there isn't enough computer power currently available to complete this task. (Source: usatoday.com)