Note: This post contains information posted on the web by
magazines and newspapers and thus likely to go away soon,
So I reproduced the text here as an archive and added a tag
to the subject line to make it easy to find.

help bot wrote:

David Richerby wrote:

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

As I have not seen that magazine, I have no idea
whether or not "they" (whoever they are) would likely
place such an article under such a name.

The obvious google search [ checkers science magazine ]
[ http://www.google.com/search?q=Check...ience+magazine ]
brings you right to it:

-------------------------------------------------------
|
|ABSTRACT
|
|Published Online July 19, 2007
|Science DOI: 10.1126/science.1144079
|Submitted on April 20, 2007
|Accepted on July 6, 2007
|
|Checkers Is Solved
|Jonathan Schaeffer, Neil Burch, Yngvi Bjoson,
|Akihiro Kishimoto, Martin Mu1ler, Robert Lake,
|Paul Lu, Steve Sutphen
|
|1 Department of Computing Science, University of Alberta,
| Edmonton, Alberta T6G 2E8, Canada.
|
|* To whom correspondence should be addressed.
|Jonathan Schaeffer , E-mail: jonathan{at}cs.ualberta.ca
|
|The game of checkers has roughly 500 billion billion possible
|positions (5 x 1020). The task of solving the game, determining
|the final result in a game with no mistakes made by either player,
|is daunting. Since 1989, almost continuously, dozens of computers
|have been working on solving checkers, applying state-of-the-art
|artificial intelligence techniques to the proving process. This
|paper announces that checkers is now solved: perfect play by
|both sides leads to a draw. This is the most challenging popular
|game to be solved to date, roughly one million times more complex
|than Connect Four. Artificial intelligence technology has been
|used to generate strong heuristic-based game-playing programs,
|such as DEEP BLUE for chess. Solving a game takes this to the
|next level, by replacing the heuristics with perfection.
|
http://www.sciencemag.org/cgi/content/abstract/1144079
|
-------------------------------------------------------
|
|News of the Week
|Science 20 July 2007:
|Vol. 317. no. 5836, pp. 308 - 309
|DOI: 10.1126/science.317.5836.308a
|
|COMPUTER SCIENCE:
|Program Proves That Checkers, Perfectly Played, Is a No-Win
|Situation
|
|Adrian Cho
|
|If two players face off at checkers and neither makes a wrong
|move, then the game will inevitably end in a draw. That's the
|result of a proof executed by hundreds of computers over nearly
|2 decades and reported online by Science this week
|
http://www.sciencemag.org/cgi/conten.../317/5836/308a
|
-------------------------------------------------------
I also found these:

| NEW YORK TIMES
|
|Champion at Checkers That Cannot Lose to People
|By KENNETH CHANG
|Published: July 20, 2007
|
|Checkers has been solved.
|
|A computer program named Chinook vanquished its human competitors at
|tournaments more than a decade ago. But now, in an article published
|Thursday on the Web site of the journal Science, the scientists at the
|University of Alberta who developed the program report that they have
|rigorously proved that Chinook, in a slightly improved version, cannot
|ever lose. Any opponent, human or computer, no matter how skilled, can
|at best achieve a draw.
|
|In essence, that reduces checkers to the level of tic-tac-toe, for
|which the ideal game-playing strategy has been codified into an
|immutable strategy. But checkers -- or draughts, as it is known in
|Britain -- is the most complex game that has been solved to date, with
|some 500 billion billion possible board positions, compared with the
|765 possibilities in tic-tac-toe.
|
|Even with the advances in computers over the past two decades, it is
|still impossible, in practical terms, to compute moves for all 500
|billion billion board positions. So, the researchers took the usual
|starting position and looked only at the positions that occurred
|during play.
|
|"It's a computational proof," said Jonathan Schaeffer, a professor of
|computer science at the University of Alberta who led the effort.
|"It's certainly not a formal mathematical proof." That means it is
|impossible for anyone to check every calculation the computer has
|performed.
|
|Because of the vast calculations, the researchers had to keep
|painstaking track of the data. Miscopying a single bit -- a glitch that
|did occur every few months -- could render their result incorrect if
|not caught and corrected. When an error was caught, calculations had
|to be restarted from that point. A checkers hobbyist has independently
|verified major components of the proof with another computer program.
|
|Dr. Schaeffer began his quest in 1989, aiming to write software that
|could compete with top checkers players in the world. In April, 18
|years later, he and his colleagues finished their computations.
|
|"From my point of view, thank God it's over," Dr. Schaeffer said.
|
|For an exercise in futility, anyone can play a game against the
|perfect Chinook at http://www.cs.ualberta.ca/~chinook/play/. (It is
|limited to 24 games at a time.)
|
|The earlier incarnation of Chinook, relying on artificial intelligence
|techniques and the combined computing power of many computers, placed
|second in the 1990 United States championship behind Marion Tinsley,
|the world champion, who had won every tournament he had played in
|since 1950.
|
|That achievement should have earned Chinook the right to challenge Dr.
|Tinsley, a professor of mathematics at Florida A&M University, for the
|world championship, but the American Checkers Federation and the
|English Draughts Association refused to sanction a match. After much
|wrangling in the checkers world, Dr. Tinsley and Chinook battled for
|the man-versus-machine checkers title in 1992.
|
|Dr. Tinsley won, 4 to 2 with 33 draws. Chinook's two wins were only
|the sixth and seventh losses for Dr. Tinsley since 1950. In a rematch
|two years later, Dr. Tinsley withdrew after six draws, citing health
|reasons. Cancer was diagnosed, and Dr. Tinsley died seven months
|later.
|
|Chinook easily triumphed over other human challengers, but the
|unfinished match against Dr. Tinsley left lingering doubt whether
|Chinook could claim to be the best of all time.
|
|The new research proves that Chinook is invincible in traditional
|checkers. In most tournament play, however, a match now starts with
|three moves chosen at random. In solving the traditional game, the
|researchers have also solved 21 of the 156 three-move openings,
|leaving some hope for humans.
|
|Alexander Moiseyev, the current world champion in what is known as
|three-move checkers, has never faced Chinook. He said he used
|computers to study and analyze games but did not play against them,
|and he readily conceded that people were no longer worthy competitors
|for computers.
|
|"This time is over today," he said. "It doesn't bother me." The next
|game Dr. Schaeffer hopes to conquer is poker, which is harder to
|solve, because players do not have complete knowledge of their
|opponents' positions. Next week, his program, Polaris, will take on
|two professional poker players in Texas Hold 'Em for the $50,000
|man-versus-machine world championship.
|
|Soon, computers may not just be winning games, but taking people's
|money, too.
|
http://www.nytimes.com/2007/07/20/sc...=1&oref=slogin
|
-------------------------------------------------------
|
|INFORMATION WEEK
|Canadian Programmers Claim Their Checkers Program Is Unbeatable
|
|Software developers at the University of Alberta say they've 'solved'
|checkers by developing a program that's guaranteed to never lose.
|
|By K.C. Jones
|InformationWeek
|July 20, 2007 11:58 AM
|
|Software developers in the department of computing at the University
|of Alberta say they've perfected a checkers program so powerful that
|human competitors can never win.
|
|The developers said the best players can do against the improved and
|"unbeatable" Chinook is to end the game in a tie.
|
|"Checkers is solved," they pronounced in a statement on their Web
|site.
|
|From the starting position, black (which moves first) can only draw
|against a perfect opponent, and white (which moves second) is also
|guaranteed a draw, regardless of what black plays as the opening move,
|developers said.
|
|"This is the largest non-trivial game of skill to be solved," the
|developers said. "It is more than one million times bigger than
|Connect Four and Awari."
|
|Connect Four and Awari were the biggest and most complex games solved
|before Chinook became unbeatable at traditional checkers, called
|draughts in England. A traditional game of checkers allows for
|three-move openings and about 500 billion total board positions for
|the duration of the game. The developers' claims come from a computer
|proof, not a mathematical one.
|
|Developers began work on the Chinook program in 1989 in an attempt to
|build a program that could beat the human World Checkers Champion.
|Chinook suffered a narrow loss to the world checkers champion in 1992,
|but limited the champion to draws in 1994. Two years later, Chinook
|proved stronger than people and retired. Chinook won the World
|Man-Machine Championship, three years before the Deep Blue chess
|match, marking a milestone in the history of artificial intelligence.
|
|Those who want to challenge Chinook can test their mettle online.
|
http://www.informationweek.com/story...leID=201200179
|
-------------------------------------------------------

