http://www.spectrum.ieee.org/jul07/5379 seems to be a fairly decent article
about the Chinook
teams' solving of the Checkers game.
To recap, they built an endgame database which has all board positions with 10
or fewer pieces. Once you reach the endgame database, you no longer expand the
tree; the solution is known.
Start from the root of the tree, one uses best-first search to narrow the
search to those positions which are in the endgame database.
"Of the 5 x
1020 possible positions,
Schaeffer needed to evaluate only
1014 to prove that checkers,
played perfectly, results in a draw."
Terry McIntyre <[EMAIL PROTECTED]>
They mean to govern well; but they mean to govern. They promise to be kind
masters; but they mean to be masters. -- Daniel Webster
----- Original Message ----
From: Álvaro Begué <[EMAIL PROTECTED]>
To: computer-go <computer-go@computer-go.org>
Sent: Thursday, July 19, 2007 1:17:59 PM
Subject: Re: [computer-go] Draughts / Checkers solved
On 7/19/07, Chris Fant <[EMAIL PROTECTED]> wrote:
> On 7/19/07, steve uurtamo <[EMAIL PROTECTED]> wrote:
> > my guess is that you are in fact missing something --
> > it seems unlikely that they enumerated _on disk_ all
> > possible games and their correct response moves.
> >
> > anything taking up less space than that would require
> > something more intelligent (or at least with a better
> > capacity to collapse situations) than brute force.
> >
> > please someone set me straight -- if it's simply a list,
> > generated one at a time, of board positions and response moves,
> > i'll have a merry laugh tonight.
> >
> > s.
>
>
> You would not need to enumerate positions that cannot be reached when
> neither player is playing perfect. Not sure how many that leaves.
That leaves about the square root of the total number of nodes, if you
are using a good heuristic to sort the moves.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
____________________________________________________________________________________
Take the Internet to Go: Yahoo!Go puts the Internet in your pocket: mail, news,
photos & more.
http://mobile.yahoo.com/go?refer=1GNXIC_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
