A midweek review of Corewar
September 29, 1993
-------------------------------------------------------------------------------
I. The Standings:
# %W/ %L/ %T Name Author Score Age
1 40/ 31/ 29 QuickFreeze v1.4 P.Kline 150 8
2 45/ 44/ 11 Iron Gate 1.01 Wayne Sheppard 146 247
3 34/ 24/ 42 Deck of Many Things c w blue 143 7
4 45/ 48/ 8 Agony 6.0 Stefan Strack 142 56
5 44/ 46/ 11 Dragon Spear c w blue 142 1206
6 39/ 38/ 24 Winter Werewolf 3 W. Mintardjo 139 422
7 42/ 45/ 13 Impurge Fredrik Ohrstrom 138 428
8 33/ 27/ 40 FlyPaper 3.0 J.Layland 138 528
9 40/ 42/ 18 Beholder's Eye v2 W. Mintardjo 137 24
10 42/ 48/ 9 Backstabber Anders Ivner 136 2
11 35/ 37/ 28 Herem VI Anders Ivner 134 276
12 29/ 25/ 46 Impact v1.0 Anders Ivner 133 241
13 29/ 26/ 45 Hydra Stephen Linhart 133 173
14 34/ 36/ 30 Keystone t13 P.Kline 132 62
15 30/ 27/ 43 ttt nandor sieben 132 328
16 36/ 41/ 23 Leprechaun 1b Anders Ivner 130 172
17 26/ 23/ 51 pMARS pMARS project 129 153
18 28/ 26/ 46 Imprimis 7 P.Kline 129 344
19 28/ 29/ 43 Night Crawler Wayne Sheppard 128 1104
20 38/ 51/ 11 Cleaver Wayne Sheppard 126 1
21 27/ 28/ 45 Sphinx v2.8 W. Mintardjo 125 2102
-------------------------------------------------------------------------------
II. The Basics:
-Core War Archives, including many helpful articles, warrior source
code, and reliable emulators, are available via anonymous FTP
at soda.berkeley.edu in pub/corewar.
-FAQ for this newsgroup is available via anonymous FTP at
rtfm.mit.edu as pub/usenet/news.answers/games/corewar-faq.z
-------------------------------------------------------------------------------
III. The Scoop:
** EXTRA ** EXTRA ** EXTRA ** EXTRA ** EXTRA ** EXTRA ** EXTRA **
Today saw the ever-durable Sphinx v2.8 pushed off KotH, at the record age
of 2102. After A. Ivner's "Backstabber" dropped *all* the imps to the
bottom ranks, W. Sheppard's "Cleaver" finished the job - barely - by a single
point nosing Sphinx off the Hill. KotH now awaits the 'imp'roved Sphinx,
which has been flexing its muscles in the wings, faster launch, offset boot,
unique stone and all! Is this a conspiracy or what :-)
All the other imp-authors are holding their breath to see who's next for the
chop, since all are firmly settled in the bottom rankings (Imprimis nooo!)
*****************************************************************************
It happened last October! A mighty wind swept the Hill. Brave and hardened
warriors were whisked away like paper dolls. Imps were back, and this time
they meant business!
The Corewar world watched in dismay as Anders Ivner's "The IMPire strikes back"
dismantled such valiant fighters as "Charon", "No Mucking About", "B-scanners
live in vain", and "Sucker". Even venerable "Flash Paper" dropped in the
rankings. As Ivner put up test after test afficionados marveled at his
;strategy line: "What is the optimal setup?".
Imps? There were no imps on KotH. Imps can only tie and ties only bring 1
point. After basking in the glory a day or so, Ivner posted his source, and
we all pondered the fact that fast imps only tie, but slow imps can kill you.
Here is a report from October 13, 1992:
# %W/%L/%T Name Author Score Age
1 40/11/49 The IMPire strikes back Anders Ivner 169 1
2 47/42/10 No Mucking About Campbell Fraser 152 596
3 38/28/34 Atomic Sheep c w blue 149 54
4 45/45/ 9 nandor sieben 146 383
5 33/23/44 dead end nandor sieben 144 20
6 36/30/34 Chaff v2.8 Patrick Hunt 142 107
7 43/44/13 Falling Leaf 1.21 Matt Hastings 142 734
8 34/26/41 Flash Paper3.7 Matt Hastings 142 648
9 42/43/15 testing Roadrunner S. Halvorsen 140 440
10 41/41/18 Pale Shears Matt Hastings 140 385
11 43/46/11 Charon v7.0 J.Cisek & S.Strack 139 244
12 42/47/11 Sucker 4 Stefan Strack 138 849
13 41/45/14 Dain7 1 Dan Nabutovsky 137 14
14 40/44/16 B-scanners live in vain Matt Hastings 136 578
15 36/38/26 Smooth Noodle Map 6 Matt Hastings 135 400
16 39/44/17 Gimli Dan Nabutovsky 135 10
17 38/42/20 SNAKE Wayne Sheppard 134 5
18 40/46/14 Twilight Pits 3 W. Mintardjo 133 86
19 38/46/16 Eclipse v3.0 P.Kline 131 67
20 42/53/ 5 Orc c w blue 130 117
A quick scan down the loss column tells the story. IMPire was not
yielding any losses. If he wasn't beating you he was stealing your wins
with ties. Authors scrambled to unravel this mystery. Better and faster
imp-launchers appeared. Something called 'imp-gates' were uncovered in the
archives, dusted off, and tacked into programs. A new form made its
appearance - the stone-imp combination, shortly followed by the vampire-imp.
Here is a report from October 20, 1992 - one week later:
# %W/%L/%T Name Author Score Age
1 38/12/50 Impression 1 Dan Nabutovsky 164 19
2 35/13/52 Red Dragon c w blue 156 6
3 43/38/19 Beholder's Eye v1.1 W. Mintardjo 148 41
4 39/34/27 Winter Werewolf W. Mintardjo 145 25
5 45/45/10 test Stefan Strack 145 2
6 33/22/45 The Sender of Eight Matt Hastings 143 47
7 43/45/12 Emerald P.Kline 141 17
8 38/36/26 a B-scanner Darkly Matt Hastings 141 9
9 25/10/64 repimp nandor sieben 141 30
10 33/27/41 Atomic Sheep c w blue 139 175
11 32/28/40 Tarrasque c w blue 135 10
12 40/50/11 sproba nandor sieben 130 8
13 33/37/29 Pale Shears2 Matt Hastings 129 26
14 37/45/19 Dain Dan Nabutovsky 129 16
15 35/43/22 A CMP-Scanner Darkly Matt Hastings 128 12
16 23/20/57 The IMPire strikes back Anders Ivner 126 70
17 37/48/15 Eclipse 2.0 P.Kline 126 1
18 38/50/12 nandor sieben 125 504
19 34/48/17 Charon v7.0 J.Cisek & S.Strack 121 365
20 33/52/15 No Mucking About Campbell Fraser 113 717
Compare the age columns from these reports and you will see how great the
"impact" of this new warrior-form. Programs that had been on the Hill for
months had vanished.
Some 'imp'ortant facts:
The standard form of the imp-spiral is:
a mov 0,b
b mov 0,c
c mov 0,d
...
n mov 0,a+1
where a,b,c,...n are equidistant in core and execute in the above order. After
n, the process at a advances to a+1 and executes. Attacking a single point
in the spiral only kills it if it is his turn to execute, or if it is the
trailing process (a). And if you are overrun by the spiral while executing
fewer processes than he is, you will outrun him and die.
There are 1224 imp-numbers in a core size of 8000. Since all mod-one
steps are imp-numbers, there are no core sizes (larger than 2) which
support no imp-spirals. Any prime number which is not a factor of the
core size would be an imp-number. Some interesting imp-numbers are:
#pts imp# (#pts and imp# can be interchanged)
1 1 (8001)
3 2667
7 1143
9 889
11 5091
13 3077
17 2353
19 7579
31 3871
63 127
2571 2571
7981 429 (the largest)
To find imp-numbers, solve for N in both of these equations:
1. (J*coresize + 1) mod N = 0
2. (J*coresize + 1) / N < coresize
where J is any positive integer.
I once wrote a 3-point launcher that calculated its imp-number at startup, so
it would work on any core size. What did I call it? "Improvise" of course!
Unfortunately in many core sizes, 3 is not an imp-number. However it
may be possible to do a startup search for imp-sizes up to 13 (which
would cover all core sizes up to 30030), and guarantee an imp-launch.
While much progress has been made in combatting imps, it appears they are
here to stay, just like paper, stone, and scissors. By adding forms
to the mix on KotH, however, it becomes harder for new programs to break
in - they just don't have a large advantage against enough forms
to create a sufficiently high score. You might have a great scanner-killer
but there aren't enough scanners out there to boost your score. So new
programs may need multiple strategies to make it on KotH. And adding a spiral
may be an attractive option :-)
****************************************************************************
On a non-imp topic, we can't overlook the passing of Grimm's Vampyre at
the respectable age of 282. With Grimm's goes the last vampire on the Hill
(as far as I can tell :-)
Also, welcome back to S. Morrell and Imps! Imps! Imps!.
-------------------------------------------------------------------------------
IV. The Outlook:
5 43/ 47/ 9 Backstabber Anders Ivner 140 1
6 30/ 24/ 46 Deck of Many Things c w blue 137 1
-------------------------------------------------------------------------------
V. The Quick Look:
16 23/ 15/ 63 Imps! Imps! Imps! Steven Morrell 131 1
16 29/ 29/ 43 NC Test Wayne Sheppard 129 1
20 38/ 51/ 11 Cleaver Wayne Sheppard 126 1
21 0/ 78/ 22 SPL-Bomb Slava Shinderov 22 0
21 2/ 54/ 44 SPLIMP v1.1 Remy A. G. Wetzels 49 0
21 2/ 56/ 42 PiggyBack 0.2 Ben Byer 47 0
21 5/ 67/ 28 pb bb 44 0
21 14/ 39/ 47 Thundering buttocks J Horwich 90 0
21 15/ 68/ 17 Nosferatu 0.21 J Kyle Kelso 63 0
21 16/ 28/ 56 Sauron v3.0 Michael Constant 103 0
21 16/ 48/ 36 spriteII Cormac Walsh 85 0
21 17/ 27/ 56 sub-type-something or oth c w blue 106 0
21 17/ 58/ 25 All That Glitters v2.1 Mike Nonemacher 76 0
21 17/ 61/ 22 Imperor VII Pierre Baillargeon 74 0
21 19/ 40/ 41 Tangle 1.0 Devin Kilminster 99 0
21 19/ 77/ 4 Test Ray Cromwell 60 0
21 21/ 18/ 60 Wriggler III Geoff Rehmet 124 0
21 21/ 21/ 59 Wriggler II Geoff Rehmet 120 0
21 22/ 24/ 54 Red Baron v3.3 Mike Nonemacher 121 0
21 22/ 69/ 10 Morticia v1.0 Mike Nonemacher 75 0
21 24/ 34/ 42 Hunger Pangs Steven Morrell 115 0
21 26/ 64/ 11 Cat v2.0 Tim Scheer 88 0
21 28/ 52/ 21 bugII shaun 103 0
21 32/ 51/ 16 Sunburst 31 Jay Han 113 0
21 36/ 49/ 15 Grimm's Vampyre c w blue 123 0
21 39/ 52/ 9 Tiny Gate Wayne Sheppard 126 0
-------------------------------------------------------------------------------
VI. The Hint:
On Killing Imps. Oh yes, they can be killed. Here are some of the ways.
1. Gates. Gates. Gates. Say again. Gates. Gates. Gates
Here is the form W. Mintardjo used in Beholder's Eye and Winter Werewolf:
gate equ example-10
example spl 0,<gate
dat <gate
The DAT line can be adapted to hold an increment for bombing/scanning:
dat #-gate,<gate
An imp cannot pass 'gate' because of the continual decrementing. (Well
actually I have seen an imp structure that passes such a gate, but it was
a little too delicate to survive normal bombing :-)
Here is the form used in the vampires, Sucker and Twilight Pits:
gate equ example-10
example spl 0,<gate
jmp trap,<gate
....
trap dat <gate
These gates are an end-game strategy. The program does its normal attack,
vamping or stunning, then a core-clear which eventually moves the DAT line
into place. From then on 'gate' is continuously decremented.
Don't overlook partial gating, which decrements 'gate' on every-other or
one-out-of-three. If it is not possible for your program to evolve a
perfect gate, you can still pick up wins with a partial. This includes
-every- available statement into which you can put a predecrement operand.
Got JMP's? Turn them into JMP x,<gate. SPL's the same thing. Strive
to create an imp-hostile environment. Your decrementing instruction may
be the only one to survive the battle!
Here is a core-clear incorporating a partial gate:
gate equ example-10
example spl 0,<gate+2667
clear mov bomb,<gate
jmp clear,<gate+2667
bomb dat <example-1-gate
This code is either decrementing gate or gate+2667, which makes a 66% gate
against a 3-point imp, or a 50% gate against other sizes.
To harden your 'bomb' against itself being decremented, use the form:
bomb dat <example-1-gate,<example-1-gate
Then if both the SPL and DAT get decremented you are still okay, and
also if only the DAT gets decremented.
Here is the form called 'wimps' by B. Thompsen:
wimp jmp 0,<-10
Thompsen starts a couple of these in core, then after core-clearing causes
his other code parts to self-destruct, leaving the wimps to kill any
remaining imps. Smart!
2. Imp-killing scan increments. These are imp-size specific, so are
not quite as effective as gates, but still useful. Normally used against
3-point imps, they work only after some portion of the imp-opponent has been
spl-stunned and is therefore running very slowly. The increment is chosen
so that it scans location N, then other locations for a while, then location
N+2667. Assuming that the imp has not had time to repair N, N+2667, or
N+5334, the delay between N and N+2667 can be several hundred cycles.
A scan increment that scanned N+2667 too quickly after N would be a very
inefficient one. But there are a number of increments that scan N and N+2667
in less than 1000 scans which are also efficient core-scanning increments.
There are even a few that scan N+2667 *and* N+1143 (7-point imps) in less
than 1000 scans which are moderately efficient. Of the 2100 numbers that
most quickly find opponents of size 13, and scan N+2667 after N in
from 300-1000 steps, here are the four smallest:
59, 81, 83, 107
In order for this to be a successful strategy, scanning must continue for
as long as possible, yet still allow time for a core-clear and for the
opposing processes to all die.
3. Forward bombing and decrementing, two different strategies, but
the same principle. Since the imp never repairs its trailing process
you can knock them off with a left-to-right bombing run. Depending on the
bomb you are using, this can be more-or-less successful. Here is one
approach:
example spl 0,<gate
loop add inc,stone
stone mov <10,loop
djn loop,<-20
inc dat #2667,#3044
This is a mod-4 bomber, which runs three decrementing streams at stone+10,
stone+10+2667, and stone+10+5334, which may overtake and kill a 3-point imp.
After 25% of core has been tracked, 'stone' will drop a bomb on 'loop',
so you need to have something out there (wherever the a-operand is pointing)
that moves you into the next phase - could be 'loop' again for that matter.
Another approach would be to watch for imp instructions, pick one
up and start bombing from there, using it as the increment.
4. DAT bombing. The best bomb is:
dat <2667,<5334
but your chances of killing an imp-spiral with single-bomb DAT's is
almost nil, and the bomb is only effective against 3-point imps. Here is
an example of using the bomb in paper:
start spl 1
spl 1
mov -1,0 ; < create 7 processes
p1s mov p1b,<1000 ; decremented by parent
p1 mov #7,p1s
mov <p1s,<p1n ; create child
p1n spl @p1n,-1188 ; start child
mov p1b,<p1n ; bomb in sequence with child
jmz @0,@p1 ; if i'm ok, go again
p1b dat <2667,<5334
This paper should kill at least 30% of short 3-point imps (spiral length
less than 9), but is less effective against longer imps. The advantage of
using paper to bomb is that imps can't kill paper. Unfortunately, imps
tend to subvert paper processes so the effective bombing rate goes down
as the game progresses. However the above paper resists subversion somewhat
by bombing ahead of and -2667 ahead of its children to prevent their being
overrun by its own 'imped' processes.
5. Self-splitting. Since the imp only kills your program if you have
fewer processes than he does, you can create a tie by having more. Then
if you are overrun you will follow, not outrun him. This means extra
processes at -every- location, including spl-zero lines, since any or
all other lines may be dat-bombed and lost during the battle.
6. Very rapid startup. Imps and their co-components can take 40-50
instructions to launch, plus a 'large' startup code. If you come out
swinging that's 40-50 instructions for bombing or scanning to your
advantage.
7. Program-specific attack. If you have the source for the imp-opponent,
you may find some other weakness or characteristic that will give you an
advantage. For example, you might see that he is booting his stone 1200
locations from the startup code. If you start by searching for the startup
code, then bomb both it and 1200 locations away, you will at least kill off
the stone with no problem. Then a simple gate will complete the job. This
is a poor substitute for good strategy, but as long as the opponent stays on
the Hill, you get free points. (Honest - I haven't done this - except
inadvertently in QuickFreeze. You guys really ought to vary your boot
distances a little :-)
-------------------------------------------------------------------------------
VII. The End:
Paul Kline
pk6811s@acad.drake.edu