Interesting. This "strategy" was never mentioned in
the article I read; that article stated flatly that the
"scientists" were moving on, having settled on a
partial solving of checkers, and placing the blame
for their partial failure on a lack of computer power.

All I can say is that the sources quoted above seem to be
authoritative.

--
Guy Macon
http://www.guymacon.com/

On Jul 23, 4:10 pm, Guy Macon http://www.guymacon.com/ wrote:

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

As I have not seen that magazine, I have no idea
whether or not "they" (whoever they are) would likely
place such an article under such a name.

The obvious google search [ checkers science magazine ]
[http://www.google.com/search?q=Check...ence+magazine]
brings you right to it:


Er, no it doesn't! That search yields nearly 1.5 million
hits from which to choose. LOL!



|The game of checkers has roughly 500 billion billion


Uh, this should I think be 500 quadrillion, not any
"billion billion" or "million million million", etc. :D



possible
|positions (5 x 1020). The task of solving the game, determining
|the final result in a game with no mistakes made by either player,
|is daunting. Since 1989, almost continuously, dozens of computers
|have been working on solving checkers, applying state-of-the-art
|artificial intelligence techniques to the proving process. This
|paper announces that checkers is now solved: perfect play by
|both sides leads to a draw. This is the most challenging popular
|game to be solved to date,


Another item posted here put that as "problem",
rather than "game" -- a gigantic difference. --Ed.



roughly one million times more complex
|than Connect Four. Artificial intelligence technology has been
|used to generate strong heuristic-based game-playing programs,
|such as DEEP BLUE for chess. Solving a game takes this to the
|next level, by replacing the heuristics with perfection.


|In essence, that reduces checkers to the level of tic-tac-toe, for
|which the ideal game-playing strategy has been codified into an
|immutable strategy. But checkers -- or draughts, as it is known in
|Britain -- is the most complex game that has been solved to date, with
|some 500 billion billion possible board positions, compared with the
|765 possibilities in tic-tac-toe.


Note how the rough guesstimate numbers yield a
distinct impression of approximation, not "perfection".


|Even with the advances in computers over the past two decades, it is
|still impossible, in practical terms, to compute moves for all 500
|billion billion board positions. So, the researchers took the usual
|starting position and looked only at the positions that occurred
|during play.


Unclear. Does this imply they examined only
checkers positions which occurred in tournament
play between checkers masters, or all legally
possible checkers positions which can be reached
via a sequence of legal moves?


|"It's a computational proof," said Jonathan Schaeffer, a professor of
|computer science at the University of Alberta who led the effort.
|"It's certainly not a formal mathematical proof." That means it is
|impossible for anyone to check every calculation the computer has
|performed.
|
|Because of the vast calculations, the researchers had to keep
|painstaking track of the data. Miscopying a single bit -- a glitch that
|did occur every few months -- could render their result incorrect if
|not caught and corrected. When an error was caught, calculations had
|to be restarted from that point. A checkers hobbyist has independently
|verified major components of the proof with another computer program.


Note how the "hobbyist" goes unnamed, as does
his program and just about anything anybody might
want to know in order to verify if these claims are
truly airtight. Coincidence? Maybe... .


|Dr. Schaeffer began his quest in 1989, aiming to write software that
|could compete with top checkers players in the world. In April, 18
|years later, he and his colleagues finished their computations.
|
|"From my point of view, thank God it's over," Dr. Schaeffer said.
|
|For an exercise in futility, anyone can play a game against the
|perfect Chinook athttp://www.cs.ualberta.ca/~chinook/play/. (It is
|limited to 24 games at a time.)


