Home » Library » Modern Library » Meta Getalife Coretierra

Meta Getalife Coretierra


 
 
   

Get A-life

Core Wars: Crash The System

Early computers were so expensive that it was unthinkable that you would have an entire computer to yourself. Instead, many people would use a single “timesharing” computer system. Unfortunately, early primitive operating systems lacked technologies like memory protection. If a program accidentally malfunctioned, it would sometimes end up crashing other programs, or the operating system itself.

Computer scientists tend to have a strange sense of humor, and some of them decided to make competitive program-crashing into a sport. Rather than crashing the actual computer, they built software that modeled a much simpler virtual computer, designed so it could run malicious programs without damaging the real operating system–much like the Java virtual machine in many web browsers.

 

The game became known as Core War, named after the “core memory” used in early computers; it was first described in detail by A.K. Dewdney and D.G. Jones in 1984. The virtual machine used for the game had a very simple instruction set called RedCode. Competitors would write RedCode programs that attempted to copy themselves elsewhere in memory and then run the extra copies. Programs would also try to find and overwrite competing programs and make them crash. Some Core War code would carefully take over the competing software, stealing its allocation of CPU time like a virus. Eventually, the last program left running would be the winner.

By the late 80s, Core Wars had become a cult pastime amongst computer programmers, with several versions of the software existing. There are even tournaments held over the Internet. However, it would take a biologist to make the next imaginative leap.

  ;redcode

;name Dwarf

;author A.K. Dewdney

bomb DAT #0

dwarf ADD #4, bomb

MOV bomb, @bomb

JMP dwarf

END dwarf

Tierran Mutants

 

Tom Ray had studied evolution in the real world, but found it a frustrating subject. He wanted to be able to watch its effects on thousands of generations of organisms, evolving there in front of him.

Years before, an MIT computer hacker had introduced him to the idea of self-replicating computer code in a virtual machine. He wondered if he might be able to build some kind of artificial life or a-life software, that would let him run experiments in evolution. He built a computer program to model a virtual computer similar to the one in the Core Wars game, and called his virtual world Tierra. However, Ray added a new feature to the virtual world that had been missing from Core Wars: mutation.

Computers are generally programmed in textual languages of words, symbols and numbers that humans can understand–languages like C, Java and BASIC. However, the integrated circuit at the heart of the machine only understands a much simpler language of binary numbers. To add two numbers together, you might need to read them from memory into spaces called registers, add the two registers together, and then write the result out to memory again. Each of those small steps would be represented by a series of binary numbers.

Your web browser software consists of millions of binary instructions. They were assembled automatically by software called a compiler, following instructions written in the original programming language–the “source code”. It’s possible to write machine code directly, but only if the program is fairly small. The programs in Core Wars and Tierra are only a few tens of bytes, maybe a couple of hundred at most, and are written in machine language.

Ray altered the Tierra system to simulate a computer with a slight flaw. Every now and again, the machine code instruction which copied data between memory cells would randomly flip one of the bits during copying. If the data being copied was the machine code of the program itself as it tried to reproduce, the result would be a slightly different mutant program.

High-end computers use special error-correcting memory, specifically to avoid bits getting flipped. They do this because if you flip bits in the machine code of a piece of software, it will almost certainly crash. Conventional wisdom before Tierra was that randomly flipping bits of a machine code program could never result in improvement to that program–the chances against it were astronomical.

Like in the real world, Tierra had natural selection. Mutant programs that crashed were eliminated as unfit. In addition, a process called The Reaper would pick off the oldest programs to free up space–meaning this new virtual world had death, as well.

Ray decided to start his Tierra system off with a population of the most simple programs possible. He wrote a piece of code that simply copied itself elsewhere in memory then spawned the copy. It was 80 bytes long, so he named it 80. He spread a few 80s through the Tierra system’s memory, and started the clock.

For the first few thousand generations, nothing much of interest happened. There were a few minor mutations that didn’t break the code, but that was about it. Before long, though, there were a number of 81s–mutants with an extra byte of program code. A little later, a 79 appeared. Because the 79 had one less byte of code, it took less time to reproduce, and was more successful than the 80 or 81. It began to take over the Tierra ecosystem.

