A midweek review of Corewar
January 27, 1994
-------------------------------------------------------------------------------
I. The Standings:
# %W/ %L/ %T Name Author Score Age
1 40/ 26/ 34 Killer instinct Anders Ivner 154 112
2 45/ 38/ 17 SJ-4a J.Layland 153 49
3 47/ 42/ 11 Iron Gate 1.1 Wayne Sheppard 153 12
4 40/ 29/ 31 Match Stick c w blue 152 27
5 39/ 26/ 35 NC decoy Wayne Sheppard 151 133
6 35/ 20/ 45 Cannonade P.Kline 150 121
7 44/ 41/ 15 test-tw Fredrik Ohrstrom 148 16
8 33/ 21/ 46 ttti nandor sieben 145 128
9 43/ 43/ 14 Blitzkrieg Mike Nonemacher 144 42
10 44/ 45/ 10 Medusa's v5.1 W. Mintardjo 143 52
11 34/ 25/ 41 Imprimis 7 P.Kline 143 780
12 39/ 35/ 26 Winter Werewolf 3 W. Mintardjo 142 858
13 41/ 41/ 19 Fast Food v2.1 Brant D. Thomsen 141 37
14 43/ 46/ 11 Dragon Spear II c w blue 140 191
15 38/ 36/ 25 Keystone t13 P.Kline 140 387
16 32/ 24/ 44 Patapouf v2.0 P.E.M & E.C 140 36
17 36/ 34/ 29 Vagabond P.Kline 139 48
18 37/ 38/ 24 Clown v8.1 P.E.M & E.C 136 131
19 39/ 44/ 17 My wife is pregnant! Steven Morrell 135 1
20 36/ 38/ 25 .T.E.S.T. V0.1 P.E.M & E.C 134 80
21 2/ 98/ 0 test P.Kline 7 0
-------------------------------------------------------------------------------
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:
I'm back. Last issue of _Push Off_ was November 4. It's not your local
server, so stop cussing your administrator :-), I was just busy.
KotH and StormKing are still up, but not very active it seems. Personally
I can't work on both old and new standards, and MacPmars is still kludgy
so I'm mostly limited to the old standard using RedCoder. Which is kind
of my excuse for reporting mostly on KotH :-( My recommendation is to
move quickly to approve the new standard and get everyone upgraded.
Anyway, there's a lot of fighters on KotH that have never been published.
When I first got into CoreWars, many of the authors were posting their
source regularly so everyone could learn and react, and the whole game
advanced more quickly. That also made it much easier for newcomers to
break in - it's just too tough to fight 20 mystery programs, when all
you've seen is dwarf, imp, and mice. And even though hundreds of more
advanced programs are available from soda.berkeley.edu, the ones on the
Hill are different.
So how about some 'revelations', 'confessions', and the like? :-)
Source Code! Source Code! Source Code! Even if you've already
posted it once, let's give the newbies a hand up.
We must take a moment to observe the passing of F. Ohrstrom's Impurge,
at the ripe old age of 854. Impurge took a drop in the ratings when
W. Shephard submitted Iron Gate 1.1, and was shortly pushed off.
Impurge's passing leaves two competitors over age 500, Imprimis and
Winter Werewolf.
-------------------------------------------------------------------------------
IV. The Outlook:
Yeesh. 3 months worth is just too many.
-------------------------------------------------------------------------------
V. The Quick Look:
Double-yeesh.
-------------------------------------------------------------------------------
VI. The Hint:
Regarding Imp-spirals, here is some recycled stuff:
------------------------------------------------------------------------------
From the FAQ glossary:
Imp - Program which only uses the MOV instruction.
example MOV 0, 1
or
example MOV 0, 2
MOV 0, 2
Imp-Gate - A location in core which is bombed or decremented continuously
so that an Imp can not pass. Also used to describe the program-code
which maintains the gate.
example ...
...
SPL 0, <example
DAT <example, #0
[this may need restating since Cannonade proves gates can be passed :-)]
Imp-Ring - A minimal Imp-Spiral.
d EQU (coresize+1)/3
A MOV 0,d ; copy self to B
B MOV 0,d ; copy self to C
C MOV 0,d ; copy self to A+1
Imp-Spiral - An Imp-like program with two or more processes supporting
each other. A three-point spiral, with six processes running in this
sequence:
d EQU (coresize+1)/3
A MOV 0,d ; copy self to B
B MOV 0,d ; copy self to C
C MOV 0,d ; copy self to A+1
A+1 MOV 0,d ; copy self to B+1
B+1 MOV 0,d ; copy self to C+1
C+1 MOV 0,d ; copy self to A+2
--------------------------------------------------------------------------
Today's topic is imp launching, or actually imp-spiral launching, using
several different launch techniques, with some pointers as to their merits.
Just for fun, here is the old 'worm' launcher, which could be considered
a one-point spiral with an imp-size of 8001:
length dat 0,#10
go spl extrude,0
djn 0,length
mov length,extrude ;Stop making the worm
;
extrude spl 0,0 ;spin here and make a worm
mov 0,1 ;of imps
end go
The unfortunate thing about worm is that the processes execute in reverse
order. The leading process executes, then the one behind that, the one
behind that, etc. In a true spiral you want each mov instruction to
write over the location that the next process is going to execute. So
there is no time lag between writing the mov instruction and executing
it. That, plus the great separation of instructions in core, is the
strength of spirals.
Anyway, here is a standard binary launcher:
boot equ 1000
impsize equ 2667
start mov imp,imp+boot
s1 spl s2
spl s1a
jmp imp+boot
s1a jmp imp+boot+(1*impsize)
s2 spl s2a
jmp imp+boot+(2*impsize)
s2a jmp imp+boot+(3*impsize) ; <- or jmp to stone/vamp/???
imp mov 0,impsize
The binary launcher is fast, creating just the right number of
processes and jumping them into position in the necessary order.
However, this is a very short spiral that can be killed with
a single dat-bomb. A spiral with eight processes would require
twice the code to launch, making it more vulnerable to early detection.
And the binary launcher is most efficient when creating power-of-two
number of processes, though it can be tailored to kill or re-use
excess ones.
Here is a Nimbus-style launcher:
boot equ 1000
impsize equ 2667
start mov imp,imp+boot
spl 1 ; <- add more splits for longer spiral
spl 1
spl s2
s1 jmp @0,imp+boot
s2 add imp,s1
dat #0 ; die or jump to stone/vamp/???
imp mov 0,impsize
This launcher is short, can be adapted for any imp-size or spiral length,
but is not quite as fast as the binary launch, since every jmp is
accompanied by an add. The 'adding' processes also have to be disposed of,
either through letting them die, or by putting them to work. However,
Nimbus successfully launches a 64-point spiral this way, which is
remarkable.
Here is about the shortest 3-point launcher possible:
start spl imp+5334
spl -1
spl imp+2667
imp mov 0,2667
In fact, this launcher doesn't generate a true spiral, but a series of
rings instead. Each ring is slightly separated from the succeeding one
due to the imbedded spl-delay in the launcher. However it is fast
and continuously launches rings which become difficult to kill.
----------------------------------------------------------------------------
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 :-)
----------------------------------------------------------------------------
A couple of issues back I posted this imp-spiral launch code:
boot equ 1000
impsize equ 2667
start mov imp,imp+boot
spl 1 ; <- add more splits for longer spiral
spl 1
spl s2
s1 jmp @0,imp+boot
s2 add imp,s1
dat #0 ; die or jump to stone/vamp/???
I also suggested that the extra processes that die on the last DAT #0
line could be put to work in a stone or something. THAT WAS A BAD IDEA.
Those extra processes should be left to die immediately. What happens
is that they execute alternately with the processes in the spiral, thus
weakening the spiral. Ideally, the spiral processes all execute in turn,
then any others in your program, then the spiral processes again, etc.
----------------------------------------------------------------------------
And here is something new:
Generating large numbers of processes is a prerequisite for launching a
spiral. The usual way is to: 1. determine how many processes you need.
2. subtract one from that number and convert to binary. 3. replace
the binary digits left-to-right with lines of code like:
spl 1 ; where there's a 1
mov -1,0 ; where there's a 0
Unfortunately this can create a large number of lines, making you a big
target while waiting for the processes to step through them.
If the number of processes you want is a power-of-2 try this code:
spl 1,<1
jmn -1,#N
where N is the number of processes minus one. It takes longer to execute,
but its small size makes it competitive with other code.
-------------------------------------------------------------------------------
VII. The End:
Paul Kline
pk6811s@acad.drake.edu