It's bad to be a perfectionist when you're trying to make a living making software, except when your goal is to make a very strong Go program. Because I don't think cutting corners is going to work.
While I was implementing the n-th order liberty functionality, I did of course a lot of literature research. GNU Go does not expand them into (first order) enemy liberties, so I implemented that as well because it makes sense from a Go programming POV. But then I came to the conclusion that cheap tricks are not good enough.
So I decided to do a "Bouzy territory" approximation, where there are force fields between chains. So a black chains' 4th order liberty can't expand into a white chains' 3rd order liberty. This makes sense from a Go programming POV, because when both chains are alive, white is able to prevent black from expanding onto that point. And this knowledge is very useful to have in a tactical search. The expense of maintaining it may well be outweighed by greatly increased pruning efficiency and a better sorting of plausible moves.
This would be easy to make, if it weren't for severe (L1) space and (execution) time constraints. I can't have large lookup tables and linked lists all over the place. Everything, including the lookhead data, has to fit into 64 KB of L1 data cache. So I have to make do with my existing data structures to make a Bouzy-type map, and still make it very fast. This kind of stuff is pretty slow even with the most efficient data structures, let alone when you need to keep track of the number of order-libs per chain and do this from sub-optimal data. (Sub-optimal for that particular task, not for the system as a whole).
It doesn't help that the Opteron (AMD64) needs 9 cycles for a BSF (Bit Scan forward, or better: Barrel Shifter Forward). I guess I have to "Roeien met de riemen die ik heb". (A Dutch expression, literally: "Row with the oars I have").
Update: Blogging really helps! By expressing my thoughts here and re-reading them - trying to attack their premisses - I came to the conclusion that maintaining a Bouzy map is in fact totally superfluous, because I can achieve the same result by cleverly processing the data I already am maintaining. Your mileage may vary in your own Go program, however.
