Archive for the 'computer science' Category

Checkers Solved

Posted by mikedaum on July 19th, 2007

BBC is reporting on a spectacular result from the upcoming issue of Science. Researchers at the University of Alberta have computed the entire game tree for the game of checkers. For non-cs geeks, the game tree is a data structure which describes every possible sequence of moves in a game. Knowledge of the complete game tree allows one to categorize a game such as checkers into one of three classes:

  1. First mover can always win
  2. Second mover can always win
  3. It is always possible to force a tie

In the case of checkers, the answer turns out to be door number 3, which means that perfect players of checkers will always tie, regardless of who moves first. The paper’s authors have demonstrated this by writing a piece of software which “plays” checkers while in possession of the complete game tree. This program is of course not playing in the sense that other software plays. Rather, you can think of it as having a big checkers manual. When it considers moving, it turns to the page of the board it sees, and makes the move indicated on that page…which is the best possible move: guaranteed.

It is interesting to note that chess will never be solved in this fashion because the number of bits required to store the tree exceeds the information capacity of the universe we’re in. Same for the game of Go, which is not solvable even for a 9×9 teaching board, much less the full 19×19 board which is usually used.