Totally Random

Each animal in EvolveJs is written in a specialised assembly code. This assembly language was designed with some inspiration from Tierra. Each thread is essentially a stack machine and each operation operates on that stack.
An assembly operation is a pair of [operation, operand].

One of the key concepts is in markers used for jumping. To make the animal’s code more robust to modification, all jump targets (such as for loops and branches) are marked as a series of nops, and the jump command specifies the jump target as the number of nops to search for.

So as a concrete example I will show a simple process that can reproduce itself.

This is the 5 label. The nop function does not require an argument, so is by convention set to 0.

["nop",0],["nop",0],["nop",0],["nop",0],["nop",0], //label 5


Now we initialise the read pointer to point to the start of the parent, and the write pointer to point to the end of the parent. The jmp*PtrB functions jump the pointer to the start of the nop template, and the jmp*PtrF functions jump to the end of the nop template. In this code all templates are unique, but it is not necessarily so. The jmp*PtrF functions search forward and wrap around, and the jmp*PtrB functions search backward and wrap around.

["jmpReadPtrB",5], //jmp to start of template 5
["jmpWritePtrF",2], //jmp to end of template 2


Get the parents memory size, allocate memory at the end of the parent, and move the write pointer to the start of the new memory.

["pushMemSize",0],
["alloc",0],
["incWritePtr",0], //inc write pointer to start of new animal


The copy loop. Copy from the read pointer to the write pointer, and increment both pointers.

["nop",0], //start copy loop
["copy",0],
["incReadPtr",0],
["incWritePtr",0],


Push the value for the write pointer and the animals total memory size (including the new child memory) to the stack and compare them using the lt operator.

["pushWritePtr",0],
["pushMemSize",0], //if writeptr < memSize
["lt",0],

Then, if write pointer is less than memory size, jump back to start of template 1.
If write pointer is not less than memory size, then the execution pointer gets incremented by 1 + operand (in this case 1), which means that the copying process has finished.

["ifdo",1],
["jmpB",1], //if not finished copying


This is the division loop. When a parent divides, the parent attempts to put the child in the square immediately in front of them. If this position is already occupied, then division fails, and the parent gets to try again.

["nop",0],["nop",0],["nop",0],["nop",0],["nop",0],["nop",0], //template 6

Divide attempts division and pushes a boolean result onto the stack indicating success. If division succeeds, then jump all the way back to template 5, and start making a new baby.

["divide",0],
["ifdo",1],
["jmpB",5], //if division successful

Here, we are using one of those nop templates to store data.
The memory pointer jumps to the first memory address in the 6template. The data that is stored in the operand is pushed onto the stack, incremented, stored back in the memory slot and compared to 4 (number of cardinal directions)

["jmpMemPtrB",6],// jump the mem pointer to a location to store some data
["pushM",0],
["add",1],
["popM",0],
["pushM",0],
["push",4],
["gte",0],

If it has already tried this 4 times, then this animal is surrounded and can't reproduce at the moment. So it sleeps, and we reset the counter. Otherwise, the ifdo,3 increments the execution pointer by an extra 3.

["ifdo",3],
["sleep",450],
["push",0],
["popM",0],

The divide didn't work, try again facing in a new direction.

["turnR",0], //turn around and try again
["jmpB",6],

The end tag

["nop",0],["nop",0]

This application is a “proof of concept” evolution simulator. Each animal (process) has the following properties

• Memory: This is both readable and writable memory addresses starting from address 0 for each animal.
• Threads: Each animal can have multiple threads that communicate via it’s memory.
• CpuTime: Each animal is granted cputime by it’s parent when it is born, and after that is given cputime by the environment (like sunshine) each cycle.
• Position: Each animal has a current position in the grid
• Direction: Each animal is pointing in a certain direction (this is not currently shown in the display.

Each thread in each animal has the following properties:

• Stack: this is essentially current memory. Operations can put information on the stack, manipulate the top item on the stack, or pop information off the stack.
• Execution Pointer: Each thread is executing the same program, but potentially at a different address (different function) in memory.
• Read Pointer and Write Pointer: These are used for copying operations.
• Memory Pointer: This is used for writing operands only.
• Speed: An animal can choose to operate faster, multiple operations per second. This is expensive for the animal.
• SleepCycles: The thread can sleep for a set number of cycles. It will be woken when this counter reaches 0.

There have so far been two Ancestors created:

1. A simple non-mobile vegetable. This has a single thread that is devoted to reproduction.
   Once all 8 slots around the animal are full, it sleeps for a period and then checks again.
2. A simple mobile vegetable. This has two threads: one is devoted to reproduction, the other moves in a straight line forever.
   When it reproduces, it turns right.

Animals reproduce by allocating memory at the end of their memory, then copying their code into the new memory, and then dividing the new memory.
This creates a new process.
The copying process has a non-0 random chance of failing to accurately copy the data requested.
This results in the child not always being the same as the parent, and the chance for evolution is created.
Successful species (when a species has had enough animals with the same code, occurs at powers of 10) are sent to the server.
When the application starts it requests the 10 best animals from the server.
Things you can do:

• Click on an individual to see information about it on the “Process Details” tab
• View code of species on server to see what has evolved from the “Progenitors”

Future features:

• Ability to examine the code of any individual.
• Allow the user to insert new processes (with new code) into the environment.

I have been playing with javascript a bit lately, testing out techniques that I might use for doing a full web 2.0 business application (if any clients would agree…). The application that I have written is a game along the same sort of lines as RoboCode. 

It allows users to implement "animals" in custom written assembly code ("genomes"), which compete for resources and can move around and eat each other. I have currently written two simple genome, a vegetable (it doesn't move) and a predator (it does move). They are both using almost the simplest algorithms for each of these tasks as possible.

The animals run virtual cpu's and also implement virtual threading. The predator animal has a reproductive thread and a movement thread. The vegetable has only a reproductive thread. And as the last real feature, the animals also have a non-zero chance of their mem-copy commands (part of the requirement of reproduction) failing to copy correctly. This introduces mutations and hopefully mutation.

The javascript application is backed on the server by a ruby on rails application that stores successful animals (animals that survive to reproduce).

I have a few problems with the current implementation that limits it's usefulness.

1. First, the application is pretty slow. It runs at about 600hz on my computer in firefox 3b2. (This means that it executes 500 virtual cpu instructions per second.) Compare this to my actual machine running at 2 billion instructions per second, and there is a factor of 4 million difference. Some of this can be explained by the fact that each virtual instruction is implemented as a block of javascript code that does stuff to memory in the cpu. Some more is probably explained by me not using javascript to its full potential. The rest must be explained by javascript being s l o w. I have used firebug to do some profiling of the code to find hotspots and have been able to find some issues. To make the evolution part of the application do anything useful it would need to be 10x faster at least. But I think that to make it a factor of 10 faster i would need to radically change the architecture.
2. Another issue is that the application occasionally just freezes. I imagine it is doing some sort of garbage collection in the background. I would love to be able to get more control over this, so that I could see what was happening, or at least predict when it might happen.

These are the same issues that I would face implementing a large javascript client in a web 2.0 application, so I am glad to have found them now rather than later.

An early alpha version (where it isn't possible to inject new animals into the application, except by editing the source directly, and the server communication isn't working properly) is available. The source is all on the page in easily read code, if anyone is interested.