[computer-go] incremental liberty counts

[Rémi Coulom]

Don Dailey wrote:
> But I am considering now to make this more like a hash table - the chain
> ID is the same as the index of the first stone placed in that chain.
> So if you place a stone on bd[17], 17 becomes the chain ID and you don't
> worry about running out of space or anything.   If you place more stones
> next to bd[17], they of course become part of chain "17".
>   
That's how I do it in Crazy Stone. I try to do a lot of clever things 
with the redundant data, so it would not be very meaningful to compare 
speeds. Also, I keep more information, such as whether strings in atari 
are connected to opponent strings in atari. I am very deeply convinced 
that I could not do what I do faster without redundant data.

I do not think I use particularly clever tricks. The two non-obvious 
ideas I can think of are the idea of using an array of marks to note 
already-visited points or strings (incrementing the mark value to clear 
the marks, like it is done in GNU Go), and the idea that small strings 
should be merged into the largest string, when strings are merged. When 
strings are merged, the liberty count can be updated without visiting 
the largest string, which saves a lot of time.

Also, I don't know how you profiled your program, but I'd like to say a 
word of warning against gprof. I thank Łukasz Lew for suggesting to me 
that it does not measure time accurately. I now use sysprof instead 
(http://www.daimi.au.dk/~sandmann/sysprof/). Sysprof provides much more 
accurate timings. I observed very big differences between sysprof and 
gprof on my program. Sysprof does not instrument the code, and works by 
sampling the code pointer. I suppose similar tools exist for Windows. I 
believe that's the only reasonable way to obtain accurate timings.

Rémi