MacTierra logo

How it works

This gives a brief overview of the inner workings of MacTierra, and therefore Tierra in general. See Ray (1981) for a more thorough treatment.

The Tierran environment

Tierra is essentially an emulator of a parallel computer with a variable number of CPUs. It has its own machine language (a vastly simplified machine code with only 32 instructions) and a novel addressing mode, both of which were designed to avoid the brittleness associated with standard machine code. Brittleness is a problem when you wish to allow the evolution of code fragments (which is what Tierra does), because the vast proportion of mutant fragments are completely inviable. Using its own machine language also prevents problems of code fragments 'escaping' and infecting the host computer, which cannot happen, either in the original implementation, or with MacTierra.

The machine language
Ray pared down traditional CISC instruction sets to end up with a language of 32-instructions including operands, which compares favourably with the 64 codons which are translated into the 20 amino acids used to make proteins in real organisms.

The instructions are listed here:

	nop_0		(no operation 0; used in templates)
	nop_1 		(no operation 1; used in templates)
	or1 		(flip the low bit of cx)
	sh1 		(shift left cx)
	zero 		(zero cx)
	if_cz 		(if cx=0 do next instruction)
	sub_ab 		(subtract bx from ax, result into cx)
	sub_ac 		(subtract cx from ax, result into ax)
	inc_a 		(increment ax)
	inc_b 		(increment bx)
	dec_c 		(decrement cx)
	inc_c 		(increment cx)
	push_ax		(push ax onto the stack)
	push_bx		(push bx onto the stack)
	push_cx		(push cx onto the stack)
	push_dx		(push dx onto the stack)
	pop_ax		(pop top of stack into ax)
	pop_bx		(pop top of stack into bx)
	pop_cx		(pop top of stack into cx)
	pop_dx		(pop top of stack into dx)
	jmp		(move ip to template)
	jumpb		(move ip backward to template)
	call		(call a procedure)
	ret		(return from procedure)
	mov_cd		(move cx to dx)
	mov_ab		(move ax to bx)
	mov_iab		(move instruction pointed to by bx to address in ax)
	adr		(address of nearest template into ax)
	adrb		(search backwards for template)
	adrf		(search forwards for template)
	mal		(allocate memory for daughter cell)
	divide		(cell division)
The addressing mode
The Tierra language uses 'addressing by template', another feature borrowed from the world of wet life. After each jmp or adr instruction is expected a template of perhaps 4 instructions which consists of nop_0 and nop_1 instuctions. On execution of a jmp the simulator looks either forwards or backwards from the instruction pointer for the complement of this template, and resumes execution at this point. Thus a mutation in a template which turns 0001 to 0011 could have signficant consequences on program execution.

The CPU

Each creature in the soup consists simply of a string of machine instructions, but is assigned by the simulator its own processor (CPU) which executes those instructions, in the standard fetch-decode-execute-increment IP cycle of most computers. For example, if the instruction pointed to by the IP is 0x02 (or1), the CPU flips the low-order bit of the contents of register cx. If it is 0x14 (jmp), the CPU looks in both directions for the complement of the 4 instructions that follow that jmp instruction, and then moves the IP to point to that if found.

However, execution of these instructions is flawed at a low frequency, and the copying of instructions from parent to offspring also involves flaws at a low rate. This is equivalent to mutation and copying errors during DNA repliation.

The CPU data stucture is:

struct cpu {
	short	ax;		//Address register
	short	bx;		//Address register
	short	cx;		//Numerical register
	short	dx;		//Numerical register
	char	fl;		//Flag (set when errors occur)
	char	sp;		//Stack pointer
	short	st[10];		//Stack
	short	ip;		//Instruction pointer
}

The soup

The soup is simply a block of computer memory between 16 and 256 kilobytes in size, within which the creatures live. It is cellular, in the sense that a creature cannot simply write instructions anywhere, but has only write priviledges in its own block, and that of its daugher cell, if it has one (though see Settings for details of how this can be controlled).

