Evolving Warriors

By Linus Thorsell

 

 

 

 

 

This page was created by Linus Thorsell, Gothenburg, Sweden 1999-11-01

Last modified by Linus Thorsell 1999-11-02

Specific questions and/or requests for clarifications can be directed by email to:

mailto:f95lith@dd.chalmers.se

Abstract

Two computer programs in their native habitat – the memory chips of a digital computer – stalk each other from address to address. Sometimes they go scouting for the enemy; sometimes they lay down a barrage of numeric bombs; sometimes they copy themselves out of danger or stop to repair damage. A.K. Dewdney introduced this game in an article in Scientific American the year 1984. He named the game Core War.

The Core War Tribes project is aimed at evolving Core Warriors, using the tools of Genetic Programming.

A Core Warrior is a program whose ultimate goal is to take total control over a computer by throwing out all other processes, similar to what a malevolent virus would do to your personal computer.

The instruction set for Core Wars, Redcode (see section The System), is a limited assembly language, but it is computationally (Turing) complete. Thus anything, which can be done by a computer program, can be done in Core Wars, given a large enough memory space.

The Core War system can be compared to a biological system, where the production of synthetic organisms based on a computer metaphor of organic life in which CPU time is the “energy” resource and memory is the “material”’ resource. Memory is organized into informational patterns that exploit CPU time for self-replication. Mutations generate new forms, and evolution proceeds by natural selection as different genotypes compete for CPU time and memory space (as discussed in the section Comparisons with Artificial life and similar systems).

The structure of this document

This document is divided in the following parts:

Abstract1

The structure of this document1

The History. 2

A Fight to the Bitter End...3

Further reading. 4

The System.. 4

Introducing Redcode. 4

Instructions. 6

Operations. 6

The addressing modes. 8

The instruction modifiers. 8

Modulo math. 9

The Process Queue. 9

Further reading. 10

Introducing Core War Tribes. 10

Score. 10

The Genetics. 10

Comparisons with Artificial life and similar systems. 10

Core Wars, Darwin flavored. 11

The Smallest Gene. 11

Recipe for primordial soup, a la Core Wars. 11

Selection and Evaluating. 12

Tribes and Breeding. 12

Copy with optional Point Mutation. 12

Single point crossover13

Results and Discussion. 13

The Next Generation. 14

The Future. 14

Future genetic work. 14

Future features for the simulator14

P-space - the final frontier14

Acknowledgements. 15

References. 15

Appendix. 16

The Warrior E1. 16

The Implementation. 18

The History

A.K. Dewdney proposed the concept of Core Warriors in an article in Scientific American, around 1984. Dewdney also proposed a simulated environment for running these warriors, and a simple assembly language (Redcode) for describing them. This was quickly assimilated by a large group of computer hackers around the world, who grew fond of the idea of “competitions among programmers on their on turf”. Annual competitions were held, where contestants would send in their best warriors and let them compete against the warriors of other programmers.

The simulated system goes by the name MARS (Memory Array Redcode[1] Simulator)

An international standard for Core War was created: the ICWS (International Core War Society) the first one came in 1986 and was followed by ICWS’88 the latest is the ICWS’94 draft standard [ICWS’94].

The memory, which is by tradition named “core”, is circular and all instructions use relative referencing (you point to instructions at distances relative the current executing instruction). All calculations are done modulus the size of the core.

Later, extensions were made to the instructions set and firmer rules were laid out for competitions and score calculations.

A Fight to the Bitter End...

Two or more warriors compete in a simulated computer with a simulated instruction set, the warriors are positioned at random in the (simulated) memory and each warrior is given an execution thread each. The areas not occupied by warriors are usually filled with DAT #0,#0 (see  is defined by placing a label at the pseudo instruction EQU (for “equates”) that label will then be expanded to the expression following the EQU instruction on that line.

Example: The Imp-Gate

gate EQU wait-10

wait JMP $ wait, < gate

The Imp-Gate waits and destroys imps that happen to pass 10 instructions before it. It is seldom overrun by imps and its small size makes it difficult to locate. The Imp-Gate is defensive by nature. It will not win against a stationary enemy unless the enemy self-destructs.

The process running at wait jumps to the A-value (the first argument) of this command, i.e. back to wait. The process also decrements the B-field (the second argument) of an instruction positioned ten steps ahead (the Imp-Gate).

Decrement (or predecrement) is another of the eight addressing modes allowed in Core War. The < X means predecrement the value in the B-field of the instruction positioned at X relative the current instruction, and use that value as a relative address (relative the instruction at X) as the instruction that this operation should apply to.

Example:

v  DAT   0, p+1

   JMP < x, 0    ; <-1

  ...

p  ...

On execution the value of the B-field of the DAT instruction (at v) is decremented to p and the execution is moved to instruction p.

v  DAT   0, p

   JMP < x, 0   

  ...

p  ...         ; <-2

This is further explained in The addressing modes.

Returning to the Imp-Gate:

When an enemy Imp comes by this is what happens:

MOV $ 0, $  1

MOV $ 0, $  1  ;<-x Here comes the Imp

DAT   0,   -5  ;    Here is the gate

The imp copies itself and advances onto the gate:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  1  ; <-(x+1) Here is the gate

The gate decrements:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  0  ; <-(x+1) Here is the gate

The imp copies this instruction to itself (effectively doing nothing) and advances, falling off the end:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  0  ;         Here is the gate

...            ; <-(x+2)                   

The gate decrements again (but the damage has already been done.)

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $ -1  ;         Here is the gate

...            ; <-(x+2)                   

The enemy process executes an illegal instruction and dies.

Instructions) or random instructions.

The warriors are allowed to execute one instruction each in a round robin like manner. When a warriors executing thread executes a DAT instruction (explained later), or divide by zero or similar, that thread is removed. If all executions threads for a warrior is removed the warrior is considered “dead”. The fight ends when all except one warrior is “dead” or after a certain timeout (usually around 80000 executed instructions per warrior).

