Ok, on 2x2 I get a consistent result now that I implemented PSK. It gives the same result with SSK too. It's a 1 point win for the first player. I'm not sure this is in agreement with other peoples findings. But it appears to be consistent. I can work my way through the game and it always returns the same score if I make the move(s) the search believes is best.
After black plays the first move, white's best response is to move to the opposite corner. Otherwise it's a 4 point win for black. Here are the parameters I use: 1. positional superko unless otherwise stated. 2. evaluation function: Each stone is alive - an empty point belongs to a player if only his stones touch it. 3. game over after 2 passes. 4. suicide illegal. 3x3 gives a black win by 9 points (the whole board.) If black plays first move on the edge (a2 for instance) then he wins by 3 points instead of 9. If black plays first move on corner, white wins by 9 points. Does anyone have any data to check these "facts" ?? It may try this with 4x4 after doing something to improve the move ordering. - 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/
