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/...65.htm&sc=1333

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.


-- help bot

Since checkers can be shown to end in a draw (both white and black are
guaranteed a draw with perfect play), it is considered weakly solved.
Checkers is so far the "largest" of the board games to show this, I
believe.

help bot wrote:
To my mind, "solving" checkers would not simply mean being able to
handle any human or present computer opponent without losing;

They've done much more than that! They've demonstrated that the game
can be held to a draw against any possible opponent.


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.

That is a slightly stronger condition and I'm not sure exactly what
the UAlberta guys have done. At the very least, they can tell you
whether any position that can be reached from the initial position
according to the replies they would make is a win, loss or draw. (In
chess terms, if their computer would play 1.d4 all the time, it might
not be able to tell you about unreachable positions such as that after
1.e4.)


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.

Yes, checkers is very, very much simpler than chess. But it's still a
pretty complex game and far more complex than anything that's been
solved before.


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

They're claiming in scientific journals that they've solved it.
Nobody publish that claim if all they'd done was produce a very very
strong engine.


Dave.

--
David Richerby Hilarious Solar-Powered Clock (TM):
www.chiark.greenend.org.uk/~davidr/ it's like a clock but it doesn't
work in the dark and it's a bundle
of laughs!

On Jul 20, 7:19 am, David Richerby
wrote:

That is a slightly stronger condition and I'm not sure exactly what
the UAlberta guys have done. At the very least, they can tell you
whether any position that can be reached from the initial position
according to the replies they would make is a win, loss or draw. (In
chess terms, if their computer would play 1.d4 all the time, it might
not be able to tell you about unreachable positions such as that after
1.e4.)


I didn't read the link because I would have to sign up
and go through all that junk, just to read about checkers.
:D


Yes, checkers is very, very much simpler than chess. But it's still a
pretty complex game and far more complex than anything that's been
solved before.


Except... the human genome, for instance. And
developing "the bomb". The thing is, checkers is
a finite problem, so, unlike exploring space, you
know exactly how far you have to go to the end.


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

They're claiming in scientific journals that they've solved it.
Nobody publish that claim if all they'd done was produce a very very
strong engine.


Sanny would. And Sam Sloan. And Weaver Adams.


-- help bot

help bot wrote:

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


The last report I read said that checkers has been "weakly solved".
Positions with 10 checkers or fewer are completely solved.

I don't know how to reconcile this with the quote "the initial position
is a draw". I suspect it's a slight mis-quote. I can imagine a claim
that "the program can achieve at least a draw" - but that's not quite
the same thing.


--
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/

In article .com,
help bot wrote:

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.

They've done this.

Checkers is solved.

Kenneth Sloan wrote:
help bot wrote:

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


The last report I read said that checkers has been "weakly solved".
Positions with 10 checkers or fewer are completely solved.

I don't know how to reconcile this with the quote "the initial position
is a draw". I suspect it's a slight mis-quote. I can imagine a claim
that "the program can achieve at least a draw" - but that's not quite
the same thing.


Now that's just silly. What was I thinking...

--
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, 12:30 pm, Ron wrote:
In article .com,
help bot wrote:

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.

They've done this.

Checkers is solved.


So why are there people here saying just the opposite?
Adding on qualifiers?

"Solved", to me, means that every legal position has a
known result, and that every legal move leads to another
position which has a known result, and every capture
yields a simpler position, with a known result. NOT just
having a computer which can't be beaten (like say, Rybka).

In chess, which has been worked on for many decades,
they max out at about only seven men on the board! Add
one lousy isolated, blockaded, worthless Rook-pawn, and
the program draws a complete blank, requiring human
intelligence to intervene (as with the Whitaker game, which
I knew was a win, though not an easy one).

At the beginning of a game of checkers, there are 24 men
on the board, but most of them are blocked and can't yet
move. If, when a man reached the last row it merely scored
a point and then was removed, this would be fairly simple,
but instead the darned things promote to Kings, which can
move backwards. So, you get repetitions of position (yeck).


-- help bot

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