[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
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/