Sunday, June 18, 2006

Engineers vs. Mathematicians

One of the key components of a strong tactical module is the part that maintains a count of the n-th order liberties. My design however needs more than that: It needs to know, for each point, which chains have what order liberties there. All this has to be updated with lightning speed (preferably faster) when stones are placed and chains are merged or captured. Simply recalculating everything would be too expensive.

Another bone of contention is the maximum order number of liberty that we should track. The higher it is, the slower the lookahead, and lookahead compensates for having a low max. order number. I've decided to dedicate no more than 20% of the L1 cache for liberty-order administration, which yielded a max. liberty order number of 4. I think this is the optimum value for 64-bit hardware when the algorithms are optimized for this architecture.

I am now starting to code the n-th order liberty delta-update module, after having spent days struggling with getting a grasp on the most efficient way to do it, and deciding which special cases could safely be ignored. Chess programs are surprisingly simple state machines with efficient info-extractors operating on them, and many tricks are used to cut corners, as long as it works. I am doing the same thing with my Go program. My design for fast delta-updating of n-th order liberties is faulty in case chains of a certain shape are merged. But this is a rare case, and its consequences are relatively minor.

In practice, the system will work like a charm. This approach is an advantage to that of the Mathematician. Mathematicians are looking for accurate ways to describe systems. Engineers are simply trying to build things that do what they're supposed to do.