[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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

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