Hacker's Delight?

It arrived! Cool book, in spite of the fact that it wastes a lot of pages on proofs. I trust the author, I don't need no stinkin' proofs. I would have preferred twice as many bit twiddling tricks! And shouldn't the title be "Hackers' Delight"?

I need the quickest way to count trailing zero's, that sort of thing. As I said before, the NSA covertly prevented the ability to do any such important things (popcount as well) quickly on desktop machines. This book gives ideas and code how to do it a hundred times slower than a dedicated instruction would have done it*, but it's still very useful. *Don't forget that a mispredicted branch incurs a penalty of at least 10 cycles.

Due to MSB issues, the usability of some code is questionable to Pascal users, but for the tactical engine, I use Pascal only to generate MASM assembly anyway, and the ultimate goal is to code directly in 64-bit assembly.

It is insane not to write it in anything else but Assembly. People argue that the language used is less important than the efficiency of pruning heuristics and eval function, but they are assuming that I will write highly sub-optimal code. Even if I would do that, using assembly would outweigh that.

So me being an Assembly hacker might very well offset my currently limited Go knowledge as it will be applied to various heuristics, because the difference between compiler-optimized optimal 32-bit C code and human-optimized 64-bit assembly code is enormous - sometimes a factor 10 or more. Because using 64-bit registers allows for a radically different, highly efficient approach of some aspects, and coding at the metal is incomparably better than being at the mercy of the optimizer.

Cool Forum

I found a forum with people talking about Life, the Universe and The Rest, with heaps of chess programming techniques as a bonus. Since the computer Go mailing list is all about boring non-programming stuff these days, the Chess forum is all there is - but it's very useful anyway:

http://216.25.93.108/forum/

Short Story

I managed to salvage an old version of a SF story I wrote.


God?

The Search for Extraterrestrial Intelligence finally seemed to bear fruit: A consistent signal was received that came from an entire quadrant of the galaxy, superimposed on the background radiation in that area. This was remarkable, because the source of the signal was not a stellar object or even a location in the universe, but it was like it was uniformly distributed over an area of about one sixteenth of the outer sphere of the universe. Hard to miss, therefore. The signal hadn't been there before.

It didn't take long before they cracked the code, to be more precise, the NSA did it. The CIA took it from there. They put a couple of bright kids onto the puzzle. The code was simply a sequence of zero's and ones. They discovered that the number of binary digits was the square of a prime number. When the digits were arranged in a square so that a side was equal to that of that prime number, the resulting box of 0's and 1's formed an image. Kind of like a fax.

There were quite a number of those images, and they were repeated all the time. It took about a month for all the data to be received.

Together, they formed the schematics of a rather simple looking electronic device. The images were annotated with a kind of symbolic mathematical script.

It didn't take long before also that was deciphered as well. Some symbols pertained to atom numbers, indicating the composition of the materials. Some symbols were measurements expressed in wavelengths of Hydrogen.

To make a long story short: The US government, even the President himself, were consulted. The CIA wanted to build the device. Experts said that it could do no harm, it seemed to be some kind of simple receiver that apparently didn't even need a power source. Although it was unclear what
exactly it would receive.

They built it and as soon as they turned it on, it outputted a similar stream of binary digits, only much more than had been originally received by SETI, and in much higher resolution and with a much higher frequency. It was like they had hooked up a Hard Disk, transferring many megabytes of data in an endless loop.

Everybody thought it was a hoax. Investigations were launched. They got people from outside the team to find malversations. They put the receiver in a cage of Faraday, and it kept on receiving. They let another team assemble a similar device, which worked just as well and produced the same output, synchronously to the last bit, with he first device. They took it into an abandoned coal mine, and it kept working. Components were replaced with equivalent components and it kept working.

People were getting nervous. The output of this device looked like the blueprints of some kind of transceiver. It would take a while to build it. Some of the components were hard, possibly impossible to manufacture. One of the components was a diamond ball of around 2 cm in diameter. They would have needed to steal the Koh-I-Noor and polish it into a rather dull marble, in order to comply with those blueprints.

