________________________________ From: Heikki Levanto <[email protected]> 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. Most cases do test for zero/one/two/many, but if we want smart playouts, it helps to know in advance exactly how many liberties some strings have, compared to others in a capturing race. Any program which assumes that "n liberties is enough to live" may be tricked by a player who can count to n+1.
_______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
