At the forefront of Artificial Intelligence

Home » Articles » Genetic Algorithms » Applications/Code

eVM & Shinka: Experiments Evolving Assembly Code

eVM and Shinka were experiments I'd tried. I've decided to release the code, since it might be useful or interesting to other people beside myself! If you want to compile and load real Zilog Z80 code into eVM you will need ZiLOG ZDS or another similar assembler. Below is a modified version of my initial report on Shinka.

Shinka (Japanese for evolution) is a program I am creating and experimenting with. I wanted to implement some similar to TIERRA but using some of my own ideas. Shinka is in the very early stages, as I am programming the virtual machine (eVM) at the moment, and experimenting with the various ideas as I go along. This page is intended as a mini weblog detailing the progress of Shinka.

I'm not so interested in breeding programs, as actually bringing about an orderly program out of "chaos". By executing random opcodes, it is possible that instructions will start to align to create a "useful" program? If this program then self-replicates, I'll be mighty impressed! I'm not trying to recreate the Earth's evolution, instead I'm trying to mimic the equivalent on a computer and observe what happens.

Implemented

Virtual Machine (called eVM) based on ZiLOG Z80 microprocessor. The eVM currently holds about 40-50 opcodes including: 8-bit and 16-bit loading, memory addressing, stack (push and pop), logic operators (and, or, xor, cpl, not), arithmetic (add, sub, inc, dec) and compare instructions. The eVM does not (and will not) include an index register, memory refresh register or interrupt register.
Random function: load a random number into any 8-bit or 16-bit register.
Support for ZiLOG Developer Studio: ZDS is the IDE that can be used for Z80 development. ZDS outputs Intel Hex format, which must be stripped and converted into pure object code. Custom instructions are handled via macros.

To Do

Complete instruction set and custom set. This includes 16-bit arithmetic, jumps and function calling (perhaps). The port commands will also be implemented, but the context and protocol is TBA.
As of yet, programs are not loaded into an address space. Instead they are executed out of the (virtual) RAM, therefore, self-modifing code is impossible. The problem with loading the programs into the RAM is how to handle multiple-programs.

Results So Far

Something quite interesting has come up. Even at this primitive stage, an instruction group has found a way to self-replicate itself perfectly. What I did was set up the virtual machine to generate 64K of random opcodes in its RAM. The virtual machine would then set about executing them. I would take RAM dumps before and after. I found that after around 500 iterations, the instructions would start to form groups. After about 1000 iterations, two opcodes would completely dominate but would be found paired together. The opcodes were 0x0001h and 0x00C5h. Now, look at a four of these instructions adjacent to each other (once the opcodes are executable, I've placed a comment denoting the Z80 instruction):

0x0001 	
0x00C5 	
0x0001	; ld bc,C501h
0x00C5	; push bc

Now, due to the Z80 architecture and how the stack functions, this is a simple version of self-replicating code! When it pushes C501h on to the stack, it places another version of itself in the RAM! Soon it takes over the entire RAM! Check this register dump after 1024 iterations:

Register Dump:
  A:    0x0097 | 151
  B:    0x0001 | 1
  C:    0x00c5 | 197
  D:    0x00c5 | 197
  E:    0x0001 | 1
  H:    0x0040 | 64
  L:    0x0018 | 24
 SP:    0x706a | 28778
 PC:    0x002c | 44

Notice B and C? I've also seen the RAM overtaken by 0x00C5 0x00C5 which works on the same principle.

Download Code

As I mentioned at the top, I've released this code as-is - it is incomplete, undocumented, shoddy, badly-coded and whatever else but interesting! If you make any improvements to the code, I'd really like to hear about it! Included is the code as I last left it, a release compile (executes 1024 iterations of the RAM in under 4 seconds on my computer) and a Projects directory with the Zilog ZDS file, assembly file and a hex file to load. Enjoy.

evm.zip (130Kb)

Submitted: 05/07/2001

Article Toolbar

BibTeX entry