Re: Checkers is solved

The point at which the paper is accepted sounds like a reasonable time
to announce the result, to me.  Ordinarily, one would put a copy on
one's website but perhaps _Science_ are stricter about that than most
other journals?

Of course.

For the record, I have not seen the paper, in any form.

Not sure.  But it's perfectly normal not to print the raw data...

Dave.

In which case, it's perhaps wise to wait before making announcemens,
making claims, and certainly before trying to evaluate the claims.
Perhaps we should just wait for the paper and then read it.

Unless, of course, one has seen a review copy - but it would be
unethical to base any comments on such a source, right?

I wonder if that part of the tree that they expanded will fit in one
issue of "Science".

Of course.

Of course.  But the paper hasn't been published yet and isn't
available on the project website.  So that's all there is for the time
being.  But I suspect the proof will consist of ``We ran the initial
position through this big alpha-beta search using ten-man tablebases
to evaluate the leaves and it said `draw'.''  It's hard to imagine any
other sort of proof for something so big.  It is, after all,
essentially just the case-split of the century.

Dave.

a) don't believe everything you read in "Science"
b) we don't want a demonstration - we want a proof.

They wouldn't be publishing partial results in _Science_ under the
title ``Checkers is Solved.''

What you are doing is taking a journalist's garbled description of
Schaeffer et al.'s work, and saying ``That doesn't work.  Therefore
the claim is false.''  This is unreasonable and unfair.

What Schaeffer actually seems to have done is developed 10-man
tablebases and then searched from the initial 24-man position to give
a drawing strategy for white for every position that is consistent
with the strategy.  See

 http://chinook.cs.ualberta.ca/users/chinook/index.html

for a demonstration.

Dave.

 That is precisely what I mean by empty hype.

 My take is that possibly the use of a technical term,
to mean "only partly solved" was the reason so many
reporters keep mucking things up.

 Indeed, all you really need to see is the link which
admitted that they have only solved for ten men or
fewer.  Logic tells us that since there are 24 men at
the beginning of each game, they cannot have truly
solved checkers.  An interesting thing is that they
have decided to move on... blaming a lack of
computer power for this partial failure.

 I'm noting the hype, and how easily many people
are confused by the misuse of the term "solved".

 -- help bot

I disagree.  It looks to me like bad reporting.  this research team is
rock solid and I trust their papers.  the trouble is - all I've seen so
far are the news reports - NOT the paper.

I'm objecting to the gloss - not questioning the result.

 It looks to me like yet another case of empty hype.

 The article on Yahoo! says that they have only
solved checkers with ten or fewer men on the board.
More than ten, and they are in the same boat as
Rybka and Ace Ventura -- they are the best there is,
but hardly perfect.

 The article blames a lack of computer power for
their failure to "solve" checkers; in short, they must
be doing a brute force approach, like Conan the
Barbarian or the world hot-dog-eating champion.

 Still, when it comes to this sort of thing, there is
no besting IM Innes or Sanny or Sam Sloan -- they
are the real Aces of hype.

 -- help bot

"Schaeffer's team started with the end of a game with just one checker
on the board. Then the team looked at every possible position with two
checkers, on up to 10 checkers on the board.

Every combination of 10 checkers offers 39 trillion positions for the
endgame, he said. Chinook can calculate them all.

It does not matter how the players make it to 10 checkers left because
from that point on, the computer cannot lose, Schaeffer said. For two
players who never make a mistake, every game would be a draw, he said."

I hope there's more than this - or that this is a bad paraphrase.

Of course it "matter(s) how the players make it to 10 checkers".
Surely SOME positions with 10 checkers are lost, no?

We now need a proof that a player CAN, in fact, always manage to reach a
10-checker position that happens to be drawn with best play.

I'm certain that this proof must be in the full paper.

Can someone who has actually read the paper please supply the missing steps?

Actually, what I'd love to see is an example of a "well-balanced"
10-checker position that is NOT drawn with best play.

Here is a yahoo link:

http://news.yahoo.com/s/ap/20070719/ap_on_hi_te/solving_checkers

Doesn't need a password.

Interesting news.

Fred

 That link asks for a password.

 To my mind, "solving" checkers would not simply
mean being able to handle any human or present
computer opponent without losing; instead, I want
to have every legal checkers position scored as a
win/loss/draw, by calculating every simpler position
that can arise from it and so forth; like the endgame
tablebases in chess.  I suppose you would begin
with the simplest positions, and work backwards,
adding more and more for many years until one day,
your efforts suddenly hit a wall -- having tackled
every legal position and tallied the results.

 Although checkers uses a similar board to chess,
only half the squares are actually used; critically,
since every man moves and captures the same
way (until a promotion at least), this should be
much easier than solving chess.  Also, many of
the possible moves of a random checker will be
blocked, reducing further the possible legal moves.

 I am wondering whether they really "solved" the
game or, as the chosen language suggests, they
merely succeeded in never losing in practice.

 -- help bot

Computer Program Can't Lose at Checkers
By RANDOLPH E. SCHMID

WASHINGTON (AP) - Perhaps Chinook, the checker-playing computer
program, should be renamed ``King Me.'' Canadian researchers report
they have ``solved'' checkers, developing a program that cannot lose
in a game popular with young and old alike for more than athousand
years.``The program can achieve at least a draw against any
opponent,playing either the black or white pieces,'' the researchers
say in this week's online edition of the journal Science.

http://netscape.compuserve.com/news/story.jsp?floc=ne-main-9-l7&idq=/ff/story/00
01%2F20070720%2F0119365665.htm&sc=1333