[ExI] Computer Plays "Perfect Checkers"?

[Lee Corbin]

My comments below.  Taken from 
http://www.cnn.com/2007/TECH/07/20/computer.checkers.ap/index.html


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

"Clearly ... the world is not going to be revolutionized" by this,
said Jonathan Schaeffer, chairman of the department of computing
science at the University of Alberta.

The important thing is the approach, he said. In the past, game-
playing programs have used rules of thumb -- which are right most of
the time, he said -- to make decisions.

"What we've done is show that you can take nontrivial problems,
very large problems, and you can do the same kind of reasoning with
perfection. There is no error in the Chinook result. ... Every decision
point is 100 percent."

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.

"'Checkers is solved' is an intriguing title for this wonderful and delightful
article about another former human skill falling to the ubiquitous computer,"
said Ernest L. Hall, director of the Center for Robotics at the University
of Cincinnati.

That does not mean an end to people playing checkers, said Hall,
who was not part of Schaeffer's research team. Even though a
computer beat the world chess champion, people still enjoy and
play the that game.

"Anything we can do to encourage the further study of science and
engineering, of developing problem solvers for the many known
needs of the world, should be encouraged," Hall said. "So I applaud
Schaeffer for making a breakthrough in computer problem solving
for the game of checkers. It may encourage others to solve the other
games we encounter in life."

Schaeffer's proof is what is called a "weakly solved" result. It calculates
the result from an initial position -- 10 pieces on the
board -- rather than from the beginning of the game.

Could Schaeffer's team produce a "strong solution" by calculating every
position from the beginning of a game? Maybe, but there is
not enough computer power available, he said. It took more
than 18 years to get where they are now.

How about chess? Current chess computers still rely on rules of
thumb rather than trying to study every possible position, Schaeffer
noted.

"Checkers has roughly the square root of the number of positions in
chess," the researchers said. "Given the effort required to solve checkers,
chess will remain unsolved for a long time, barring the invention of
new technology."


It's not clear to *me* that their computer can play perfect
checkers.  I may have to read the entire article itself, which
I haven't had time to do. For one thing, it may be that before
one of the endgame positions is reached---ten pieces, it said
---the computer could already find itself in a lost position
(not that any human may be able to discover such a fine line
of play, but, say, at the hands of another, program one 
perhaps not as yet written).

This certainly is the situation in chess, where the programs
have indeed already solved up all six-piece endings (or
some such number, it changes all the time of course).
But obviously when they do lose---either to each other
or to a human---it's because they've made mistakes
long before getting to the endgame (on the extremely
reasonable assumption that neither white nor black
has a forced win in chess from the beginning position).

Lee