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.

Sunday, September 25, 2005

Random Thoughts

When people say: "I built my own computer", they mean they buy a motherboard, drives, CPU, cooling system, RAM, power supply, case and screw and plug it all together.

So I always have to explain that when I say: "I built my first computer myself" I mean that I had to actually solder all components onto the motherboard. (The empty motherboard of my Acorn Atom came with a bag of resistors, IC's, capacitors and connectors).

Still I should not say: "I built my computer myself", for I know a guy that has really done so. He lives in Tbilisi, Republic of Georgia and he showed me his self-made computer. It was unique. He designed the hardware using "Soviet" IC's, and he hand-designed and etched the motherboard in an acid bath. He drilled the holes for the component's wires with a dentist's drill. He wrote the BIOS. He wrote the OS. He wrote the compiler. He wrote the system utilities. Tbilisi had rationed electricity in the early nineties so he powered his computer from old car batteries. Those batteries were refurbished. He had emptied them of battery acid, collected the best plates, washed and cleaned them, hammered them flat again and put them back in the battery casing and filled it up with new acid.

If I would really build my own computer today, I would add a very important thing for computer scientists: A crappy carbon resistor or a crappy Germanium diode. In fact I am prepared to pay more for a system that has it.

The thing is, crappy carbon resistors or crappy Germanium diodes noise (verb). The DAI had one. (The DAI hails from the same era as the Acorn Atom, the TRS 80 and the Exidy Sorcerer, around 1980). Such "Johnson" noise is produced by the random movement (Brownian motion largely caused by thermal effects) of electrons in the component (PN junction noise in case of a [Zener]diode or transistor). This is real quantum-randomness. Mathematicians will start to drool at this point. People that use Zobrist hashing will salivate as well.

John von Neumann said: "Anyone who considers arithmetic methods of producing random digits is, of course, in a state of sin."

The DAI used quantum noise to generate truly random numbers. You do this by amplifying the noise, Schmitt-triggering it, feeding the pulse train into a shift register and clocking the resulting machine word out. Highly cool. Strange that this is not integrated into modern CPU's. Hundreds of millions of transistors, but nobody thinks of using a handful of them (downgraded to be "noisy") to generate real random numbers fast.

But yet, really good hardware random generators are unwieldy and expensive.

Thermal noise-based random is slow compared to generating "random" numbers with a shift register, but this can be augmented by giving each bit its own random generator, hashing the bits to compensate for the fact that some generators will have an asymmetric duty cycle, and having a constantly filled-up "random cache" with a capacity of a few thousand 64-bit random numbers, to be used as either integers or floats by the CPU. Random numbers would be really random and load into a register in a single clock cycle! This would be near-trivial to do for AMD, Motorola, IBM or Intel. And I want royalties.

Why would you need a "perfect" random? I am not a statistician or some kind of dogmatic purist, but I do need one. I make pattern recognizers for "Artificial Intelligence" purposes, excusez le mot ;)

I started with the random generator in Delphi. That one sucked. When you plotted the random on a 1024 x 1024 field, entire patches remained empty. So my pattern recognizer sometimes shot an old lady because it mistook it for a tank (this is a metaphor, it would go too far to explain what my stuff actually does, and why some forms of pattern recognition need really random random).

I then decided to generate random numbers myself, ensuring they all were in a certain Hamming distance range from each other. That's allegedly very useful for Zobrist (xor) hashing, to get an even spread (minimize collisions). But then a discussion on the computer Go newsgroup made me have doubts, and I now use a Mersenne Twister. The verdict on that one is still pending.

<tinfoil hat> Note how none of the modern mainstream CPU's/PC's provide functions to decrypt quickly (popcount) or encrypt well (true random), but that older CPU's/PC's did provide this functionality.. </tinfoil hat>