| Author |
Message |
M Winther (Kalroten)
New member
Username: Kalroten
Post Number: 33
Registered: 1-2007
| | Posted on Sunday, July 22, 2007 - 1:12 am: | |
Scientific American's summary of the claim that Checkers has been SOLVED by computer analysis (and it is a draw when played perfectly by both sides!)
http://www.sciam.com/article.cfm?articleID=DBE35D70-E7F2-99DF-3ECB392CEF7AC028&chanID=sa007
=== begin quoted passage ===
July 19, 2007
Computers Solve Checkers-It's a Draw
King me! Top computer scientist proves perfect play leads to draw, recounts battle for world championship, gets kinged
By JR Minkel
Jonathan Schaeffer's quest for the perfect game of checkers has ended. The 50-year-old computer scientist from the University of Alberta in Edmonton left human players in the dust more than a decade ago after a trial by fire against the greatest checkers champion in history.
And now, after putting dozens of computers to work night and day for 18 years-jump, jump, jump-he says he has solved the game-king me!. "The starting position, assuming no side makes a mistake, is a draw," he says.
Schaeffer's proof, described today in Science ... would make checkers the most complex game yet solved by machines, beating out the checker-stacking game Connect Four in difficulty by a factor of a million....
"It's a milestone," says Murray Campbell, a computer scientist at IBM's T. J. Watson Research Center in Hawthorne, N.Y., and co-inventor of the chess program Deep Blue. "He's stretched the state of the art."
Although technological limits prohibit analyzing each of the 500 billion billion possible arrangements that may appear on an eight-by-eight checkerboard, Schaeffer and his team identified moves that guaranteed the game would end in a draw no matter how tough the competition.
Like any complicated mathematical proof, the result will have to withstand scrutiny. But "it's close to 100 percent," says computer scientist Jaap van den Herik of Maastricht University in the
Netherlands, who has seen the details. "He has never published anything that was not completely true."
http://www.sciam.com/article.cfm?articleID=DBE35D70-E7F2-99DF-3ECB392CEF7AC028&chanID=sa007 |
Greg Schmidt (Gschmidt2)
New member
Username: Gschmidt2
Post Number: 35
Registered: 1-2007
| | Posted on Sunday, July 22, 2007 - 8:05 am: | |
I was aware of this reasearch but hadn't realized there was now a proof. I've been reading Schaeffer's book "One Jump Ahead" which is about his world class checker playing program "Chinook" and his quest to beat the world champion checkers player, Marion Tinsley.
I highly recommend the book and I also recommend the following books:
"Behind Deep Blue" - Feng-Hsiung Hsu
"Blondie24: Playing at the Edge of AI" -David B. Fogel
One of the things Schaeffer discusses is how Chinook's level of play improves as he builds larger and larger end game databases. I believe his work to solve the game began with his work on improving Chinook's end game databases.
Along these lines, a recent result has been discovered for Rubik's cube. It has been proven that all positions can be solved in no more than 26 moves (a previously proven upper limit was 27). It is conjectured, but not proven, that 20 moves is the "true" upper bound.
See:
http://www.sciencedaily.com/releases/2007/05/070531131326.htm |
|