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

[Rémi Coulom <Remi.Coulom@xxxxxxxxxxxxxx>]

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.
>
> 2. When is an approximate number of liberties sufficient?  Semai's are 
> a common case for tracking a larger number of liberties, but in many 
> cases, a pure liberty count is insufficient anyway.
>
> 3. Besides liberties dropping to zero or possibly a group having less 
> than N liberties (as a warning sign), what other ways do real 
> bots/people count liberties?
>
>
>
>
> 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 
> 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.
>   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.
>
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx
> http://www.computer-go.org/mailman/listinfo/computer-go/
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.

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