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/