[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

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

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".


> -----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