Article 2405 of rec.games.corewar:
Newsgroups: rec.games.corewar
Path: hellgate.utah.edu!utah-morgan!cs.utexas.edu!howland.reston.ans.net!vixen.cso.uiuc.edu!newsrelay.iastate.edu!dunix.drake.edu!acad.drake.edu!pk6811s
From: pk6811s@acad.drake.edu
Subject: _Push Off_
Message-ID: <1994Jan27.115914.1@acad.drake.edu>
Lines: 303
Sender: news@dunix.drake.edu (USENET News System)
Nntp-Posting-Host: acad.drake.edu
Organization: Drake University, Des Moines, Iowa, USA
Date: Thu, 27 Jan 1994 17:59:14 GMT

                                _PUSH OFF_
                        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