Re: [computer-go] Groups, liberties, and such

[drd@xxxxxxx]

Jason,

When a move connects 2 strings,  isn't it easy and fast to calculate 
the liberty count of the newly combined string? 
 
   new_count = old_string_A_count + old_string_B_count - 1 + LNC.

LNC means Liberties Not in Common.  For the newly placed stone (that does
the connecting), we look at the 4 neighbor points.   If they are empty,
we tally 1 if they are not liberties of EITHER of the OLD strings.
This idea is easily extended for connections of 3 or 4 groups.

When connecting 2 groups, you would have to look at 6 points at most,
the 2 possible new liberties,  and the 3 possible points around these new 
liberties to check if they touch the old group.

Compared to other more complicated schemes, this is fast.   What little
extra time this takes is very tiny when amortized over all the moves
your program will be making.

Am I understanding the problem correctly or am I confused about your
requirements?

If the new connection is also a capture,  this doesn't work, but that's
a problem for any of the incremental liberty calculations, not just the
connecting ones.

- Don



On Monday 17 October 2005 11:21 am, Jason House wrote:
> A true liberty count is only needed for chains with only a few liberties
> (less than 4?).  Chains with more liberties are generally assumed stable
> and higher order logic is required for an overall group stability.  The
> exceptional case of a semai requires much more than conventional liberties.
>
> I think that I'll track pseudo-liberties (since it's just so darn easy),
> and calculate actual liberties only when the result can be less than
> some fixed value (initially 4).  Actually I may do something as force a
> liberty calculation if the pseudo-liberties are less than 10.
>
> If a semai occurs, an exact calculation of liberties is not nearly
> enough and extra work will have to be done anyway, so I won't mind
> paying for the liberty calculation.
>
> Rémi Coulom wrote:
> > I had very similar ideas to yours when I started to write CrazyStone. I
> > started with a disjoint-set data structure, and the
> > hope that I could do all incremental updates locally, without going
> > through long chains. I gave up because of the problem of updating
> > liberties. As you wrote, it seems very difficult to incrementally update
> > liberty counts when chains are merged. So I gave up with the
> > disjoint-set data structure, and I now store a group number for each
> > stone.
> >
> > It is rather rare that long chains are merged together, so the merging
> > operation can be made very efficient by not exploring the longest chain.
> > I found that not passing through the longest chain is a very big speedup
> > in CrazyStone. But that may depend on your data structure.
>
> David Fotland wrote:
> > 1.  I don't know of one.  Many Faces keeps a sorted list of liberties and
> > a count of liberties for each chain.  When chains are merged, the sorted
> > lists are merged (one pass through both), and the count is updated during
> > the merge.
> >
> > 2. For tactical stability, 4 liberties is enough.  When I do tactical
> > look ahead I stop when a chain can be proven to have 4 liberties or more.
> >  For semeai, I calculate several liberty-related values, which are
> > estimates of the number of moves it takes to capture a chain with each
> > side to move first.  To compare liberties in a semeai you need
> > distinguish between shared (inside) liberties, and outside liberties, and
> > you need to compare the number of eyes in each group.  There is a good
> > discussion in "The Second Book of Go".
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/