MY FIRST COREWAR BOOK
by Steven Morrell
PREFACE
This book is an introductory collection of corewar warriors with commentary. It
assumes an acquaintance with the ICWS '88 redcode language (See M.Durham's
tutorial.1 and tutorial.2 for details). Unless otherwise noted, all redcode is
written in ICWS '88 and is designed for a coresize of 8000, process limit 8000.
All documents referred to in this text are available by anonymous FTP at
ftp.csua.berkeley.edu in one of the subdirectories of pub/corewar/.
After a brief introduction, each chapter presents warriors by subject. I then
pontificate on the merits of these various warriors and give some hints for
successful implementation. I mention credits and give references to other
warriors worth further investigation. Unless otherwise indicated, these warriors
are archived in warrior10.tar in the redcode/ directory.
The presentation of each warrior follows roughly the same format. First, the
parameters of the warrior are given. These include the name, author, attack
speed, effective size, durability, and effectiveness, and score against the
Pizza Hill. The effective size is the size of the executing code during the
attack phase, taking into account regenerative code. Next, self-contained source
code is given, followed by a brief description of the warrior. Finally, a
detailed technical description of how the warrior runs is given.
I hope that this helps. If you have questions or comments, send them to
morrell@math.utah.edu, where you can reach me until June,1994.
Steven Morrell
Chapter 1: Imp-Rings
On October 14, 1992, A.Ivner posted a warrior that revolutionized the game of
corewar. "The IMPire strikes back" scored about 170 on the Intel hill and only
suffered 10% losses, putting it firmly in first place. A.Ivner had invented a
way to kill other programs with imps -- the world's first imp-ring. D.Nabutovsky
improved the launch code a bit by making an imp-spiral and adding a stone in his
"Impressive", which lost only 2% and scored 195 when it started on the hill (for
more information on stones, see chapter 2). Since that time, most warriors on
the hill have either been imps or something hostile to imps.
This chapter deals with imps, from the basic imp proposed by A.K.Dewdney in the
original Scientific American articles to the modern-day imp-spiral we see as a
component of many successful warriors.
--1--
Name: Wait
Speed: None
Size: 1
Durability: Strong
Effectiveness: None
Score:
wait JMP wait
end wait
Wait is the simplest warrior. Its small size makes it difficult to locate.
However, it has no attack, so it only wins if the enemy program self-destructs.
We shall be using this program for fodder.
--2--
Name: Imp
Author: A.K.Dewdney
Speed: 100% of c (sequential)
Size: 1
Durability: Strong
Effectiveness: Poor
Score:
imp MOV imp, imp+1
end imp
Imp presents the enemy with a small, moving target that will not die without a
direct hit. It ties a lot, and is vulnerable to the imp-gate. (See program 3)
HOW IT WORKS: 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.) When process
(1) executes, 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.
Process (2) now executes. Since all addressing is relative, the process copies
its instruction to the next address and advances.
MOV 0,1
MOV 0,1
MOV 0,1 (3) ;This is the second copy.
And so it goes, 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.
--3--
Name: Imp Gate
Speed: None
Size: 1
Durability: Strong
Effectiveness: Excellent against imps, Extremely Poor against others
Score:
gate equ wait-10
wait JMP wait,Chapter 2: Stones
If you are fast and small, you can find the enemy before the enemy finds you.
This is the philosophy of pattern bombers, a group of warriors much maligned by
frustrated corewar enthusiasts trying to make intelligent warriors. But the fact
remains, frenzied maniacs can often kill the slow brooding kind.
Pattern Bombers are also refered to as stones, as part of the stone - scissors
- paper analogy. Scissors, which includes vampires and scanners, are bigger than
stones and therefore tend to get beat up by them more often. Paper, also known
as a replicator, is a program that makes copies of itself throughout the core
faster than a pattern bomber can destroy all of them. Stones are thus
ineffectual against paper, or at least they were until W. Mintardjo stuck a two
-pass core-clear on one of his stones.
--1--
Name: Dwarf
Author: A.K.Dewdney
Speed: 33.33% of c
Size: 4
Durability: Weak
Effectiveness: Average
Score:
bomb DAT #0
dwarf ADD #4, bomb
MOV bomb, @bomb
JMP dwarf
end dwarf
Dwarf bombs every fourth instruction with DAT instructions in hopes that enemy
processes will execute this code and die. Since 4 divides coresize, Dwarf will
never drop a bomb on itself. Because Dwarf only hits every fourth instruction,
it is a mod-4 bomber.
HOW IT WORKS: Before anything executes, core looks like this:
DAT #0, #0 ;bomb
ADD #4, -1 (1)
MOV -2, @-2
JMP -2, 0
Then process (1) adds 4 to the B-field of bomb:
DAT #0, #4 ;bomb
ADD #4, -1
MOV -2, @-2 (2)
JMP -2, 0
Process (2) moves bomb 4 instuctions forward, where the B-field of bomb points
to:
DAT #0, #4 ;bomb
ADD #4, -1
MOV -2, @-2
JMP -2, 0 (3)
DAT #0, #4
Process (3) simply makes the program loop back to the beginning.
DAT #0, #4 ;bomb
ADD #4, -1 (4)
MOV -2, @-2
JMP -2, 0
DAT #0, #4
Process (4) adds 4 to the B-field of bomb:
DAT #0, #8 ;bomb
ADD #4, -1
MOV -2, @-2 (5)
JMP -2, 0
DAT #0, #4
Process (5) drops the next bomb where the B-field of bomb is pointing.
DAT #0, #8
ADD #4, -1
MOV -2, @-2
JMP -2, 0 (6)
DAT #0, #4
DAT #0, #8
Process (6) loops back, and bomb after bomb are dropped forward through core.
--2--
Name: Stone
Author: Matthew Householder
Speed: 33.34% of c
Size: 4
Durability: Weak
Effectiveness: Average
Score:
start MOV <2, 3
ADD d1, start
JMP start
DAT #0
d1 DAT #-5084, #5084
end start
Stone is a mod-4 bomber like Dwarf, but with two important improvements. First,
the step-size has been increased somewhat for better distribution of bombs
against larger opponents. Second, Stone decrements other adresses while it
bombs. Decrementing opponent's code may wound it so that DAT bombs can destroy
it later.
HOW IT WORKS: Pre-decrement indirect addressing can be tricky, so we shall use
the intuitive approach, even though it yields wrong results for weird
instructions like MOV <0,<1. See "tutorial.2" or the ICWS '94 standard for
precise details.
When Stone is loaded, core looks like this below. The DAT #0,#0 instruction is
used only as a spacer between the executable code and the other DAT statement,
as we shall shortly see.
MOV <2, 3 (1)
ADD 3, -1
JMP -2, 0
DAT #0, #0
DAT #-5084, #5084
The B-field of the JMP instruction (pointed to by the A-field of the MOV
instruction) is decremented, so that it now points to the ADD instruction. This
ADD instruction is now moved to the DAT #0,#0 instruction (pointed to by the B
-field of the MOV instruction). Core now looks like this:
MOV <2, 3
ADD 3, -1 (2)
JMP -2, -1 ;this has been decremented
ADD 3, -1 ;this has been copied
DAT #-5084, #5084
This last sequence may be a little misleading, because it looks like we are
dropping ADD 3,-1 bombs throughout core. We shall see this is not usually the
case.
We now come to the ADD 3,-1 instruction. Since this ADD is not immediate, as it
was in Dwarf, the A-operand of the DAT instruction is added to the A-operand of
the MOV instruction and the B-operand of the DAT instruction is added to the B
-operand of the MOV instruction:
MOV <-5082, 5087
ADD 3, -1
JMP -2, -1 (3)
ADD 3, -1
DAT #-5084, #5084
The executing process now jumps back (the -1 in the B-field is ignored).
MOV <-5082, 5087 (4)
ADD 3, -1
JMP -2, -1
ADD 3, -1
DAT #-5084, #5084
Process (4) drops another bomb: the location -5082 behind the MOV instruction is
decremented and whatever it points to is moved 5087 in front of the MOV
instruction. The pattern continues until someone is killed or time runs out.
Stone, then, doesn't really drop bombs as such, but rather moves instructions
around core in a pseudo-random fashion. But since core is initialized to DAT
0,0, most of the instructions it moves are deadly DAT statements. This process
is called transposition in the literature.
--3--
Name: Armadillo
Author: Stefan Strack
Speed: 32.86% of c
Size: 5
Durability: Strong
Effectiveness: Average
Score:
bomb SPL 0
loop ADD #3039, ptr
ptr MOV bomb, 81
JMP loop
MOV 1, <-1
end bomb
Armadillo drops SPL 0 bombs throughout core to stun the enemy, and then lays
down a DAT carpet (also called a core-clear) to kill the enemy. This is one of
the earliest bombers that used a core-clear to erase all of memory. It scores
100% wins against Wait (program 1, chapter 1) where Dwarf and Stone only score
25% wins and 75% ties. In my experience, SPL bombs are the most effective
single-instruction bomb a warrior can drop. However, SPL bombs don't kill many
programs cleanly, don't allow you to simultaneously bomb the rest of the core
with decrements, and don't paralyze the opponent as well as the multi
-instruction bombs that scanners drop.
Another innovation in Armadillo is the use of a SPL 0 instruction inside the
warrior. If any of the other instuctions are hit with DAT bombs, the program may
not operate correctly, but the bomb doesn't kill all of the processes.
Additionally, this self-splitting code generates enough processes that imps
cannot kill Armadillo by themselves.
HOW IT WORKS: When Armadillo is loaded into core, it looks like this:
SPL 0, 0 (1)
ADD #3039, 1
MOV -2, 81
JMP -2, 0
MOV 1, <-1
Process (1) splits into processes (2) and (3).
SPL 0, 0 (3)
ADD #3039, 1 (2)
MOV -2, 81
JMP -2, 0
MOV 1, <-1
Process (2) executes and process (3) splits.
SPL 0, 0 (6)
ADD #3039, 1 (5)
MOV -2, 3120 (4)
JMP -2, 0
MOV 1, <-1
Process (4) drops a split bomb, process (5) changes the bombing location, and
process (6) splits.
SPL 0, 0 (10)
ADD #3039, 1 (9)
MOV -2, -1841 (8)
JMP -2, 0 (7)
MOV 1, <-1
Process (7) jumps back in order to conserve processes, (8) bombs, (9) changes
the bombing location, and (10) splits.
SPL 0, 0 (15)
ADD #3039, 1 (14) (11)
MOV -2, 1198 (13)
JMP -2, 0 (12)
MOV 1, <-1
And so the process continues. The ever-lengthening string of processes executes
the code (backwards!) that drops the SPL bombs. Eventually, a SPL 0,0 gets
dropped on the JMP statement:
SPL 0, 0
ADD #3039, 1
MOV -2, 1
SPL 0, 0 (1)
MOV 1, <-1
The loop is broken, and all of the processes fall through to this second SPL
instruction eventually. We examine this last bit of code as if there were only
one process running at the SPL instruction, since the program doesn't depend on
process order from this point on. Process (1) splits:
SPL 0, 0
ADD #3039, 1
MOV -2, 1
SPL 0, 0 (3)
MOV 1, <-1 (2)
Process (2) decrements the B-field of the SPL instruction (which the SPL
instruction doesn't need) and moves the blank (DAT 0,0) instruction to where the
SPL instruction points:
SPL 0, 0
ADD #3039, 1
SPL 0, -1 (3)
MOV 1, <-1
(4)
Process (3) splits:
SPL 0, 0
ADD #3039, 1
SPL 0, -1 (6)
MOV 1, <-1 (5)
(4)
Now process (4) executes an illegal instruction and dies, (5) decrements the SPL
instruction again and bombs the next instruction backwards, and (6) splits:
SPL 0, 0
SPL 0, -2 (9)
MOV 1, <-1 (8)
(7)
This pattern repeats until eventually the core clear wraps around and erases
itself. Just before this erasure occurs, core looks like this:
SPL 0, 2 (23997)
MOV 1, <-1 (23996)
(23995)
Process (23995) dies as usual, but this time, when process (23996) bombs, it
erases the bombing instruction:
SPL 0, 2 (23997)
(23998)
Now, if we ignore all of the dying processes, we see that this SPL command keeps
splitting processes to itself, keeping the warrior alive.
--4--
Name: Cannonade Stone
Speed: 24.51% of c
Size: 5
Durability: Average
Effectiveness: Good
Score:
MOV <6, 1
start SPL -1, <5144
ADD 3, -2
DJN -2, <5142
DAT #0, #0
MOV 190, <-190
end start
Cannonade Stone takes the idea of self-splitting code to another level. Altough
it bombs somewhat slower than other bombers, it splits off processes so quickly
that a stun attack on other components of the warrior will not halt the
execution of the stone. The bombing run hits every fifth instruction, with a
transposition at every tenth position and a decrement between each
transposition. Additionally, a DJN-stream is laid through memory, giving another
form of attack without increasing the size or speed of the program. At the end
of the bombing run, Cannonade Stone converts into a core-clear and partial imp
-gate.
HOW IT WORKS: When Cannonade Stone is first loaded into memory, it looks like
this:
MOV <6, 1
SPL -1, <5144 (1)
ADD 3, -2
DJN -2, <5142
DAT #0, #0
MOV 190, <-190
Process (1) splits:
MOV <6, 1 (3)
SPL -1, <5144
ADD 3, -2 (2)
DJN -2, <5142
DAT #0, #0
MOV 190, <-190
Now processes (2) and (3) execute, adding and then bombing like every other stone.
MOV <196, -189
SPL -1, <5144 (5)
ADD 3, -2
DJN -2, <5142 (4)
DAT #0, #0
MOV 190, <-190
Process (4) usually jumps back to the SPL instruction (more on this in a
moment), and the pattern repeats: each process at the SPL command splits into
two processes, which add and bomb in rapid succession.
At the end of the bomb run, the bomber mutates itself into a core-clear. The SPL
-1,<5144 instruction is overwritten with the MOV 190,<-190 instruction. The
executng portion of code then looks like this:
MOV 190, <-190
ADD 3, -2
DJN -2, <5142
The first instruction performs the core-clear, the second instruction does
nothing of strategic worth, and the third instruction loops processes back to
the first instruction. Additionally, the decrement in the MOV command sets up a
partial (33%) imp-gate 190 instructions before it, and the decrement in the DJN
instruction sets up a second partial (33%) imp gate 2666 instructions before the
first one. Since 2667 is the magic number for 3-point imps, these instructions
defend the bomber against 3-point imps at roughly 67% efficiency.
Let us examine in more detail how the DJN -2,<5142 instruction works. When it is
executed, the predecrement in the B-field decrements the instruction 5142 after
the DJN intstruction, which is probably a DAT 0,0 command:
DJN -2, <5142
...
DAT 0, -1
The DJN instruction now decrements the instruction before that, which probably
doesn't have a B-value of 1, so the executing process jumps back to the
beginning of the loop:
DJN -2, <5142
...
DAT 0, -1 ;this was decremented by the DJN
DAT 0, -1 ;this was decremented by the <
The next time the DJN instruction is executed, the B-field 5142 after the
instruction is decremented, and so is the instruction pointed by that B-field (2
before it):
DJN -2, <5142
...
DAT 0, -1 ;this was decremented by the DJN
DAT 0, -1
DAT 0, -2 ;this was decremented by the <
As the DJN instruction is repeatedly executed, a carpet of decrements is laid
down backwards through core.
This is not exactly the pattern that is laid down in core, because the SPL
-1,<5144 command decrements the same B-field as the DJN instruction does. This
adds gaps in the DJN-stream, making it more spread out and liable to hit the
enemy program. Additionally, it turns the B-field into a better partial imp
-gate.
We have made two assumptions: First, that the instruction 5142 after the DJN
instruction is DAT 0,0; second, that the instruction pointed to by that
instruction does not have a B-field of 1. If the first assumption fails, the
worst that can happen is a non-zero B-field, in which case the DJN stream is
laid somewhere else. If the second assumption fails, then the executing process
does not jump back and proceeds instead to an illegal instruction. Fortunately,
this is just one of many processes, so the bombing loop is not seriously
affected. This result may be compunded, however, if the enemy has lots of B
-fields with value 1.
--5--
Name: Night Crawler Stone
Author: Wayne Sheppard
Speed: 32.86% of c
Size: 4
Durability: Strong
Effectiveness: Good
Score:
start SPL 0, <-1001
MOV <21, 1m
SUB 1, -1
DJN -2, <-2234
end start
Night Crawler Stone is a self-splitting mod-2 bomber with a DJN-stream. When it
finishes its bombing run, it turns into code that performs an addition core
-clear.
HOW IT WORKS: Night Crawler Stone bombs memory similarly to Stone, with the
obvious improvements that Night Crawler Stone bombs in a tighter mod-2 pattern,
is self-splitting, uses a DJN-stream, and embeds the bombing step size in the
executing code, making it one instruction smaller.
After the SPL 0,<-1001 instruction has split off about 144 processes into the
main loop, it is bombed, making the effective size of Night Crawler Stone only 3
instructions long. Just before the bomber hits the bombing loop, the SUB 1,-1
instruction is decremented, starting an addition core-clear.
Unlike traditional core-clears, the addition core-clear doesn't overwrite core
with DAT statements. Instead, it modifies the A- and B-fields of the
instructions to mess up the enemy's control structures. For example, a SPL 0
that survived the bombing run becomes a SPL 2 which will not hold processes by
itself. An addition core-clear is only slightly less effective than a
traditional core-clear, and requires no additional instructions to run.
Just before the addition core-clear takes effect, Night Crawler Stone looks like
this:
DAT 0, -1
MOV <1, 3895 (12938) (12941) ...
SUB 1, -1 (12940) (12943) ...
DJN -2, <-2234 (12939) (12942) ...
Process (*38) executes, decrementing the SUB instruction and doing a copy:
DAT 0, -1
MOV <1, 3895 (12941) ...
SUB 1, -2 (12940) (12943) ...
DJN -2, <-2234 (12939) (12942) ...
Process (*39) executes, laying down another decrement in the DJN stream. Process
(*40) then executes, changing the A- and B-operands of the DAT statement:
DAT 2, 2233
MOV <1, 3895 (12941) ...
SUB 1, -2 (12943) ...
DJN -2, <-2234 (12942) ...
Process (*41) executes, decrementing the SUB instruction again, and then (*43)
modifies the operands of the next instruction back:
DAT 2, 2234
DAT 2, 2233
MOV <1, 3895
SUB 1, -3
DJN -2, <-2234
So goes the core-clear, until at the end the DJN instruction is hit and turns
into DJN 0,<0, where all of the processes go and execute repeatedly, laying down
a DJN stream until time expires.
--6--
Name: Keystone Stone
Speed: 32.86% of c
Size: 5
Durability: Strong
Effectiveness: Good
Score:
step equ 2517
emerald SPL 0, <-25
MOV <-step+1, 92
SUB 2, -1
DJN -2, <2002
JMP step, <-step
wait DJN 0, <-12
paper DJN 0, <-12
boot MOV emerald+4, paper-step
MOV emerald+3, 73
mod-2 3094/2234 under-100 -> 98
mod-4 3364/3044 under-100 -> 76
mod-5 3315/2365 under-100 -> 95
mod-8 2936/2376
mod-10 2930/2430
The constant for Night Crawler Stone, for instance, is taken from this table.
Another common rating is how closely to in half the new bomb subdivides the old
gap when it is dropped. By taking the differences between where the bombs fall
and the middle of each gap and adding these distances up, we get an alternate
method for testing efficiency.
Both of these methods are useful for finding general-purpose step sizes. But
suppose you wanted to find a step size optimized for killing other stones. Since
stones usually have four or five instructions, you would want a step size that
would bomb every 4th and 5th instruction quickly, regardless of how it does in
general.
Fortunately, there is a program in the public domain that calculates all of
these things quicky. Corestep by Jay Han can be found as misc/corestep.c, and
calcutates optima numbers and optimal step sizes. You will need a C compiler to
use it, but it is otherwise self-contained. For more infromation, FTP a copy and
read through it. The classic formula calculates optima numbers, the alternate
formula calculates the sum of the distances between bombs and midpoints, and
find-X calculates optimal step sizes against a specific program length.
If you don't have access to a C compiler or want this for some other reason, P.
Kline has compiled a list of all 8000 step-sizes with their mod, find-4, find-5,
find-10, and find-13 numbers, along with imp-killing constants and imp-numbers.
This table is designed for use in spreadsheets or databases. It is available in
the misc/ directory under the name num8000.txt with documentation in
num8000.doc. He used this on Keystone Stone to come up with a mod-1 constant
with a low find-4 score, so that it would act like a mod-4 bomber but interfere
with enemy scans (more about this in the next chapter).
Here is a list of successful stones. All of these can be found in warrior10.tar
in the 88 directory, except for SJ-4A and Keystone t21, which are buried deep
within the file feb94.txt.Z (in the newsgroup directory last time I checked.)
Everything here by P.Kline has an anti-vamp component, which will be talked
about in a later chapter.
"Leprechaun 1b" by Anders Ivner (leprechaun)
"Emerald 2" by P.Kline (emerald2)
"ExtraExtra 2" by P.Kline (extra2)
"Keystone t21" by P.Kline
"SJ-4A" by J.Layland
"Moonstone 1" by Dan Nabutovsky (moonstone)
Self-splitting stones with imp-rings can be very effective. Here is a list of
imp-stone combos that are worth investigating. All of them except Cannonade can
be found in warrior10.tar, and Cannonade can be found in the feb94.txt.Z file.
"Cannonade" by P.Kline
"Imprimis 6" by P.Kline (imprimis6)
"Night Crawler III" by Wayne Sheppard (nightcrawl)
"Sphinx 2.8" by W. Mintardjo (sphinx)
Program 1, Dwarf, was written by A.K. Dewdney for his Scientific American
articles.
Program 2, Stone, was taken from the ICWS 1990 corewar tournament. It bears a
remarkable resemblance to Rock by Scott Nelson, which was posted to the net a
couple of months before the tournament. Strange, eh?
Program 4, Cannonade Stone was extracted from P.Kline's Cannonade.
Program 5, Night Crawler Stone without the SPL 0 was submitted as "No Ties
Allowed," and confused the experts as to how something so deadly could fit into
3 lines.
Program 6, Keystone Stone, was stolen from P.Kline's "Keystone t21." The
bootstrapping code in the example differs somewhat from the bootstrapping code
used in Keystone.
Program 7, Winter Werewolf, originally did not copy the stone away from a decoy.
I am led to speculate that the code as it exists here with a bigger decoy
resembles Winter Werewolf 3, a program that was very successful on the hill.