Sunday, June 04, 2006

Hyperfast Empty Area Splitter

Everything about Moyo Go is "speed", and especially the TsumeGo module should be fast.

A useful thing to speed up L&D analysis is the concept of "empty chains", but it can be a time-consuming process to detect whether a move split a chain into up to four new ones.

The computer Go mailing list archive had a few interesting and speedy solutions to this problem, but I kept having some nagging objections to even the fastest proposed solution. I don't know whether it was luck or wisdom, but I ran into a much faster solution. To determine whether a split occurs I have to look only at the data in one single cache line! And the number of operations required is so small that it seems close to the theoretical minimum.

The split itself typically takes very few clockcycles and happens in less than a handful of cache lines as well. It's achieved by a combination of minimalistic data representation, advanced boolean algebra and a thorough understanding of the CPU.