Awesome. I believe similar aproach also in game of Go.
I short that there is no limit how smartly you can store information and thats
why I believe Erik e.t.c research in small board sizes is important and why I
have tried to study TSP kernighan kind of algorithms those don't search even
1/1000000.. of all possible routes in big problem instances.
For example if some patterns say from 1000000 board positions that Black is
winning thats is end of search
in that branch. Like it was in this group earlier "random" position is allmost
end position in go game and so on and believe such facts minimize "impossible
looking" search space enought and make search possible in near future atleast
in 9*9 board.
> "Of the 5 x 1020 possible positions, Schaeffer needed to evaluate only 1014
> to prove that checkers, played perfectly, results in a draw."
Even similar things are lot harder in game of go, but there is "living groups"
you can prove you can get minimun scores for white and black and atleast in
theory you can reduce search space a lot. In NaruGo project goal is generate
patters which make search faster to found new better patterns and repeat that.
http://sourceforge.net/projects/narugo
t. harri
----- Original Message -----
From: terry mcintyre
To: computer-go
Sent: Thursday, July 19, 2007 11:31 PM
Subject: Re: [computer-go] Draughts / Checkers solved
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/
------------------------------------------------------------------------------
Got a little couch potato?
Check out fun summer activities for kids.
------------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
