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