Thanks both. I guess reading over my message it was a bit ambiguous since I could have meant either liberty counts i.e.. |liberty| or the actual contents of the liberty set. I actually meant the latter.
When it comes to liberty counts- the only system I know of (which I read about here) was to not have precise liberty counts but rather have a situation which you guarantee that the liberties reach 0 at the same time a liberty count would. I think the term used here was pseudo-liberties. This makes merging easy but I am curious how are merges handled if you have precise liberty counts. I assume that one would have to walk the stones in a given chain after you perform the addition and subtract one for each duplicate. --- On Fri, 8/14/09, Don Dailey <[email protected]> wrote: > From: Don Dailey <[email protected]> > Subject: Re: [computer-go] representing liberties > To: "computer-go" <[email protected]> > Date: Friday, August 14, 2009, 6:16 PM > I'm not sure I understand your > question. But I'll try to explain it a little > better. > > Basically, you keep a C structure or the equivalent which > tracks each individual chain. On your board array you > put the index of that structure (or a pointer to it.) > > > The structure will look something like this: > > typedef struct > { > int color; > int stone_count; > int head_stone; > int liberty_count; > > } chain_t; > > And perhaps other crap you may want to keep. > > > So lets say you have an array of these, one for each chain > on the board with room to grow. > > When you place a stone on the board, you look at the 4 > neighbors to see if this is going to be a new chain of 1, or > connect to an existing chain. If it's an existing > chain, you will need to create a brand new entry, set the > stone_count to 1, the liberty count to 1, 2, 3 or 4 (by > looking at the 4 surrounding points) and set the > head_stone to the location of the new stone. the > head_stone can be ANY stone in the group - it's just a > way to quickly reference one of the stones in the group. > > > Your board of course will have the index of the > chain_t. I start at 1 and make zero mean empty but you > could use -1 to represent empty squares if you want to. > So if the value of the board array is 5, it means it is > the 5th chain in the chain_t array and you can immediately > see how many stones are there, how many liberties etc. > > > The logic for updating the liberty count is pretty basic. > When you place a stone next to an existing group, you know > that group loses 1 liberty, so you subtract 1 from ANY group > of either color that touches it (there can only be 4 at > most.) But then you must check to see if the stone > you just placed created liberties for the group it belongs > to. So you count the empty points around the new stone > that do not already belong to that same group. > (There is also the case where 2 chains must be merged, but > we will ignore that for now.) > > > When a group is captured, you must do a bit more > housekeeping. You need to delete it's entry somewhow > in the chain array and you will have to recalculate the > liberties for any enemy chain that is currently touching any > of the captured stones. This is not as hard as it seems > once you work it out. > > > One way to delete the entry is to just set the stone_count > to zero for instance. You may want to > "compress" the chain list from time to time but if > you make the list big enough, you will be able to complete > one or more playouts without needing to do this. You > could also keep a "free list" so that you > immediately re-use entries - that's probably what I > would recommend because it's real simple and the free > list will never grow very large. > > > How do you unmake moves? I suggest that you > don't. Instead, making a move should either be by > state copy, or if you know you will never need to unmake a > move (such as when doing fast playouts) you don't have > to worry about it. But of course you will still want > to keep some original copy to track the state of the actual > game. > > > So your should wrap your whole game state up into a neat > little package and operate only on those. You will be > thankful if you ever decide to go with parallel processing > for instance. > > So to make a move you might have something like this in C, > this is non-object oriented version: > > > int make( const position *original_state, position > *new_state, move_type mv ) > { > *new_state = *original_state; > > status = low_level_make( new_state, mv ); > return status; > > } > > The "position" object is a C structure that has > the entire board, chain lists and move history. The move > history can be implemented as a pointer to previous move > states. > > So in any kind of recursive search situation, you are > simply passing position states down the tree, never having > to unmake a move. In the playouts you don't even > have to copy state. > > > With this data structure you can also easily iterate > through the chains without having to loop over every point > on the board. In fact you can always know exactly how > many chains are on the board of either color and do > something wth them if needed. Or you can quickly count > the number of stones on the board (of course if you wanted > to you could keep this in a separate counter in the position > state.) > > > When you make captures you will need to hit every stone. > I use a recursive flood fill type of routine to do this. > I know that some programs keep linked lists of stones - > I'm not sure if that is worth the trouble and extra > space. Mabye it is. I think I figured out that you > rarely have to go through every stone, mainly in > captures. > > > > Ok, now my disclaimer. There are some very experienced > go programmer here and they may find this naive or > silly. My reference bots do not use this, they just do > the dumb thing - a single flat array the represents the > board and the stones on it. > > > > - Don > > > > > > > > > > > > > > > > On Fri, Aug 14, 2009 at 6:10 PM, > Carter Cheng <[email protected]> > wrote: > > So to determine where the last two > liberties for a group of stones for example is the obvious > method of just doing it to have some method of liberty > counting + a exhaustive search to determine the last two > liberties for example? > > > > > --- On Fri, 8/14/09, Don Dailey <[email protected]> > wrote: > > > > > From: Don Dailey <[email protected]> > > > Subject: Re: [computer-go] representing liberties > > > To: "computer-go" <[email protected]> > > > Date: Friday, August 14, 2009, 2:33 PM > > > > > > > > > On Fri, Aug 14, 2009 at 5:13 PM, > > > Carter Cheng <[email protected]> > > > wrote: > > > > > > I have been having difficulties selecting a good > > > representation for liberty sets for strings of stones. > I am > > > curious how other people might be doing this. I > suspect that > > > for heavier playouts one would like to know not only > the > > > count of the liberties but also where precisely they > might > > > be relatively quickly(to determine if the group is in > atari > > > among other things). > > > > > > Simple is best, until you know EXACTLY what you will > want > > > to do and how often you will need to do it. > > > > > > Something pretty simple that I have used in the past > is to > > > track each chain and incrementally maintain the > liberty > > > count. > > > > > > > > > When you plop a stone down, you have to look at only > 4 > > > points to see which group if any it belongs to, or if > it > > > connects 2 or more groups. And you can update > the > > > liberty counts of all affected groups very quickly. > > > > > > > > > Where there is a capture, you must do considerably > more > > > work - but captures represent only a small fraction of > the > > > moves. Small captures are more common than large > > > captures, but they require little work. > > > > > > > > > - Don > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > _______________________________________________ > > > > > > computer-go mailing list > > > > > > [email protected] > > > > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > > > > > > > > > -----Inline Attachment Follows----- > > > > > > _______________________________________________ > > > 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/ > > > > > -----Inline Attachment Follows----- > > _______________________________________________ > 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/