Usually multiple fights are fought with the same warriors and scores are calculated after some formulae. This is necessary since even the most stupid warrior can get lucky (if he and the opponents are positioned just right he might kill them all before they find him, even though he does not make any clever moves, and just blindly bombs at a fixed address).

Further reading

Do not miss these interesting articles relating to Core Wars, available at:
http://www.dd.chalmers.se/~f95lith/CoreWar/Articles/Index.html

The System

Introducing Redcode

This section introduces the Core War system. It is not in any way intended as a tutorial or beginners guide, such information can be found at [koth], [Pizza] and [Planar].

One of the core components in a Core War system (or MARS) is the Redcode language. Redcode is the specially tailored assembly language used for describing core warriors. It has instructions for moving memory contents; basic arithmetic and control transfer (see listing at Operations).

With each instruction, the programmer is required to supply at least one argument. Actually all instructions have two arguments even if some instructions only use one for the actual operation, the reason for this is that both arguments are always evaluated for possible side effects (like preincrementing and postincrementing).

For example the instruction JMP 7 the mnemonic JMP (for “jump”) is followed by the argument 7 which means transfer execution to the instruction seven steps ahead in memory.

This method of calculating a position in memory is called relative addressing, and is the only method for addressing allowed in Redcode. In fact, there is no way for a warrior to know its absolute position in the memory array. 

The instruction MOV 3,100 means copy the instruction three steps ahead to position one hundred steps ahead, overwriting what’s previously there. The arguments are given in direct mode, meaning that they are to be interpreted as addresses to be acted on directly. There exist eight modes for arguments (see The addressing modes) but direct (which can be specified by a preceding $ to each argument) is the default[2].

Example: A Warrior named Imp

MOV $ 0, $ 1

When Imp is loaded and before it executes, it looks like this:

MOV $ 0, $ 1 ; <-1

The <-1 shows which instruction will execute on the first cycle. Upon execution, it first copies its instruction to the next address and then moves to the next instruction:

MOV $ 0, $ 1 ;     This is the original.

MOV $ 0, $ 1 ; <-2 This is the copy.

In this manner, the imp moves through the core overwriting anything in its path with MOV $0,$1 instructions. So when it encounters enemy code, it replaces the enemy code with MOV $0,$1 instructions, turning the enemy processes into imps. Note that although the enemy code is gone, the enemy processes live on, so imps do not win unless the enemy code self-destructs.

To facilitate programming Redcode allows labeling lines in the code for later referrals. Redcode also allows expressions to be entered as arguments, under the condition that the expressions can be evaluated during compile time (as opposed to run-time).

Example: Making the Imp more readable

this MOV $ this, $ this+1

Here the previous example has been (arguably) simplified by introducing the label this to refer to the instruction. When the “this” label is used in an expression, it is immediately expanded to the relative offset between the current instruction and the labeled instruction.

Redcode also has a compile time feature for handling constants. A constant is defined by placing a label at the pseudo instruction EQU (for “equates”) that label will then be expanded to the expression following the EQU instruction on that line.

Example: The Imp-Gate

gate EQU wait-10

wait JMP $ wait, < gate

The Imp-Gate waits and destroys imps that happen to pass 10 instructions before it. It is seldom overrun by imps and its small size makes it difficult to locate. The Imp-Gate is defensive by nature. It will not win against a stationary enemy unless the enemy self-destructs.

The process running at wait jumps to the A-value (the first argument) of this command, i.e. back to wait. The process also decrements the B-field (the second argument) of an instruction positioned ten steps ahead (the Imp-Gate).

Decrement (or predecrement) is another of the eight addressing modes allowed in Core War. The < X means predecrement the value in the B-field of the instruction positioned at X relative the current instruction, and use that value as a relative address (relative the instruction at X) identifying the instruction that this operation should apply to.

This is further explained in The addressing modes.

Returning to the Imp-Gate:

When an enemy Imp comes by this is what happens:

MOV $ 0, $  1

MOV $ 0, $  1  ;<-x Here comes the Imp

DAT   0,   -5  ;    Here is the gate

The imp copies itself and advances onto the gate:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  1  ; <-(x+1) Here is the gate

The gate decrements:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  0  ; <-(x+1) Here is the gate

The imp copies this instruction to itself (effectively doing nothing) and advances, falling off the end:

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $  0  ;         Here is the gate

...            ; <-(x+2)                   

The gate decrements again (but the damage has already been done.)

MOV $ 0, $  1

MOV $ 0, $  1      

MOV $ 0, $ -1  ;         Here is the gate

...            ; <-(x+2)                   

The enemy process executes an illegal instruction and dies.

Instructions

All instructions in Core War are binary (they have two arguments). The composition of an instruction is:

*   Operation

*   Operation Modifier

*   Argument A Modifier

*   Argument A Value

*   Argument B Modifier

*   Argument B Value

The operation simply identifies the type of operation (for example SUB). The operation modifier changes the behavior of the operation (i.e. if the A Value is subtracted from the B Value or vice versa). The value of an argument may be direct (immediate in machine code terms) or it might refer to a value at another memory location (like C-style pointers) depending on the argument modifier.

This is explained more in-depth in the following sub-sections.

Operations

DAT

Originally, as its name shows, DAT was intended for storing data, just like in most languages. In Core War, it is common to minimize the number of instructions by storing pointers etc. in unused parts of other instructions. This means that the most important thing about DAT is that executing it kills a process. Since the ICWS‘94 standard [ICWS’94], do not have any illegal instructions. DAT is defined as a legal instruction, which removes the currently executing process from the process queue.

Although this may sound like splitting hairs, but precisely defining the obvious can often save a lot of confusion.

The modifiers have no effect on DAT, and in fact, some MARS’ remove them. However, remember that predecrementing and postincrementing are always done even if the value isn’t used for anything. One unusual thing about DAT, a relic of the previous standards, is that if it has only one argument it’s placed in the B-field.

MOV

MOV copies data from one instruction to another. MOV is one of the few instructions that support .I, and that’s its default behavior if no modifier is given and neither of the fields uses immediate addressing.

ADD

ADD adds the source value(s) to the destination. Modifiers work the same as with MOV, except that the .I modifier is not supported, and instead behaves like .F.

