Attack of the Underflow

In principle, the last major piece of Wallace has landed: randomly generating solutions, evaluating them, throwing away bad ones, and generating new solutions through asexual (cloning and mutating) and sexual (using crossover) reproduction.

However, there’s two small problems. First, the stack-based VM is exceptionally prone to crashing. Second, the stack-based VM is exceptionally prone to crashing. Now I know technically speaking that’s only one problem, but I thought it was such a big one, it was worth mentioning twice.[0]

The implementation of the VM, of course, is fine. (At least, there aren’t any known bugs in it.) Rather, the programs that are running within the VM have a tendancy to perform an illegal operation and crash. There are four ways in which a program can crash inside the VM, most common first:

  • Stack underflow: It tries to pop a value off the stack, but the stack is empty.
  • Reserved opcode: It tries to execute an opcode that has no operation associated with it.
  • Stack overflow: It tries to push a new value onto the stack, but the stack is already full.
  • Divide by zero: Because you can’t.

Reserved opcodes could be eliminated by assigning them to something, but the stack underflows are quite problematic. Out of 89 operations the VM supports, only 6 of those don’t try to pop anything off the stack. The vast majority of operations not only need to pop their operands, but they also leave the stack with fewer values on it than it originally had. So naturally, when you’re randomly generating programs to run in the VM’s instruction set, most of the time they’ll trigger a stack underflow and crash.

In fact, the vast majority of programs crash on their very first instruction. Furthermore, in a trial using a population size between 100 and 500 candidate solutions, measuring fitness solely by how many instructions got executed before a crash, even after 50 generations the typical candidate solution still only managed to successfully execute 2 instructions before crashing.

Granted, that’s up from a median of 0, but it’s still not very encouraging. And to keep this in perspective, you’ll obviously want these programs executing more than one instruction per emulated frame, and there’s slightly over 60 such frames per second. Programs that die after only a handful of instructions aren’t going to get anywhere.

(As a side note, however, one candidate solution — one of the initial randomly-generated ones — actually managed to hit the 6000-instruction timeout I arbitrarily set! I wasn’t able to peek into it and see what it was doing, but I strongly suspect it managed to jump into the “uninitialized” portion of memory, which would be filled with 0 bytes, all of which map to nop. Whatever it did, that “gene” never got passed on to anyone else in the population.)

I’m forced to conclude that, despite the stack-based VM being attractive from an implementing-the-VM perspective, it’s quite unsuitable when throwing random code at it. A register-based VM would be infinitely more robust, since the registers the instructions operate on will always be there; just the values stored inside them would change. Alas, this change involves replacing just about everything in the VM except for the mutation engine, which is a large chunk of tedious (but relatively straightforward) coding. But unfortunately, it must be done.


[0] To steal a line from my laptop’s namesake.

4 Responses

  1. This is why most GP systems I’ve seen store the program itself in a tree, with the tree itself representing stack operations, and where executing just involves traversing the tree in a depth-first manner. This also allows for easy mutation because the only operation you have to support is subtree-swap (since you initially seed your genepool with various primitives like +(0,0), -(0,0), setA(0), etc).

    LISP is a pretty common language to use, since mapping s-expressions to a tree is trivial.

    I was actually going to comment on this in the previous article but I didn’t see it until after I’d updated my RSS feed again.

  2. True, but an expression tree doesn’t let you do any control flow, which could limit what the solutions could do. OK, you could use a series of expression trees, sort of like what a compiler might do with its IR trees, but then you might not be able to swap any two arbitrary subtrees.

    Using bytecode for everything, mutations simply act on one or more bytes, regardless of whether they represent code or data (or both). There’s also the possibility of evolving a self-modifying program, something which most sane programmers stay as far away from as possible.

  3. it’s just one excuse after another…

  4. Er, LISP has an if structure. In the context of a GP you don’t need anything so fancy though, you can just have it conditionally execute the second child if the first child evaluates true.

Comments are closed.