Wednesday, September 5, 2007

12:50, press Return

The deed is done.

I and my friend Nils made a "sprint" last night, where we finished the first version of our seed AI.

First we made a simple IQ-function that tests how well a program (a Program Generator or PG) can generate new programs (leaves) from feedback of how close a leaf is to what we want.

A PG that receives the best IQ so far gets a chance to generate new PG's, in effect it becomes a Program Generator Generator. We call this state a Challenger. When a Challenger generates a new PG with the best IQ so far, it has verified that not only does it have good IQ, but it can produce other programs with good IQ, and is thus promoted to the status of Master (and the smart PG gets to be Challenger).

The programs are generated and run in a circular buffer under a virtual machine, where all sequences of integers are valid programs and no operators can throw exceptions. Such a VM is much slower than machine code, but the process gets faster than if it were running on bare bones x86, because on an x86 (or other architecture) most bytes are meaningless and will throw exceptions, which are slow to process. A PG that is good enough (for example a human) to understand how to write code without generating (many) exceptions, would theoretically run faster on x86, but our current primitive PGs will benefit from a virtual environment.

Anyway, we wrote the code, pressed Enter (the title is a reference to the nice movie Pi), and voĆ­la, our random generating seed started finding more intelligent programs than itself - Challengers. After a while, Nils calls it 15 seconds, a Challenger managed to become Master and after a longer while the Master produced a Challenger that later became the third generation Master. Spectacular!

Now we just need a better IQ test and a way to inspect the generated programs! Well, we also need tons and tons of hardware. This is the sort of task that could happily use up Google's entire computer armada for a year and still benefit from more. Hmm.. perhaps if I ask them nicely..

No comments: