[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Groups, liberties, and such
On Fri, 2005-10-14 at 22:09, Jason House wrote:
> Here's my main questions, but below them I've tried to give a lot of
> background for those who are interested.
> 1. When connecting two stone chains is there any way to calculate the
> new chain's liberties without iterating over all the stones? While not
> simple, tracking a chain's identifier can be done in O(1) and I'm
> looking for a comparably efficient solution if it exists.
You can add them up, but you have correct for the liberties they
have in common, and the liberties added/consumed by the connecting
> I've tried to make updates from placing a new stone on the board be an
> incremental, O(1) change wherever possible. I'm trying to keep this up
> but some information tracking is tough to do in O(1)
> Group Identifiers
> I've shied away from storing an explicit group number of individual
> stones on the board. When placing a stone that connects two groups, the
> update would be O(min(N1,N2)) where N1 and N2 are the group sizes.
> For the actual tracking of group id's, I've settled on the concept of
> a disjoint set. Effectively, each group member has a pointer to a
> representative member. Mergers result in some members seeing a linked
That is a quite normal method, IMO.
> list to reach their head, but then collapse the linked list to allow
> direct access. Theoretical analysis shows operations O(1) for all
> practical group sizes.
I don't know what a 'collapsed' linked list is.
Linked lists are quite 'heavy' structures wrt updates.
Plain arrays or bitmaps are cheaper structures for
> See http://en.wikipedia.org/wiki/Disjoint-set_data_structure
> 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.
Forget about the pseudo-liberties, they are nearly useless.
Adriaan van Kessel.
computer-go mailing list