Remember that all maths’s in Core War is done modulo the size of the core.

SUB

This instruction works exactly like ADD, except for one obvious difference. In fact, all the “arithmetic-logical” instructions work pretty much the same.

DIV

DIV too works pretty much the same as MUL and the others, but there are a few things to keep in mind. First, this is unsigned division, which can give surprising results sometimes. Division by zero kills the process, just like executing a DAT, and leaves the destination unchanged. If you use DIV.F or .X to divide two numbers at a time and one of the divisors is 0, the other division will still be done as normal.

MUL

Similar to DIV, computes the product of two unsigned integer values.

MOD

Similar to DIV, including the division by zero complication.

MOD computes the modulus (remaining part after unsigned integer division)

The result of a calculation like MOD.AB #10, #-1 depends on the size of the core. For the common 8000-instruction core, the result would be 9. (7999 mod 10)

JMP

JMP moves execution to the address defined by its A-field. The obvious but important difference to the “math” instructions is that JMP only cares about the address, not the data that address points to. Another significant difference is that JMP doesn’t use its B-field for anything. Being able to jump (or split) into two addresses would simply be too powerful, and it’d make implementing the next three instructions quite difficult. Remember that you can still place an increment or a decrement in the unused B-field, with luck damaging your opponent’s code.

JMZ

This instruction works like JMP, but instead of ignoring its B-field, it tests the value(s) it points to and only jumps if it’s zero. Otherwise, the execution will continue at the next address. Since there’s only one instruction to test, the choice of modifiers is limited, and .AB means the same as .B and .BA the same as .A, and .X and .I the same as .F. If you test both fields of an instruction with JMZ.F, it will jump only if both fields are zero.

JMN

JMN works like JMZ, but jumps if the value tested is not zero. JMN.F jumps if either of the fields is non-zero.

DJN

DJN is like JMN, but the value(s) are decremented by one before testing. This instruction is useful for making a loop counter, but it can also be used to damage your opponent.

SPL

This is the big one. The addition of SPL into the language was probably the most significant change ever made to Redcode, only rivaled perhaps by the introduction of the ICWS‘94 standard. SPL works like, JMP, but the execution also continues at the next instruction, so that the process is “split” into two new ones. The process at the next instruction executes before the one, which jumped to a new address, which is a small but very important detail[3]. If the maximum number of processes has been reached, SPL works like NOP. Like JMP, SPL ignores its B-field and its modifier.

SEQ

SEQ compares two instructions, and skips the next instruction if they are equal. It only jumps two instructions forward, because there is no room for a jump address. Since the instructions are compared only for equality, using the .I modifier is supported. Quite naturally, with the modifiers .F, .X and .I the next instruction will be skipped only if all the fields are equal.

SNE

This instruction skips the next instruction if the instructions it compares are not equal. If you compare more than one field, the next instruction will be skipped if any pair of them is not equal.

CMP

CMP is an alias for SEQ. This was the name of the instruction before SEQ and SNE were introduced. Today it does not really matter which name you use, since the most popular MARS (including Core War Tribes) programs recognize.

SLT

Like the previous instructions, SLT skips the next instruction, this time if the first value is lower than the second is. Since this is an arithmetical comparison instead of a logical one, it makes no sense to use .I. It might seem that there should be an instruction called SGT, (skip if greater than) but in most cases, the same effect can be achieved simply by swapping the operands of SLT. Remember that all values are considered unsigned, so 0 is the smallest possible number and -1 is the largest.

NOP

This instruction does nothing. It’s almost never used in an actual warrior, but it’s very useful in debugging. It also seems to be useful for introns in Genetic Programming.

Remember that any increments or decrements are still evaluated.

The addressing modes

In the first versions of Core War, the only addressing modes were the immediate (#), the direct ($ or nothing at all) and the B-field indirect (@) addressing modes. Later, the predecrementing addressing mode, or <, was added. It’s the same as the indirect mode, except that the pointer will be decremented by one before the target address is calculated.

DAT   #  0, #  5
MOV      0, < -1 ; next instruction

When this MOV is executed, the result will be:

DAT   #  0, #  4 ;  ---.
MOV      0, < -1 ;     |
...              ;     | +4
...              ;     |
MOV      0, < -1 ; <---‘

The ICWS’94 standard draft added four more addressing modes, mostly to deal with A-field indirection, totaling 8 modes:

#

Immediate

$

Direct (the $ may be omitted)

*

A-field indirect

@

B-field indirect

{

A-field indirect with predecrementing

<

B-field indirect with predecrementing

}

A-field indirect with postincrementing

>

B-field indirect with postincrementing

 

The postincrementing modes are similar to the predecrementing, but the pointer will be incremented by one after the instruction has been executed, as you might have guessed.

DAT   #  5, # -10 ;
MOV     -1, }  -1 ; next instruction

Will after execution look like this:

DAT   #  6, # -10 ;  --.
MOV     -1, }  -1 ;    |
...               ;    |
...               ;    | +5
...               ;    |
DAT   #  5, # -10 ; <--‘

One important thing to remember about the predecrementing and postincrementing modes is that the pointers will be incremented/decremented even if they’re not used for anything.

So JMP -1, <100 would decrement the instruction 100 even if the value it points to isn’t used for anything.

Even DAT <50, <60 will decrement the addresses in addition to killing the process

The instruction modifiers

The most important new thing brought by the ICWS ‘94 standard wasn’t the new instructions or the new addressing modes, but the modifiers. In the old ICWS’88 standard, the addressing modes alone decide which parts of the instructions are affected by an operation.

For example, MOV 1,2 always moves a whole instruction, while MOV #1,2 moves a single number and always to the B-field! Naturally, this could cause some difficulties.

*   What if you only want to move only the A-field and B-field of an instruction, but not its operation? (You would need to use ADD)

*   What if you only want to move something from the B-field to the A-field? (It’s possible, but very tricky)

To clarify the situation, the instruction modifiers were invented.

The modifiers are suffixes that are added to the instruction to specify which parts of the source and the destination it will affect. For example, MOV.AB 4, 5 would move the A-field of the instruction 4 into the B-field of instruction 5.

