Sections
Home
Hills
Infinite Hills
Tournaments
Software
Evolving
Optimizer
Community
Newsletter
Discussion
History
Sections
 
For Beginners
First Steps
FAQ
Guides
Lexicon
Benchmarks
For Beginners
> Home > The Corewar Newsletters > The '94 Warrior > Issue #12

August 18, 1994                                                      Issue #12
______________________________________________________________________________

_The_'94_Warrior_ is a monthly newsletter dedicated to supporting and
encouraging the game of Corewars.  This includes coverage of the more popular
"hills" (which allow users anywhere on the Internet to compete against other
users), and also by encouraging traffic in the rec.games.corewar newsgroup.

The FAQ (Frequently Asked Questions) for the rec.games.corewar newsgroup is
available through anonymous FTP to rtfm.mit.edu, as
/pub/usenet/news.answers/games/corewar-faq.Z.  There are also several
tutorials on the '88 and '94 (draft) standard available on
soda.csua.berkeley.edu that will greatly ease the process of becoming a
proficient "redcoder."  I would highly recommend referring to the FAQ if you
are curious about exactly what Corewars is, or if you are unfamiliar with any
of the terms used in this newsletter.
______________________________________________________________________________

CHANGES and CORRECTIONS:

For those of you using a Macintosh to develop your redcode wonders, a new
version of MacpMARS is available on soda.csua.berkeley.edu.  Look in the
"pub/corewar/incoming" directory for it.

At the request of several readers, I have added the '94 beginner hill to the
list of hills I will be covering in this and future issues of _The_'94_Warrior_.
______________________________________________________________________________

The ICWS '94 Draft Hill:

	Standard:       '94 Draft (with extensions)
       Core size:       8000 instructions
   Max processes:       8000 per program
	Duration:       After 80,000 cycles, a tie is declared.
Max entry length:       100 instructions

The current ICWS '94 Draft hill on "Pizza":
 #  %W/ %L/ %T                      Name               Author   Score     Age
 1  34/ 12/ 54                B-Panama X       Steven Morrell     156      28
 2  49/ 42/  9                  Agony II        Stefan Strack     156      22
 3  42/ 30/ 29                  Torch t8              P.Kline     154       1
 4  34/ 16/ 50          Silk Warrior 1.4        J.Pohjalainen     152      29
 5  36/ 26/ 39               Blue Funk 3       Steven Morrell     146      87
 6  44/ 44/ 13             Iron Gate 1.5       Wayne Sheppard     143     376
 7  41/ 39/ 20                      SJ-4            J.Layland     143      88
 8  35/ 28/ 37               Phoenix 1.1        J.Pohjalainen     141      24
 9  38/ 35/ 26               Stimpy v2.0     Brant D. Thomsen     141     128
10  30/ 20/ 49                      Test       Wayne Sheppard     141       7
11  30/ 21/ 49                      Aeka                T.Hsu     139      42
12  36/ 34/ 29        Homemade Ice Cream              P.Kline     138      64
13  37/ 36/ 27               IVScan 8000        James Layland     138      50
14  41/ 45/ 14         Betrave & Rubarbe           J.P.Laurin     138      36
15  32/ 27/ 41                    Sasami                T.Hsu     137     112
16  31/ 26/ 43                 Blue Funk       Steven Morrell     137     399
17  39/ 42/ 18              Keystone t33              P.Kline     136      18
18  30/ 25/ 45                 Cannonade              P.Kline     136     257
19  40/ 45/ 14                  Futility           M R Bremer     135      21
20  37/ 47/ 16              Pyramid v5.5     Michael Constant     128     177

