Home > Math News Archive Detail

<< Prev 1/27/2008 Next >>

First Tic-Tac-Toe, Now Checkers

As a kid I enjoyed playing Tic-Tac-Toe...but as I got older, I realized it was no longer a game. That is, every possible strategic move (and its subsequent effects) had been worked out; the game had lost its challenge and fun elements. To make matters even worse, as a first year teacher, I helped one of my students program a computer to play tic-tac-toe and never lose...based on a thorough flow-chart of the game we had mapped on the chalk board. In sum, the game of tic-tac-toe was no longer a game...it had become an algorithm that either I or the computer could rotely implement.

And now, Jonathan Schaeffer, University of Alberta, has announced that the same has been done for the game of checkers. That is, the game of checkers has been "solved," is now merely an algorithm; every game of checkers, if each "play" follows the perfect algorithm, will end in a draw.

Schaeffer and his colleagues focused on the Checkers problem for 18 years, using hundreds of computers working since 1989 to "analyze all possible board combinations of checkers, roughly 500 billion scenarios." In short, all of the fun, the strategy, the element of a surprise move, the aniticipation of an opponent's move....all are no more. Checkers has become a perfect "draw" game.

So what's next...chess?

Source: R. Mitchum's "Science of Checkers Revealed," Bellingham Herald, July 20, 2007