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:
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.