Thursday, February 18, 2010

Evolutionary AI: A Proposed Experiment

I've been thinking about this quite a bit lately, and I'm going to lay out a rough experimental design for an evolutionary approach to AI.  For the moment I'm calling it ELI, for Evolving Language Interpreter, in homage to the classic AI simulation Eliza.

From a technical perspective, I'm proposing that we start with the fabled Infocom Z-machine, because it's a framework engineered around a parser that takes input and generates output.  It was designed for interactive fiction and is not specifically oriented towards conversation, but its limited set of opcodes seems appropriate to the task.  It saves us designing a virtual machine of our own to fulfill much the same purpose, and lets us focus on the mechanism for generating, evaluating and "breeding" candidate codomes (no, that's not a word, but I like it as a simile for genome, so I'm going to use it until I find something better.)

I've considered whether using the Z-machine is a cheat, but there are biological analogies here.  It's very possible that chimpanzees have the vocal hardware necessary for speech, and we know apes can deal with language to a degree.  But our close relatives don't seem to have the cultural urge to communicate in the way that we do.  Similarly, the Z-machine is platform-independent and abstracts out the details of input, output, parsing and response so we don't have to deal with those at a code level -- that is, the hardware is already in place -- but it doesn't impose too much of a framework on what our random code does with its available mechanisms.  It does have an internal data structure, but so does our brain, and we are not generating anything but random code -- if it fits into the structure and does something interesting, then we are making progress.

Using the Z-machine means that we have a very fundamental fitness criterion right off the bat -- our random collection of bits has to be something that does not make a Z-machine choke.  So this helps us establish the endpoints of our preliminary evaluation scale:

0 -- Z-machine won't even run it
1 -- Runs on the Z-machine, spews gibberish
2 -- Capable of starting a conversation
3 -- Capable of continuing a conversation
(... a miracle occurs? ...)
10 -- Passes the Turing Test

The gap between 2 and 3 is likely to be very wide, and I have no idea what to do with 4-9 yet.  But at this stage everything about this idea is up for grabs, so I'll go with this for the moment.

There are also some technical considerations.  Early implementations of the Z-machine could handle up to 128k of code/data, so I'm going to start with a small codome size.  This will allow room for the system to grow and develop before its brain gets too big for its skull, so to speak.  Later implementations such as Frotz allow for larger files, so this may not prove to be a real constraint -- at any rate, if an individual codome grows too large for the Z-machine to run, its fitness will revert to an evaluation status of 0, essentially killing off that individual and limiting ELI's development in a completely natural way.

I'd ultimately like to build a website so many more people can try and evaluate ELI's current state, but to begin with I'm going to take a very simple approach to see if the idea even gets anywhere.  I'll write some code to generate a number of random codomes, and attempt to launch each one using the Z-machine.  It's very likely that none of them will even run at first, so everybody's fitness will be the same (i.e. 0) for the second generation.  Essentially all we'll have is random combination and mutation for some number of generations, all descended from the first random round of codomes.

If this approach is able to generate something that will at least launch under the Z-machine, that individual will gain fitness level 1, and its codome will inform multiple descendants in the next generation.  I expect that mutation, if it does arise, to spread very quickly.  It is also possible that mutations will arise in such a way that we jump from 0 to 2, receiving a sensible opening salutation like Hi. or Greetings! from the codome as soon as it's able to execute.  But as there's no selection pressure on the content of the opening statement until the codome can at least run, this is not likely.

It's a simple first step to try, at least, as the Z-machine testing can be automated -- I don't have to sit down and evaluate every response manually to start with, just let the process work until it comes up with (or runs for a long while and fails to come up with) a viable bit of Z-machine code.  Whatever happens, I'll share the results here.

No comments:

Post a Comment