[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Groups, liberties, and such
On 10/14/05, Jason House <jhouse@xxxxxxxxxxxxxxxxx> wrote:
So far, I have not thought of a good way to handle liberties in an
efficient manner. The problem is that looking at the empty spaces
surrounding each individual stone, and summing up leads to an incorrect
value. I've started calling this incorrect value pseudo-liberties. As
an example, every stone in a hollow 3x3 square has 2 pseudo-liberties.
Summing up over the 8 stones results in 16 pseudo-liberties instead of
the correct 13 liberties. When combining two long stone chains, the
pseudo-liberties are easy to calculate incrementally, but I have no good
way to incrementally track real liberties.
As a simple example, consider the letter H formed by 7 stones.
Before adding the center stone each 3 stone wall has 8 liberties, but
share 3 liberties with its neighbor. While adding the center stone and
re-examining all of its liberties would yield the proper result of 12,
this doesn't hold in general.
Consider moving the connecting stone by one (forming the capital
letter U). Re-examining only the liberties of the connecting stone
would result in 14 liberties instead of the correct 13. Generalizing
the problem, there's no guarantee that chains can not come near each
other at different points and reduce the liberty count.
Maybe you want to check out the UniqueList implementation in
to see how you can make
sure you don't add the same liberty more than once. Or the whole
incremental board-administration in there for that matter. You can also
try to find old articles from this group, it has been discussed at
computer-go mailing list