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

["David Fotland" <fotland@xxxxxxxxxxxxxxx>]

1.  I don't know of one.  Many Faces keeps a sorted list of liberties and a
count of liberties for each chain.  When chains are merged, the sorted lists
are merged (one pass through both), and the count is updated during the
merge.

2. For tactical stability, 4 liberties is enough.  When I do tactical look
ahead I stop when a chain can be proven to have 4 liberties or more.  For
semeai, I calculate several liberty-related values, which are estimates of
the number of moves it takes to capture a chain with each side to move
first.  To compare liberties in a semeai you need distinguish between shared
(inside) liberties, and outside liberties, and you need to compare the
number of eyes in each group.  There is a good discussion in "The Second
Book of Go".

David

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Jason House
> Sent: Friday, October 14, 2005 1:09 PM
> To: computer-go
> Subject: [computer-go] Groups, liberties, and such
> 
> 
> 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/
> 


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