And that is exactly what they did. Synthetic diamonds of that size were impossible to manufacture. The team who did it, was immediately afterwards assasinated by a "special" team. And the assassins themselves disappeared shortly afterwards. The diamond was polished and the result was referred to as: "The marble". The engineers thought it was made of glass. For increased security, ten identical devices were assembled, nine of which used an ordinary quarz marble.

When the thing was finished, a small team of NSA mathematicians and linguists was assembled. All were in their mid-fourties. None of them was married. They were given the neccessary security clearance. They were informed about the need for total secrecy and the consequences of breaking secrecy. Curious as they were, all of them agreed. They would work in duo's, one mathematician, one linguist, taking turns on the thing that was presumed to be a communication device.

The machine, modest in size, was hooked up to the serial port of a computer. It only had one input or output (whatever it was), a copper rod, protruding from the base. The device itself was simple in construction, but the dimensions were extremely accurate and the materials were rather exotic. The spherical diamond was partly embedded into two blocks of Rubidium and Osmium alloy, joint at polished sides in the middle. The thing was like a crystal-earphone, only more solid and a tad more expensive.

The base was connected to the ground of the PC. It didn't say that in the instructions, but it seemed a good idea.

Only two mathematicians were allowed to do the initial testing. A NSA programmer had made a simple program with which mathematical symbols could be converted into zeros and ones, and put into the device. And whenever similar pulses would be received, those pulses would appear as their corresponding mathematical symbols on the screen. The "LaTeX" symbols the scientist were familiar with were translated in the deciphered symbols used in the original blueprints.

The most senior of the two was called McFarlow.

McFarlow started to type. Normally a touch-typist, he now used one finger at a time, slowly, hitting each key squarely on the head.

"This is my version of 'Who are you'", McFarlow whispered hoarsely, as he entered the symbols for:

"Outside This Collection Equals"

There was an almost unperceptible delay as the following appeared:

"Collection Sum Collections"

McFarlow seemed to hold his breath. In fact he inhaled very slowly through his nose, trying to remain calm.

He glanced around the periphery of the computer screen, as if to see if he wasn't tricked in some way.

This wasn't happening. If this was a joke, he wasn't sure he had the sense of humor to appreciate it.

He had just asked "Who are you", in mathematical equivalent symbolic notation. Or at least, that was what he intended to ask.

The answer could only be interpreted as: "I am somewhere that contains where you are" or, more dramatically "I include/encompass everything".

"This is impossible" he said.

"Whoever we are talking to, a signal can't go faster than light. The furthest anyone can be who's answering this, is the Moon."

"What about faster-than light, like gravitational waves?" Wayne Drury suggested.

"We don't know how this thing works".

McFarlow unfocused his eyes for a moment in thought and then typed:

"Outside This Collection Position Equals"

"What does that mean?".

"I try to ask where this comes from, where he, she or it is located".

The answer was immediate.

"Outside All Collections Largest Sum Collection".

Wayne said nothing.

McFarlow looked intently at the screen and didn't blink an eye.

"Time Min Max Equals" he entered.

Again, the answer appeared barely after his finger released the ENTER key.

"ONE True Inside Collection Zero Towards Positive Infinity TWO True Outside All Collections Negative Infinity Zero Positive Infinity"

Wayne looked at him and before he could ask, McFarlowe said with a hoarse voice: "Shhst! Let me look at this".

He frowned as he made a smudge trail with his finger as it moved, word for word, over the text on the screen.

After a while he said with a sigh: "I asked about when it came into existence, when it would cease to exist". I think it means this:

"1. For us here, it has existed since the beginning of time and will exist until the end of time."

"Funny how it doesn't use "Infinity minus one" but simply 'infinity'.."

"2. For itself, it claims it has always existed and will always exist."

Wayne, incredulously but highly exited exclaimed: "So, what you are saying is.. We're talking to God!"

"It appears so". McFarlow looked very serious. Solemn, almost.

"Jezus Christ.." Wayne said.

"I don't believe it until he proves it" McFarlow said.

"I just don't believe it".

"Ask it a question" Wayne suggested.

"Like what?"

