[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.
> 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?
> 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
> 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
> 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
> value. I've started calling this incorrect value
> pseudo-liberties. As
> an example, every stone in a hollow 3x3 square has 2
> 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 mailing list