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:
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:
The structure of this document
Comparisons with Artificial life and similar systems.
Recipe for primordial soup, a la Core Wars
Copy with optional Point Mutation
Future features for the simulator
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.
This is further explained in The addressing modes.
When an enemy Imp comes by this is what happens:
MOV $ 0, $ 1 ;<-x Here comes the Imp
The imp copies itself and advances onto the gate:
MOV $ 0, $ 1 ; <-(x+1) Here is the gate
MOV $ 0, $ 0 ; <-(x+1) Here is the gate
MOV $ 0, $ 0 ; Here is the gate
The gate decrements again (but the damage has already been done.)
MOV $ 0, $ -1 ; Here is the gate
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/