Issue 84 08 December, 2002
_______________________________________________________________________________
Core Warrior is a newsletter promoting the game of corewar. Emphasis is
placed on the most active hills - currently the '94 no-pspace and '94 draft
hills. Coverage will follow wherever the action is. If you haven't a clue
what I'm talking about then check out these five-star Internet locals for
more information:
FAQs are available from:
http://www.koth.org/corewar-faq.html
http://homepages.paradise.net.nz/~anton/cw/corewar-faq.html
Web pages are at:
http://www.koth.org/ ;KOTH
http://www.ecst.csuchico.edu/~pizza/koth ;Pizza (down)
http://para.inria.fr/~doligez/corewar ;Planar
http://www.ociw.edu/~birk/corewar ;C.Birk
http://de.geocities.com/fizmo_master ;Fizmo
Newbies should check the above pages for the FAQs, language specification,
guides, and tutorials. Post questions to rec.games.corewar. All new players
are infinitely welcome!
_______________________________________________________________________________
Greetings...
The 10 weeks since last issue have been an interesting time for Core War.
The '94 draft hill has return to Koth and the hills have been buzzing with
activity.
A good number of interesting warriors have been published, including Jinx,
CrazyShot 2, Wallpaper, The Pendragon, pre75-z47a, Willow, Defensive,
Silking, Revenge of the Papers, Help I'm Scared, Velvet Glove and Twinshot,
all of which enter the top 100 of the 94nop Koenigstuhl hill. In addition,
Pihlaja shared an Optima Number finder, written in Redcode.
This issue, prepare yourself for an inspiring Core War journey, thanks to
our three contributors:
* 'RotF Qscan' by M Joonas Pihlaja
* 'Airbag: Exposed' by Lukasz Grabun
* 'Digitalis 2002' by Christian Schmidt
-- John Metcalf
______________________________________________________________________________
Current Status of the KOTH.ORG '94 No Pspace Hill:
# %W/ %L/ %T Name Author Score Age
1 35/ 21/ 44 Son of Vain Oversby/Pihlaja 149.0 1188
2 35/ 24/ 41 Reepicheep Grabun/Metcalf 146.8 419
3 32/ 17/ 52 Return of the Pendragon Christian Schmidt 146.2 25
4 35/ 24/ 41 Dark Lowlands Roy van Rijn 145.7 16
5 33/ 21/ 46 Positive Knife Ken Espiritu 145.1 262
6 46/ 48/ 7 Willow revised John Metcalf 144.0 76
7 31/ 20/ 49 Firestorm John Metcalf 142.3 224
8 41/ 41/ 18 Herbal Avenger Michal Janeczek 142.2 37
9 37/ 33/ 30 Digitalis 2002 Christian Schmidt 141.4 55
10 32/ 22/ 46 Revenge of the Papers Fizmo/Roy 141.1 226
11 25/ 10/ 65 Decoy Signal Ben Ford 140.9 115
12 34/ 27/ 40 The Stormkeeper Christian Schmidt 140.6 296
13 39/ 38/ 23 Return of Vanquisher Test Lukasz Grabun 139.5 6
14 28/ 17/ 56 Blowrag Metcalf/Schmidt 138.5 153
15 41/ 46/ 13 Blade Fizmo 135.8 505
16 43/ 51/ 6 Claw Fizmo 135.5 156
17 31/ 26/ 43 golden thread Simon Wainwright 135.1 39
18 40/ 46/ 14 Vamp test 2 John Metcalf 135.1 1
19 39/ 43/ 18 Hazy Lazy ... reborn Steve Gunnell 134.2 273
20 39/ 44/ 18 Morbid Dread IV Philip Thorne 133.2 2
Since last issue there have been 306 successful challenges. For the third
consecutive issue the hill loses it's oldest warrior. No-one can claim a
pattern is forming however, as it is unlikely Son of Vain will be pushed off
before next issue. Son of Vain becomes the oldest warrior ever to be Koth.
Koth report: Since last issue Reepicheep has been the most frequent King
(#1 after 110 successful challenges), followed by Son of Vain (after 40),
Hazy Lazy ... reborn (33), Blade (25), Digitalis 2002 (17), Geist v0.1 (13)
and Claw (11).
The warriors which perished included Uninvited (age 1130), Vanquisher (469),
Hazy Lazy ... again (350), Candy (276), Oneshot Test (266), Glenstorm (219),
SilKing (214), CrazyShot 2 (211), Wallpaper (177), Defensive (142), Willow
(135), Paperazor (107), GenerationX (104) and finally Golden Thread (102).
_______________________________________________________________________________
The '94 No Pspace Hall of Fame: * indicates the warrior is still active.
Pos Name Author Age Strategy
1 Blacken Ian Oversby 1363 Q^2 -> Stone/imp
2 nPaper II Paul-V Khuong 1270 MiniQ^3 -> Paper
3 Son of Vain Oversby/Pihlaja 1188 * Q^4 -> Stone/imp
4 Uninvited John Metcalf 1130 MiniQ^3 -> Stone/imp
5 Behemot Michal Janeczek 1078 MiniQ^3 -> Bomber
6 Olivia Ben Ford 886 Q^4 -> Stone/imp
7 Keyser Soze Anton Marsden 823 Qscan -> Bomber/paper/imp
8 Quicksilver Michal Janeczek 789 Q^4 -> Stone/imp
9 Eraser II Ken Espiritu 781 Scanner
10 Inky Ian Oversby 736 Q^4 -> Paper/stone
11 Jinx Christian Schmidt 662 Q^3 -> Scanner
12 Jade Ben Ford 600 Q^4 -> Stone/imp
13 Blade Fizmo 505 * Qscan -> Scanner
14 G3-b David Moore 503 Twoshot
15 Vanquisher Lukasz Grabun 469 Q^4 -> Bomber
16 Revival Fire P.Kline 468 Bomber
17 The Phantom Menace Anton Marsden 465 Qscan -> Paper/imp
18 Boys are Back in Town Philip Kendall 441 Scanner
= Zooom... John Metcalf 441 Scanner
20 Reepicheep Grabun/Metcalf 419 * Q^4 -> Paper/stone
21 Qtest Christian Schmidt 394 Q^3 -> Paper
22 Stalker P.Kline 393 Scanner
23 Hazy Lazy ... again Steve Gunnell 350 Scanner
24 Vain Ian Oversby 330 Q^2 -> Stone/imp
25 Omnibus John Metcalf 327 Q^2 -> Stone/imp
Two new entries, Blade and Reepicheep. Uninvited, Vanquisher and Hazy Lazy
meet their final resting place.
_______________________________________________________________________________
Current Status of the KOTH.ORG '94 Draft Hill:
# %W/ %L/ %T Name Author Score Age
1 30/ 13/ 57 Blowrag Metcalf/Schmidt 148.0 87
2 44/ 40/ 15 Herbal Avenger Michal Janeczek 147.7 43
3 44/ 41/ 15 Bustling Spirit Christian Schmidt 147.6 1
4 37/ 27/ 36 Dark Lowlands Roy van Rijn 147.6 36
5 31/ 14/ 55 Incredible! John Metcalf 147.6 26
6 36/ 24/ 41 Reepicheep Grabun/Metcalf 147.5 160
7 34/ 22/ 44 Son of Vain Oversby/Pihlaja 146.8 131
8 39/ 33/ 28 Cyanide Excuse Dave Hillis 144.8 33
9 43/ 41/ 16 Combatra David Moore 144.4 32
10 35/ 27/ 37 Uninvited John Metcalf 143.9 150
11 37/ 31/ 31 Digitalis 2002 Christian Schmidt 143.5 71
12 40/ 39/ 21 Help...I'm Scared Roy van Rijn 141.2 79
13 31/ 22/ 46 Revenge of the Papers Fizmo/Roy 140.9 138
14 41/ 42/ 17 CrazyShot 2 Christian Schmidt 140.5 143
15 32/ 25/ 43 Paperazor Christian Schmidt 140.3 104
16 40/ 40/ 20 Mantrap Arcade Dave Hillis 139.9 9
17 38/ 39/ 23 Joyful Maw Dave Hillis 138.3 97
18 31/ 27/ 42 Wallpaper Christian Schmidt 135.4 142
19 36/ 37/ 27 Mad Christian Schmidt 135.2 119
20 40/ 47/ 13 Cupric siren Dave Hillis 133.9 19
Time to blow the dust from those old p-space routines; the 94 draft hill has
returned after a long absence. Already, a small number of handshakers have
been spotted - look for the bright green blips in the huge array.
Koth report: Since the hill opened for business, Reepicheep has been the
most frequent King (#1 after 81 successful challenges), followed by Pattel's
Virus (after 26), Son of Vain (22) and Herbal Avenger (19).
Just two warriors of notable age have left the hill, Self-Modifying Code
(age 132), and Shapeshifter (107)...
_______________________________________________________________________________
Spring / Summer 2002 Corewar Tournament - Round 4 Results:
A total of 13 authors and 23 warriors take part in the restricted length
round, competing using '94 draft redcode, maximum length 50. Although each
author can enter two warriors as usual, only one is permitted to make use
of p-space.
For the second time Ben Ford takes first place with a oneshot. This time he
uses Geist v0.1, which has recently been King of the '94nop hill. Holding a
close second place is Michal Janeczek with a p-switcher: paper, scissors and
stone.
Gunnell's procoptodon comes 4th, a scanner based on Hazy Lazy, while 5th is
claimed by van Rijn with Neanderthaler (oneshot). Marsupial Lion (scanner)
takes 6th for Schmidt, followed by p-switchers from Philip Thorne (7th) and
Dave Hillis (9th).
# %Won Lost Tied Name Author Score %
1 55.2 33.3 11.5 Geist v0.1 Ben Ford 177.02 100.0
2 51.8 29.0 19.3 Microvenator Michal Janeczek 174.55 98.6
3 53.7 33.1 13.1 Herbal Avenger Michal Janeczek 174.26 98.4
4 52.3 34.3 13.5 procoptodon Steve Gunnell 170.23 96.2
5 49.5 34.6 15.9 Neanderthaler Roy van Rijn 164.30 92.8
6 50.8 41.1 8.1 The Marsupial Lion Christian Schmidt 160.56 90.7
7 47.1 36.8 16.1 Confused Moth Philip Thorne 157.48 89.0
8 48.1 40.2 11.7 Dire Wolf Philip Thorne 155.99 88.1
9 36.4 17.5 46.2 Bear Dog Dave Hillis 155.24 87.7
10 33.3 13.8 52.9 Blue Pike Roy van Rijn 152.83 86.3
11 33.4 16.5 50.1 Cheep! Half-Off! Ben Ford 150.33 84.9
12 27.7 15.5 56.9 thylacine Simon Wainwright 139.86 79.0
13 25.7 18.0 56.3 The Demon Duck of Doom Christian Schmidt 133.44 75.4
14 27.0 24.2 48.8 Muttaburrasaurus Steve Gunnell 129.75 73.3
15 19.7 14.2 66.1 Dodo Lukasz Grabun 125.16 70.7
16 16.9 18.3 64.8 minotaur Simon Wainwright 115.49 65.2
17 17.1 21.7 61.2 Hallucinogenia Dave Hillis 112.50 63.6
18 15.7 24.8 59.5 Little Girl Sheep 106.53 60.2
19 17.6 28.9 53.5 Smart Protoceratops German Labarga 106.26 60.0
20 13.0 35.4 51.6 Brontosaurus German Labarga 90.66 51.2
21 2.6 42.9 54.4 Trinity Darek L. 62.35 35.2
22 7.2 66.6 26.2 Sea Mink bvowk 47.77 27.0
23 7.2 68.1 24.7 Coelacanth bvowk 46.34 26.2
The most popular strategy is the p-switcher, of which there are six. Four
of these contain two components (in ranks 7, 9, 14, 19) while the remainder
have three (2, 15). Also, there are three each of oneshots (1, 5, 8),
scanners (3, 4, 6), paper/stone (10, 11, 13) and evolved (17, 22, 23) -
two papers (16, 18) - and just one each of stone/imp (12), bomber (20) and
paper/imp (21).
# Competitor Tiny BigLP 88Win Len50 Total
1 Michal Janeczek 93.3 100.0 100.0 98.6 391.9
2 Dave Hillis 99.9 84.3 87.3 87.7 359.2
3 Steve Gunnell 91.0 85.0 82.4 96.2 354.6
4 Ben Ford 100.0 74.4 75.1 100.0 349.5
5 Simon Wainwright 79.1 71.5 89.1 79.0 318.7
6 Philip Thorne 75.5 68.0 72.7 89.0 305.2
7 Lukasz Grabun 81.3 . 67.6 70.7 219.6
8 Robert Macrae 89.7 61.0 . . 150.7
9 Winston Featherly-Bean 72.9 47.3 . . 120.2
10 David Moore . 51.4 63.6 . 115.0
11 Roy Van Rijn . . . 92.8 92.8
12 Christian Schmidt . . . 90.7 90.7
13 Martin Ankerl 88.2 . . . 88.2
14 Ken Espiritu . . 86.3 . 86.3
15 Leonardo H. Liporati 84.3 . . . 84.3
16 mushroommaker 71.3 . . . 71.3
17 Arek Paterek 66.0 . . . 66.0
18 Paul Drake 61.9 . . . 61.9
19 Sheep . . . 60.2 60.2
20 German Labarga . . . 60.0 60.0
21 Compudemon 53.9 . . . 53.9
22 Darek L. . . . 35.2 35.2
23 bvowk . . . 27.0 27.0
_______________________________________________________________________________
The Hint - RotF's Qscan by M Joonas Pihlaja
Shortly after Leonardo Humberto and John Metcalf published their Q^3 qscan
decoder which uses multiplication, David Moore pushed the cutting edge of
qscan decoders by publishing Return of the Fugitive. Moore's decoder has
only three cycles decoding overhead, the minimum possible, and a much
smaller footprint than previous qscans.
The basic idea in the Humberto/Metcalf qscan is to compute the scanned
location by an expression ptr + FAC*[table entry #1]*[table entry #2] using
this kind of decoder:
; decoder
slow mul.b tab, ptr ;\ multiply FACTOR in ptr by
fast mul.ab tab, @slow ;/ one or two table entries.
decide sne dat0, @ptr ;\ choose between A- or B-field
add #SEP, ptr ;/ locations. dat0 = empty core.
...
ptr: mov bmb, FAC ; the bomb pointer and factor FAC
...
; decoding table
dat 15, 10
tab: dat 7, 4
dat 13, 11
This decoder has four cycles of decoding overhead, compared to five in Q^2
qscans like Probe. The scans are SEQ scans, similar to Probe, that scan
via their A- and B-fields two locations that are separated by (a constant)
SEP cells
seq ptr + FAC*K1*K2*SEP, ptr + FAC*K1*K2*SEP + SEP
where K1 and K2 are (possibly mutated) table entries. When location LOC =
ptr + FAC*K1*K2*SEP is decoded, then the sne/add #SEP,ptr needs to choose
between LOC and LOC+SEP. After a scan finds something, it mutates either
the entries in the decoding table, or the A- and B-fields of the 'fast' and
'slow' lines to multiply the factor FAC by the right constant(s).
The main improvement of the Humberto/Metcalf qscan over Probe's Q^2 is that
it achieves one cycle faster decoding using the same number (three) of
cells dedicated to the decoding table. Note that the same response time is
possible using a Q^2 by using multiple tables, but it costs (to the best of
my knowledge) at least one or two extra cells dedicated to decoding tables,
depending on the number of scans required --- see Aggression is a Switch
for the example.
* Faster dada, Faster!
----------------------
The decoder in RotF's qscan achieves three cycle decoding overhead by using
indirection to choose the multiplier from several multiplier tables. It
has this conceptual form:
; Decoder (1) (label dat0 points to empty core)
decode mul.b *tabptrs, ptr ; Multiply ptr by a table entry.
decide sne dat0, @ptr ; Choose A- or B-scan.
add.? ???, ptr ; ??? = separation between scans.
...
ptr mov bmb, FAC ; bomb pointer and factor
...
dat tab1, ? ; \ These are pointers to the decoding
tabptrs dat tab2, ? ; } tables
dat tab3, ? ; /
dat ?, A1 ; \ Multipliers A1, A2
tab1 dat ?, A2 ; /
dat ?, B1 ; \
tab2 dat ?, B2 ; } Multipliers B1, B2, B3
dat ?, B3 ; /
tab3 dat ?, C2 ; Multiplier C2
where `?' fields aren't referenced (this allows embedding the decoding
tables into unused A- and B- fields of a warrior). The separation between
A- and B-scans is actually variable, picked from a table of possible
separations, and is marked with `???' in the decoder above. Ignore it for
now. When a scan finds something it mutates the A-field of `decode' to
choose a specific decoding table from `tab1', `tab2', or `tab3', and
(possibly) the `tabptrs' table to choose a specific element from the table
(say between A1 and A2 of `tab1').
The first size optimisation in RotF is to overlap the decoder code and the
`tabptrs' table as follows:
; Decoder (2)
decode mul.b *2, ptr ; \
decide sne tab1, @ptr ; \} Decoder.
add.? tab2, ptr ; /} A-fields are pointers to
? tab3, ? ; / decoding tables.
Stop! Now the A-field of the SNE line doesn't point to empty core anymore as
required by decoder (1). The trick in RotF is to use indirection in the SNE
line:
...
sne *tab1, @ptr ; A-field of `tab1' entries point to
add.? tab2, ptr ; empty core.
...
and force the tab1 entries to have the form
dat dat0, A1 ; dat0 points to empty core.
tab1 dat dat0, A2
Now when the sne instruction checks the decoded location it uses empty core
at tab1+dat0 for the comparison. As always, there's a downside. The
restriction that the A-fields of the `tab1' entries point to empty core all
but precludes embedding the table into unused B-fields of other code. So
instead RotF uses a-predecrement:
...
sne {tab1, @ptr ; A-field of `tab1' entries point
add.? tab2, ptr ; to a cell that is preceded by empty
... ; core.
tab1 dat foo, A1 ; \ foo and bar must be preceded
dat bar, A2 ; / by empty core.
which is much easier to arrange. There's no reason why the entries in
`tab2' shouldn't be used themselves as the separation between A- and
B-scans, so the ADD.? instruction becomes ADD.B. With these modifications
the other tables `tab2' and `tab3' may usually be at least partially
embedded into other code without too much trouble, as in RotF or Son of
Vain.
* The scans
-----------
From the decoder in (2) with ADD.B we see that the separations between A-
and B-scans are determined by the entries in the `tab2' table, because the
ADD.B instruction's A-field points to the table `tab2':
; Decoder (2) (repeated)
decode mul.b *2, ptr ; \
decide sne tab1, ptr ; \} Decoder.
add.b tab2, @ptr ; /} A-fields are pointers to
? tab3, ? ; / decoding tables.
This means the scanning phase must scan location pairs of the form
ptr + K*FAC, ptr + K*FAC + B_i
where K is a multiplier and B_i is related to the entries B1, B2, B3 in
tab2. This also forces the `tab2' entries B1, B2, B3 to be fairly large so
that the A- and B-scan separation isn't too small. You may wonder why
immediate mode couldn't be used in the ADD line like so:
decode mul.b *2, ptr
decide sne tab1, ptr
add #tab2, ptr
? tab3, ptr
There's no show-stopping reason, but consider the maximum distance between
the ADD line and `tab2' in a warrior --- it is bounded from above by the
MAXLENGTH of a warrior, so the separation between scans would be bounded by
MAXLENGTH too. [Sidenote: We'll see later that the largest minimum
separation is bounded by MAXLENGTH in any case, but at least then the
separation is that small only for one pair of scans, rather than for all of
them when # mode is used.]
When the scans are only SEQ scans, then it turns out that there are only a
handful of possible locations that can be distinguished by the decoder.
Namely, if we label the decoder (2) with labels `q0' for the pointer to the
table of multiplier tables at label `q1' like so
; Decoder (2) (with labels q0 and q1)
decode
q0 mul.b *q1, ptr ; A-field chooses table.
decide sne tab1, ptr ; \
q1 add.b tab2, @ptr ; } A-fields are pointers to
? tab3, ? ; / decoding tables.
then the possible locations that may be decoded using SEQ scans only are:
qscan seq ptr + FAC, ptr + FAC + B2
jmp decide ; no decode.
; q0 mutations
seq ptr + FAC * C2, ptr + FAC * C2 + B2
jmp decode , }q0 ; make decoder use C2 of tab3
seq ptr + FAC * A2, ptr + FAC * A2 + B2
jmp decode , {q0 ; make decoder use A2 of tab1
seq ptr + FAC * A1, ptr + FAC * A1 + B2
djn.a decode , {q0 ; make decoder use A1 of tab1
; q1 mutations
seq ptr + FAC * B1, ptr + FAC * B1 + B1
jmp decode , {q1 ; make decoder use B1 of tab2
seq ptr + FAC * (B1-1),ptr + FAC * (B1-1) + (B1-1)
djn decode , {q1 ; make decoder use B1-1 of tab2
seq ptr + FAC * B3, ptr + FAC * B3 + B3
jmp decode , }q1 ; make decoder use B3 of tab2
; no mutations
seq ptr + FAC * B2, ptr + FAC * B2 + B2 ; decoder uses B2 of tab2.
jmp decode
That's a pathetically short qscan. Moore's insight was to use SNE/SEQ
scanning pairs where the SEQ instruction itself reprograms the decoder to
decode the correct location in a novel way. Namely, one operand of the SEQ
instruction mutates one of the decoding tables by scanning indirectly via
the table entry itself! OK, that wasn't very understandable, so here's an
example. First we have, say, this scan:
seq ptr + FAC*C2, ptr + FAC*C2 + B2
jmp decode, }q0 ; '}' makes decoder use C2 in tab3
When the scan finds something the decoder decodes the location ptr + FAC*C2
and uses B2 as the scan separation. Now, consider this pair of SNE/SEQ
scans:
sne ptr + FAC*C2, ptr + FAC*C2 + B2
seq <tab3, ptr + FAC*(C2-1) + B2
jmp decode, }q0 ; make decoder use tab3
Now if the SNE scan finds something the decoder works like before and
decodes the location ptr + FAC*C2 just as it should, but if it doesn't it
falls through to the SEQ scan. The SEQ instruction in turn scans the
locations (note the predecrement in <tab3)
tab3 + C2-1 and
ptr + FAC*(C2-1) + B2
and _mutates_the_decoding_tables_ by decrementing the C2 entry of `tab3'.
So if anything was found at those locations, the decoder decodes the
location
ptr + FAC * (C2-1)
The decoded location is evident from the form of the decoder (2), which
will look like this if something is found:
; This A-field has been incremented to use `tab3'
decode ;/
q0 mul.b *3, ptr ; -- A-field refers to the B-field
decide sne {tab1, @ptr ; | of `tab3' which is = C2.
add tab2, ptr ; |
? tab3, ? ; <-
In any case, for decoding to work correctly, the relative locations of
`ptr' and `tab3' must satisfy the relation
ptr + FAC * (C2-1) = tab3 + C2-1
If we consider FAC and the relative distance tab3-ptr of `tab3' from `ptr'
to be known, we can solve for C2 as follows:
ptr + FAC * (C2-1) = tab3 + C2-1
FAC * (C2-1) - (C2-1) = tab3 - ptr
(FAC - 1) * (C2-1) = tab3 - ptr
C2 = 1 + (tab3 - ptr) * (FAC-1)^{-1}
where the division by (FAC-1) is done by computing its inverse modulo
CORESIZE. The division forces (FAC-1) to be invertible modulo CORESIZE,
that is, to be a mod-1 number. The same trick can be applied to most of
the other scans to obtain i) smaller scanning code consisting of SNE/SEQ
pairs, and ii) similar equations for all the decoding table entries A1, A2,
B1, B2, B3, C2 in terms of the factor FAC and the relative positions of the
decoding tables from `ptr'. Note especially that the scanned locations may
change dramatically when the decoding tables or `ptr' are moved inside the
warrior due to the multiplication of (tab-ptr) by (FAC-1)'s inverse modulo
CORESIZE.
* The attack
------------
In decoder (2) (repeated below) there needs to be an instruction with
a-field pointer to `tab3' denoted by ?:
decode mul.b *2, ptr ; \
decide sne tab1, ptr ; \} Decoder.
add.b tab2, @ptr ; /} A-fields are pointers to
? tab3, ? ; / decoding tables.
How to best use this instruction with forced A-field in the attack is
somewhat interesting. RotF makes the `tab3' line a part of a two-line
brainwashing payload used in its qscan attack, Son of Vain uses a .5c qscan
attack with `tab3' as its qscan bomb, and the example code below uses
`tab3' to initialise a .6c bombing Torch-like attack loop.
* The example code
------------------
The code is structured similarly to the qscan in Son of Vain and RotF, but
there's a significant difference: The "decoding factor," that's named FAC
in the explanation above, is made a derived constant from an independent
parameter FACTOR = (FAC+1)^{-1} (mod CORESIZE). Inverses (mod CORESIZE) of
an invertable number X are computed via Euler's totient function by raising
X to 3199 (mod CORESIZE) using this macro:
; Set register `y' to the inverse mod 8000 of register `x'.
M equ 8000
invert equ (a=x*x%M)+(a=a*x%M)+(a=a*a%M)+(a=a*x%M)+(b=a*a%M)+(b=b*b%M)\
+(b=b*b%M)+(c=b*b%M)+(c=c*b%M)+(d=c*c%M)+(d=d*d%M)+(d=d*d%M)\
+(d=d*c%M)+(d=d*d%M)+(d=d*c%M)+(y=a*d%M)
The macro `invert' may fail on (very) old versions of pMARS due to
overflowing the macro expansion buffer. A more serious concern for
portability is that line continuation using `\' isn't supported by the
version of pMARS used at KOTH.org, or possibly the KOTH.org scripts (I'm
not sure which fails). I've succesfully tested the qscan at KOTH.org by
unwrapping the continued lines into one line.
Incidentally, I discovered an easy way to test a qscan code while writing
this: First modify your code to either die or do nothing when booting.
Second, use an opponent like 'jmp 0,0' and run all permutations like so
$ pmars-server -b -P qscan.red jmp.red -c 200
RotF qscan by M Joonas Pihlaja scores 168
Unknown by Anonymous scores 46638
Results: 56 15546 0
If the qscan code wins exactly twice the number of locations it scans, then all
locations are decoded and attacked properly.
;redcode-94nop
;name RotF qscan
;author M Joonas Pihlaja
;strategy Cut-and-paste version of Moore's qscan in Return of the Fugitive
;strategy in Return of the Fugitive for CW.
;assert CORESIZE==8000
load0 z for 0
rof
boot jmp 0
dat0 equ (load0-123)
;--------------------------------------------------------------------------
; An expression that sets register y to the inverse mod 8000 of register x.
; Uses scratch registers a, b, c, d.
M equ 8000
invert equ (a=x*x%M)+(a=a*x%M)+(a=a*a%M)+(a=a*x%M)+(b=a*a%M)+(b=b*b%M)\
+(b=b*b%M)+(c=b*b%M)+(c=c*b%M)+(d=c*c%M)+(d=d*d%M)+(d=d*d%M)\
+(d=d*c%M)+(d=d*d%M)+(d=d*c%M)+(y=a*d%M)
;--------------------------------------------------------------------------
; Constants
;
; A factor FACTOR that relates the distances between the bomb pointer
; `qb' and the decoding tables `t1', `t2', and `t3' to the locations
; that are scanned. The entries in the decoding tables are derived
; from FACTOR and the relative positions of the tables and the bomb
; pointer. FACTOR must be relatively prime to 8000.
FACTOR equ 1283
; We need to evaluate FACTOR's inverse before using it. We can do
; this unintrusively by placing the expression in the dat's operand
; below anywhere before the quickscan code (or even in the first cell
; of the quickscan).
dat 0*((x=FACTOR) + invert) ; y = FACTOR^{-1} (mod 8000)
; Next come the derived constants: A1, A2, B1, B2, B3, and C2 are
; entries in the decoding tables, and the constant D is the magic
; decoding factor 1+FACTOR^{-1} (mod CORESIZE). The equations giving
; these constants are derived from the form of the decoder and
; mutations in the scan phase.
D equ (y+1) ; decoding factor
A1 equ (1 + FACTOR * (t1-1 - qb)) ; t1 entry
A2 equ (1 + FACTOR * (t1 - qb))
B1 equ (1 + FACTOR * (t2-1 - qb)) ; t2 entries
B2 equ (1 + FACTOR * (t2 - qb))
B3 equ (1 + FACTOR * (t2+1 - qb))
C2 equ (1 + FACTOR * (t3 - qb)) ; t3 entry
;--------------------------------------------------------------------------
; Decode tables
;
dat 0 , B1
t2 dat 0 , B2
dat 0 , B3
; The only limitation on the placing of the tables is that `t2' must be
; separated from the other tables by at least one cell to avoid bad bomb
; spread.
dat 123,123 ; any old cell.
; In the `t1' table the decoder uses the a-fields to get hold of a dat 0,0
; to compare the found location with.
dat dat0+1 , A1
t1 dat dat0+1 , A2
; The only reason the a-field contains the bomb pointer `qb' is that
; the current decoder prepares the attack phase for .6c bombing.
t3 dat qb , C2
;--------------------------------------------------------------------------
; Decoder and attack
;
; Basic idea: multiply decoding factor `D' by a table entry and
; optionally offset by another table entry. The scan phase mutates
; the table pointers and entries to make it all work out.
;
; The line following `q1' isn't really a part of the decoder proper
; but it's needed to hold a pointer to `t3' if the `t3' scan is used.
; In this version it also does double duty by preparing the attack for
; .6c bombing.
; -- Decoding phase --
decode
q0 mul.b *2 , qb
decide sne {t1 , @qb ; \ The A-fields are pointers to
q1 add.b t2 , qb ; } decoding tables.
add.ba *t3 , qb ; /
; -- Attack phase --
mov qdat , *qb
mov qdat , @qb
qb mov 24 , *D
sub qsub , qb
djn -4 , #6
jmp boot
qsub dat -15 , 21
qdat dat 10 , 0
;--------------------------------------------------------------------------
; Scan phase
;
; Notes:
;
; - The two scans marked with !!! interact so that the distance between
; their scans is t2-qb+1, so you'll want `t2' and `qb' at opposite ends of your
; warrior if you plan to use both scans. If this is causing you grief then
; remove the second line marked with !!!.
;
; - If you're looking to make the scan smaller, then good candidates
; for removal are the scans involving `C2' from the `t3' table.
;
; - The equations in the right margin are the conditions that must be
; met for decoding of the scans with < predecrements to work. They
; have the form
;
; table + ofs + (TABLE_ENTRY-1) = qb + D*(TABLE_ENTRY-1)
;
; from which we can solve for TABLE_ENTRY to get the expressions for
; A1, A2, ... given in the constants section.
;
; - The order of the scans matters due to the mutations of the
; decoding tables by the scans with < predecrements.
; no decoder mutations
qscan seq qb + D , qb + D + B2 ; !!!
jmp decide
; q0 mutations
sne qb + D * C2, qb + D * C2 + B2
seq <t3 , qb + D * (C2-1) + B2
jmp decode , }q0 ; t3 + C2-1 = qb+D*(C2-1)
sne qb + D * A1, qb + D * A1 + B2
seq <t1-1 , qb + D * (A1-1) + B2
djn.a decode , {q0 ; t1-1 + A1-1 = qb+D*(A1-1)
sne qb + D * A2, qb + D * A2 + B2
seq <t1 , qb + D * (A2-1) + B2
jmp decode , {q0 ; t1 + A2-1 = qb+D*(A2-1)
; q1 mutations
sne qb + D * B1, qb + D * B1 + B1
seq <t2-1 , qb + D * (B1-1) + (B1-1)
jmp decode , {q1 ; t2-1 + B1-1 = qb+D*(B1-1)
seq qb + D * (B1-2),qb + D * (B1-2) + (B1-2)
djn decode , {q1
sne qb + D * B3, qb + D * B3 + B3
seq <t2+1 , qb + D * (B3-1) + (B3-1)
jmp decode , }q1 ; t2+1 + B3-1 = qb+D*(B3-1)
; no mutations
sne qb + D * B2, qb + D * B2 + B2 ; !!!
seq <t2 , qb + D * (B2-1) + (B2-1)
jmp decode ; t2 + B2-1 = qb+D*(B2-1)
jmp boot
end qscan
_______________________________________________________________________________
The Hint - Airbag: Exposed by Lukasz Grabun
I was asked a question - what an airbag really is, and how to use it?
* The concept
-------------
The airbag technique was mentioned by M Joonas Pihlaja in a thread in
r.g.cw, while I was a newbie:
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&threadm=Pine.OSF.4.30.01
Here's what Joonas said:
: So where before a self-splitting loop was good for life-expectancy, real
: dat bombs are turning it into a liability.
: The fix: Use a bombing loop that won't die if it is dat bombed, but
: also without self-splitting. Aka an airbag.
: The idea is to use a small fixed number of processes that are scheduled
: to execute a loop exactly like a single process, and the clever bit is
: that the loop is created so that the processes can detect if the loop is
: dat bombed, in which case they fall through to the clear. I doubt I
: could explain the mechanics of it as lucidly as Paulsson in his posting
: of his bomber Airbag, so I won't even try. Also see Janeczek's Behemot
: bomber for this technique.
* The code
----------
Okay, so how far is it from the idea to the implementation itself? I must
confess that 12 months ago, when I posted my first warrior to r.g.cw and
Joonas mentioned the airbag technique, I was a little confused. Namely:
I didn't know what the guy was talking about :-) So I can understand the
problems faced by a newbie when dealing with airbag.
Since it is often best to follow some code to understand an idea, let's
take a look at how airbag is implemented in a warrior. The most recent,
to my knowledge, is Return of Vanquisher. It was published a week or so
ago; although I am still tweaking the q-scan, the main code is finalised
and nothing will change. So it fits our purposes:
sStp equ 1022
sLoo mov sSb , <sPtr ; main loop starts here
mov sJb , *sPtr
sPtr mov sStp+1 , *sStp*3+1
add sInc , sPtr
mov }sMb , @sPtr
jmz.a sLoo , {sMb ; and ends here
jmz.f clear , >clear
sInc jmz.f sStp*3 , @sStp*3+1
; some empty core
sJb jmp @sStp , sStp-1
sSb spl #1-sStp , 8
sMb mov @0 , <sSb
I tried to snip out the irrelevant parts. Hopefully, I didn't snip too
much away. :-)
First, let's take a look at the main loop. We have six instructions, and
it more or less looks like a standard bomber using incendiary bombs. A
little big, maybe, but it delivers one spl/mov incendiary and two jmp
bombs. So we have 4 (?) bombs in a six instruction loop. This means the
bomber runs at 0.66c - reasonably fast.
What makes it differ from the standard bombers are the lines:
sCMb mov }sMb , @sPtr
sChk jmz.a sLoo , {sMb ; and ends here
; ...
sMb mov @0 , <sSb
If we take a look at the sMb line, which contains the mov half of the
incendiary, we notice it's a-field is zero. Therefore, the instruction at
sCMb copies the sMb bomb into core (via the pointer at sPtr), and then
increments the a-field of sMb.
Next, the jmz.a in the sChk line, decrements the a-field of sMb, and jumps
back to the beginning of the loop (unless somehow, the a-field of sMb no
longer contains zero - which leads us to the next point).
* Parallel execution of processes
---------------------------------
As for now the idea is of no practical use. It gives no protection or
anything like it. To be more precise: the bomber does a little bit of
scanning, since it checks the a-field of a single cell. While fighting a
paper, this cell would most likely be overwritten by the paper's code or
bombs sooner or later (sooner, we presume). So the scanning line jmz.a
could be used as a simple check.
More importantly: we can develop this idea to protect the main loop
itself. How can this be possible? Since we have just one process in the
loop, once we have been hit our process terminates and the battle ends.
But why not place extra processes in our code to make it more resistant to
dat bombs? If we can make them execute the loop just like a single process
would... This would be perfect!
If we have more processes, a single dat bomb does not kill us so quickly.
Now, we can check not only if sMb has been modified, but also if we have
been hit by a dat bomb. How can we do this? A single dat bomb would not
kill the warrior immediately, but would interfere with subtle timings.
Some processes would be killed. Other processes while executing the sChk
line would "know" something is wrong because a previous process did not
execute sCMb, and the a-field of sMb contains an unexpected value. These
processes would fall through to the line after sChk to perform the end
phase (in RoV this is a simple d-clear).
* The booting code
------------------
The main problem is to arrange processes to execute the code in the way
a single process does. It is not as hard as one can expect:
org bBoo
sStp equ 1022
sLen equ 7
bOff equ (3408+sLoo) ; bomber boot distance
dOff equ -254 ; offset between bomber & bombs
bSrc mov.i {0 , #sLen
sLoo mov sSb+dOff , <sPtr
mov sJb+dOff , *sPtr
sPtr mov sStp+1 , *sStp*3+1
add sInc , sPtr
mov }sMb+dOff , @sPtr
sChk jmz.a sLoo , {sMb+dOff
sSpr jmz.f clear , >clear
sInc jmz.f sStp*3 , @sStp*3+1
;-- boot bombs and extra lines
bBoo mov sMb , bOff+19+dOff
mov sSb , bOff+18+dOff
mov sJb , bOff+17+dOff
mov sInc , bOff+sLen+2
mov sSpr , bOff+sLen+1
bDst spl 1 , bOff+sLen+1
spl 1 , }0
spl 1 , 0
;-- boot bomber
mov <bSrc , <bDst
bJmp jmp >bDst , 0
I copied all of the boot code to give you the full picture.
All starts at the bBoo line. First, we are moving bombs and extra lines
that do not belong to the main loop. Then, thanks to John Metcalf's
snippets from CW #69, we quickly generate seven (yes,seven) parallel
processes. We copy all lines between bSrc and sChk.
And then the magic begins. The b-field of the bDst line points to the
mov.i {0,#xx instruction in the booted bomber. The bJmp line directs the
first process there. The next process, due to post-increment addressing,
jumps to the next line in the booted bomber. And so on. After booting is
complete, we have the following situation:
dat 0, 0
1 mov.i {0, #0 ; 1st process <- this process executes first
2 sLoo ; 2nd process <- this process executes second
3 . ; 3rd "
4 . ; 4th "
5 . ; 5th "
6 . ; 6th "
7 sChk ; 7th "
The first line simply moves the dat 0,0 that lays behind our code to the
over itself. After this one process has executed we have the following
situation:
1 dat 0, 0
2 sLoo ; 1st & 2nd process <- the 2nd process will execute next
3 . ; 3rd " <- then the 3rd process
4 . ; 4th " <- then the 4th process
5 . ; 5th " <- etc
6 . ; 6th "
7 sChk ; 7th "
And finally, after the 7th process has executed, it will be the turn of
the first process to execute once again, and so on... You can create a
"diagram of process flow" in the code. This is left as an easy exercise
for the reader. :-) What you should note is processes execute the code as
though it is being executed by a single process, which was our goal. Now,
one hit in the lines 2 to 6 of our warrior and we jump to the clear phase,
to hopefully deal with the nasty opponent.
* Variants
----------
Booting can be achieved in other ways. One method was mentioned by
Pihlaja in the thread quoted at the beginning of this article. This is
used by Vanquisher.
bBoot mov bIncen , bOff+bAway-4-CURLINE
mov bSpare , bAway-CURLINE
bSrc spl 2 , bStart+5
bDest spl 2 , bAway-CURLINE
cSrc spl 1 , cStart+4
mov <bSrc , <bDest
cBoot mov <cSrc , <cDest
mov <dSrc , <dDest ; boot the bomber
bDjn djn >bDest , #5 ; jump into the code
cDest jmp bAway-CURLINE-4 , cAway-CURLINE
bStart add #bStep , bPtr
bMov mov bOff , @bPtr
bPtr mov >bEvac , @2-bDist
bChk jmz.b bStart , <bEvac
bEvac jmz.b bSpl , bSpl
bSpare jmz.b dOff-5 , dOff-5
Since the loop now has four lines we need five processes to be place into
it. Note that no mov.i {0,#0 line is required with this method. We use
the cDest line and direct jump the remaining process into the correct
position.
How is it done? After the booting phase completes in the cBoot+1 line we
order *four* processes to jump into the bombers code. This is done by the
djn instruction at bDjn. Note the post increment addressing mode - it's
quite similar to the jmp >... from the previous example. Now, since we
don't have the mov.i {0,#0 line we need to position the remaining process
using some alternative means. This is easy enough to take care of by a
simple jmp, and this is done at cDest. Now the warrior and allocated
processes look like:
bStart 1st process, 5th process
bMov 2nd process
bPtr 3rd process
bChk 4th process
And the story begins once again.
* Summary
---------
Whichever you decide to use, you'll discover the airbag technique to be
extremely useful. Not only because it protects our warrior, but also
because you can use processes to perform a sophisticated end-phase. In
Return of Vanquisher and in Vanquisher itself. processes runs two
independent core-clears. This increases the offensive power of the
warrior.
I hope you have enjoyed this article and find it useful.
* Acknowledgements
------------------
Obviously for Joonas for his hints when I was a newbie. Kudos go also
to John Metcalf for pointing out a nasty bug in Return of Vanquisher code.
_______________________________________________________________________________
Extra Extra - Digitalis 2002 by Christian Schmidt
Well, after a long period of time I decided to work again on a new
d-clear/imp warrior. As a starting point I used Digitalis 4, which was for
a short period successful on the hills. The first thing to change, was to
use a multi-process boot, which is now common for todays warriors. As it
is much smaller in size, I decided to also boot the imp-launcher.
An advantage is also, thanks to the multi-process booting, I need to boot
only a few spl 1 instructions together with the imp-launcher. Later, I also
decreased the imp launcher by one line, adding the step in the imp to the
pointer, instead of having the step in a separate line. This gave me a
fraction of a point increase against my testsuite.
Another feature of the imp-launcher is it is pushing further processes into
the d-clear. The tests against my testsuite show, as I expected, a
significant weakness to some scanners, while it didn't lose too much to
most papers. So, I computer generated different sets of boot distances for
the imp and the clear components and tested them against Hazy Lazy, Willow,
Claw, Uninvited, Son of Vain and Reepicheep (score check to see if the imps
spreads well).
The best scoring of these I sent to the hills and, wow, Digitalis scores
quite well on the 94nop and the 94 draft hill. After they were pushed off
at an age of about 80, I was again trying some improvements. I now felt it
was losing a little too often against papers, so I must increase the
processes to the imp. I found that if I include another spl 1 instruction
before I jump to the booted imp-launcher, it gives me significantly lower
loses against papers. So, with this code I now hope to survive also a hill
dominated by papers. The future will us show if my hope was right.
;redcode-94nop
;name Digitalis 2002
;author Christian Schmidt
;strategy Mini Q^4 -> d-clear + 7pt imps
;strategy multi-process bootstrapping
;strategy boot away the clear AND the imps
;strategy v0.1 new, optimized constants
;strategy v0.2 fixing a bug in the imp-launcher
;strategy v0.3 fixing a bug with the qscan
;strategy v0.3a rearranging the components
;strategy v0.4 new process allocation
;strategy v0.5 imp-launcher 1 instruction smaller
;assert 1
org qGo
impoff equ 100
impsize equ 1143
cBoot equ 2390
iBoot equ 459
spl 1, }qC
qTab2 spl 1, }qD
spl 2, }qE
djn.f imp, <-250
add.a imp, -1
djn.f cBoot-iBoot, <-400
dat 0, 0
imp mov.i #impsize, *0
dat 0, 0
dat 0, 0
iEnd dat 0, 0
ptr dat 0, 1800
clrb dat >2667, 25
clear spl #0, >ptr-15
loop mov clrb-15, >ptr-15
cc djn.f loop, >ptr-15
dat 0, 0
dat 0, 0
cEnd dat 0, 0
pGo mov.i clrb, cEnd+cBoot-18-3
mov.i ptr, cEnd+cBoot-19-3
spl 2, }-345
spl 1, }-567
mov -1, 0
mov.i {cEnd, {cBoo
mov.i {iEnd, {iBoo
mov.i {iEnd, {iBoo
cBoo spl cEnd+cBoot
spl 1
iBoo jmp cEnd+iBoot
for 15
dat 0, 0
rof
dat 0, }qA
qTab1 dat 0, }qB
for 27
dat 0, 0
rof
qX equ 3080
qA equ 3532
qB equ 2051
qC equ 6177
qD equ 4696
qE equ 3215
qF equ 583
qStep equ 7
qTime equ 16
qOff equ 87
qBomb dat {qOff, qF
qGo sne qPtr+qX*qE, qPtr+qX*qE+qE
seq <qTab2+1, qPtr+qX*(qE-1)+(qE-1)
jmp qDec, }qDec+2
sne qPtr+qX*qF, qPtr+qX*qF+qD
seq <qBomb, qPtr+qX*(qF-1)+qD
jmp qDec, }qDec
sne qPtr+qX*qA, qPtr+qX*qA+qD
seq <qTab1-1, qPtr+qX*(qA-1)+qD
djn.a qDec, {qDec
sne qPtr+qX*qB, qPtr+qX*qB+qD
seq <qTab1, qPtr+qX*(qB-1)+qD
djn.a qDec, *0
sne qPtr+qX*qC, qPtr+qX*qC+qC
seq <qTab2-1, qPtr+qX*(qC-1)+(qC-1)
jmp qDec, {qDec+2
sne qPtr+qX*qD, qPtr+qX*qD+qD
jmz.f pGo, <qTab2
qDec mul.b *2, qPtr
qSkip sne <qTab1, @qPtr
add.b qTab2, qPtr
qLoop mov qBomb, @qPtr
qPtr mov qBomb, }qX
sub #qStep, @qSkip
djn qLoop, #qTime
djn.f pGo, #0
end
_______________________________________________________________________________
Questions? Concerns? Comments? Complaints? Mail them to people who care.
Beppe Bezzi <giuseppe.bezzi@galactica.it>, Philip Kendall <pak21@cam.ac.uk>,
Anton Marsden <anton@paradise.net.nz>, John Metcalf <grumpy3039@hotmail.com>
and Christian Schmidt <DrSchmidt007@aol.com>
|
