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

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

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.

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

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

computer-go mailing list