> On Thu, Apr 2, 2009 at 5:14 AM, <w...@swcp.com> wrote:
> > Isaac,
> >
> > I implemented about 6 way to track liberties,
> > a couple years ago, and measured the running
> > performance, and by far the best is also the
> > simplest: keep an array of liberties for each
> > chain, and do a simple linear search.
> >
> > 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.
--
Psssst! Schon vom neuen GMX MultiMessenger gehört? Der kann`s mit allen:
http://www.gmx.net/de/go/multimessenger01
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
