Canadian Programmers Claim Their Checkers Program Is Unbeatable

Software developers at the University of Alberta say they've 'solved' checkers by developing a program that's guaranteed to never lose.

K.C. Jones, Contributor

July 20, 2007

1 Min Read

Software developers in the department of computing at the University of Alberta say they've perfected a checkers program so powerful that human competitors can never win.

The developers said the best players can do against the improved and "unbeatable" Chinook is to end the game in a tie.

"Checkers is solved," they pronounced in a statement on their Web site.

From the starting position, black (which moves first) can only draw against a perfect opponent, and white (which moves second) is also guaranteed a draw, regardless of what black plays as the opening move, developers said.

"This is the largest non-trivial game of skill to be solved," the developers said. "It is more than one million times bigger than Connect Four and Awari."

Connect Four and Awari were the biggest and most complex games solved before Chinook became unbeatable at traditional checkers, called draughts in England. A traditional game of checkers allows for three-move openings and about 500 billion total board positions for the duration of the game. The developers' claims come from a computer proof, not a mathematical one.

Developers began work on the Chinook program in 1989 in an attempt to build a program that could beat the human World Checkers Champion. Chinook suffered a narrow loss to the world checkers champion in 1992, but limited the champion to draws in 1994. Two years later, Chinook proved stronger than people and retired. Chinook won the World Man-Machine Championship, three years before the Deep Blue chess match, marking a milestone in the history of artificial intelligence.

Those who want to challenge Chinook can test their mettle online.

About the Author(s)

Never Miss a Beat: Get a snapshot of the issues affecting the IT industry straight to your inbox.

You May Also Like

More Insights