"Well, is it almighty, how's it like in heaven, that kind of stuff.." Wayne replied. Wayne was a religious person.

"I'm not sure how to translate that into mathematical notation". McFarlow obviously was losing his patience but seemed intrigued at the same time.

He started to type.

"Unknown True: Element A Inside This Collection Towards Not Element A In This Collection Equals Element A Inside Collection Sum Collections".

Wayne, the linguist, wiggled his eyebrows. "I'm afraid you've lost me here".

McFarlow hadn't hit the ENTER key yet.

"We have to hurry", he said. "We don't know how long the connection will last".

"I am asking whether there is a heaven, more exactly, something after we cease to exist, after our universe ceases to exist, is there anywhere we will still be". He pressed ENTER.

Again, the answer was instantaneous.

"Not True".

"At least it seems to understand what I mean", said McFarlow.

Wayne was visibly disappointed . He tried to hide that fact that he was taking offence.

"Ask whether it is almighty".

"Do you have any idea on how to formulate that?"

"Something with the collections?" Wayne suggested. "Like, can he make our world, our 'collection', disappear?".

McFarlow didn't need much encouragement. He typed:

"Unknown True: Collection Sum Collections Statistical Probability
GreaterThan Minus Infinity Towards Not This Collection".

ENTER

"True".

"The answer is yes", McFarlow said.

"Oh".

"Are you sure?".

"I'm not even sure this isn't some sick joke".

"Ask it whether it knows everything, whether it is all-knowing".

"Unknown True: Collection Sum Collections Includes Equation Solved True Sum Actions This Collection"

"Not True"

"Hm", said Wayne.

"So he claims to be God and to be able to be all-powerful or at least able to destroy us, but there is no heaven and he does not know what is happening here?"

"Nobody was ever sure about the true nature of God" said McFarlow.

"It's obviously better to ask him directly".

"A pity he doesn't speak normal English" Wayne joked.

"Can't we send him some pictures, ask him what he thinks about starving African AIDS orphans, that kind of stuff?"

McFarlow looked at him.

"That's not such a bad idea at all. We could send it in the same format as the blueprints. Digitized pictures, black & white, as binary digit in squares with the same side length as the blueprints we got".

"OK then, let's do it", Wane said.

They Googled some pictures of starving children, victims of the Hiroshima bombing and a particularly gruesome image from the Holocaust. They scaled the images to the right size and converted them to monochrome.

From the network, they prepared to send the images to who- or whatever was on the other side.

"When were are really talking to God, I would like to see what he has to say about THIS" McFarlow mumbled. It would only take a second or so to send them all and they accompanied the images with the following question:

"Unknown: Sample Here Collection Towards Collection Sum Collections Unknown True False".

Both mathematicians realized there was no way of expressing an ethical judgement, of expressing "good" or "bad" in mathematical language. They needed a more subtle means of communication. But whoever was on the other side seemed to be able to make sense of their symbols, at least for now.

They proceeded with sending the images, which took only a second or so.

But there came no answer.

They tried a few more questions but there was no response. They thought they had perhaps overloaded the tranmitter.

Later that day, the engineers put the diamond marble into one of the nine spare tranceivers and McFarlow and Drury were allowed to try again. No result.

They handed over the records of communication, and they were reproached for having sent the images.

Another team took over, with NSA minders this time.

The line was dead.

McFarlow suggested offering an apology, which he creatively formulated in LaTeX:

"True True True: This Collection Element Equals Minus Infinity This Collection Element Equals Not True Not True Not True"

A tear ran over his cheek as he typed it. The only chance for a dying Earth to be elevated to a higher level - technologically as well as spiritually - forever spoilt by a reckless demonstration of the worst of humanity?

 An answer never came.

Reached Clockcycle Level