The hill has been taken over by replicators.  Silk Warrior 1.4 and B-Panama X
are both putting up strong fights for the top position.  An ironic twist
resulting from this "paper invasion" is how poorly vampires do on the hill
as a result.  Christopher and Request have disappeared entirely from the hill,
and the last remaining vampire, Pyramid, has a very uncertain future.  (It was
in second place on this hill just a month ago.)  The addition of A-field
indirection has made it much easier to add anti-vampiric elements to programs 
-- and it looks like the Rock/Scissors/Paper analogy has gone out the window
because of it.  Perhaps now would be a good time to dust off your old scanners
and see how well they can do.

Among the older programs to disappear from the hill are NC 94 by Wayne
Shepherd at the age of 387, Lucky 3 by Stefan Strack at the age of 350+
(I forgot to record it exactly), and Christopher by Steven Morrell at the age
of 289.

Congratulations also to Steven Morrell on having his program Blue Funk reach
the age of 400.  (It should be at least that old when he reads this.)  I
believe Blue Funk is the first program to reach that age on any hill since the
original KotH hill.
______________________________________________________________________________

The ICWS '94 Draft Experimental Hill:

	Standard:       '94 Draft (with extensions)
       Core size:       55,440 instructions
   Max processes:       10,000 per program
	Duration:       After 500,000 cycles, a tie is declared.
Max entry length:       200 instructions

The current ICWS '94 Experimental (Big) hill on "Pizza":
 #  %W/ %L/ %T                      Name               Author   Score     Age
 1  48/ 33/ 20                  ivscan6b            J.Layland     162      29
 2  46/ 35/ 19             Request-55440     Brant D. Thomsen     158     165
 3  34/ 17/ 49                   Aleph 1              Jay Han     151      27
 4  33/ 15/ 52      Big Silk Warrior 1.0        J.Pohjalainen     151       7
 5  44/ 38/ 18              Pyramid v5.3     Michael Constant     150      56
 6  36/ 23/ 41             Variation G-1              Jay Han     148     129
 7  42/ 39/ 18                     Fscan              Jay Han     146      13
 8  41/ 37/ 23               Stimpy v2.0     Brant D. Thomsen     145      20
 9  40/ 39/ 21                   Aleph 0              Jay Han     142      28
10  38/ 39/ 23                Vanity IIx        Stefan Strack     138     120
11  33/ 28/ 39                  Lucky 13        Stefan Strack     138     171
12  43/ 48/ 10                      Test        Stefan Strack     138       1
13  30/ 23/ 47              NotSoBigImps        James Layland     137      25
14  42/ 48/ 10                 Rave B4.1        Stefan Strack     137     126
15  30/ 24/ 46 Der Zweite Blitzkrieg - 9      Mike Nonemacher     136     127
16  30/ 25/ 44                  Splash 1              Jay Han     136     130
17  29/ 24/ 47                 Blue Funk       Steven Morrell     135      19
18  35/ 39/ 26                      Lump            J.Layland     131     110
19  39/ 48/ 12                    Squint      Mike Nonemacher     130     103
20  25/ 24/ 51              Insight v1.0     Brant D. Thomsen     126       8

It looks like replicators may soon be taking over the "Big" hill, just like
they have the '94 draft hill; Big Silk Paper is close to the top of the hill.
It will be interesting to see if paper programs will remove Request and Pyramid
from their lofty positions, or if vampires will continue to be an effective
programming technique on the "Big" hill.
______________________________________________________________________________

The ICWS '88 Standard Hill:

	Standard:       '88
       Core size:       8000 instructions
   Max processes:       8000 per program
	Duration:       After 80,000 cycles, a tie is declared.
Max entry length:       100 instructions

The current Standard KotH hill on "Pizza":
 #  %W/ %L/ %T                      Name               Author   Score     Age
 1  36/ 22/ 42               Sphinx v5.1         W. Mintardjo     151       1
 2  33/ 16/ 51                      ttti        nandor sieben     149      71
 3  35/ 24/ 41     Der Zweite Blitzkrieg      Mike Nonemacher     146      49
 4  34/ 22/ 45                The Plauge            Anonymous     146       4
 5  39/ 32/ 29          Yop La Boum v2.1         P.E.M & E.C.     146      45
 6  33/ 22/ 45                 NC Killer            Anonymous     145       5
 7  31/ 20/ 49              Blue Funk 88       Steven Morrell     143      14
 8  40/ 37/ 23               Christopher       Steven Morrell     143      41
 9  32/ 21/ 47   CAPS KEY IS STUCK AGAIN       Steven Morrell     142      55
