[IP] Checkers is Solved

[David Farber <dave@farber.net>]

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 at
http://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




-------------------------------------------