tour de force, n. A feat requiring great virtuosity or strength, often deliberately undertaken for its difficulty.
An article in Science by Jonathan Schaeffer and colleagues at the University of Alberta claims to have proven that checkers is a solved game — perfect play by both players will result in a draw. This is an amazing result!
“The game of checkers has roughly 500 billion billion possible positions (5 x 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times more complex than Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as DEEP BLUE for chess. Solving a game takes this to the next level, by replacing the heuristics with perfection.”
Access to the article requires a subscription, but you can access some online material for free. Better yet, you can see a video and 95 minute podcast of Schaeffer describing the Chinook program how they proved that checkers is a draw game. Amazingly, Shaeffer says that his programs that have been exploring the checkers game tree have been running, off and on, for eighteen years! Also, check out the article Computer Checkers Program Is Invincible in today’s New York Times.
Can you play a perfect game? To find out, you can try the Chinook program on-line.