[computer-go] incremental liberty counts

[Mark Boon]

Don,

About a year and half ago, almost two, I tried to analyze what would
be the minimal amount of work necessary to keep chains and their
liberties incrementally. This was because in my Life and Death project
the single most expensive function was getNLib() which would get the
number of liberties of a chain on the fly and returned the points
where they are in a small list. I hoped I could win time by keeping
the liberties incrementally, and ideally some chain information as
well.

The result you can find in my library. It is rather data-structure
intensive and uses  some memory. The conclusion was that it worked
pretty fast if you wanted to have the liberties of all chains at all
times compared to other methods. And it would mean no longer needing
getNLib() (or at least it would be much simpler and faster).

But using it in a tactical module actually slowed things down a lot
compared to the custom code it used to make moves and undo them. Since
that also must detect capture, just like in your case, I doubt you'll
be able to speed-up a simple make-move routine that only needs to know
whether something gets captured by replacing it by an incremental
administration.

When you say it takes 30% of all your computation time to detect
capture it makes me wonder. Seems very high. Maybe you get the actual
liberty count, where all you really need to know is whether a chain
has a liberty or not? That would make a big difference.

Other than that I wouldn't know, but to me it sounds like an
incremental data-structure is not the answer you're looking for.

Mark