RE: [computer-go] Chains and liberties

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> > Adding all the stones and marking the Chain object in the chain array 
> > takes O(n) where n is the total number of stones involved.
> 
> It might not fit into this approach but merging stone lists can always
> be done in constant time if the strings are represented as cyclic
> lists in a board array.
> 
> /Gunnar

Merging the stone lists is a simple constant time operation, but telling
each point which chain it belongs to is proportional to the number of stones
in the smallest chain to be merged. If you avoid that cost, then you pay
extra when trying to determine the chain at a given point (at least an
O(log(n)) loop instead of an array access). I've found that during tactical
search, having instant access to the chain for each point is worth the extra
expense when merging chains.

When designing the data structures for tactical search, I'd suggest keeping
the following frequent operations in mind:
- Checking whether two points are in the same chain.
- Iterate through the chains adjacent to a given chain.

Anders Kierulf
www.smartgo.com


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