Has Checkers been SOLVED?

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 a thousand years.

"The [Chinook] 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.

Source:

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

Here's an abstract of the Science article:

http://www.sciencemag.org/cgi/conten...c etype=HWCIT

or

http://tinyurl.com/33tyg6

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

The Chinook Checkers Supercomputer which did the work:

http://www.cs.ualberta.ca/~chinook/

While you're there, why not try your hand PLAYING against Chinook?!?

http://www.cs.ualberta.ca/~chinook/play/index.html

Brett
Bishop Berkeley's Phantasmagorical Chess Interface
http://www.bbbbbb.org/

Scientific American's summary of the claim that Checkers has been
SOLVED by computer analysis (and it is a draw when played perfectly by
both sides!)

http://www.sciam.com/article.cfm?art...8&chanID=sa007

=== begin quoted passage ===

July 19, 2007

Computers Solve Checkers-It's a Draw

King me! Top computer scientist proves perfect play leads to draw,
recounts battle for world championship, gets kinged

By JR Minkel

Jonathan Schaeffer's quest for the perfect game of checkers has ended.
The 50-year-old computer scientist from the University of Alberta in
Edmonton left human players in the dust more than a decade ago after a
trial by fire against the greatest checkers champion in history.

And now, after putting dozens of computers to work night and day for
18 years-jump, jump, jump-he says he has solved the game-king me!.
"The starting position, assuming no side makes a mistake, is a draw,"
he says.

Schaeffer's proof, described today in Science ... would make checkers
the most complex game yet solved by machines, beating out the checker-
stacking game Connect Four in difficulty by a factor of a million....

"It's a milestone," says Murray Campbell, a computer scientist at
IBM's T. J. Watson Research Center in Hawthorne, N.Y., and co-inventor
of the chess program Deep Blue. "He's stretched the state of the art."

Although technological limits prohibit analyzing each of the 500
billion billion possible arrangements that may appear on an eight-by-
eight checkerboard, Schaeffer and his team identified moves that
guaranteed the game would end in a draw no matter how tough the
competition.

Like any complicated mathematical proof, the result will have to
withstand scrutiny. But "it's close to 100 percent," says computer
scientist Jaap van den Herik of Maastricht University in the
Netherlands, who has seen the details. "He has never published
anything that was not completely true."

Opening Play: Walking a Precipice

Schaeffer's odyssey began in the late 1980s. He had written a top
chess program but IBM was on the verge of pouring its far vaster
resources into Deep Blue. "I like to be competitive," he says, so he
turned his attention elsewhere. "I naively thought I could solve the
game of checkers," he recalls. "You can teach somebody the rules in a
minute."

Setting out in 1989 with 16 megabytes of computer memory, he quickly
found that checkers, like chess, was too rich with possible positions
to dash off a solution. So he switched gears, vowing to topple
legendary checkers champion Marion Tinsley, who had lost only three
games in tournament play since 1950.

In 1992 Schaeffer's program Chinook took on Tinsley, who had resigned
as world champion when the American Checker Federation and English
Draughts Association temporarily refused to sanction the man-computer
matchup.

Tinsley was so good that his opponents played dull games in the hope
of securing at least a draw, according to Schaeffer; Chinook
apparently put the magic back in the game for the champ. "It played
brash, aggressive moves-it walked on the edge of a precipice,"
Scheaffer anthropomorphizes. "It would do things people looked at and
said, 'Man, is that program crazy?'"

The program actually beat Tinsley twice, but computer glitches led to
a forfeit that gave the human a 3-2 lead with two games left in a best-
of-40 match. Schaeffer set Chinook on an aggressive course to try to
recoup, resulting in another loss for the computer that cost it and
its creator the match, Schaeffer recounted in his book One Jump
Ahead....

=== end quoted passage ===

[Article concluded he
http://www.sciam.com/article.cfm?cha...mber=2&catID=1
]

Brett
Bishop Berkeley's Phantasmagorical Chess Interface
http://www.bbbbbb.org/