Checkers (10^20 positions) Solved: Perfect Play Leads To Draw

Sat 21 July 2007

Wow! Jonathan Schaeffer of the University of Alberta has solved the game of checkers. Games like tic-tac-toe, checkers, chess, and go are all known to have optimal strategies (I don't recall  of the exact game-theory restriction that describes such games: "perfect information, sequential"?). That's why tic-tac-toe is boring -- it's always correct to first play to a corner and its always correct to respond by playing to the ~~opposite corner~~ middle .

The bigger games like checkers, chess, and go have such huge solution spaces that one wouldn't think their solutions could be discovered by brute force. Schaeffer's calculation has been ongoing for 18 calendar years (no word on total processing time) and involved "just" 10\^14 calculations. It seems that he reduced the tree by finding many equivalent positions and then brute-forcing every possible endgame involving fewer than 10 pieces. The conclusion is that perfect play leads to a draw (I believe it's still unknown if perfect play in chess leads to a draw).

What I'm impressed by from a software standpoint is that obviously he figured a way to maintain the partial calculations of his system over 18 years, even as he undoubtedly brought newer generations of hardware and software to bear on the problem. Well done!

blogroll

social