There are seven different modifiers available:

MOV.A

Moves the A-field of the source into the A-field of the destination

MOV.B

Moves the B-field of the source into the B-field of the destination.

MOV.AB

Moves the A-field of the source into the B-field of the destination.

MOV.BA

Moves the B-field of the source into the A-field of the destination.

MOV.F

Move both fields of the source into the same fields in the destination.

MOV.X

Move both fields of the source into the opposite fields in the destination.

MOV.I

Moves the whole source instruction into the destination.

Some instructions like JMP and SPL, however, don’t care about the modifiers.

Since not all the modifiers make sense for all the instructions, they will default to the closest one that does make sense. The most common case involves the .I modifier; to keep the language simple and abstract no numerical equivalents have been defined for the Operations, so using mathematical operations on them wouldn’t make any sense at all. This means that for all instructions except MOV, SEQ and SNE (and CMP which is just an alias for SEQ) the .I modifier will mean the same as the .F.

Another thing to remember about the .I and the .F is that the addressing modes too are part of the Operations, and are not copied by MOV.F.

Modulo math

Addresses in the core wrap around, so that the instruction one coresize ahead or behind the current instruction refers to the current instruction itself. However, in fact, this effect goes much deeper: all numbers in Core War are converted into the range [0, coresize-1].

For those of you who already know about programming and limited-range integer math, let us just say that all numbers in Core War are considered unsigned, with the maximum integer being coresize-1 (you may now skip to the next section).

In effect, the length of the core (the coresize) divides all numbers in Core War, and only the remainder is kept. You might try thinking of a calculator with a display of only 8 numbers that throws off any digits past that, so that 100*12345678 (1234567800, of course) is only shown (and stored) as 34567800. Similarly, in a core of 8000 instructions, 7900+222 (8122) becomes only 122.

What happens to negative numbers, then? They are normalized too, by adding coresize until they become positive. This means that -1 is actually stored by the MARS as coresize-1, or in an 8000-instruction core, as is common, 7999.

Of course, this makes no difference for the addresses, which wrap around anyway. In fact, it does not make any difference to the simple math instructions like ADD or SUB either, since with coresize=8000, 6+7998 gives the same result of 4 (or 8004) as does 6-2.

What’s the problem, then? Well, there are a few instructions where it makes a difference. Such instructions as DIV, MOD and SLT always treat numbers as unsigned. This means that -2/2 is not -1, but (coresize-2)/2 = (coresize/2)-1 (or for coresize=8000, 7998/2=3999, not 7999) Similarly, SLT considers -2 (or 7998) to be greater than 0! In fact, zero is the lowest possible number in Core War, so all other numbers are considered greater than it is.

The Process Queue

The warriors are allowed to execute one instruction in one of their threads in robin style (Warrior 1, Warrior 2, Warrior 3, Warrior 1, Warrior2... and so on) if a warrior has multiple threads they to are executed round robin style.

Example: If two warriors are loaded W1 and W2, and W1 has two threads T11 and T12 while W2 only has one thread T21 the execution order might be: T11, T21, T12, T21, T11, T21, T12...

Further reading

Further specifications on the inner workings of the Core War system can be found in the latest draft of the international Core War society standard [ICWS’94]. Several excellent online tutorials exists in the art of Core Wars [Karonen], [Durham], [Lewis] and [Morell]. Several handcrafted Core Warriors can be downloaded from the web [Sub89] and [Sub90].

There are also several online tournaments are continuously running, where warriors can be submitted online [koth], [Pizza] and [Planar]. Finally, Steven Morell has created an excellent article on the subject of numerically optimal step sizes (i.e. where to “bomb” out the DAT instructions in order to maximize the likelihood of hitting your opponents code) [Step].

Introducing Core War Tribes

Core War Tribes Implements the ICWS’94 draft standard[4], but can also be used in ICWS’88 compatible mode. The application includes a portable[5] MARS-core a Redcode assembler and disassembler in Standard C++[6]. These components use an implicit callback mechanism so they can be easily connected to a GUI[7]. Such a GUI is implemented for Win32.

Core War Tribes runs one or more warriors written in Redcode that are provided as files. Two warriors are pitted against each other for standard play; any number of warriors can be named for “Multi-Warrior” core war.

If the warrior(s) assemble without error(s), they are loaded into the core array and executed in round-robin mode starting with the first warrior. Warrior 1 is loaded starting at core position 0, warrior 2, 3, etc., at either a random or fixed position. For fairness the starting order is randomized each round.

Score

The score is reported after all rounds have been played. A round ends either when a single surviving warrior remains or when a maximum number of cycles have elapsed. For each round, every surviving warrior is awarded points calculated from a score formula (F).

By default, this is F(W,S) = (W * W-1) / S, where W is the total number of warriors participating, S is the number of survivors, and “/” is integer division.

The Genetics

Comparisons with Artificial life and similar systems

One of the goals of the field of Artificial Life, as stated by David Jefferson, is to provide alternative kinds of life to study in order to better understand life in general. Yet, in most of the computer simulations done in this field, one of the primary techniques used is to model some feature of a natural animal, like an ant [Jefferson].

Some of these experiments have generated useful results; for instance being able to evolve trail following behavior (for ants), but this type of experiment skirts the goal of finding alternative types of life. The problem is that ants and other natural critters live in a world that is very different from the world in which the simulation is conducted. For example, ants follow a trail of pheromones, yet computers and programs really have no sense of smell, but this fact is overlooked by researchers. Likewise, an experiment that confirms our beliefs about neural patterns involved in the tail-flip of a crayfish is interesting, but not entirely useful, since computers have no tail to flip. If we truly wish to study models of life in a computer environment, it would constrain our studies to phenomena, which actually occur in a computer environment.

The domain of binary biology, or binology, has enough interesting properties that there is truly no need to go outside of its bounds to provide good A-life experiments.

