[computer-go] Incrementally recognizing regions of empty space

[Eric Boesch]

House, Jason J. wrote:
>I've been thinking about how to identify empty regions.  I'd like to ask 
>the
>community how they do it?

I think I gave a reasonable answer to part of your question here:

http://computer-go.org/pipermail/computer-go/2006-February/004349.html

Of course, just knowing how many groups you have after splitting up a chain 
is not enough; you still have to migrate some of the stones to the new chain 
and update neighbor/liberty counts correspondingly. But at least the 
function tells you whether the chain has split and which sub-chain is 
probably biggest (if you avoid traversing the biggest chain during merges 
and splits, then you can save a lot of time both in theory and in practice, 
as others have observed).

When repeatedly playing and undoing 120 random moves on a 19x19 board, the 
profiler indicated that the program averaged very roughly 1/3 microsecond 
(on an Athlon 3500+) per move/undo pair in chain-splitting, which happens to 
empty chains every time a move is played and to colored chains (called worms 
in the program, but I should change that) every time a move is undone 
(because I haven't implemented undo stacks). I think the empty chains can be 
worthwhile if you're doing more than just random playouts -- I use them many 
places -- but your mileage may vary.