Dum Pendebat Filius

The game of checkers (aka “English draughts”) has been solved. A computer program called Chinook is literally unbeatable.

The team directed Chinook so it didn’t have to go through every one of the 500 billion billion (5 * 10 ^ 20) possible moves. Not all losing plays needed to be analysed; instead, for each game position, Chinook needed to work out only a move that would allow it to win. In the end, only 1/5,000,000 of the moves were computed.

As Chinook has worked out all relevant lines of play, it needs virtually no time to ‘think’ to work out each perfect move in a game. The results were announced today in the journal Science. The paper and supporting materials, including the ability to play Chinook, are available on the web at http://www.cs.ualberta.ca/~chinook.