That's okay. I generally play no more than nineteen or
twenty checkers games at a time myself. ;D



|Dr. Tinsley won, 4 to 2 with 33 draws. Chinook's two wins were only
|the sixth and seventh losses for Dr. Tinsley since 1950. In a rematch
|two years later, Dr. Tinsley withdrew after six draws, citing health
|reasons. Cancer was diagnosed, and Dr. Tinsley died seven months
|later.
|
|Chinook easily triumphed over other human challengers


(...if you look over all the draws...)


, but the
|unfinished match against Dr. Tinsley left lingering doubt whether
|Chinook could claim to be the best of all time.
|
|The new research proves that Chinook is invincible in traditional
|checkers. In most tournament play, however, a match now starts with
|three moves chosen at random. In solving the traditional game, the
|researchers have also solved 21 of the 156 three-move openings,
|leaving some hope for humans.


There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

I think the conclusion is that these guys are
confident that no human or computer will ever
beat their machine from now on, and are moving
on, satisfied with less than perfection.


-- help bot

help bot wrote:

Guy Macon http://www.guymacon.com/ wrote:

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

As I have not seen that magazine, I have no idea
whether or not "they" (whoever they are) would likely
place such an article under such a name.

The obvious google search [ checkers science magazine ]
[http://www.google.com/search?q=Check...ence+magazine]
brings you right to it:

Er, no it doesn't! That search yields nearly 1.5 million
hits from which to choose. LOL!

The VERY FIRST ONE was _Science_ magazine (Google even gives
you a special "I'm feeling lucky" button...) and ONE CLICK
brought me to the title "Checkers is Solved" I would have
taken you less time to do that then to write the paragraph
above confessing your ignorance.

The rest of your comments are arguing with the wording
of newspaper and magazine articles. Feel free to address
any criticisms of them to the respective authors.

--
Guy Macon
http://www.guymacon.com/

On Jul 23, 8:41 pm, Guy Macon http://www.guymacon.com/ wrote:

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

As I have not seen that magazine, I have no idea
whether or not "they" (whoever they are) would likely
place such an article under such a name.

The obvious google search [ checkers science magazine ]
[http://www.google.com/search?q=Check...ence+magazine]
brings you right to it:

Er, no it doesn't! That search yields nearly 1.5 million
hits from which to choose. LOL!

The VERY FIRST ONE was _Science_ magazine (Google even gives
you a special "I'm feeling lucky" button...) and ONE CLICK
brought me to the title "Checkers is Solved"


Hmm. One chance out of nearly 1.5 million, and you
got lucky! ;D


I would have
taken you less time to do that then to write the paragraph
above confessing your ignorance.


Speaking of ignorance, I think what you meant to
say was "*It* would have taken you less time to do
that *than* to write the post", but then, such
differences may be too subtle for your sort of mind.

The point of my comments was not to suggest that
the article was difficult to locate; on the contrary, I
merely pointed out how your statement was in error.
As far as I know, the magazine in question can be
found at my local Wal-mart, so that is not the issue.


The rest of your comments are arguing with the wording
of newspaper and magazine articles.


Nah, I don't usually argue with magazine articles
because they can't reason or respond intelligently
(much like IM Innes!); what I did was simply observe
and comment on the hype surrounding this stuff; in
particular, the choice of "solved" I find to be rather
misleading. So, what would have been a better way
to describe an unbeatable machine? Well, how
about "Checkers program now unbeatable" for a
headline? Of course, with Mr. Tinsley out of the
way, this doesn't involve much in the way of risk.

To my mind, many programmers are riding the wave
of the increased power and speed of computers, and
taking as much of the credit for this as they can get
away with. Were it not for technical difficulties, we
could very easily cut through all the bull by loading
the newer programs onto the old hardware, to see
how they fare in direct comparison to their forebears.


Feel free to address
any criticisms of them to the respective authors.


Right. I'm going to track down every author of every
article mentioned here in rgc, and give them a piece
of my mind. LOL


-- help bot

There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

This is a misinterpretation of the results. The Chinook team proved
checkers is a draw from *the starting position* or so called "go as
you please" play. The 156 checker openings are ballots used in the 3-
move restriction style of play, where the first three plies (2 red
moves, one white move) are pre-determined. The Chinook team is not
saying that they have solved all of these, but they don't need to in
order to claim that unrestricted checkers is a draw.

"help bot" wrote in message
oups.com...
On Jul 23, 4:10 pm, Guy Macon http://www.guymacon.com/ wrote:




, but the
|unfinished match against Dr. Tinsley left lingering doubt whether
|Chinook could claim to be the best of all time.
|
|The new research proves that Chinook is invincible in traditional
|checkers. In most tournament play, however, a match now starts with
|three moves chosen at random. In solving the traditional game, the
|researchers have also solved 21 of the 156 three-move openings,
|leaving some hope for humans.


There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely?

Because you can force a draw without reaching
the positions that they haven't calculated.

seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.


In traditional checkers, also called
Go As You Please (GAYP), any
legal move is possible. The version of
the game that starts from one of 156
positions selected at random and has
not (yet) been solved. In fact, the
openings contained in the proof are
not the best in practical play.



I think the conclusion is that these guys are
confident that no human or computer will ever
beat their machine from now on, and are moving
on, satisfied with less than perfection.


No. Checkers has been understood to
be a draw for at least a century, and computers
have been unbeatable for ~10. What has been
done here is to document the path from starting
position to draw. So GAYP is a proven draw.

On Jul 24, 10:53 am, "
wrote:
There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

This is a misinterpretation of the results. The Chinook team proved
checkers is a draw from *the starting position* or so called "go as
you please" play. The 156 checker openings are ballots used in the 3-
move restriction style of play, where the first three plies (2 red
moves, one white move) are pre-determined. The Chinook team is not
saying that they have solved all of these, but they don't need to in
order to claim that unrestricted checkers is a draw.

Exactly. To put it in chess terms, this would be like a computer
program that proves that it can always win or draw at chess with the
white pieces. Every game, it starts with 1. e4, and it never loses,
then help bot comes along and says "But it didn't prove that chess is
solved, because it's not proven for games starting with 1. d4."

--Richard

On Jul 24, 10:53 am, "
wrote:

There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

This is a misinterpretation of the results. The Chinook team proved
checkers is a draw from *the starting position* or so called "go as
you please" play. The 156 checker openings are ballots used in the 3-
move restriction style of play, where the first three plies (2 red
moves, one white move) are pre-determined. The Chinook team is not
saying that they have solved all of these, but they don't need to in
order to claim that unrestricted checkers is a draw.


I see. If I read you correctly, this is akin to Gary
Kasparov stating that he has solved chess, and it
is a draw. BUT... if you play, say, 1.f4 or 1.h3 or
1.Na3, he has no clue as to the game's proper
result; you must therefore stick to his narrow 1.e4!
[Sicilian Defense!!] analysis or else he is lost in a
fog, 'cause he just doesn't "get" the closed openings.
:D


-- help bot

On Jul 24, 12:59 pm, "David Kane" wrote:

|The new research proves that Chinook is invincible in traditional
|checkers. In most tournament play, however, a match now starts with
|three moves chosen at random. In solving the traditional game, the
|researchers have also solved 21 of the 156 three-move openings,
|leaving some hope for humans.

There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely?

Because you can force a draw without reaching
the positions that they haven't calculated.


But this only proves that Chinook is invincible, which
is not the same as "solving" checkers; if you mean
only solving for the result (win, loss, draw), fine. But
to me, solving is more than just that. In chess, one
could claim to have calculated the best line of play in
every conceivable opening, and that it is a draw, but
this leaves much to be desired; what is desired is to
know the best move in every position AND the result
with best play AND maybe also the distance to
conversion. If we must sacrifice something, let it be
only the massive move trees, which understandably,
cannot be kept watered and fertilized and free of
insects forever.


Here's what makes me question all these accounts:
every one which didn't merely summarize, but instead
included direct quotes, inserted all sorts of qualifiers
which pulled back from the headline (Checkers is solved!).
Real science requires no such waffling of this sort. In
real science, a headline which reads "Gold from lead!"
would read simply as a process in which lead is
converted into gold (without need to add platinum or
diamonds or even silver).


seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

In traditional checkers, also called
Go As You Please (GAYP), any
legal move is possible. The version of
the game that starts from one of 156
positions selected at random and has
not (yet) been solved. In fact, the
openings contained in the proof are
not the best in practical play.


Same with chess!


I think the conclusion is that these guys are
confident that no human or computer will ever
beat their machine from now on, and are moving
on, satisfied with less than perfection.

No. Checkers has been understood to
be a draw for at least a century


So has chess, but this was merely an assumption,
not a fact.


and computers have been unbeatable for ~10.


You must mean unbeaten. Obviously, any
program which is not perfect can be beaten, if
you simply write a superior program. Another
way is to have the program play itself (thinking
on opponent's time = off), and give one side
much more time than the other.


What has been
done here is to document the path from starting
position to draw. So GAYP is a proven draw.


Okay. The link posted earlier went to a checkers
program where the user was invited to test his skill
against the improved Chinook program; this was not
very convincing, and reminded me of somebody
setting up a chess Web site and inviting all comers
to try and beat him (i.e. Rybka). Obviously, anyone
could do that and no one alive could even hope to
win a single game.

The closest thing I have seen to a proof is one
statement that 10 men were solved, and an engine
of some sort cranked away from the opening while
accessing this database... yet they did not claim
to have tackled the whole analysis tree, and this
fell right in line with all the other accounts which
pulled away from the headline.

In one of the earliest linked-to articles, the word
solved was used interchangeably with partly-solved,
or as we in the chess world would understand it, not
really solved at all... .


-- help bot

On Jul 24, 1:24 pm, Richard wrote:
On Jul 24, 10:53 am, "
wrote:

There it is. How on earth can it be possible to
solve 21 out of 156 checkers openings instead of
156 out of 156 UNLESS they have not really
solved checkers completely? This also would
seem to explain the strange comments posted
here earlier, which suggested the same thing by
misusing the term solved to mean partly-solved.

This is a misinterpretation of the results. The Chinook team proved
checkers is a draw from *the starting position* or so called "go as
you please" play. The 156 checker openings are ballots used in the 3-
move restriction style of play, where the first three plies (2 red
moves, one white move) are pre-determined. The Chinook team is not
saying that they have solved all of these, but they don't need to in
order to claim that unrestricted checkers is a draw.

Exactly. To put it in chess terms, this would be like a computer
program that proves that it can always win or draw at chess with the
white pieces. Every game, it starts with 1. e4, and it never loses,
then help bot comes along and says "But it didn't prove that chess is
solved, because it's not proven for games starting with 1. d4."


Precisely. The claim "checkers is solved" is
misleading. What is commonly understood as
"checkers drawn with correct play" is hardly the
same as actually solving the game.


Da Vinci Helicopter Flies Atlantic! (in theory)

Fischer Busts King's Gambit! (on paper)

Tal Sacrifices Proved Unsound! (after the games)



I may yet be forced to admit that checkers has
indeed been "solved", but I doubt it. I'd sooner
admit that the French Defense is sound, or that
Bxh2 was just a miscalculation.


-- help bot