10  38/ 35/ 27              Keystone t21              P.Kline     142      87
11  40/ 40/ 19              Request v2.0     Brant D. Thomsen     141      68
12  32/ 23/ 45             Night Crawler       Wayne Sheppard     140      77
13  40/ 39/ 21                 Vanity II        Stefan Strack     140      89
14  41/ 44/ 15                     Armor             c w blue     139       3
15  42/ 44/ 14             Iron Gate 1.5       Wayne Sheppard     139      98
16  41/ 44/ 14              Dragon Spear             c w blue     139      67
17  39/ 43/ 18                     SJ-4a            J.Layland     136      48
18  29/ 23/ 48                Imprimis 6            Anonymous     135       6
19  36/ 39/ 25                   Unknown         Ned Flanders     134      10
20  36/ 39/ 25                Blue Blood         Ned Flanders     133       9

A few new programs have made things interesting on the '88 hill.  W. Mintardjo
resubmitted the latest version of his classic program Sphinx, and it jumped
right to the top of the hill.  Many other classic programs have also been
submitted anonymously, and three of them seem to have caught hold.  There
aren't many new faces on this hill, but the ordering has dramatically changed.
______________________________________________________________________________

The ICWS '94 Beginner Hill:

	Standard:       '94 Draft (with extensions)
       Core size:       8000 instructions
   Max processes:       8000 per program
	Duration:       After 80,000 cycles, a tie is declared.
Max entry length:       100 instructions

The current Beginner KotH hill on "Pizza":
 #  %W/ %L/ %T                      Name               Author   Score     Age
 1  61/  7/ 32         Rabid Dwarfs v1.0        Brian Zellner     215       3
 2  45/ 26/ 29    Rubarbe et mort-vivant           J.P.Laurin     163      11
 3  52/ 42/  6         Rubarbe et frappe           J.P.Laurin     163      13
 4  52/ 42/  6         Rubarbe et frappe           J.P.Laurin     161      12
 5  42/ 26/ 32              Slate, v0.3a     Bharat Mediratta     157      62
 6  40/ 32/ 28       Rubarbe et grafigne           J.P.Laurin     149      10
 7  45/ 43/ 12             Viewmaster4.0            Ryan Case     148     141
 8  43/ 39/ 17          Bloody Fang v2.0     Bharat Mediratta     147     118
 9  40/ 34/ 26             Count Zero #1         Marc Schefer     145       4
10  44/ 43/ 14            Viewmaster 4.2            Ryan Case     145     127
11  39/ 34/ 28          Bloody Fang v2.1     Bharat Mediratta     144       1
12  38/ 34/ 28          Bloody Fang v2.1     Bharat Mediratta     143       2
13  43/ 44/ 13           Viewmaster 4.2a            Ryan Case     143     128
14  40/ 40/ 20              Slate, v0.3b     Bharat Mediratta     141      61
15  38/ 35/ 27          Bloody Fang v2.1     Bharat Mediratta     140     109
16  43/ 50/  7                        It                 Hari     136     125
17  40/ 49/ 11                 Gross 1.8                Osric     132     120
18  40/ 48/ 12 Another Fanging Vampire 2          Matt Jaques     131     175
19  41/ 53/  5             Ecstacy (XTC)        Brant Thomsen     129       8
20  37/ 50/ 13                  Cat v2.0           Tim Scheer     124      82

