Also, count real liberties, but dont store them. > -----Original Message----- > From: computer-go-boun...@computer-go.org [mailto:computer-go- > boun...@computer-go.org] On Behalf Of w...@swcp.com > Sent: Saturday, August 15, 2009 9:03 AM > To: computer-go > Subject: Re: [computer-go] representing liberties > > There are many ways to track the liberties of a chain > And there are many different implementations of each: > > * none > * count pseudo liberties > * simple count > * do count, sum, and sum squared, which can detect atari > * array of liberties > * store all liberties > * store first k liberties > * linked list of liberties > * doubly linked list, fixed locations for liberties (needs many nodes) > * doubly linked list, also store liberty (needs only 1600 nodes) > > After fairly extensive performance testing on an Intel Core chip, > I find that most reasonable techniques perform within a factor > of 1.5 or 2.0 of the best, so as a practical matter, it doesn't > really matter that much. Yet, 2 performance results stand out: > > * for doing pure MC, use simple pseudo liberties > * for doing board analysis (like reading ladders), use arrays of > liberties. > > I am in the middle of porting this to the i7 core architecture. because > of the larger, faster L2 cache doubly linked lists may work well. > > I have a code generator that makes it (somewhat) easy to try this out: > http://pages.swcp.com/~wing/cgbg/ > > Of course, writing out the different implementations yourself is a good > exercise to help understand what happens. > > Michael Wing > > > 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/
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
