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

[Moi <dld@xxxxxxxxx>]

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.
> 
> Questions
> ----------
> 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
stone.


> Background
> -----------
> 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
representing sets.

>    See http://en.wikipedia.org/wiki/Disjoint-set_data_structure
> 
> 
> Liberties
> ----------
>    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.

See above. 
Forget about the pseudo-liberties, they are nearly useless.

Adriaan van Kessel.


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/