Canadian Programmers Claim Their Checkers Program Is Unbeatable - InformationWeek

InformationWeek is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them.Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

IoT
IoT
Software // Enterprise Applications
News
7/20/2007
11:58 AM
50%
50%

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.

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.

We welcome your comments on this topic on our social media channels, or [contact us directly] with questions about the site.
Comment  | 
Print  | 
More Insights
Commentary
2021 Outlook: Tackling Cloud Transformation Choices
Joao-Pierre S. Ruth, Senior Writer,  1/4/2021
News
Enterprise IT Leaders Face Two Paths to AI
Jessica Davis, Senior Editor, Enterprise Apps,  12/23/2020
Slideshows
10 IT Trends to Watch for in 2021
Cynthia Harvey, Freelance Journalist, InformationWeek,  12/22/2020
White Papers
Register for InformationWeek Newsletters
Video
Current Issue
2021 Top Enterprise IT Trends
We've identified the key trends that are poised to impact the IT landscape in 2021. Find out why they're important and how they will affect you.
Slideshows
Flash Poll