PBEM v94 n02 (10May94)

======================================================================
Modern Core Wars                                          Greg Lindahl
======================================================================

Core Wars? Didn't I read about that in Scientific American 10 years
ago? Perhaps you remember it, perhaps not. But it's alive and well,
and you can play by mail. Core Wars is a game of battling computer
programs. Put away your battletech toys; assembly language is now the
weapon of choice. Some programming experience is required.

Actually, Core Wars is much more like a wargame than you might think.
The object of this article is to convince you of this.

What sort of assembly language does Core Wars use? It will look
somewhat unusual to anyone. There are only 11 different instructions
(move, jump, data, conditional jump) and 4 addressing modes. All
addresses are relative to the current instruction, and the program
memory is of finite size, but wraps around, so that programs can
pretend that memory is infinite. The starting location of the enemy
program is unknown. The object of the game is to keep your program
running while making the enemy program execute an illegal instruction,
that is, to kill the enemy program.

One of the simplest Core Wars programs is this one, from the original
Scientific American article:

;                             Imp, by A. K. Dewdney
imp     MOV 0, 1            ; This program copies itself ahead one
        END                 ; instruction and moves through memory.

This program moves itself forward through memory: the contents of the
address 0 is the MOV instruction itself, and it gets written into the
next address 1, which, coincidentally, is the instruction which is
executed next. As I said earlier, addresses are relative to the current
instruction. 

Imp has a hard time actually killing another program: if it overwrites
a location in memory and the enemy program tries to execute that
instruction, the enemy will be turned into an Imp. The only way that
Imp can score a kill is to overwrite the other program's data or
otherwise interfere with it such that the other program
self-destructs.

A second Core War program from the original article is a "bomber".  It
tries to kill enemy programs by writing illegal instructions all over
memory. If an instruction in the enemy program is overwritten and the
enemy attempts to execute it, the enemy dies.  Bombers must be careful
to not bomb themselves.

While the best defense against a bomber is a good offense, there is a
good defense against the Imp program, often called an "Imp Stomper".
Since Imps can only move forward in memory, a program knows that Imps
will always approach from smaller memory addresses. If a program
repeatedly bombs some fixed location at a smaller address, it can kill
an Imp.

Modern Core Wars has a few more instructions than the Core Wars
described in the original article. The most important new instruction
allows programs to multi-task -- they can create multiple threads of
execution. In order to kill an enemy, you must kill all of its threads.

I will now explain the 5 major strategies employed by modern Core
Warriors. The first is bombing, which I've already described.
An efficient bomber must cover a lot of memory quickly, which means
that bombers leave gaps between their bombs. The best gap size differs
for different enemies, so a bomber designed to fight against many
enemies must compromise and depend on luck.

The second strategy is scanning. The memory in the Core Wars computer
begins initialized to a particular value. A scanner looks around
memory for locations whose values have been changed, hopes it just
found the enemy program, and then bombs nearby these locations. If a
bomber is bombing with the same value that memory is initialized to,
then the scanner will ignore the bombs, and only pay attention to the
bombing program. Bombing with an illegal instruction different from
the initial value is called giving bombs "color", and will make
scanners waste time bombing nothing.

The third strategy is the Imp-spiral, which is a multi-instruction and
multitasking version of our Imp program above. One of the features of
the multitasking in Core Wars is that splitting your program into 2
threads means that each thread only executes half as many instructions
as a single thread would. This means that an Imp Stomper could be
overrun if it is multitasking with anything else. An Imp Spiral
consists of multiple cooperating processes which lay down the
instructions for each other. An enemy program overrun by an Imp Spiral
will be killed unless it happens to have more threads than the spiral.

The fourth strategy is the replicator. Replicators are programs which
are capable of copying themselves to a new location in memory. They
can be thought of as self-moving bombs.

The fifth strategy, which I find the most interesting, is the vampire.
It is possible to bomb memory with JMP instructions. An enemy program
which runs across such an instruction will be "captured", and can be
forced to execute useless code. One particularly nasty implementation
of a vampire sucks the enemy program into code where it not only
splits into many different threads, which slows down all the enemy
threads, but also slowly bombs memory in a fashion which will never
kill the vampire! Unfortunately, vampires have to leave pointers to
their "pits" all over memory, so anti-vampire programs can look for
these pointers and bomb the pits or write useful code over them.

The most successful modern Core Wars programs are often combinations
of two of these five strategies.