Next, something astonishing happened. A 45 appeared. Ray was initially mystified; he’d written the simplest code he could imagine and it was 80 bytes. A 79 seemed reasonable, but how could a 45 reproduce in only just over half the space? Examining the code of 45 provided the answer–and a new surprise. The 45 was a parasite: instead of reproducing itself, it hunted for the reproductive code of an 80, then called that code. It was almost like a biological virus, which reproduces by inserting its DNA into a host cell and using the cell’s reproductive apparatus to build more viruses.

No parasite code had been written at any stage in Tierra’s development, and the system had not been designed to support parasites; the fact that one program could make use of code in another was an accident. Yet the system had reproduction, death, natural selection and mutation, and that seemed to be enough to cause parasites to appear from nowhere. Suddenly Tierra was an ecosystem in balance. If there were too many 45s, then the 80s would die out, unable to compete; and then the 45s would die out too, unable to reproduce without a host.

It turned out that the 79s were immune to the 45 parasite. Ray placed some 45s in a Tierra world heavy with 79s, and soon a new 51 parasite appeared which was able to use 79s to reproduce. If the system was left running long enough, parasites of parasites began to appear.

Then came another surprise: after a long period of mutation and natural selection, another new program appeared. This was a 22, and it was completely self-contained, not a parasite. Somehow Tierra had evolved a program that was smaller than any human being had managed to come up with.

The power of evolution had been demonstrated, but Ray was curious to see which elements of the system were required for evolution to work, and what ranges of frequency of mutation resulted in rapid evolution. He tried turning off mutation completely, out of curiosity–and was amazed to find that evolution carried on happening anyway!

It turned out that sometimes, two programs attempting to reproduce would choose the same location for their offspring, and would interact during reproduction. One of the programs might be overwriting the same memory as the other, slightly behind, and then die from old age or be killed by another program. The result would be a hybrid, with part of the code of one program and part of the code of the other. Similar hybrids would occur if a parasite was busy reproducing using a host program, and that host program died.

In sexual reproduction in the real world, the male and female genetic material from the two sets of chromosomes gets spliced together via recombination. Now it seemed Tierra had recombination too; and recombination alone, with no mutation, was enough to lead to evolution through natural selection.

Whereas Biomorphs were bred by changing the parameters of a fixed algorithm, Tierra’s equivalent of DNA described operations to perform. Like real DNA, it could alter the processes at work within the organism, change how it reproduced, and have a direct result on its evolutionary fitness. Tierra, unlike Biomorphs, did not need a human to guide it.

  80:

01 nop_1

01 nop_1

01 nop_1

01 nop_1

04 zero

02 or1

03 sh1

03 sh1

18 mov_cd

1C adrb

00 nop_0

00 nop_0

00 nop_0

00 nop_0

07 sub_ac

19 mov_ab

1D adrf

00 nop_0

00 nop_0

00 nop_0

01 nop_1

08 inc_a

06 sub_ab

01 nop_1

01 nop_1

00 nop_0

01 nop_1

1E mal

16 call

00 nop_0

00 nop_0

01 nop_1

01 nop_1

1F divide

14 jmp

00 nop_0

00 nop_0

01 nop_1

00 nop_0

05 if_cz

01 nop_1

01 nop_1

00 nop_0

00 nop_0

0C push_ax

0D push_bx

0E push_cx

01 nop_1

00 nop_0

01 nop_1

00 nop_0

1A mov_iab

0A dec_c

05 if_cz

14 jmp

00 nop_0

01 nop_1

00 nop_0

00 nop_0

08 inc_a

09 inc_b

14 jmp

00 nop_0

01 nop_1

00 nop_0

01 nop_1

05 if_cz

01 nop_1

00 nop_0

01 nop_1

01 nop_1

12 pop_cx

11 pop_bx

10 pop_ax

17 ret

01 nop_1

01 nop_1

01 nop_1

00 nop_0

05 if_cz

2000.01.01

#0123[4]5R

<PRV//NXT>

[Continued]