[ExI] Computer Plays "Perfect Checkers"?

[Lee Corbin]

Bryan writes

> On 7/20/07, Lee Corbin <lcorbin at rawbw.com> wrote:
>> My comments below.  Taken from
>> http://www.cnn.com/2007/TECH/07/20/computer.checkers.ap/index.html
> 
> 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:

http://www.nature.com/news/2007/070716/full/070716-13.html

which reads:

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

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

    Un-trivial pursuit

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

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.

Lee