[ExI] Computer Plays "Perfect Checkers"?
lcorbin at rawbw.com
Sun Jul 22 23:00:25 UTC 2007
> On 7/20/07, Lee Corbin <lcorbin at rawbw.com> wrote:
>> My comments below. Taken from
> This has been discussed over at Slashdot with some interesting
> comments (and links),
> http://games.slashdot.org/games/07/07/19/1952211.shtml (341 comments)
The best thing I found there was this article:
Long-time world checkers champion Marion Tinsley consistently bested
all comers, losing only nine games in the 40 years following his 1954
crowning. He lost his world championship title to a computer program in
1994 and now that same program has become unbeatable; its creators have
proved that even a perfectly played game against it will end in a draw.
Jonathan Schaeffer and his team at the University of Alberta, Canada,
have been working on their program, called Chinook, since 1989, running
calculations on as many as 200 computers simultaneously. Schaeffer has
now announced that they have solved the game of American checkers,
which is played on an 8 by 8 board and is also known as English
The team directed Chinook so it didn't have to go through every one of
the 500 billion billion (5 * 1020) possible moves. Not all losing plays
needed to be analysed; instead, for each game position, Chinook needed
to work out only a move that would allow it to win. In the end, only
1/5,000,000 of the moves were computed.
As Chinook has worked out all relevant lines of play, it needs
virtually no time to 'think' to work out each perfect move in a game.
The results were announced today in the journal Science1. The paper and
supporting materials, including the ability to play Chinook, are
available on the web at http://www.cs.ualberta.ca/~chinook.
Jaap van den Herik, editor of the International Computer Games Journal,
calls the achievement "a truly significant advance in artificial
The solvability of a board game generally depends on two factors: the
number of possible positions, or 'state-space complexity', and the
difficulty of deciding on the best move, or 'decision complexity'.
Tic-tac-toe is simple on both counts - simple enough to be figured out
by children. Checkers, says van den Herik, is complex in both regards
(see 'How hard is your game').
Chess is even harder to solve than checkers, with a state-space
complexity of 1046. Decision complexity is difficult to quantify, but
it is clearly high for chess. Van den Herik thinks that chess will be
solved "not within our lives, but within the lives of our children - I
would say between 2060 and 2070".
"Twenty years ago, we thought chess was as an infinite game," notes van
den Herik. "But the proof of Schaeffer is one more signpost that we are
approaching the solution."
But Schaeffer says new tools are needed before that will happen. "Chess
and Go cannot be solved with the type of technology that we have
today," he says. The game of Go, as played on a 19 by 19 grid, is often
considered to be the hardest popular game to crack, with something like
10100 possible positions.
Game of Life
Schaeffer notes that his research has implications beyond the checkers
board. The same algorithms his team writes to solve games could be
helpful in searching other databases, such as vast lists of biological
information because, as he says, "At the core, they both reduce to the
same fundamental problem: large, compressed data sets that have to be
Thus what I wrote before along the lines of
> 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
seems quite unjustified. That article too carefully quotes actually knowledgeable
software types. Perhaps they've simply proved somehow that the program
can and will reduce *any* position (starting from the initial position with
itself playing black or white) to one of the ten-piece winning/drawing positions.
More information about the extropy-chat