If you’re into AI, you might have heard by now that Checkers has been solved. Solved, as in determining the final result of a game in which either player makes no mistakes whatsoever: The AI will always make the perfect play. Checkers has roughly 500 billion billion possible positions (5×1020) and is now the largest game that has been solved to date. It took dozens of computers running almost continuously around the clock since 1989 to solve. My advisor at Reykjavik University, Yngvi Björnsson, is a part of the development team and one of the authors of the article published in Science magazine, July 6th, introducing the solution to Checkers. My congratulations to Yngvi and the team for this achievement!
The gaming system Chinook is the underlying architecture that produced the solution. Chinook is a system that’s been under development since 1989, and has since then been under constant development. By 1996 it was stronger than any human, and it was the first program to win a human world championship in a boardgame. Basically, solving Checkers means that it can’t be beaten. If you make no mistake whatsoever during the entire gameplay, you’ll make a draw at best. The solution is described on the Chinook project pages:
From the standard starting position, Black (who moves first) is guaranteed a draw with perfect play. White (moving second) is also guaranteed a draw, regardless of what Black plays as the opening move.
Awesome achievement, and humbling to have Yngvi as an advisor. He’s really rocking the game AI world these days, as he’s also supervising a master’s project that recently won the preliminaries of Stanford’s General Game Playing Competition, and is headed next for the main event hosted at AAAI’07.
The web is bursting with news on the Checker’s solution & AI system, so I won’t be regurgitating it here. See the links below for some more info, system authors and news.
Links & References
- Abstract for the Science article
- Chinook page & Chinook authors
- Google News Results for Chinook
- Compete against Chinook online
- Stanford’s General Game Playing Competition
- [CADIA] Center for Analysis and Design of Intelligent Agents (aka the lab in Think Artificial posts)