Hi Harri, I don't see a way to do anything larger than 5x5 as a table - and 5x5 is pushing it. Even if we had an arbitrary amount of memory it would take a vast amount of time to enumerate all the positions for anything larger than 5x5.
But I am more optimistic about some kind of practical solver based on some the ideas we both mentioned. It may be that even 7x7 is possible. You can test any idea based on scoring (but without 100% certainty) by doing a search of many positions at different depths looking for conflicting data, which would prove incorrectness. It's much more difficult to prove correctness. So such a practical solver might seem correct empirically, but difficult to prove correct. But that would satisfy me since I am looking for practical applications (such as building really strong small board players.) One approach I would like to try to is to gradually build up a set of rules (likely based on a combination of patterns and heuristics such as Bensons algorithm) that return a lower and upper bound on the score. For instance with 5x5 we can initially assign (-25, 25) as our upper and lower bounds for ALL positions. Rules to prune moves would also be extremely useful since this would be a search based solver. I think for this to be practical the bounds function has to be able to produce narrow bounds a lot and also it needs to be able to identify perfect scores a lot. To do 7x7 it has to produce trees with a branching factor much lower than 2 and that will be very difficult. But first I will have to grapple with some difficult problems. I am experimenting with tiny boards such as 2x2 and 3x3. Those are good because you can brute force search them without even needing transposition tables and without dealing with GHI. A brute force 2x2 search, using chinese scoring as the evaluation function and simple KO, does not produce a stable score. It alternates between 2 or 3 different values. I'm sure this is because I'm using simple KO, but I will experiment with PSK and SSK. A 3x3 board returns a score of 9, but if you play A2 and then search, the score is not stable, it will alternate between 2 scores from one iteration to the next. If I play forward from there, I get interesting patterns where one score repeats some number of times and then another score, then the pattern repeats. Again, I'm thinking that a good KO rule will solve this. I'll let you know. I'm not sure how to handle seki yet, I'm hoping the deep search approach will handle it on these small boards. To summarize, I'm hoping to build an evaluation function that returns a lower and upper bound for any position passed to it and furthermore I'm hoping that this evaluation function is admissibly correct. I might not be able to prove it's correct, but I can test each rule in a significant way and try to get a lot of empirical evidence that it's correct. - Don Harri Salakoski wrote: >> 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. > Yes it was "proof" level paper, doing something lot less > mathematically valid for example only some open source code which can > do good search against 7*7 is more realistic. Kind of allowing all > possible short-cuts, like using several patterns to judge board score > even it is not absolutely sure that score is right for combination of > patterns. > >> 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. > Agree that goal, scoring system must be accurate _when_ it thinks it > knows score. I see score meaning minimal score for player archieves > from this position if plays right. > >> 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." > But is this other class of used patterns also to guide search, I see > this estimator goal should proof minmum scores for player. > All kind of eye knowledge is offcourse important for minimal scoring > patterns. > >> 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? > I have thinked patterns which take area of board and proof that > another player can take "X" points from that area/group. > If that player has benson alive groups in other areas on board score > can be proven "benson alive groups" + one group which is not benson > alive but can be proven to get "X" points if only defending that group > for rest of 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 am planning partial table patterns. Seki and other consepts should > be used with patterns if possible. > >> 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. > Yep, such practical problems are intresting, but atleast those are > possible to fix as 5*5 and earlier proofs show. > > It can be intresting attack 7*7 from end positions side, trying to > make solver that gives exact score for part of positions and try to > "increase" that procent but keep score exact. When end position > scoring system is good enought then it could be possible try start > search from some near end middle positions. I don't know is anybody > really deebly investigated 7*7, kind of more like started existing go > programs search algorithms from scratch and gived up. I also lack of > 7*7 board knowledge, other hand 7*7 sounds practical, fast and light > board. > > t. harri > >> 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/ > > _______________________________________________ > 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/
