[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