Checkers Solved Friday, July 20, 2007

Via Sirlin.net...

As announced in Science magazine today and reported at Nature.com and the BBC, a team of Canadian computer scientists at the University of Alberta have officially solved the game of checkers. Using dozens of computers analyzing all of the 500 billion billion (5 × 10²⁰) possible game states, their software, Chinook, has worked out every possible move and now has a database of all possible winning strategies. Chinook was already the first computer program to win the championship in any game as of 1994, when it took the highest honors in checkers and remained undefeated until it was "retired" in 1997. Now, however, the software has been proven to be unbeatable.

Checkers is now the most complex game ever completely solved (Wikipedia has a great article on the subject of solved games for more information). According to Science Daily, Jaap van den Herik, editor of the International Computer Games Journal, calls this "a tremendous achievement -- a truly significant advance in artificial intelligence". He goes on to speculate that Chess (a game with a state space of 10⁴⁶, many billions of times more complex than Checkers) may be solved by 2070.