Processes can be born, die, move, reproduce, communicate, and do a host of other things without having to introduce concepts like smell. The abundance of computer viruses and worms demonstrate the ability of processes to take on characteristics of life. In fact, these programs are lifelike enough to scare computer users into taking precautions against them as they would against any parasite.

Compared with “usual” computer programs, that do more or less “menial tasks” (from the programs point of view), Core Warriors has a more important goal, namely survival.

The fact that Core Wars programs share this purpose with biological life forms lends credence to the practicality of Core Wars as a binological environment.

It is certainly not difficult to find other analogies between Core Wars programs and biological life forms. Core Warriors are comparable to a genotype and the corresponding phenotype is the behavior that the processes realize when they are placed in a Core Wars simulator (MARS). A warrior can copy itself and then split to the copy, (thus executing the original and the copy in parallel) which is much like cell division, or jump to the copy, which is more like a binological equivalent of movement. A process can cause another process to stop executing (or kill it, if you will), which is somewhat like biological predation [Perry].

Furthermore, some of the more complex programs in previous tournaments have displayed such abilities as setting a trap, self-repair, and mimicry, all of which have biological equivalents.

Core Wars, Darwin flavored

The Smallest Gene

One difficult problem with applying genetic algorithms to Core Wars consists of choosing the level of the gene. As in biology, it isn't clear what the optimal size is for the smallest information-carrying unit of genetic code.

Three distinct levels present themselves as viable candidates for the level of the binological gene:

*  The bit

*  The instruction

*  The meta-instruction

Meta-instruction refers to an abstract chunk of code, which has some function that will show up at the phenotype level. In biological genetics features like 'blue eyes', or 'eight legs', or 'black feathers' would be an example of a meta-instruction, and in fact this is the level at which most work in biological genetics is done.

A binological meta-instruction should consist of more than one instruction since most interesting things that can be done by a computer can't be done by one instruction.

An example of the meta-instruction level with respect to Core Wars is something like “copy block” or “Exit Thread”[8].

The best justification for the bit as the gene level of binology is that it is truly the smallest unit of information that one can change on a computer. On the other hand, single bits aren't always critical in a functional sense on computers. Changing a bit in an unused data field may make no difference in how the instruction at that address executes, or in the functional performance of the program. The instruction level is the smallest level of binological representation that assures functional distinction in the phenotype.

The meta-instruction is intrinsically difficult to handle since either it involves: doing a semantic analyze on the instructions (to find the meta-instruction) or revert to only combining pre-supplied (human coded) meta-instruction.

For these reason, the instruction is defined to be the gene-level in Core Wars Tribes with the reservation that mutations are allowed at a sub-gene level.

I.e. when two warriors are being mated, the instruction level is the level of crossover, but mutation works at a bit level.

Recipe for primordial soup, a la Core Wars

In order to genetically evolve Core Warriors the Core War Tribes system in its current incarnation  (version 0.1.xxxx) uses the following scheme.

1.      A number of Core Warriors (500) was created with random instructions, where the number of instructions is in the interval [1,100].

2.      In order to preserve diversity these warriors were divided into tribes (10). The common term is deems, but is seems more natural to group warriors into tribes.

3.      The selection mechanism is to randomly choose a few warriors in a tribe (4)

4.      The evaluations then immediately follows, were the selected warriors (on a per tribe basis) are pitched against each other in a match of a few (10) rounds. This quickly results in a large number[9] of rounds being fought.

5.      The winners of the evaluation are the warriors with the highest score (see scoring above).

6.      The losers are then killed and replaced by the offspring of the winners.

7.      Point 3-6 is repeated once for each tribe.

8.      Every once in a while (after each tribe has been “evolved one step”) there is a small chance of migration between the tribes.

9.      Repeat 3-8 until done

Selection and Evaluating

At first, the selection criterion is rather unfair, but it’s equally unfair against everybody. For example when comparing the best of the best (say the N best individuals in a tribe) someone has to be worst of the best, and that individual(s) will thus be “killed” and replaced by the winners offspring even though there are quite a few other warriors in the same tribe that are far worse. This lack of omni-consciousness actually works in favor for preserving diversity inside a single tribe of warriors.

By only evaluating a few warriors against each other, the number of rounds that has to be fought is lowered considerably. For instance to compare N warriors against each other, N × ( N -1 ) / 2 pairs has to be compared with a few rounds each (a minimum of 10 but 100 should be sufficient).

The lack of ordering is also a problem; which is the best warrior in a tribe and how good that warrior actually is can not be deducted by only considering the results of the mentioned scrimmages. Because of this, the final “sorting” of the warriors in each tribe had to be done “by hand” (a rather tedious task).

Tribes and Breeding

The ordering of warriors in tribes is another step to increase/preserve diversity in the population. A few initial tests were done without dividing the population in tribes; but it became apparent that the tribes did increase the efficiency of the evolution.

In the beginning, there were just random instructions... and thus most warriors were of the suicidal type; but by using tribes, only 15000 warriors had to be breed before viable offspring were more common than non-viable. A viable offspring were defined as a warrior that could “survive” for 4096 clock cycles[10] in an empty core without “killing” itself.

After this evolutionary turn point, a new rule was introduced in the breeding process:
All new offspring is tested for viability immediately after birth, if it does not meet the test it is immediately discarded and another offspring is generated.

This greatly enhanced the progress of the GP system since several time-consuming evaluations could be saved.

Two different genetic operators were used when “breeding” Warrior offspring from Warrior parents, copy with optional point mutation and the single point crossover.

Copy with optional Point Mutation

One warrior is copied with a 60% chance of single point mutations occurring were used. When mutations occurred, one to eight “bits” are flipped in randomly chosen instructions[11].

When a bit flip occurs in an instruction different chances were used for different part of the instruction. This also serves to “mellow” out the effect of the mutation. A mutation in the operation is stronger and potentially more destructive than a mutation in a parameter value, or the operation modifier. Therefore, the following rates were used.

Operation

8%

Operation modifier

10%

Parameter mode

12% (x 2)

Parameter value

39% (x 2)

Single point crossover