As I have only been watching this hill for a couple of weeks, I can't really
give you a summary of what is happening on it.  However, I must admit to being
surprised at the number of programs that are constantly being submitted to
this hill.  The ages of the current programs don't reflect this, since most
of the submittals never make it onto the hill, but there is still a steady
stream of traffic.  (In this regard, the beginner's hill is very much the same
as the '88 hill covered above.)

If I could pass along some advice to the players currently on this hill, it
would be to use the ";kill" directive to get rid of some of the duplicate
copies of warriors on this hill.  This will usually cause your remaining 
warrior to do better, as programs it does well against are not penalized as
much, and it will make it easier for other programmers -- or the new program
you are developing -- to get onto the hill by freeing up some slots.
______________________________________________________________________________

HINTS and HELPS:

This month's hint has been supplied again by Ting-Yu Hsu.  For those of you
who have been dying of curiosity about exactly what a "vector-launched imp"
is, you are about to find out!


Vector Launched Imps

When I first got back into Corewars after a 3 year hiatus, I figured that it
would be trivial to place a warrior on the hill.  After all, when I first
played it, it took almost no thought to place a warrior on the top of the
Intel hill.  Boy, was I in for a shock.  I ran into a wall that all newcomers
to the hill quickly run into, the imp.

After going through a period of denial, I decided to get down and just
learn what the hell an imp was and how it worked.  In the process, I learned
one major thing.  I had NO desire to write binary launch code.  This meant
one of two things.  I could write a C program to write the redcode for me, or
I had to figure out a new way to launch an imp.  Since I was revulsed by the
idea of writing redcode via a C program, I took the latter (i.e., insane)
approach.

Here were the requirements I set for myself.
1. The imp launch code must be easily written and understandable.
2. The imp launch code must be as fast or almost as fast as a binary launch.
3. The imp launch code must be shorter than a binary launch.

What I came up with, after quite a bit of trial and error, was the vector
launched imp.  A vector launch boots an imp in O(2*N+C) cycles and is
O(log2(N-1)+(N/2)+1) in length.  The first example below is a "perfect"
vector launch, i.e., it is exactly as fast as a binary launch and yet it is
smaller and easier to read.  The second example shows an alternate method
of vector launching a smaller imp.
------------------------------------------------------------------------------
;redcode-94
;name   Vector
;author T.Hsu

imp_sz  equ     2667

boot    spl     1      ,#0
	spl     1      ,#0
	spl     <0     ,#vector+1
	djn.a   @vector,#0

imp     mov.i   #0,imp_sz

	jmp     imp+imp_sz*7,imp+imp_sz*6   ; normally this is in a for/rof
	jmp     imp+imp_sz*5,imp+imp_sz*4   ; loop, but I wanted to make the
	jmp     imp+imp_sz*3,imp+imp_sz*2   ; order of the vectors obvious
vector  jmp     imp+imp_sz  ,imp

	end     boot
------------------------------------------------------------------------------
;redcode-94
;name   Single Vector
;author T.Hsu

imp_sz  equ     2667

	dat     0      ,#imp+imp_sz*3
boot    spl     1      ,#imp+imp_sz*2
	spl     1      ,#imp+imp_sz
vector  djn.a   @vector,#imp

imp     mov.i   #0,imp_sz

	end     boot
------------------------------------------------------------------------------
	:
vector  djn.a   @vector,#imp
	:

Shown above is the crucial instruction in making the vector launch work.
There are a few peculiarities about this instruction.  First off, you cannot
directly follow this instruction with the vector table.  This is because the
"djn.a" will evaluate to zero, and thus no jump would occur.  Second, you
should notice that the B-field of this instruction evaluates to zero as part
of the instruction.  Therefore, you can put it to good use as a pointer (in
the second example above, I used it as the first imp vector).  And third,
this is a good example of the difference between in-memory evaluation and
in-register evaluation.

See how the jump point is stored into a register before the decrement and
test occurs.  Thus, our jump point is not affected by the decrement and test.
Before the in-memory/in-register clarification by the '94 rules, it would
have been ambiguous whether a simulator would decrement/test/load_jump_pt/jump
or load_jump_pt/decrement/test/jump.  Obviously the latter is the correct
interpretation as stated by the '94 rules.

One final thing you should notice is that non-power of 2 imps will waste
cycles while launching and that non-multiple of 2 imps are a bit tricky to
put together.  This is because the "spl" statement is basically optimized
for power of 2 process generation.  Below are side-by-side examples of the
"spl" instructions necessary to create a 6 point launch and a 7 point launch.

    ; 6 point imp           |   ; 7 point imp
	:                   |       :
	spl     1     ,#0   |       spl     1     ,#0
	mov.i   -1    ,#0   |       spl     1     ,#0
	spl     <0    ,#vec |   mm  mov.i   2     ,#0
	djn.a   @vec-1,#0   |       djn.a   @vec-1,#0
	:                   |       spl     <0    ,#vec-mm
	:                   |       :

The 6 point launch wastes 1 cycle performing the "mov" instruction and the
7 point launch wastes both a cycle and an instruction.  This basically
means that you should try to launch power of 2 spirals whenever possible, and
if that is not possible, you should try to minimize the number of "mov"
instructions necessary during the process creation.  Also notice that the 7
point launch requires a few modifications in the vector table since the
B-field is accessed twice before an A-field is accessed.

Although I happen to be partial to "djn.a", it is not the only construct
available to someone writing vector launch code.  The availability of A-field
indirection allows a whole host of other possibilities which I haven't even
begun to explore.

Below is Aeka, the first warrior I created using a vector launched imp.
The stone and the boot code associated with the stone were taken almost
directly from Cannonade by P.Kline.  I have changed these constants, but the
changes are currently not on koth, so the point is moot.

Aeka uses quite a few tricks within her code, but I'm not going to explain
them here, since the main focus is on the vector launch code.  As for some
of the weird constants, well, Aeka tends to kill off a few of her imps during
her own core clear, so I had to get really creative in the constants in order
to minimize this problem.

Oh yeah, Aeka is an alien princess (who, of course, looks perfectly human)
in the Japanese anime "Tenchi Muyo".  Just in case you were wondering where
the name comes from.

T.Hsu
ting@teloquent.com
------------------------------------------------------------------------------
;redcode-94
;name     Aeka
;kill     Aeka
;author   T.Hsu
;strategy Suicidal stone & vector launched, gate busting imp spiral
;assert   CORESIZE == 8000 && MAXLENGTH >= 100
;macro
;-----------------------------------------------------------------------------
;  1.0  Original based on Cannonade by P.Kline
;  1.1  Erase pointer to stone, better decoy, use immediate mode more
;  1.2  Reposition imps so that they don't cause djn.a to fall through
;  1.3  Use a decoy that looks like a pointer, put boot ptrs in unused fields
;  1.4  Use A-field indirection to shorten imp launch code
;  1.5  Use "spl <0,#vector" instead of "djn.a *(vector-1),#0"
;       Split before finishing to boot the gate busting imps, better constants
;  1.6  Back to "djn.a *(vec-1),#0" to be less vulnerable to quick-scanners
;       Move around decoy code & launch vectors, launch normal imps first
;  1.7  Back to "spl <0,#vec" to save on space, no decoy
;       More redundancy in for the imps
;  1.8  Compress boot code for the gate busting imp
;  1.9  Made B-field of "djn.a" do double duty as a boot pointer
;       Made dec_offset help gate against imps during core-clear
;  2.0  Better use of for/rof in the vector launch
;
;  Vulnerabilities
;  -- hyper-perfect gates (gate busting imps have a tough time with these)
;  -- anti-imp paper (the stone is not designed to stun/kill paper)
;  -- suicidal stone (if gate busting imp dies, we don't want stone to die)
;  -- quick scanners (due to long boot time and use of "spl <0,#vec")

imp_sz01    equ     2668
imp_sz02    equ     imp_sz01
imp_sz03    equ     2667
imp_prc01   equ     8
imp_prc02   equ     imp_prc01
imp_prc03   equ     10
imp_off01   equ     -2
imp_off02   equ     0
imp_off03   equ     -7
imp_first   equ     (start-1834)+2*imp_sz02
stone_inc   equ     190
stone_offst equ     701
dec_offst   equ     (imp_sz03*2)-stone_inc

	    org     start
;-----------------------------------------------------------------------------
;  Boot strap

start       mov.i   imp_2,imp_first+imp_off02+2 ; gate busting imp
	    mov.i   imp_3,imp_first+imp_off03   ; normal imp
	    mov.i   <stone_src,@stone_dst2      ; stone
	    mov.i   <stone_src,<stone_dst       ;   put B-field of "djn.a"
	    mov.i   <stone_src,<stone_dst       ;   to use as the stone_src
	    mov.i   <stone_src,<stone_dst
	    spl     @stone_dst,<dec_offst
	    mov.i   <stone_src,<stone_dst
;-----------------------------------------------------------------------------
;  Vector launch the imps

imp_split   spl     1,<dec_offst                ; 26 processes
	    spl     1,<dec_offst
	    mov.i   imp_2,<start                ; finish booting imp
stone_dst   mov.i   -2,#stone_end+1-stone_offst     ;\ notice how these ptrs
stone_dst2  mov.i   -1,#stone_end+1-(stone_offst-1) ;/ are conviently erased
	    spl     <0,#imp_vector               ;\ decrement self to launch
stone_src   djn.a   @(imp_vector-1),#stone_end+1 ;/ imps, B-fld before A-fld
;-----------------------------------------------------------------------------
;  Self splitting stone and core clear

stone       mov.i   <stone_spl+5+stone_inc*800,stone_spl
stone_spl   spl     stone,<dec_offst+stone
	    add.f   stone_end+1,stone
	    djn.f   stone_spl,<dec_offst+stone
stone_end   mov.i   stone_inc,<-stone_inc
;-----------------------------------------------------------------------------
;  Decoy

cnt         for     65
	    dat     0,0
	    rof
;-----------------------------------------------------------------------------
;  Launch vectors

imp_2       mov.i   #(imp_sz02/2),imp_sz02
imp_3       mov.i   #(imp_sz03/2),imp_sz03

imp_A_fld   equ     imp_first+(imp_prc&who+1-2*cnt)*imp_sz&who+imp_off&who
imp_B_fld   equ     imp_first+(imp_prc&who+0-2*cnt)*imp_sz&who+imp_off&who
who         for     3
cnt         for     (imp_prc&who)/2
	    jmp     imp_A_fld,imp_B_fld
	    rof
	    rof
imp_vector
	    end


EDITORS NOTE:

Vector-launched imp-spirals can be cause a significant reduction in the
number of lines your imp-launching code will take.  A 16-point imp-spiral
vector launch code requires less than half the number of lines required for
the corresponding binary launch code, and a 64-point imp-spiral requires less
than a third the number that a binary launch would need.  With quick scanners
being so common on the hill, a few less lines can make a big difference.

However, there still are reasons that binary imp-spiral launch code will not
be disappearing soon.  Probably the most obvious is that the '88 standard
is still going strong.  Binary launches are also more flexible, as they allow
the programmer can choose later times to send processes to other parts of the
program (such as stones).  And, of course, one final advantage of binary
imp-spiral launches is that they are impervious to DJN.B streams.

Thanks again to Ting-Yu Hsu for sharing a hint which I am certain will have a
significant influence on the hill in the future.
______________________________________________________________________________

Looking to the Future:

This newsletter is now being published monthly.  As always, your comments,
suggestions, criticisms, and submissions are encouraged and appreciated.
2002-2005 corewar.info. Logo C. Schmidt