Interesting People mailing list archives
Checkers is Solved
From: David Farber <dave () farber net>
Date: Thu, 19 Jul 2007 19:40:49 -0400
Begin forwarded message: From: Rod Van Meter <rdv () sfc wide ad jp> Date: July 19, 2007 6:30:53 PM EDT To: David Farber <dave () farber net> Subject: Checkers is Solved Write the names Jonathan Schaeffer and his collaborators Neil Burch, Yngvi Björnsson, Akihiro Kishimoto, Martin Müller, Robert Lake, Paul Lu, and Steve Sutphen in the history books: checkers is now solved. To save you the suspense, with perfect play, it's a draw. Schaeffer has spent eighteen years perfecting his search program and running through enough of the 5*10^20 possible games to know that. What's more, he has apparently compressed the results down to the point where a reasonable-sized program and database can actually play the perfect game in real time against a human. See the research paper at (www.sciencemag.org/cgi/content/abstract/1144079). Published Online July 19, 2007 Science DOI: 10.1126/science.1144079 Checkers Is Solved Jonathan Schaeffer 1*, Neil Burch 1, Yngvi Björnsson 1, Akihiro Kishimoto 1, Martin Müller 1, Robert Lake 1, Paul Lu 1, Steve Sutphen 1 and a short news blurb at COMPUTER SCIENCE: Program Proves That Checkers, Perfectly Played, Is a No-Win Situation Adrian Cho (20 July 2007) Science 317 (5836), 308a. [DOI: 10.1126/science.317.5836.308a]http://www.sciencemag.org/cgi/content/summary/317/5836/308a? maxtoshow=&HITS=10&hits=10&RESULTFORMAT=&fulltext=checkers&searchid=1&FI RSTINDEX=0&resourcetype=HWCIT
You can try your luck against the program on the web at http://www.cs.ualberta.ca/~chinook/ or read the New York Times article athttp://www.nytimes.com/2007/07/19/science/19cnd-checkers.html? _r=1&ref=science&oref=slogin
which notes that tournament play starts with three moves chosen at random; Schaeffer's paper shows that at least one of those combinations is a loss, and several are wins, but perfect play by both sides from move one is a draw. --Rod ------------------------------------------- Archives: http://v2.listbox.com/member/archive/247/=now RSS Feed: http://v2.listbox.com/member/archive/rss/247/ Powered by Listbox: http://www.listbox.com
Current thread:
- Checkers is Solved David Farber (Jul 19)