A single point crossover is created by using two parents and selecting one point in each parents genome (see “The Smallest Gene” above) at random. One part of each parent is the randomly chosen and combined to create the offspring, again the order of the combining is random. If the length of the offspring genome is above the allowed maximum length, the order of combining is re randomized until it’s within the prescribed length (it is easy to formulate a proof that there always exist at least one such offspring for any chosen pair of crossover points, this is left as an exercise to the reader).

Figure 1, example of single point crossover

Initial tests suggested that single point crossover usually is extremely destructive when creating a core warrior, and thus the chance of single point crossover was set at 10% (the remaining 90% were copy with optional point mutation).

Results and Discussion

After evolving 125.000 warriors (i.e. generation 250) a fairly aggressive and competent warrior has been breed. In order to spot the best warrior in the population, an elimination-competition was conducted (by hand) where all warriors were paired and the winner was allowed to continue to the next match in the tournament. 

The winner of this evaluation (hereby referred to as E1 in the remaining document) can be found in the section The Warrior E1 in appendix.

This warrior has then been compared to a few selected “hand coded” warriors (from previous annual core war tournaments [Sub89] and [Sub90]). Each warrior was compared to the evaluated warrior in a 100 round match, and the number of times winnings and ties

Warrior (W)

Win E1

Tie E1

Win W

Points E1 - W

Blur 2 by Anton Marsden

23

14

63

83 – 203 (29%)

Impfinity v4g1 by Planar

2

62

36

68 – 170 (29%)

Benji's Revenge 1.0 by Robert Macrae

2

37

61

43 – 220 (17%)

Although this is by no means a spectacular result, one must consider the fact that 250 generations is nothing in the light of evolution. Further evolution would possibly result in even better results, 125.000 individuals were evolved using idle time on one CPU in a dual PII-400MHz for one week. The Core War Tribes system is prepared for conversion to multi-threading (every tribe could be evolved in parallel).

One of the greatest “flaws” of the system in its 0.1.xxxx version is its meager support for continuous progress reporting. As of now a log file is created when running, containing the results of the fitness evaluation in each scrimmage and the current offspring count when the scrimmage was made.  This does not give any real information on the actual progress of the evolution since its only comparisons among the warriors of the same generation. The only useful information it gives is that if the warriors individual points in the scrimmage is not equal neither is the warriors (probably), thus giving us a rough estimation of the diversity in the population.

The Next Generation

Encouraged by these results, the next generation of the Core War Tribes is already in the making. The mayor change is support for a second evaluation method.

This method is a variant on the LEO (Last Elite Opponent[12]) methods (as described in [Miller&Cliff]) where every warrior in each tribe is evaluated against a set of opponents consisting of LEO’s and fixed selected opponents (for example the three warriors above). The points of the different matches are then weighted together for each warrior, this sum is the warriors grade.

A percentage of the best warriors are kept as breeders (parents) the rest are “killed” and replaced by the offspring of the previously mentioned.

There is much to gain by this method:

*  The warriors internal ordering is always established

*  The progress of the evolution is easy to monitor, as the results against the rounds Elite Opponent against LEO’s

*  The comparison against selected opponents serves to “nudge” the evolutional direction against learning to beat the selected opponents. This also serves to “soften” the effects of intransitive dominance where evolution tends to “go around in circles”[13].

The Future

Future genetic work

*   Introduction of P-Space (explained below) should provide an interesting aspect of evolving teams of warriors that work together.

*   Different methods of evaluation as explained above.

*  An overhaul on the mutation operations (breeding operations). Maybe involving dynamic rates of mutation (where for example the rate of cross over mutations increase after a certain time of low evolutional progress)

*  Addition of two point crossover and homologous crossover

*  Addition of some kind of “evolutional protection mechanism”, similar to the ADFs used by Koza, that serves to minimize the rate of mutations in commonly reoccurring sub-expressions (gene sequences).

Future features for the simulator

*   Running a single warrior for debugging

*   A line-oriented debugger

*   Compatibility fix so for-macro and multiline EQU can be used/handled in the Redcode-files (see [ICWS’94])

*   User defined, alternative score formulas

*   P-Space as explained below.

P-space - the final frontier

You might notice that two instructions, namely LDP and STP are missing. They are a recent addition to the language and are currently not implemented in Core War. However, since P-Space adds an interesting aspect to the game, they might eventually be added to Core Wars Tribes.

P-space is the latest addition to Redcode. The “P” stands for private or personal. The P-space is an area of memory, which only one warrior can access, and which survives between rounds in a multi-round match.

The P-space is in many ways different from the normal core. First, each P-space location can only store one number, not a whole instruction. In addition, the addressing in P-space is absolute, i.e. the P-space address 1 is always 1 regardless of where in the core the instruction containing it is. Finally, yet importantly, the P-space can only be accessed by two special instructions, LDP and STP.

The syntax of these two instructions is a bit unusual. The STP, for example has an ordinary value in the core as its source, which is put into the P-space field pointed to by the destination. Therefore, the P-space location isn’t determined by the destination address, but by its value, i.e. the value that would be overwritten if this was a MOV.

So STP.AB #4, #5 for example would put the value 4 into the P-space field 5. Similarly,

STP.B  $  2, $  3

...

DAT    #  0, # 10

DAT    #  0, #  7

This will put the value 10 into the P-space field 7, not 3! This can get confusing if the STP itself uses indirect addressing, which leads into a sort of “double-indirect” addressing system.

LDP works the same way, except that now the source is a P-space field and the destination a core instruction. The P-space location 0 is a special read-only location. Any writes to it will be ignored, and it is initialized to a special value before each round. This value is -1 for the first round, 0 if the program died in the previous round, and otherwise the number of surviving programs. This means that, for one-on-one matches, 0 means a loss, 1 a win and 2 a tie.

The size of the P-space is usually smaller than that of the core, typically 1/16 of the core size. The addresses in the P-space wrap around just like in the core. The size of the P-space must naturally be a factor of the core size, or something weird will happen.

There is one little peculiarity in the pMARS[14] implementation of P-space. Since the intention was to keep access to P-space slow, loading or saving two P-space fields with one instruction isn’t allowed. This is a Good Thing, but the result is at the very least a kludge. What this actually means is that LDP.F, .X and .I all work like LDP.B (an the same for STP too, of course).

