Tuesday, December 14, 2010 - NewsOK - ‘Solving' the game of checkers
NewsOK
POWERED BY THE OKLAHOMAN
THE STATE'S MOST TRUSTED NEWS Article features a computer scientist Jonathan Schaeffer who used computers to prove that checkers, when played perfectly, is a no-win game.  news link


‘Solving' the game of checkers

Strange But True: A computer scientist Jonathan Schaeffer used computers to prove that checkers, when played perfectly, is a no-win game.

BY BILL SONES AND RICH SONES, PH.D. Oklahoman Published: December 14, 2010

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.”


Articles