Tuesday, July 31, 2007

Checkers solved: a draw



This month, computer scientists from University of Alberta have announced that their computers have scanned 500,995,484,682,338,672,639 (half a hexillion) board configurations of American checkers, also known as English draughts or Czech madam. Surely, they had to analyze many of them in huge "trivial" classes because otherwise the Hubble time wouldn't be enough.

They have determined the right move for each of them. The main conclusion is that ideal players will end up with a draw:
BBC (popular), Wikipedia, Science (technical)
You may hope that the Flash applet above is imperfect. ;-) The applet has unusual, politically correct priority rules: green goes first. I have easily won but that may be only because I was green.

Some 15 years ago, I (or we) have spent a lot of time with game theory because of an interesting fellow, Karel Popp, who has done a lot of cute things about game theory. I remember having analyzed his game Iuvavum (a Latin name of Salzburg where he was a professor) and many other games and their winning and losing configurations. Painfully enough, I have completely forgotten the rules of Iuvavum.

No comments:

Post a Comment