Fred wrote:
On Fri, 20 Jul 2007 01:25:26 -0700, help bot
wrote:

On Jul 20, 3:05 am, " wrote:
Computer Program Can't Lose at Checkers
By RANDOLPH E. SCHMID

http://netscape.compuserve.com/news/...ain-9-l7&idq=/...

That link asks for a password.
Computer Program Can't Lose at Checkers

Here is a yahoo link:

http://news.yahoo.com/s/ap/20070719/...lving_checkers

Doesn't need a password.

Interesting news.

Fred


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

--
Kenneth Sloan
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/

On Jul 20, 1:37 pm, Kenneth Sloan wrote:

Here is a yahoo link:

http://news.yahoo.com/s/ap/20070719/...lving_checkers

Doesn't need a password.

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


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

"help bot" wrote in message
oups.com...
On Jul 20, 3:05 am, " wrote:
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/...ain-9-l7&idq=/...


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.


I would also wonder what rules were in effect when the game of Checkers was
reportedly solved.

Specifically, did they use the mandatory capture or optional capture rules?
Mandatory capture apparently allows for "huffing", that is, one player can
remove an opponent palyer's checker that did not make a capture when had an
open opportunity to capture.

help bot wrote:


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

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.



--
Kenneth Sloan
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/

Daniel W. Rouse Jr. wrote:

Specifically, did they use the mandatory capture or optional capture rules?

English draughts / American checkers rules.
http://en.wikipedia.org/wiki/Draughts

Mandatory capture apparently allows for "huffing", that is, one player can
remove an opponent palyer's checker that did not make a capture when had an
open opportunity to capture.

I believe that tournament rules only allow the opponent to point
out that an illegal move was made, with the usual touch rules.

On Jul 20, 6:34 pm, Kenneth Sloan wrote:
help bot wrote:

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

I disagree. It looks to me like bad reporting.


That is precisely what I mean by empty hype.


this research team is rock solid and I trust their papers.


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.


the trouble is - all I've seen so
far are the news reports - NOT the paper.


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 objecting to the gloss - not questioning the result.


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


-- help bot

help bot wrote:
Kenneth Sloan wrote:
this research team is rock solid and I trust their papers.

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.

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.

--
David Richerby Accelerated Tongs (TM): it's like a
www.chiark.greenend.org.uk/~davidr/ pair of tongs but it's twice as fast!

David Richerby wrote:
help bot wrote:
Kenneth Sloan wrote:
this research team is rock solid and I trust their papers.
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.

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.



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

--
Kenneth Sloan
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/

Kenneth Sloan wrote:
David Richerby wrote:
They wouldn't be publishing partial results in _Science_ under the
title ``Checkers is Solved.'' [...] See
http://chinook.cs.ualberta.ca/users/chinook/index.html
for a demonstration.

a) don't believe everything you read in "Science"

Of course.

b) we don't want a demonstration - we want a proof.

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.

--
David Richerby Love Tool (TM): it's like a hammer
www.chiark.greenend.org.uk/~davidr/ that you can share with someone
special!

David Richerby wrote:
Kenneth Sloan wrote:
David Richerby wrote:
They wouldn't be publishing partial results in _Science_ under the
title ``Checkers is Solved.'' [...] See
http://chinook.cs.ualberta.ca/users/chinook/index.html
for a demonstration.
a) don't believe everything you read in "Science"

Of course.

b) we don't want a demonstration - we want a proof.

Of course. But the paper hasn't been published yet and isn't
available on the project website.

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?

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.


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



--
Kenneth Sloan
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://www.cis.uab.edu/sloan/