Evolution of a Go program

About the development of Moyo Go Studio, software to (help) play the Oriental game of Go. Go is a two-player zero-sum game of perfect information. It is considered much harder than Chess. Currently, in spite of enormous effort expended, no computer program plays it above the level of a beginner.

Monday, May 01, 2006

Retarded Optimization

I'm working on a TsumeGo solver (in the broadest sense of the word, it will also know whether chains can be connected - I'm not sure that classifies as TsumeGo). The (Object Pascal - style) classname is "TTactics". And I wanted to talk about general design issues. Unscrupulous enemies are lurking, so I won't get into details, but I wanted to address something that so far yielded only two Google results: Retarded Optimization.

When constructing a TsumeGo solver, premature optimization is bad. Because you'll be swamped by trivia before the bloody thing works at all.

However: Retarded optimization is just as bad! "Retarded optimization" means it's
too late to optimize efficiently.

It takes so much time to write an industrial-strength TsumeGo/Tactics module, that you want to have exactly the right amount of optimization at exactly the right times. You need
enough optimization upfront, because after you wrote a few thousand lines of highly complex code, it's too late to change the design paradigm, all you can do is apply speedup tricks that makes the existing design run faster.

The reason it took me so long to get coding on the tactics module (four years) is because I wanted to get the design right. I wanted to design a Ferrari and not a Ford. It's insane to mod a Ford into a Ferrari. It would cost much more time and money to do that than to build a Ferrari from scratch.

Let there be no mistake - my goal is Michael Reiss taking up bonzai cultivation and Fredrik Dahl devoting the rest of his life to Backgammon.

So, while I figured out how to make a good tactics engine, I coded up some simpler stuff, like the program as it is today. I think I know now how to make the very fastest tactics engine. It requires a fast
design. After initial implementation, it will be easy to port it to 128 bit SSE3 assembly (a pity there are no 361-bit registers - see my posting "The Case For 64 bits" to see why more bits means more speed in Go programming), but that's all useless if the design wouldn't be the absolute fastest. In that case it's neither premature nor retarded optimization, it would be useless optimization.

Because that's what it comes down to - if the design isn't absolutely optimal, then optimization is pretty useless. It's like tuning a tractor's engine and transmission system to go twice as fast. You still won't outpace a 2CV. So as long as you don't have the "perfect" design, it's pointless to start coding, otherwise you'll have to do it all over again after you figured out that your design sucked and what the best design is. Of course you can build one, throw it away and start all over again (in fact I'm doing that because Moyo Go already contains most of a tactics engine in order to move/unmove, capture chains etc.) but you can't go on building crap forever. Life is short and although coding TsumeGo engines is more satisfying than French kissing Finnish boarding school girls, it still gets boring after a while.

OK. So, in my case, avoiding premature optimization means I don't go bitfucking yet. Everything in its own variable, that kind of thing. BUT, as fellow countryman Terje Mathisen said: "All programming is an exercise in caching". The Norwegian climate is exquisitely suitable to develop software, this is why WinHonte scares me. I do pay great attention to caching issues. Every thing I make is with caching peculiarities in mind. Another design parameter is the ultimately attainable level of optimizability. I even design with hardware-ization ability in mind. Can it be effectively implemented on a FPGA? What about future CPU capabilities? You get the idea. Nothing worse than a design that doesn't survive the future. This is why, four years ago, I started to code Moyo Go with 64-bit integers wherever it would provide a speedup (e.g. Zobrist hashes, bitboards and packed fields). Since yesterday, Free Pascal has a 64-bit compiler :-)

Whenever you're in doubt about the prematureness or tardiness of your optimization: Simplicitity is the hallmark of the professional.