Re: [computer-go] Chains and liberties

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Peter wrote:
> > I doubt that it's worth it, with cache misses and what not.
> 
> Can you say more about this? 

No, it was just a guess.

> The bit vector representation does allow for efficient representation 
> of mathematical morphology operations.  Specifically, to find the 
> liberties of a block, we just:
> 
> 1) Find the set of points adjacent to the block (with shift 
> operations), then,
> 2) Take the intersection of this set with the set of vacant points 
> (with bitwise AND operations).
> 
> This takes time independent of the number of stones in the block.

How do you use the liberties in your program? Can you efficiently
count the liberties or traverse them?

> > I never understood the point of having sorted liberty lists. Merging
> > lists can be done in O(n) with only a marginal memory overhead.
> 
> I guess sorted lists would be easier to test for equality...

Now I'm short on imagination. When would you ever want to test two
sets of liberties for equality? Or did I just miss a joke?

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