Wednesday, June 21, 2006

Bugfixing the State Machine

Some say the average # of LOC/day is 20 for "Joe average", and I think that's valid for me as well. That includes bugfixing, maintenance, design, testing, surfing the web for conspiracy theories and a general lack of concentration due to neuroborreliosis.

I've been at it (The Big Bug Hunt) for a day now, but I've spent less than an hour at actual bugfixing. Part of the day was spent in bed in a collapsed stupor, I started trembling in the kitchen and had to lie down.

I've found half a dozen of bugs already. One was me trying to clear a bit using XOR, but forgetting that this bit isn't neccessarily set in the first place, so I had to do an AND with the NOT of the mask I used with the XOR. Another bug was caused by a stray stack pointer. A few bugs were discovered in pointer arithmetic here & there.

I got as far as verifying that a single stone, put on Tengen, gets its neighbor lists and liberty count updated, that the neighbor of that stone (an empty chain with the size of the board) gets its size reduced, and that the n-th order liberty fill code works at least partially correct.

I still haven't yet tested merging of chains, capturing chains or the delta-updating of n-th order liberties. I'm very slow with coding & debugging nowadays, often I go lie on the bed to conjure up a hypothesis before I return to my desk to test it. I usually don't debug without a testable hypothesis.

Chess programmers (and to a lesser extent Go programmers) often report serious bugs in their engine code that surfaced only years after they had a successful program, and I want to avoid that. In other words, I'm going to test the living daylights out of this code, using a test file with Go problems and their known solutions. But that's something for the future - first the TsumeGo code itself needs to be developed.

Since I don't play Go and I am an opponent of trying to be "clever" (= putting the programmer's Go knowledge in a Go program), I'm going to use automatic learning for the TsumeGo's plausible move generator and its ordering heuristics. This is near-trivial compared to writing the state machine itself, at least for me it is because I have several years of experience with automatic learning applied to Go. Not just with "pattern urgency", I also have done successful work with connectivity patterns.

So, where other folks have specialized ladder code, net code and liberty-filling code, I'll have nothing of the sort. Later I'll might code a fast ladder module as a special case but first I will design and build a plausible move generator/sorter that finds ladder moves, tries them first and follows them as deep as needed, all automatically. I will have to program nothing for that. It will be a very simple, elegant, small and fast self-learning expert system. All basic data structures for it are already in place and are updated as part of the state machine.

I have to admit it's a bit scary. David Fotland has efficient code that moves on liberties of threatened chains, and of course this is very fast. Faster than my expert system. But Fotland's code has no, or at least no solid notion about n-th order liberties and hence has difficulties with nets. In fact the big weakness of most, if not all Go programs today is the lack of tactical insight in terms of getting too dangerously enclosed. My design caters for early static detection of enclosure in the evaluation function, but my plausible move function will generate moves that try to enclose using-, resp. try to escape from nets of 2nd or higher order all by itself, using automatic learning. If this works as it should, the result is an extremely strong tactical module that can solve "open" (non-enclosed) TsumeGo problems in acceptable time. If this does not work as it should, it has to be fixed :)

You understand that my approach is highly superior to any 4d or 5d or even pro putting hundreds of if's in his plausible move generator. My approach takes half a million games and learns which tactical moves are plausible in which tactical situations. Using an expert system is slower than using if's, but the sophistication of pruning is much better, so I can achieve the Holy Grail of Go programming, a very narrow search tree. My plausible move generator for the Tactics module, contrary to Moyo Go's pattern expert, will not use actual patterns in the form of Zobrist hashes because this is unacceptable for reasons of accuracy and speed.

Neither will I use a neural network because I am of the old school - I avoid multiplications like the plague. I have no problems with black boxes, but only when I can pry them open and have a peek in them and understand or even influence what's going on in there.