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 <[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/
>
--
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
