[computer-go] Groups, liberties, and such

[Jason House <jhouse@xxxxxxxxx>]

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/