In MacTierra, the soup is simply copied into a pixel map for display, and can then be overlayed with a 'blocks' or 'fecundity' layer, to show more detail about the location of active creatures.

The Slicer

The slicer doles out to each creature in turn a short time-slice, during which it executes a small number of instructions. This time-slicing enables an imperfect implementation of parallelism in the simulator. In MacTierra, the slicer is implemented as a circular list of creatures which is rotated at every time-slice. Offspring creatures are only inserted into the slicer queue when they become independent from their parent (when the parent executes the divide instruction).

The Reaper

When a creature is born, it is entered into a linear 'reaper' queue, at the bottom. Put simply, it moves up the queue when it fails to execute instructions (because its algorithm is flawed), and stays where it is, or moves down when it succeeds. So flawed algorithms tend to move up the queue. When the soup reaches the reaping threshold, say 80% full of creatures, the reaper kicks in, and kills off the creature which is at the top of the reaper queue (i.e. the most flawed one), at which point the CPU is deallocated, and the creature is removed from the soup (though its dead code remains there).

The Genebank

When a creature is born, it may have a genotype that differs from its parent because of mutations and copying errors. In MacTierra, such a new genotype is distinguished from its parent by a '; for example, a creature called 80aaa' has a different genotype from 80aaa, from which it is descended.

Many such offspring will be inviable, and will be quickly eliminated from the soup. However, when a new genotype managed to successfully replicate twice (i.e. produce two offspring which are identical to itself), then it is entered into the genebank, and assigned a new genotype. So 80aaa' may give rise to 80aab.

Genotypes are named using a combination of their length (80) and a three-letter code that is simply incremented when a new creature enters the genebank (aab).

Mutation

Mutations introduce variabilty into the system, and it is replication with variabilty that is necessary for evolution to occur. In MacTierra, variation is introduced in three ways: in cosmic mutations, copying errors, and flawed instruction execution.

Cosmic mutations cause the flipping of random bits in the soup at a low frequency, and are responsible for the 'speckles' you can see in a young MacTierra soup.

Copy errors occur during execution of the mov_iab instruction, and result in the instruction being copied changing at a low rate.

Flaws can occur during execution of the any instruction, and result in the instruction either using the wrong registers, or doing an operation one too many or too few times.

What to look for

Tierra provides a very rich environment in which all sorts of ecological, evolutionary and informational patterns can be observed. MacTierra in particular is extremely amenable to experimentation, by interaction of the user with running simulations.

Some things to look for, and some ideas for experiments you can perform are:

Long-term trends
Does maximum fitness increase over time?
How does the number of coexisting species vary over time? How is this affected by the size of the soup?
How do speciation and extinction rates vary over time? Does MacTierra show 'punctuated equilibria' in evolution? i.e. long periods of fairly low activity, interspersed with bursts of high speciation and extinction. Are the two rates correlated?

Different strategies for replication
Do parasites evolve?
You get an idea of whether an organism is a parasite by seeing if it replicates on its own. Dragging the suspected parasite into an empty soup (hold down the option key when choosing 'New' on the File menu), then run to see if it replicates. If not, is some dead code in the soup sufficient to get it going? Drag another creature (say 80aaa) from the Menagerie into the soup, close to the parasite, then delete it by dragging to the trash; this leaves the 'dead code' behind. Now run again.
Does any form of sociality arise? Some creatures may need to occur in large groups before they can replicate effectively.

Interactions between creatures
You can track the populations of two creatures by dragging them into the two wells in the graph window, and collecting 'Two genotype' stats for plotting. Do you get Lotka-Volterra dynamics?

Results of different levels of mutation
What happens when mutation is really high? Or really low? Does this affect speciation and extinction rates, and maximum fitness?

Results of selection for creature size.
How does creature size respond to selection on size? How does this interact with mutation rates?

That should be enough to keep you busy ;-)
If you evolve any neat creatures, or have ideas for other interesting experiments that could be performed, mail me!

Table of contents Installation Running Soup settings Preferences Statistics
Assembling Interface How it works c.f. Tierra Bugs and features Legal stuff