Core Wars 2

Programming is a joy. Everyone who’s ever done it knows that. A few seemingly insipid lines of code can burst out spinning and dancing when they work. Nothing can delight a programming enthusiast more than seeing his creations live in harmony. 

If you’re serious about programming and have taken it up voluntarily, you probably know what I mean. Either way, this series is about a “game” that gets you as close to life in a code segment as you ever will be. It’s called Core Wars and it’s about programs that battle each other in a virtual “ring”. In the previous article (see Core Wars, page 104, PC Quest January 2000), I tried giving you a God’s eye view of how the setup works. Let’s get a bit closer now, and look at some ugly details.

Warriors



Core Wars programs are called warriors. These are short programs of sizes varying from 1 to 100 instructions, written in a special assembly language known as “Redcode.” Here’s what a warrior looks like:





Dwarf 


ADD #4, 3 ßExecution starts here (L1)


MOV 2, @2 (L2)


JMP -2 (L3)


DAT #0, #0 (L4)











When a battle begins, this little warrior is placed in the Core (core wars memory, which we discussed last time) with its opponent. Henceforth, MARS (Redcode simulator, also discussed last time) executes one instruction at a time and proceeds to the next one in the memory (unless the instruction explicitly specifies a jump). Warriors execute alternately, one instruction at a time. In other words, the virtual “computer” is shared between all the competing programs, giving each of them equal opportunities.


A warrior is terminated when it executes an illegal instruction (actually, the current process is terminated in this case–more on this when we discuss splitting warriors). This can be an illegal operation, such as a divide by zero, or more frequently, a “DAT” instruction. We’ll talk about this in the discussion on Redcode op-codes below.

The object of the game



Since Core Wars is about the survival of the fittest and being the last survivor means winning the game, the aim of the game quite clearly becomes to survive as long as possible, and in turn kill as many as possible. Hence, the strategy you adopt would directly or indirectly prevent you from executing a DAT instruction and being terminated; and if possible induce your opponents to execute DAT instructions and terminate themselves.

Redcode instructions



Before we look at the Redcode instruction set, let’s recall the grammar of a Redcode assembly instruction. An instruction is represented as follows:













Here, the A-field is usually the source and the B-field, the destination. Both fields refer to memory elements. 

Addressing modes



Before we arm ourselves with a simulator and rig up our first warrior, it’s important to understand the precise semantics of Core Wars instructions. The A and B fields in all the above instructions are memory (core) addresses. These can be in the following modes:

Direct addressing



The field refers directly to the specified memory location. This is the default mode of all instructions, but can be explicitly specified with the prefix “$”.


Hence, the instruction





MOV 4, 8 or MOV $4, $8







would move the contents of memory location 4 to the memory location 8 (remember addresses are relative, so “4” refers to the instruction four instructions ahead of the current one and “-4” refers to the instruction four instructions behind the current one).

Indirect addressing



Addresses prefixed with “@” are interpreted in indirect mode. A field that carries an indirect address references the direct address to be used. For example, if we have the following block of code:





MOV @2, 3 


DAT -1, -1 


DAT -2, -2












Here, the destination address in the MOV instruction (3) is direct and quite evidently, points at W. The source here is “@2” (or INDIRECT 2). “2” points to the instruction “DAT -2 , -2” and hence references the direct address, “-2”. This direct address points two instructions behind at the instruction “MOV @2,3”. Hence the source is the instruction “MOV @2,3”


The result is that this operation overwrites W with “MOV @1,3”.

Predecrimental



This works just like the indirect mode, except that before referring to the final instruction, the direct address is decremented. Taking the above example, the address “DAT –2, -2” would become “DAT -2,-3”.

Our first warrior



The time has come to study our first warrior. The Imp looks like this:


MOV 0,1 



This is the instruction to be executed.

Interesting? Let’s see. What could one trifling line of code do? As you will recall, both the fields here are direct addresses. Hence, it would copy the contents of memory address “0” into memory address “1”. Memory address “0” refers to the current memory location. And memory address “1”, to the next. Hence, it simply copies the instruction in the current memory location to the next one. The instruction in the current memory location is “MOV 0,1”. Thus, this is copied into the next location. If execution started at location 4000 then the scenario would look like this:






4000 MOV 0,1


4001 MOV 0,1 ß Instruction to be executed








In the next cycle, instruction 4001 would be executed, which AGAIN is “MOV 0,1” and again performs the same operation, filling 4002 with “MOV 0,1”. Thus:





4000 MOV 0,1


4001 MOV 0,1


4002 MOV 0,1 ß Instruction to be executed









So, the Imp lays down a carpet of instructions that help sustain it by carrying on the same activity. If any warrior that’s not prepared for Imp lies in front, it gets overwritten and becomes a clone of Imp (it too will start executing “MOV 0,1” instructions).

If you’ve understood how all this works, you’ll also appreciate that Imp could never win a battle, since it doesn’t induce its adversaries to execute a DAT (and be terminated). All it can do is survive and tie…unless the opponents commit suicide, which doesn’t happen very often in Core Wars.