The tactics code is almost finished (1000+ LOC but a lot of that is due to LF's and unrolled loops), and the more I work on it, the faster it becomes.

I have a kind of ADHD, and often, the only way I can design an algorithm is to get away from the keyboard. Depending on the finances and the weather, it's either the pub or the tub :-) Today I walked to the harbor and designed a simple stack-based floodfill algo over a beer. The challenge was splitting empty chains most efficiently by re-using some of the cleverly-represented data, so that I do not have to floodfill both parts of a dual split.

Then I went home and hacked it up.

I keep discovering ways to get that code faster. Letting small arrays start on a cache line is an obvious speedup, but at the moment I am way beyond that and am using AMD's instruction latency table to decide whether a SHR with an AND could be replaced by a table lookup to shave off one cycle, that sort of thing. A pity I have to hit the sack, because I just found yet another dramatic speedup trick that I'm eager to implement because it also makes the source smaller and easier to read (the source looks, um, extraterrestrial).

Of course, the resulting 64-bit MASM assembly that Free Pascal generates will have to be hand-optimized by yours truly, but that will be low-pri. First the thing has to actually work, and it needs stuff around it to automate it as well. No need for undo code: I use a state stack that, due to minimalistic data representation, fits a deep treesearch entirely in the L1 cache.

Someone suggested that my business goal should be perfecting the Help file, but after years of work on Moyo Go, I need to re-invent myself, not to mention the need to do the hardest things when one's brain is youngest. There is an optimum between experience and number of deceased neurons, and it shifts leftwards with algorithmic complexity :-)

If Moyo Go wants to compete with the Big Boys and, as is the goal, ultimately dethrone them, I really have to bootstrap myself out of the swamp of bugfixing ever less serious bugs and perfecting things that are already pretty good. Nothing kills a business faster than lack of innovation. Moyo Go was never intended to be the best Go databasing/pattern system, it got that status because the Joseki library module turned out to be a super-powerful pattern expert system, so successful that even Microsoft tried to copy it. But my goal is to make a dan level Go program, and, heaven permitting, I'll succeed if I can keep away from that Help file :-)

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.

A Philosophy of Quality

This is the car I bought last week, a 1990 Saab 900i v16.

I posted this not to "show off" (the thing set me back a mere 1,500 $) but to make a point: Saab automobiles are pioneering marvels, built according to a philosophy of quality that fits that of my own. Saab originally made military fighter jets, and this is especially noticeable in older models.

These cars are fast, luxurious and very comfortable, just like Moyo Go Studio (-:

Those cars have a comfortable cruising speed of 100 mph, wonderful details like soap-spraying headlight wipers, heated chairs and electrical sunroof but most important for me is the humongous cargo hold when the back seats are lowered (my car is longer than the one in this picture and has those typical isolated tiny back windows, I bought the 5-door model but the color is exactly the same, only much darker :). In Stockholm there is a Saab 900 taxicab that has a million km on the clock and it still has the same engine!

This blog entry illustrates another important point: That it is possible for a single person with very limited means to produce high-end, state-of-the art software that can compete at the highest level. Take the Swedish Saab Gripen (photo). Sweden, a country of eight million people, builds jet fighters on a par with the Eurofighter and can even compete with the Joint Strike Fighter. The Moyo Go Studio / SmartGo competition is similar. MoyoGo is made by someone with almost zero funds, SmartGo is made by a multi-millionaire, but that is often a liability as well, and I think ultimately, it will be its demise because Anders simply buys whatever is hard to program. He has bought the source code of his TsumeGo module (Thomas Wolf's GoTools), and he has bought the sourcecode for his Joseki module from MasterGo. The result: An unmaintainable hodgepodge of "not invented here" stuff that will gather dust and rust.

In the long run, Moyo Go will win because it's made of higher quality, in-house parts.

Freeware Editor Headaches

Yesterday night I spent a few feverish hours trying to make an update to the Freeware SGF Editor (to add translations, multiple gobans and drag & drop skins/files).

Result: I destroyed the sources for the freeware version. The problem is that maintaining the same sourcecode for two versions is complex. MoyoGo is an enormous application and I have to disable thousands of parts with conditional compilation compiler directives, but I also have to physically remove all GUI widgets that are not used or hide them, whatever is appropriate.

This process is labor-intensive, and as I now know, error-prone. I simply have no time to do it, the coming months. It's too much stress, I need to concentrate my efforts on the tactical module and a few other things that suck up time and that are much more important at the moment.