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.
|