Absolutely the most common use of P-space is to use it to select a strategy. In its simplest form, this means saving the previous strategy in P-space, and switching strategies if the P-space field 0 shows the program lost last time. This kind of programs is called P-warriors, P-switchers or P-brains (pronounced pea-brains).

Unfortunately, the P-space isn’t as private as it seems. While your opponent can’t read or write your P-space directly, your processes may be captured and made execute your opponent’s code, including STP. This kind of technique is known as brainwashing, and all P-switchers must be prepared for it, and not freak out if the strategy field contains something weird.

Acknowledgements

Thanks to:

*  Peter Nordin and Mats Nordahl, for a great course in Evolutional Computation... and of course for all their feedback on this project. ;-)

References

[Genetic]                Wolfgang Banzhaf, Peter Nordin, Robert E. Keller and Frank D. Francone.,
“Genetic Programming, an Introduction”
Morgan Kaufmann Publishers, Inc. San Francisco California, 1998.
For a deeper discussion / clarification on the genetic operators in this report.

[Jefferson]             Jefferson, David.
“The Genesys System: Evolution as a  Major Theme in Artificial Life.”
Talk given at the Second Workshop on Artificial Life, Santa Fe, 1990.

[koth]                      David Moore.,
“King of the Hill”
Has tutorials and online tournaments.
http://www.koth.org/

[Pizza]                     “The CSU Chico Pizza Hill”
Has online tournaments
http://www.ecst.csuchico.edu/~pizza/koth

[Planar]                  “Planar’s Core War Page”,
http://pauillac.inria.fr/~doligez/corewar

[ICWS’94]              “The International Core Wars Standard 1994, Draft”, 1994
The currently purposed standard
http://www.koth.org/info/icws94.html

[Karonen]              Ilmari Karonen .,
 “Beginner’s guide to Core Wars” March 8, 1998
http://vyznev.net/corewar/guide.html

[Lewis]                   J.K Lewis .,
“Core War for dummies”
http://www.koth.org/info/corewars_for_dummies/dummies.html

[Durham]               Mark A. Durham .,
“Introduction to Redcode”
http://www.koth.org/info/tutorial1.html
http://www.koth.org/info/tutorial2.html

[Morell]                   Steven Morell .,
“My First Core War Book”
http://www.koth.org/info/chapter1.html
http://www.koth.org/info/chapter2.html

[Step]                      Steven Morell .,
“The Math of Core War Step Sizes”
http://www.koth.org/info/cwmath.txt

[Perry]                     John Perry .,
“Core Wars Genetics: The Evolution of Predation”
A Genetic Programming project on Core Wars
http://www.koth.org/info/evolving_warriors.html

[Sub89]                  Warriors submitted to the 1989 ICWS Tourney
http://www.koth.org/info/icws89.html

[Sub90]                  Warriors submitted to the 1990 ICWS Tourney
http://www.koth.org/info/subs90.html

[Miller&Cliff]           Geoffrey  F. Miller and David Cliff .,
“Co-Evolution of Pursuit and Evasion I: Biological and Game-Theoretic Foundations''
Technical Report CSRP311, School of Cognitive and Computing Sciences, University of Sussex, March 1994. pp.40.

[SandStone]          “Sandstone Technoligies”
The creators of Visual Parse
http://www.sand-stone.com/

[OMG]                     “The Object Managment Group”
Creators of the UML standard (Unified Modelling Language)
http://www.omg.com/

Appendix

The Warrior E1

ORG 0

SPL.B   $     76, $      0

MOV.I   <     12, <     13

MOV.F   }     11, }     12

MOV.I   <     10, <     11

MOV.I   }      9, }     10

MOV.I   <      8, <      9

MOV.I   }      7, }      8

MOV.I   <      6, <      7

MOV.I   }      5, }      6

MOV.I   *      4, *      5

MOV.I   $      9, $    427

SPL.B   @      3, <   -313

JMP.B   *      2, <   -299

DAT.F   $      7, $      6

DAT.F   <   3637, $    993

SPL.B   #      1, <      3

SPL.B   $  -1199, {    336

ADD.F   #   1144, $     -1

SUB.I   $   -569, $   -571

MOV.I   #   1729, $   1143

DAT.F   <   2667, <  -2666

SPL.B   #   2216, {   -650

MOV.I   $     -2, }     -1

ADD.F   #   2213, $     -2

DJN.F   $     -3, <    -49

MOV.B   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #   1537, $      1

MOV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #    545, $      1

MOV.I   #      1, $      1

MOV.I   #      5, @      1

SPL.B   #      1, $      1

MOV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #      1, $      1

MOV.I   #      3, $      1

MOV.I   #      1, @      1

SPL.B   @      1, $      1

MOV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #      1, $      1

DIV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #      1, $      1

MOV.I   #     33, $      1

MOV.I   #  -3903, @      1

SPL.B   #      1, $      1

MOV.I   #      1, $      1

MOV.I   #   3457, @      1

SPL.B   #   2689, $      1

MOV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   #      1, $      1

MOV.I   #   1025, $      1

MOV.I   # 5234881, @     1

DAT.B   #      1, $      1

MOV.I   #     33, $      1

MOV.I   #      1, @      1

SPL.B   $      1, $      1

MOV.I   #      1, $      1

MOV.I   #      1, @      1

SPL.B   # 16769217, $    1

MOV.I   #  -2175, #      1

MOV.I   #      1, @      1

SPL.B   #   3073, $      1

MOV.I   #   1025, $      1

MOV.I   #      1, @      1

SPL.B   @      1, $      1

MOV.I   #      1, $      1

MOV.I   #    769, @      1

SPL.B   #   1153, $      1

MOV.I   #      1, $      1

MOV.F   #      1, @      1

SPL.B   #      1, $      1

MOV.I   <     12, <     13

MOV.I   }     11, }     12

MOV.I   <     10, <     11

MOV.I   }      9, }     10

MOV.I   <      8, <      9

MOV.I   }      7, }      8

