On Fri, Apr 03, 2009 at 05:07:41PM +0200, Isaac Deutsch wrote: > > > This may seem slow, but it has a couple real > > > advantages. First, it works with the cache > > > to maximize locality. Second it is very simple. > > This *does* seem slow, even when caching the number of liberties. You > mentioned that you did this a couple years ago, do you think it still holds > true? Thank you for the information. > > > This is what I do too. I never bothered with bit-arrays but possibly > > that's simply because I fail to see how you can merge two chains and > > count liberties in O(1). > > Merging would be a simple OR operation. Counting can be done, for example, > with some kind of binary search. Counting the bits set has been well > researched and many different algorithms exist.
besides, most often you only need to know if a string has zero, one, two, or many liberties, so the counting can be aborted early. -H -- Heikki Levanto "In Murphy We Turst" heikki (at) lsd (dot) dk _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
