Merging two chains requires walking the smaller chain to find duplicates. Adding a stone to a group does not require walking a chain.
David > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of Carter Cheng > Sent: Saturday, August 15, 2009 2:07 AM > To: computer-go > Subject: Re: [computer-go] representing liberties > > 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 <dailey....@gmail.com> wrote: > > > From: Don Dailey <dailey....@gmail.com> > > Subject: Re: [computer-go] representing liberties > > To: "computer-go" <computer-go@computer-go.org> > > 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 <carter_ch...@yahoo.com> > > 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 <dailey....@gmail.com> > > wrote: > > > > > > > > > From: Don Dailey <dailey....@gmail.com> > > > > > Subject: Re: [computer-go] representing liberties > > > > > To: "computer-go" <computer-go@computer-go.org> > > > > > Date: Friday, August 14, 2009, 2:33 PM > > > > > > > > > > > > > > > On Fri, Aug 14, 2009 at 5:13 PM, > > > > > Carter Cheng <carter_ch...@yahoo.com> > > > > > 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 > > > > > > > > > > computer-go@computer-go.org > > > > > > > > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > > > > > > > > > > > > > > > > > > > > -----Inline Attachment Follows----- > > > > > > > > > > _______________________________________________ > > > > > 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/ > > > > > > > > > > -----Inline Attachment Follows----- > > > > _______________________________________________ > > 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/
