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

[drd@xxxxxxx]

Woops,

I just realized that my calculation is wrong.   The 2 old strings
may have several liberties in common.

I think it is easiest just to re-calculate, the amortized time
should be quite small.

- Don


On Monday 17 October 2005 1:02 pm, drd@xxxxxxxxxxxxxxxxx wrote:
> 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/
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/