New Scientist reports that Jonathan Schaeffer has proven Checkers to end in a draw if neither player makes a mistake.
The crucial part of Schaeffer’s computer proof involved playing out every possible endgame involving fewer than 10 pieces. The result is an endgame database of 39 trillion positions. By contrast, there are only 19 different opening moves in draughts. Schaeffer’s proof shows that each of these leads to a draw in the endgame database, providing neither player makes a mistake.
Schaeffer was able to get his result by searching only a subset of board positions rather than all of them, since some of them can be considered equivalent. He carried out a mere 1014 calculations to complete the proof in under two decades. “This pushes the envelope as far as artificial intelligence is concerned,” he says.
To sum it up: If we were only a little smarter, Checkers would be just as boring as Tic Tac Toe.
Thanks to Henrik Bennetsen for the heads up.