Core War

games programming simulation

Definition

Core War

Core War is a programming game where competing software agents, known as warriors, execute within a shared virtual machine environment. The objective is to achieve dominance by causing all opposing processes to terminate, typically by forcing them to execute an invalid instruction.

Redcode and MARS

Warriors are authored in Redcode, a low-level assembly language. The environment in which they compete is the Memory Array Redcode Simulator (MARS), which provides a circular memory space where each cell contains a single instruction rather than a byte of data.

Obs

Core War demonstrates homoiconicity, as the Redcode instructions are treated as data by other instructions, allowing warriors to overwrite, replicate, or scan for opposing code within the shared memory space.

Redcode Instruction Set

Redcode instructions consist of an opcode, an optional modifier, and two operands (the A-field and B-field). In the ICWS-94 standard, there are 17 opcodes:

Opcode	Description
DAT	Data; terminates the executing process.
MOV	Move; copies data from A to B.
ADD	Add; adds A to B.
SUB	Subtract; subtracts A from B.
MUL	Multiply; multiplies B by A.
DIV	Divide; divides B by A (terminates if $A=0$).
MOD	Modulo; remainder of B divided by A.
JMP	Jump; transfers execution to A.
JMZ	Jump if Zero; jumps to A if B is zero.
JMN	Jump if Not Zero; jumps to A if B is non-zero.
DJN	Decrement and Jump if Not Zero; decrements B and jumps if B is non-zero.
SPL	Split; creates a new process at A.
CMP / SEQ	Compare / Skip if Equal; skips next instruction if A equals B.
SNE	Skip if Not Equal; skips next instruction if A does not equal B.
SLT	Skip if Less Than; skips next instruction if A is less than B.
LDP	Load from P-space (private storage).
STP	Store to P-space.

Addressing Modes

Redcode uses relative addressing by default. The following prefixes determine how operands are interpreted:

• #: Immediate – The value itself.
• $: Direct – The memory cell at the relative offset (default).
• @: Indirect – The cell pointed to by the B-field of the cell at the relative offset.
• <: Pre-decrement Indirect – Similar to @, but decrements the pointer before use.
• >: Post-increment Indirect – Similar to @, but increments the pointer after use.

Fundamental Mechanics

1. Circular Memory: The address space is finite and wraps around. If the memory size is $M$, an address $A$ is equivalent to $A(\mathrm{mod}M)$.
2. Relative Addressing: All addresses in Redcode are relative to the current instruction pointer. An address of $1$ refers to the next instruction, while $0$ refers to the executing instruction itself.
3. Multiprocessing: Warriors may spawn new processes using the SPL (split) instruction. The MARS simulator schedules these processes using a round-robin discipline, sharing CPU cycles equally among all active processes of all warriors.
4. Termination: A process terminates if it executes a DAT instruction or any other invalid operation. A warrior loses when all its processes have terminated.

Strategy Archetypes

The Core War meta-game is often described through a complex “Stone-Paper-Scissors” relationship:

1. The Imp: The simplest warrior, consisting of a single instruction: MOV 0, 1. It copies itself forward continuously, creating a “rainbow” effect in memory. While easy to stop, its simplicity makes it a building block for more complex designs.
2. Stones (Bombers): These warriors systematically overwrite memory with DAT bombs. They typically use a loop to “throw” bombs at a fixed interval (the “step”). They generally defeat Scissors but struggle against Paper.
3. Papers (Replicators): Warriors that copy their entire code to a new location and SPL to start execution there. This redundancy makes them extremely difficult for Stones to kill, as they “clutter” the core.
4. Scissors (Scanners): Warriors that search for non-zero memory locations. Once an opponent is found, they transition to a targeted bombing phase. They are highly effective against Paper but are vulnerable to the blind bombing of Stones.
5. Vampires: A specialised archetype that uses JMP instructions (“fangs”) to redirect an opponent’s process to a “pit” (usually a loop of SPL instructions) that slows down the opponent’s execution or leads to termination.

Turing-completeness

Redcode is a Turing-complete language. Despite the lack of absolute addressing and a traditional stack, the combination of relative addressing, arithmetic operations on instruction fields, and conditional jumps allow for the simulation of a Turing machine. Specifically, memory cells can be used to represent the tape, and the relative offsets serve as pointers to move the read/write head.