I am definitely interested in this. The approach that might be interesting is a hybrid solver. I do not think the endgame database approach is very useful beyond 4x4 or possibly 5x5. Even if it's possible it's not particularly interesting except as an engineering feat.
5x5 was solved with a massive brute force search approach. Memory was used for large hash tables and endgames were scored early using Bensons algorithm, otherwise it would not have been feasible from what I understand. Although that's interesting, it's just a search. I would like to try something a little more clever (I'm just not clever enough to figure out what that should be!) I'm thinking perhaps in terms of a database assist. It would be interesting if we could come up with a small board scoring system that is very accurate. A database system might identify rules and exceptions that can be applied. For example, we have the eye rule in our monte carlo programs - although that is extremely powerful it's not 100% admissible - there are some exceptions although they probably occur only a fraction of a percent of the time. The eye rule would be powerful in a hybrid system because it is a fairly large class of positions where we can say, "never move to that point - it will never be the best move." A trivial way to include it in a hybrid system is to just put an entry in a table for the few times that is wrong. Or even better, try to determine the exact context where it's wrong. Perhaps it's never wrong in a 5x5 game? Tables like this can be stored compactly with bloom filters. Here is a question. How do you determine what a final board looks like? If you are actually building an endgame table, you start with all the final positions. But seki seems to be very difficult to identify. I'm doing a little experiment right now with small boards and a table with a few million hashed entries. I'm trying to store only perfect scores in this table but my definition is weak. I search a position using alpha/beta and if several iterations consecutively return the same score, I consider it a perfect score. I know this definition is subject to error. To handle ko, I ignore everything except simple ko. I don't store positions where the previous move was a single stone capture since it might be a simple ko. My hope is that long superko loops will be avoiding by some winning side. This is probably not a correct assumption, but I have read that it works on 5x5 and less - it's always better for one side to break the loop. The evaluation function is to consider every stone alive, and any empty intersection that touches only one color to belong to that color. The evaluation function is not really used though - except to identify perfect scores (where several search iterations return the same results.) In all the 4x4 examples I've seen, I've never seen a 3 iterations in a row return the same score unless it was correct. However, I'm using 4 in a row to determine that a score for a position is exact. If the last 4 iterations return the same score, I put the root position in the hash table as a perfect score. I sample the space randomly by making a random move after searching some position, so that it explores the full space eventually. This is not very systematic, but it's just for fun right now. - Don Harri Salakoski wrote: > > Has anyone did this before or has anybody thoughts about this? > I have done that for 4*4 and 3*3, my code is not in shape that it > could be used 5*5 but have high believes it is anyway possible used > for 6*6 some day. But this was discussed in this group earlier and > nothing new has occurred since then. > 7*7 is solved in ten years ... hahaa no need to reply that. You need > very good solver to proof that in this particular "middle" position > Black or White can archieve better than optimal score and no reason to > continue search. Bigger cut better.. > > Doing investigations in http://sourceforge.net/projects/narugo > project and happy to co-operate. > > t. hArri > > ----- Original Message ----- > *From:* Ben Lambrechts <mailto:[EMAIL PROTECTED]> > *To:* 'computer-go' <mailto:computer-go@computer-go.org> > *Sent:* Wednesday, November 07, 2007 9:03 PM > *Subject:* [computer-go] Solving Go > > I want to create a perfect player on board sizes 3x3, 5x5 and > maybe 7x7 and beyond. > > But I have no idea how to start. How do I create the move database > and how do I select the perfect move for every position? > > > > I know Go is solved on boards 5x5 and smaller, but there is no > program that plays by this perfect moves. > > > > Has anyone did this before or has anybody thoughts about this? > > > > Ben > > ------------------------------------------------------------------------ > _______________________________________________ > 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/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
