Friday, July 20, 2007

Checker is a Draw

I am very happy to see that the news of the week in Science reports on a triumph of AI and (theoretical) computer science. A team from the games group at the University of Alberta, Canada, has announced that checkers is now solved: perfect play by both sides leads to a draw. Determining the outcome of the game brings AI search techniques to bear at a totally new level of complexity. The game of checkers has roughly 500 billion billion possible positions (5 x 1020)! These are state spaces of "model-checking size" :-)

Unfortunately, the full text of the Science article is only available to subscribers. The abstract is here. See also the web page of Chinook, the world checkers champion.

I am also very happy to report that one of the members of the team that solved checkers, Yngvi Björnsson, is a colleague of mine at Reykjavík University. This success will bring some media exposure for our department. (I know that process algebra cannot be expected to do so, alas :-))

Addendum: Bill Gasarch also has a, more detailed, post on this piece of news. Do read the comments to his post, which are, as usual, interesting.

No comments: