Tuesday, December 14, 2010 - NewsOK - ‘Solving' the game of checkers
Q: In what sense was the game of checkers “solved” in 2007, and how might someone have died as a result?
A: That was when computer scientist Jonathan Schaeffer and colleagues used computers to prove that checkers, when played perfectly, is a no-win game, says Clifford Pickover in “The Math Book.” This means that checkers, like tick-tack-toe, will always end in a draw if the players make no wrong moves. Schaeffer's proof required hundreds of computers and more than 18 years of work — the most complex game ever solved. Given that there are about 500 billion billion possible checkers positions on the 8-by-8-square board, this proof was far harder than the one for tick-tack-toe. The research team considered 39 trillion arrangements with 10 or fewer pieces on the board to determine if red or black would win, achieving a “major benchmark in the field of artificial intelligence.”
In 1994, Schaeffer's “Chinook” program played world champion Marion Tinsley to a series of draws. When Tinsley died of cancer eight months later, “some chided Schaeffer for accelerating the death due to the stress Chinook placed on Tinsley.”