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/