MOV.I   <      6, <      7

MOV.I   }      5, }      6

MOV.I   *      4, *      5

MOV.I   $      9, $   1495

SPL.B   @      3, <   -390

JMP.B   *      2, <   -376

DAT.F   $      7, $      6

DAT.F   $   -952, $  -3572

SPL.B   #   1217, <      3

SPL.B   $   2779, {    337

ADD.F   #   1144, $     -1

MOV.I   $  -1720, $  -2938

MOV.I   #   8385, $   1143

DAT.F   <   2667, <  -2666

SPL.B   #  -1636, {   -650

MOV.I   $     -2, }     -1

ADD.F   #   3284, $     -2

DJN.F   $     -3, <    -48

END

The Implementation

The Core War Tribes system is implemented in C++, and all OS specific function calls are done in virtually inherited member functions in order to facilitate porting to a different platform.

Most of the memory in the application is allocated dynamically, in order to minimize the built-in restrictions in the code. The dynamically allocated objects (using C++ new) is reference counted by means of templetizised reference handles that behaves exactly like a standard C-style pointer, but also handles reference counting on all objects it points at. This differs from the Java-style reference counting in that the aforementioned is explicit as opposed to the implicit garbage-collecting scheme employed by Java and many other interpreted languages like Smalltalk. Nevertheless, the result is the same: improved reliability by eliminating memory leaks[15].

Figure 2, examples of UML notations

This extremely brief overview of the implementation of Core War Tribes system is presented here using the UML notation (Unified Modeling Language by [OMG]).

Figure 3, the dynamics of the Core

The MARS is simulated in one class the Core. While running the core generates several status notifications (as memory read, written and executed, or warrior attached, detached or killed, etc), which is propagated by means of virtual member functions to its instantiated, sub-class the VCLCore that is linked to the actual Win32 GUI.

The core holds reference handles to all the warriors attached to it. These warriors can then be loaded (started) into the core, which can then allow execution of a user defined number of instructions (clock ticks).

Figure 4, the Core Warrior

The Core Warrior is only a set instructions (which are exclusively owned by the warrior, executed by the Core and mutated by the Breeder) and a set of internal states:

*  The location of the first instruction to execute (the ORiGin pseudo-assembly instruction)

*  The number of matches fought

*  The number of winnings and ties

*  The name

*  The author

The instructions are only represented in an object-code in memory; this bears resemblance to P-Code (see any book on compiler creation for an in-depth explanation).

Figure 5, converters

In order to convert to and from this compact object-code to a more human readable form[16] the Disassembler/Assembler hierarchies exist. Currently only two incarnations in these hierarchies are implemented the Redcode Disassembler that converts object-code to the Redcode standard mentioned before, and the Redcode Assembler that does the opposite.

The Redcode Assembler uses a (highly portable) incarnation of the famous Yacc and Lex from the Unix platform, named Visual Parse developed by Sandstone Technologies [SandStone]. This creates tables for a bottom up LALR(1) (Left Associative Left to Right reading grammar). The input (Redcode file) is first tokenized into the lexical elements (lexemes) of Redcode by the means of an instance of the Redcode Lexer class which uses one of the two tables created by Visual Parse, the other is used by Redcode Yacc. The lexemes are then fed through the grammar encapsulated by the Redcode Yacc class in a dual-pass scheme in order to resolve all possible forward references created by not yet declared labels used in expressions in the Redcode.

Figure 6, the Darwin in the system

Like a spider in the web, we have the Darwin class. An instance of this class acts like an overall coordinator of the genetic processes in Core Wars Tribes. It is responsible for handling the storing and restoring a set of Core Warrior tribes to and from file. It is also acts like a coordinator for the evolutional process by systematically using it’s connected Evaluator to evaluate a tribe, and the breeder to breed new offspring.

The Evaluator is a function object (“functor” in the semantics of the C++ STL-library) with one virtual member function Evaluate that takes a tribe and a reference to the Darwin instance and returns two sets of warriors (the union of which need not be the whole tribe) the “winners” and the ”losers”. The actual evaluation functions are implemented in sub-classes that are dynamically linked to the Darwin instance at runtime. Similarly, the Breeder class is just a “functor” that takes two sets of warriors “parents” and “offspring”, and again a reference to the Darwin instance; the offspring warriors are the modified to be the offspring of the parents.

The actual storing/restoring procedure is decentralized in the way that the Darwin only stores it’s internal states and names the files for where each tribe should store it’s internal states. The tribe in its turn uses the supplied disassembler to disassemble each of its Warriors to a file[17]. Even the evaluator and the breeder gets a chance to store its states should it need to.



[1]  Redcode is the assembly language used for describing a Core Warrior

[2]  Special rules apply for DAT instructions where immediate (#) mode is usually default.

[3]  Most of today’s warriors wouldn’t work without it

[4]  As of now it does not support the p-Space (Personal Space) extensions from the Extended ICWS’94 draft standard. However, there should not present a problem to add support for this in a later version.

[5]  Operating system independent

[6]  The C++ code requires a standard compliant compiler with support for inline member templates.

[7]  GUI = Graphical User Interface

[8]  Also known as DAT-bomb

[9]  ( 4 × (4 - 1) / 2 ) × 10 = 60

[10]            All instructions in Core Wars take one clock cycle to execute (an ideal RISC-processor)

[11]            The same instruction can be mutated more then once.

[12]            Winners of previous rounds

[13]            There have been quite a few tries to classify different Core Warrior behaviors, the most commonly successive is the Paper, Stone and Scissors categories. Where the Paper-warriors “kills” Stones which “kills” Scissors, who “kills” Papers. Although all professional warriors are combinations of these classes, it suggests that there is some amount of intransitive dominance in the Core War system. See [Morell] for examples of the different warrior classes.

[14]            pMars is a freeware implementation of a MARS system.

[15]            Version 0.1.xxxx was analyzed with BoundsChecker 6 a memory-proofing tool by Numega, Inc.

[16]            ...or by all means another computer interpreted standard.

[17]            Upon loading it obviously uses the Assembler instance.