July 20, 2007 9:58 AM PDT

Canadian computer Chinook solves checkers

Font size
Print
E-mail
Share
2 comments

First, let me go on record as saying I didn't realize one could attain the title of "grand master" for playing checkers. I wish I knew such an exalted position existed for the relatively simple game of checkers back in my college days, when my chess-playing roommate would disparage me anytime I suggested we play checkers instead of engaging in yet another game of chess that would inevitably end with my resounding defeat.

That checkers grand masters walk the earth was a surprise, so imagine my shock to discover that since I was a junior in high school, hundreds of computers have been running in an effort to solve the game. Yesterday, in the journal Science, it was reported that computer scientists at the University of Alberta had solved the game, after their program, Chinook, had finished analyzing the 500 quintillion (that's 18 zeros, or a billion billion) possible checkers positions. Running since 1989 (with a four-year break from 1997-2001), Chinook has proved that checkers is a "draw game," meaning that if both players play perfectly, the game will always end in a draw. It's being called a major step forward for artificial intelligence, which may lead to advances in medicine where programs could help determine the course of treatment for a patient, for example.

Checkers is the most complex two-player game to be solved. It's a million times more complex than Connect Four, which was solved two decades ago. (After many long car trips where I was separated from my brother in the backseat of our station wagon by a miniature, travel version of Connect Four, I would like to think I may qualify as a Connect Four grand master.) Checkers is roughly the square root of chess in terms of complexity, however. While IBM's Deep Blue supercomputer famously beat chess grand master Gary Kasparov, it has yet to solve the game. Researchers say we're still a long way off from a program that can solve chess. Chinook was able to solve checkers by focusing on the end game, where there are eight or fewer pieces on the board.

You can play checkers against Chinook here.

Matt Elliott, a CNET editor since 2000, heads up coverage of computer hardware, from desktops and laptops to their assorted components and peripherals. Prior to joining CNET, he worked for PC Magazine. When not writing about computers and wrestling with their shipping boxes, he likes shooting with his Nikon D50 camera. Matt is also skilled with a tape gun. E-mail Matt.