It's possible to enumerate legal positions exactly:
http://homepages.cwi.nl/~tromp/go/legal.html
Any legal position can be obtained if players are allowed to pass... just
put down the black stones while white passes, then put down the white stones
while black passes.
--Luke Gustafson
----- Original Message -----
From: "Don Dailey" <[EMAIL PROTECTED]>
To: "David Doshay" <[EMAIL PROTECTED]>
Cc: "computer-go" <[email protected]>
Sent: Saturday, October 14, 2006 4:16 PM
Subject: Re: [computer-go] A plan for building a 7x7 GO solver.
On Sat, 2006-10-14 at 11:49 -0700, David Doshay wrote:
I don't understand this ... isn't the number 8?
The number is 16 if you consider canonical states because every position
has a canonically equivalent position with stone colors reversed.
But for a database-like application, one must also consider who's turn
to move it is which doubles the number of positions.
So it's probably 8 as you say since you can't cheat by using color
reversals in a database.
One way to reduce the size of the database further is to only store a
subset of positions. You want to store a subset that allows you to
still be able to bridge from one position to another with a search.
For instance, we could store only black to move positions, and with a
complete database we would have only to search 2 ply to get a perfect
move.
We can store even less positions by storing only position that have some
multiple of N stones. For instance, if you store only positions that
have 5, 10, 15, 20 ... stones, you have reduced the database
significantly, but have required much more searching.
The problem with ANY of this is what kind of table to build. Hash
tables are expensive and it's better if you can construct a perfect hash
function so that you do not have to store the keys. But with
rotations, reflections and canonical representations a simple indexing
function has many holes in it, which is a huge waste of space.
That is what gave me the idea of using bloom filters. With my scheme
(which I suspect is not workable) you can limit what you store using any
tricks you choose and represent the missing items fairly compactly.
The problem of course is finding a function that can score 5x5 positions
accurately a (very) high percentage of the time. But if you can solve
this, you probably are well on your way to a search based solution any
way. :-(
I am still tempted to try to make this kind of database because I think
it will teach me how to build an accurate evaluation function. I would
probably very quickly zero in on the biggest problems and hopeful find
lots of solutions. You would find ways to estimate scores that gave the
right answer quite frequently and then perhaps find ways to refine this
to improve the accuracy.
"End game database" are normally built using a technique called
"retrograde analysis" where you start with solved known positions at the
end of the game and work backwards iteratively. But I have figured out
a simple way to build it that will avoid any positions that are illegal,
or impossible to get to.
One question I have for the group: Are there legal GO positions that
are impossible to obtain from the opening position? There are in
chess. For instance you can't swap the position of the king and queen
while all pawns are on their original squares - etc. This would
reduce the number of positions if it's the case.
Another question is how many illegal board configurations are there as a
percentage? Does anyone know of any analysis on this? One could
probably estimate this by assigning each point on the board a random
state of (white,black,empty) and sampling the number of legal vs illegal
positions. This could make the bloom filter idea more attractive if
the percentage of illegal positions is really high.
This is more of a dream than a serious proposal. My intuition is that
I probably can't get the serious memory reduction I need to make it
practical on my current computer.
I'm not really interested that much in 5x5 - but I could use the same
techniques to build a "bad move" filter. My idea is to be able to
identify a lot of worthless moves in an admissible way, perhaps using
5x5 patterns or a more flexible approach. The principles would be
the same, have a procedure that is good at returning the correct answer
but doesn't have to be perfect - a bloom filter will veto the few
incorrect answers.
- Don
Cheers,
David
On 12, Oct 2006, at 11:38 AM, Don Dailey wrote:
> 1 canonical position per 16
> equivalent states. The actual number is less than 16.
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
