Archived from groups: rec.games.corewar (More info?)
Quickscanners - Part IV
=======================
This part will deal with improved q^2-scanners and the basics of
q^3-scanners.
------------------------------------------------------------------
ATTENTION! While writing this text I noticed, that accidentally my
WilFiz-benchmark is missing the file for Willow, i.e. all results
against the WilFiz-benchmark in part I, II and II are wrong :-(
The version at my homepage will eventually contain the corrected
values. In this part I use the correct benchmark.
------------------------------------------------------------------
1. Current status
=================
You can find the original YAP with a q^1-scanner now at Koenigstuhl
(http://www.ociw.edu/~birk/COREWAR/94/hill_rec.html). Currently it
is 435th with a score of 115.39. YAP II now can also be found at
Koenigstuhl. Its "simple" q^2-scan was enough for rank 372 with
a score of 122.23.
Just to see, where we are, I've benchmarked some of the better
versions of YAP against Wilkies and WilFiz using "pmars -P".
| Wilkies W T L
-------------+-----------------------------------------
original YAP | 116.571059 21.276118 52.752704 25.981178
YAP I | 127.828163 26.127526 49.445584 24.426890
YAP II | 128.609046 26.560697 48.926954 24.512349
| WilFiz W T L
-------------+-----------------------------------------
original YAP | 105.397278 16.747853 55.153720 28.098428
YAP I | 105.002030 18.891275 48.328206 32.780520
YAP II | 113.790433 22.365722 46.693266 30.941012
YAP I is the last version of YAP in part I (on Koenigstuhl as
Yet Another Paper), YAP II (on Koenigstuhl as Yet Another Paper II)
is the last version in part III.
2. Where to scan?
=================
The last part has dealt with a crude theory about where to scan.
The problem of the theory was, that it assumed, that our opponent
does not move (e.g. like imps) and does not place bombs or decoys,
but normal warriors do that all the time :-( That is why you should
probably fight a large amount of warriors to decide, whether your
quickscanner is better than another.
To improve your quickscanner, you might want to change the order
of the scanned positions. Both possibilities are quite easy to do
with YAP II. The easiest one should be to reverse the order of
scans:
....
;;
;; quickscanner
;;
start EQU boot
qStart EQU (start - 200)
qSpace EQU 7700
qNum EQU 18
qStep EQU (-qSpace/qNum)
qHop EQU (qStep/2)
....
This version scores against Wilkies about the same as YAP II, but
against WilFiz it scores more than 0.5 points better:
Wilkies: 128.612785 (W 26.718797, T 48.456394, L 24.824809)
Wilfiz : 114.404670 (W 22.571358, T 46.690595, L 30.738046)
It is easy to change the order of the scanned locations in a
q^2-scanner:
....
qGo sne.i qStart+0*qStep+0*qHop, qStart+0*qStep+1*qHop
seq.i qStart+0*qStep+2*qHop, qStart+0*qStep+3*qHop
jmp attack1, 0
sne.i qStart+2*qStep+0*qHop, qStart+2*qStep+1*qHop
seq.i qStart+2*qStep+2*qHop, qStart+2*qStep+3*qHop
jmp attack1, { attack1
sne.i qStart+4*qStep+0*qHop, qStart+4*qStep+1*qHop
seq.i qStart+4*qStep+2*qHop, qStart+4*qStep+3*qHop
jmp attack1, } attack1
....
becomes for instance:
....
qGo sne.i qStart+4*qStep+0*qHop, qStart+4*qStep+1*qHop
seq.i qStart+4*qStep+2*qHop, qStart+4*qStep+3*qHop
jmp attack1, } attack1
sne.i qStart+0*qStep+0*qHop, qStart+0*qStep+1*qHop
seq.i qStart+0*qStep+2*qHop, qStart+0*qStep+3*qHop
jmp attack1, 0
sne.i qStart+2*qStep+0*qHop, qStart+2*qStep+1*qHop
seq.i qStart+2*qStep+2*qHop, qStart+2*qStep+3*qHop
jmp attack1, { attack1
....
All you have to do is to permute the lines. (Actually you have
to permute complete 3-instruction-sets in this case.)
A random order might not seem better, but if a lot of warriors
use the same quickscanner with the same order of scans, you
might gain a little advantage that way. Especially if a new
quickscanner was published recently, the odds are high, that
the new scanner is used without modifications in your opponents.
3. A better Q^2?
================
As you well know, there are several "rules", that should be
followed, if you want to write a good warrior. (Of course you
can ignore them, if you want to write a better warrior ;-) One
is, that you should not waste a single instruction or even a
single field. Up until now, I have used the following:
....
qGo sne.i qStart+8*qStep+qHop, qStart+8*qStep+qHop
jmp attack1
....
As you can see, the B-field of the jump instruction is NOT used.
How about this version:
....
qGo sne.i qStart+8*qStep+qHop, qStart+8*qStep+qHop
jmp attack1, < qStart+8*qStep+qHop/2
....
This version has a good chance to change an instruction inside our
opponent just 1 cycle after a successful scan. Not much, but this
change is for free. For further reference I name this "attack"
1-cycle-attack.
3.1 One instruction
===================
YAP II has an average reaction time of (4+6.5) instructions, if it
finds something with attack1 and (5+6.5) instructions, if it finds
something with attack2. That's an average of 10.83 instructions
before the first bomb is thrown. Quite a long time. It seems to be
a good idea to change the quickscanner.
One instruction can be easily saved by doing the needed adjustments
for "attack2" during the scan:
....
sne.i qStart+10*qStep+0*qHop, qStart+10*qStep+1*qHop
seq.i qStart+10*qStep+2*qHop, qStart+10*qStep+3*qHop
djn.f attack1, attack1
add.ab # 12*qStep, found ; <-- NEW
sne.i qStart+12*qStep+0*qHop, qStart+12*qStep+1*qHop
seq.i qStart+12*qStep+2*qHop, qStart+12*qStep+3*qHop
jmp attack1, 0
sne.i qStart+14*qStep+0*qHop, qStart+14*qStep+1*qHop
seq.i qStart+14*qStep+2*qHop, qStart+14*qStep+3*qHop
jmp attack1, { attack1
sne.i qStart+16*qStep+0*qHop, qStart+16*qStep+1*qHop
seq.i qStart+16*qStep+2*qHop, qStart+16*qStep+3*qHop
jmp attack1, } attack1
....
dat.f 2*qStep, qStart+8*qStep-found
qTab dat.f 0*qStep, qStart+0*qStep-found
dat.f 4*qStep, qStart+6*qStep-found
attack1 add.ab qTab, qTab
add.b @ attack1, found
....
Now we need an average of 10.5 instruction before the attack
starts, but there is one extra instruction during the scan. The
results with are:
Wilkies: 128.327565 (W 26.458681, T 48.951523, L 24.589796)
WilFiz : 113.373820 (W 22.308572, T 46.448105, L 31.243324)
That seems to be slightly worse than the previous version.
3.2 Two possibilites
====================
When we use the sne/seq-trick, we have to choose between four
possible targets after a successful scan, which takes at the
moment an average of 6.5 instructions:
....
;; choose between the four possible positions
qSelect seq.i (start - 1), @ found
jmp adjust
add.ab # qHop, found
djn qSelect, # 4
....
Choosing between only two positions takes only an average of
1.5 instructions:
....
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
....
Let's see how the following version scores:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 18 ; number of scans
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 39
dat.f 0, 0
rof
;; fast attack
qGo seq.i qStart+0*qStep, qStart+0*qStep+qHop
jmp attack1, < qStart+0*qStep+qHop/2
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1, { attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, } attack1
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, > attack1
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp attack1, < attack1
seq.i qStart+5*qStep, qStart+5*qStep+qHop
djn.f attack1, attack1
;; slow attack
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, < qStart+6*qStep+qHop/2
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, { attack1
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp attack2, } attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack2, > attack1
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp attack2, < attack1
seq.i qStart+11*qStep, qStart+11*qStep+qHop
djn.f attack2, attack1
;; even slower attacks
seq.i qStart+12*qStep, qStart+12*qStep+qHop
jmp attack3, < qStart+12*qStep+qHop/2
seq.i qStart+13*qStep, qStart+13*qStep+qHop
jmp attack3, { attack1
seq.i qStart+14*qStep, qStart+14*qStep+qHop
jmp attack3, } attack1
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, > attack1
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, < attack1
seq.i qStart+17*qStep, qStart+17*qStep+qHop
djn.f attack3, attack1
jmp boot
;; choose target
dat.f 1*qStep, qStart+4*qStep-found
qTab dat.f 0*qStep, qStart+0*qStep-found
dat.f 2*qStep, qStart+3*qStep-found
attack3 add.ab # 6*qStep, found
attack2 add.ab # 6*qStep, found
attack1 add.ab qTab, qTab
add.b @ attack1, found
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
....
This version uses 18 scans (the same number as in YAP II), but
it scores better:
Wilkies: 129.411293 (W 26.923365%, T 48.641200%, L 24.435436%)
WilFiz : 116.761206 (W 23.730398%, T 45.570012%, L 30.699590%)
The first 6 scans need 5.5 instructions (1 jump to attack1,
2 at attack1, 1.5 at qSelect, 1 at adjust), the next 6 scans
need 6.5 instructions (1 at attack2, ...) and the last need
7.5 instructions (1 at attack3, 1 at attack2, ...) before the
bombing starts. That's an average of 6.5 instructions!
Now you might want to try to use a different number of scans,
for example with 22 scans and an additional "attack4" it scores
as follows:
Wilkies: 131.372580 (W 27.865017%, T 47.777529%, L 24.357454%)
WilFiz : 116.482395 (W 24.837094%, T 41.971115%, L 33.191792%)
3.3 The bad table
=================
As you well know, your opponent might have already altered your
code with his first instruction. If he has decremented one of
the 6 jumps to attack3, you could die, because now you could
jump to the last dat-instruction of "qTab" :-( The probability
of this event is very low, but it can be easily prevented.
You can change the dat-instruction to nop-instructions or
place the table at the end or some other safe location inside
your warrior.
You might even want to use a table like this:
mov.i < 1*qStep, < qStart+4*qStep-found
qTab nop 0*qStep, qStart+0*qStep-found
mov.i < 2*qStep, < qStart+3*qStep-found
and "attack" some locations of the core, when these instructions
are accidentally executed.
3.4 Another decoder
===================
So far we have used a quite simple decoder, but there are others,
for example the one of Probe by Anton Marsen. I've taken the
liberty to rewrite it in order to make it more easy to understand.
The decoder uses a set of three different add-instructions:
....
attack3 add.a qTab+1, qTab
attack2 add.ab @ attack3, found
attack1 add.b * attack3, @ attack2
;; choose between the two possible targets
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
....
found mov.i -qStep2, @ qStart ; <-- CHANGED!!
....
A first advantage is, that this decoder has the ability to
attack without any decoding at all, altough this is only possible
for the locations (qStart+0*qstep) and (qStart+0*qStep+qHop):
....
qGo seq qStart+0*qStep, qStart+0*qStep+qHop
jmp qSelect
....
(To make the code more readable, I won't use any 1-cycle-attacks.)
If this scan is successful, it directly starts by choosing the
correct target.
The new decoder uses the following table:
dat.f 10*qStep, 2*qStep
qTab dat.f 4*qStep, 1*qStep
daf.f 23*qStep, 3*qStep
Let's continue with the next scans:
....
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, { attack3
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, } attack3
....
That's nothing new so far.
....
;; "jump > attack1" jumps to attack2
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp > attack1
....
Up until now we have not thought about using the destination
of the jump for the correct calculation of the target, but it
works.
....
seq.i qStart+5*qStep, qStart+5*qStep+qHop
jmp attack2
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, { attack3
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, } attack3
;; "jmp < attack1" jumps to attack3
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp < attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack3
;; "jmp > attack1" jumps to attack2
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp > attack1, < attack3
seq.i qStart+11*qStep, qStart+11*qStep+qHop
jmp attack2, < attack3
seq.i qStart+12*qStep, qStart+12*qStep+qHop
djn.f attack2, attack3
....
Now there is a problem. There is no possiblity to decode
(13*qStep) with this decoder and this table. Probe uses a little
trick to make the decoder nontheless calculate this value.
It stores it somewhere else (see Probe for details).
For (14*qStep) even Probe has no solution. It simply skips this
scan.
....
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, < attack3
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, { attack3
....
And another problem. Probe uses the same trick to decode
(17*qStep) as to decode (13*qStep) :-(
Again Probe doesn't have a way to decode the values for (18*qStep)
and (19*qStep).
....
;; "djn.f < attack1, attack" jumps to attack3
seq.i qStart+20*qStep, qStart+20*qStep+qHop
djn.f < attack1, attack3
....
Again a trick to decode (21*qStep) :-(
....
seq.i qStart+22*qStep, qStart+22*qStep+qHop
djn.f attack3, attack3
;; "jmp > attack1" jumps to attack2
seq.i qStart+23*qStep, qStart+23*qStep+qHop
jmp > attack1, > attack3
seq.i qStart+24*qStep, qStart+24*qStep+qHop
jmp attack2, > attack3
....
Again Probe doesn't have a way to decode the value for (25*qStep),
(26*qStep) and (29*qStep).
....
;; "jmp < attack1" jumps to attack3
seq.i qStart+27*qStep, qStart+27*qStep+qHop
jmp < attack1, > attack3
seq.i qStart+28*qStep, qStart+28*qStep+qHop
jmp attack3, > attack3
seq.i qStart+30*qStep, qStart+30*qStep+qHop
jmp attack3, } attack3
....
Creating this quickscan must have taken an awful lot of time!
If we forget about Probe's trick, we get 21 positions from the
table plus one for free (qStart+0*qStep). Now we have this
quickscan:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 31
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 32
dat.f 0, 0
rof
qGo seq.i qStart+0*qStep, qStart+0*qStep+qHop
jmp qSelect
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, { attack3
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, } attack3
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp > attack1
seq.i qStart+5*qStep, qStart+5*qStep+qHop
jmp attack2
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, { attack3
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, } attack3
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp < attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack3
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp > attack1, < attack3
seq.i qStart+11*qStep, qStart+11*qStep+qHop
jmp attack2, < attack3
seq.i qStart+12*qStep, qStart+12*qStep+qHop
djn.f attack2, attack3
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, < attack3
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, { attack3
seq.i qStart+20*qStep, qStart+20*qStep+qHop
djn.f < attack1, attack3
seq.i qStart+22*qStep, qStart+22*qStep+qHop
djn.f attack3, attack3
seq.i qStart+23*qStep, qStart+23*qStep+qHop
jmp > attack1, > attack3
seq.i qStart+24*qStep, qStart+24*qStep+qHop
jmp attack2, > attack3
seq.i qStart+27*qStep, qStart+27*qStep+qHop
jmp < attack1, > attack3
seq.i qStart+28*qStep, qStart+28*qStep+qHop
jmp attack3, > attack3
seq.i qStart+30*qStep, qStart+30*qStep+qHop
jmp attack3, } attack3
;; found nothing -> boot paper
jmp boot
;; decoder table
dat.f 10*qStep, 2*qStep
qTab dat.f 4*qStep, 1*qStep
dat.f 23*qStep, 3*qStep
;; decoder
attack3 add.a qTab, qTab
attack2 add.ab @ attack3, found
attack1 add.b * attack3, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
....
There are 3 jumps to attack1, 9 to attack2, 9 to attack3 and
one to qSelect, i.e. it takes an average of 4.68 cycles before
the bombing starts. This quickscan together with YAP scores as
follows:
Wilkies: 131.207003 (W 27.885314%, T 47.551062%, L 24.563624%)
WilFiz : 117.635560 (W 25.191215%, T 42.061915%, L 32.746870%)
Probe uses another order of scans: 0, 1, 2, 3, (13), 4, 5, 6,
7, 10, 11, 12, 23, 24, (17), 8, 9, 15, 16, 20, (21), 22, 27,
28, 30. When we use this order (without 13, 17, 21), YAP scores
as follows:
Wilkies: 131.134363 (W 27.854869%, T 47.569756%, L 24.575375%)
WilFiz : 117.864697 (W 25.285220%, T 42.009037%, L 32.705743%)
Because of the inability of the decoder to generate certain steps,
there are gaps in in quickscan-pattern, that Probe uses. Fortunately
there is a way to minimize the gaps and distribute the scanned
positions more evenly.
Let's use (start + 200) as the first scanned position. I've written
a little program, that checks all values for qStep, i.e.
1 <= qStep <= 7999, whether they create a scan-pattern, that is
between the instruction 200 and 7900. In this list I've looked for
patterns with a good distribution.
With (qStep EQU 1250) the minimal gap between two scans is 250
and the maximal is 500. Together with (qHop EQU 120) and Probe's
order of scans, YAP scores as follows:
Wilkies: 131.365637 (W 27.891189%, T 47.692069%, L 24.416741%)
WilFiz : 117.782442 (W 25.230206%, T 42.091826%, L 32.677969%)
Now, that I think of the last three versions, there shouldn't be
much difference. They scan only different locations, but the rest
is the same. According to the "theory" of part III that is just
the way it should work.
3.5 Further q^2-decoders
========================
As you might have guessed by now, there are other decoders for
q^2-scanners.
3.5.1 Innocuous
===============
Innocuous by John Metcalf contains a quickscanner, that uses a
slightly bigger table than normal:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 29 ; number of scans
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 25
dat.f 0, 0
rof
qA dat.f 10*qStep, 10*qStep
qB dat.f 13*qStep, 13*qStep
qC dat.f 6*qStep, 6*qStep
qD dat.f 1*qStep, 1*qStep
qE dat.f 4*qStep, 4*qStep
;; decoder
nop { qB, { qE
attack3 add.f qD, qB
attack2 add.f @ attack3, found
attack1 add.f * attack3, found
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.f qHopAdd, found ; no, use 2nd! <-- CHANGED
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i qStart-qStep2, @ qStart ; <-- CHANGED
add.f qIncr, found
djn.b throw, # 20
jmp boot ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
qHopAdd dat.f # qHop, # qHop
....
As you can see the label "adjust" and its instruction is missing.
It is no longer necessary, because now the decoder correctly
initializes the bombing routine.
Now let's take a look at the scanner itself (without the 1-cycle-
attacks):
....
qGo seq qStart+0*qStep, qStart+0*qStep+qHop ; 0
jmp qSelect
....
Nothing new, but John Metcalf was so kind to indicate which part
of the table is used for the decoding. This scan needs no decoding
at all!
....
seq qStart+1*qStep, qStart+1*qStep+qHop ; D
jmp attack1
seq qStart+2*qStep, qStart+2*qStep+qHop ; DD
djn.b attack2, { attack2
....
(qStart+3*qStep) is not decoded. I think, that it is not possible
with this decoder, but I have not checked it.
....
seq qStart+4*qStep, qStart+4*qStep+qHop ; E
jmp attack1, } attack3
seq qStart+5*qStep, qStart+5*qStep+qHop ; DE
jmp attack2, { attack2
seq qStart+6*qStep, qStart+6*qStep+qHop ; C
jmp attack1, { attack3
seq qStart+7*qStep, qStart+7*qStep+qHop ; DC
jmp attack2, > attack3
seq qStart+8*qStep, qStart+8*qStep+qHop ; DDC
jmp attack3, > attack3
....
(qStart+9*qStep) is not decoded.
....
seq qStart+10*qStep, qStart+10*qStep+qHop ; A
djn.a attack1, { attack1
seq qStart+11*qStep, qStart+11*qStep+qHop ; DA
jmp attack2, < attack3
seq qStart+12*qStep, qStart+12*qStep+qHop ; DDA
jmp attack3, < attack3
seq qStart+13*qStep, qStart+13*qStep+qHop ; B
jmp attack1, { attack1
seq qStart+14*qStep, qStart+14*qStep+qHop ; DB
jmp attack2
seq qStart+15*qStep, qStart+15*qStep+qHop ; DDB
jmp attack3
seq qStart+16*qStep, qStart+16*qStep+qHop ; CA
djn.f attack2, attack3
seq qStart+17*qStep, qStart+17*qStep+qHop ; EB
jmp attack2, } attack3
....
(qStart+18*qStep) is not decoded.
....
seq qStart+19*qStep, qStart+19*qStep+qHop ; CB
jmp attack2, { attack3
....
(qStart+19*qStep) is not decoded.
....
seq qStart+21*qStep, qStart+21*qStep+qHop ; EEB
jmp attack3, } attack3
seq qStart+22*qStep, qStart+22*qStep+qHop ; CCA
djn.f attack3, attack3
seq qStart+23*qStep, qStart+23*qStep+qHop ; BA
djn.a attack2, { attack1
seq qStart+24*qStep, qStart+24*qStep+qHop ; DAB
djn.a attack3, { attack1
seq qStart+25*qStep, qStart+25*qStep+qHop ; CCB
jmp attack3, { attack3
seq qStart+26*qStep, qStart+26*qStep+qHop ; BB
jmp attack2, { attack1
....
(qStart+27*qStep) is not decoded.
....
seq qStart+28*qStep, qStart+28*qStep+qHop ; DDBB
jmp attack3, { attack1
....
This quickscan has 24 scans, it contains one jump to qSelect, 5
jumps to attack1, 10 jumps to attack2 and 8 jumps to attack3, i.e.
it executes an average of 3.54 instructions before an attack starts.
It scores as follows against Wilkies and WilFiz:
scans | Wilkies
------+-------------------------------------------------------
24 | 132.639512 (W 28.509700%, T 47.110413%, L 24.379887%)
23 | 132.367645 (W 28.431718%, T 47.072491%, L 24.495791%)
22 | 131.879994 (W 28.182818%, T 47.331539%, L 24.485643%)
scans | WilFiz
------+-------------------------------------------------------
24 | 117.597637 (W 25.973700%, T 39.676537%, L 34.349763%)
23 | 118.537687 (W 25.955006%, T 40.672670%, L 33.372324%)
22 | 119.224031 (W 25.910674%, T 41.492010%, L 32.597317%)
21 | 119.513524 (W 25.761120%, T 42.230163%, L 32.008717%)
20 | 119.997436 (W 25.631329%, T 43.103448%, L 31.265222%)
19 | 120.438619 (W 25.495663%, T 43.951630%, L 30.552707%)
18 | 120.064201 (W 25.087595%, T 44.801414%, L 30.110990%)
3.5.2 Aggression is a switch
============================
Aggression is a switch by M. Joonas Pihlaja uses a decoder, that
limits the maximal number of cycles before the bombing starts to
4.5 instructions. It needs an average of 4.17 cycles (24 scans)
before the bombing starts.
I will not describe this decoder here because this text is
already too long, but the version at corewars.jgutzeit.de will
eventually contain a full description. Let's simply assume, that
I was too lazy to try to understand this warrior, which is
probably the truth anyway ;-)
3.5.3 Other decoders?
=====================
There are probably other q^2-decoders out there. If you find one,
please let me know.
4. Results of the contest
=========================
In part III I've invited everybody to create the best quickscanner
(q^1 or q^2 only) for YAP. All warriors had to fight against WilFiz.
Unfortunately there wasn't much interest and I've go only one
entry :-( Anyway the winner is Zul Nadzri. Congratulations!
He has used YAP II along with a slightly modified bombing engine.
1. Zu Nadzri: 113.320408 (W 22.272251%, T 46.503653%, L 31.224095%)
Because of the low number of submissions, there won't be any new
contests for YAP. It would be nice to get good quickscanners for
YAP though.
5. Q^3-Scanners
===============
As you have seen q^2-scans have improved quite a lot over the time,
but are other possibilites. In May 1999 Leonardo Humberto and John
Metcalf published a new type of quickscanner - q^3 (Puddleglum). It
no longer decodes the correct position with a set of additions, but
with some multiplications:
....
;;
;; quickscanner
;;
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 25
dat.f 0, 0
rof
;; decoding table
dat.f 15, 10 ; A, D
qTab dat.f 7, 4 ; B, E
dat.f 13, 11 ; C, F
qGo ...
;; found nothing -> boot paper
...
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i -qStep2, @ qStart ; <-- CHANGED AGAIN
add.f qIncr, found
djn.b throw, # 20
jmp boot ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
....
I've taken the liberty to use the bombing engine IV, that we have
used along with the last versions of YAP. Puddleglum uses a 0.5c
negative bomber, which doesn't need the extra line at "adjust".
This means, that the average number of cycles before an attack
in Puddleglum starts is 1 cycle lower than in the version, that I
present here.
Let's look at the scans (without 1-cycle-attacks):
....
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect
....
This is the usual scan without decoding. During the following
scans there are a lot gaps, which the decoder cannot handle. I
will not mention this anymore, because you should be quite familar
with the problem now.
....
seq found+3*qStep, found+3*qStep+qHop ; E-1
jmp > attack1, < qTab
seq found+4*qStep, found+4*qStep+qHop ; E
jmp > attack1
seq found+5*qStep, found+5*qStep+qHop ; E+1
jmp > attack1, > qTab
seq found+6*qStep, found+6*qStep+qHop ; B-1
jmp attack1, { qTab
seq found+7*qStep, found+7*qStep+qHop ; B
jmp attack1
seq found+8*qStep, found+8*qStep+qHop ; B+1
jmp attack1, } qTab
seq found+9*qStep, found+9*qStep+qHop ; D-1
djn.b > attack1, { attack2
seq found+10*qStep, found+10*qStep+qHop ; D
jmp > attack1, { attack2
seq found+11*qStep, found+11*qStep+qHop ; F
jmp > attack1, } attack2
seq found+13*qStep, found+13*qStep+qHop ; C
jmp attack1, } attack1
seq found+14*qStep, found+14*qStep+qHop ; A-1
djn.a attack1, { attack1
seq found+15*qStep, found+15*qStep+qHop ; A
jmp attack1, { attack1
seq found+18*qStep, found+18*qStep+qHop ; B*E+1-B-E
djn.f attack2, qTab
seq found+21*qStep, found+21*qStep+qHop ; B*E-B
jmp attack2, < qTab
seq found+24*qStep, found+24*qStep+qHop ; B*E-E
jmp attack2, { qTab
seq found+32*qStep, found+32*qStep+qHop ; B*E+E
jmp attack2, } qTab
seq found+35*qStep, found+35*qStep+qHop ; B*E+B
jmp attack2, > qTab
seq found+39*qStep, found+39*qStep+qHop ; C*E-C
djn.b attack2, } attack1
seq found+52*qStep, found+52*qStep+qHop ; C*E
jmp attack2, } attack1
seq found+56*qStep, found+56*qStep+qHop ; A*E-E
djn.a attack2, { attack1
seq found+60*qStep, found+60*qStep+qHop ; A*E
jmp attack2, { attack1
seq found+63*qStep, found+63*qStep+qHop ; B*D-B
djn.b attack2, { attack2
seq found+66*qStep, found+66*qStep+qHop ; B*F-F
djn.a attack2, } attack2
seq found+70*qStep, found+70*qStep+qHop ; B*D
jmp attack2, { attack2
seq found+77*qStep, found+77*qStep+qHop ; B*F
jmp attack2, } attack2
....
In previous quickscanners the scanned locations were all
relative to the beginning of the warrior. Because we can no
longer add a value to the first scanned position, it is necessary
to make the scanned position relative to the label "found".
Now we find an interesting idea:
....
sne found+28*qStep, found+28*qStep+qHop ; B*E
jmz boot, found+28*qStep+qHop-10
....
Normally we would just add a "jmp boot" to the end of the scan, but
if the scan is immediately followed by the decoder, we have a
restricted free scan. It is restricted to a position near
(found+28*qStep+qHop), but it is free.
Before I start to benchmark this quickscan, I have to address a
problem when creating quickscanners. As you have seen they become
more and more complex and it is therefore quite probable, that they
contain bugs. If your quickscanner bombs the found position and
not only near it, there is a simple test for your quickscanner
(CoreWarrior #84).
Append your quickscanner to a "jmp 0" and let it fight against
a simple "jmp 0, 1" with "pmars -b -P -c 500 qscan.red jmp0.red".
If your quickscanner works correctly it should win exactly twice
the number of scanned locations.
Another problem of this quickscanner is, that it is no longer that
easy to assure, that all scanned positions are inside [200,7900],
but for example with (qStep EQU 5400) and (qHop EQU 1300) that is
the case.
Puddleglum's quickscan looks at 27*2+1 locations. This might be a bit
much. It scores as follows against Wilkies and WilFiz (the free scan
is always used and scans are removed from the end, i.e. beginning
with 77, 70, ...):
scaned pos.| Wilkies
-----------+------------------------------------------------------
2*27+1 | 131.955839 (W 28.590352%, T 46.184784%, L 25.224864%)
2*26+1 | 132.661945 (W 28.678481%, T 46.626501%, L 24.695018%)
2*25+1 | 132.218092 (W 28.442935%, T 46.889288%, L 24.667778%)
2*24+1 | 131.983613 (W 28.305132%, T 47.068218%, L 24.626650%)
2*23+1 | 131.836730 (W 28.228219%, T 47.152075%, L 24.619707%)
scaned pos.| WilFiz
-----------+------------------------------------------------------
2*27+1 | 113.860937 (W 25.200295%, T 38.260052%, L 36.539653%)
2*26+1 | 115.350062 (W 25.310858%, T 39.417489%, L 35.271653%)
2*25+1 | 116.271418 (W 25.300709%, T 40.369290%, L 34.330000%)
2*24+1 | 116.930522 (W 25.277208%, T 41.098898%, L 33.623894%)
2*23+1 | 117.677221 (W 25.262253%, T 41.890463%, L 32.847285%)
2*22+1 | 118.061787 (W 25.071572%, T 42.847071%, L 32.081357%)
2*21+1 | 118.561723 (W 25.011751%, T 43.526471%, L 31.461778%)
2*20+1 | 118.797804 (W 24.870743%, T 44.185575%, L 30.943682%)
2*19+1 | 118.991155 (W 24.692347%, T 44.914114%, L 30.393539%)
2*18+1 | 119.000235 (W 24.447186%, T 45.658676%, L 29.894138%)
2*17+1 | 118.976734 (W 24.239414%, T 46.258493%, L 29.502094%)
The full quickscan has 1 jump to qSelect, 6 jumps to attack1 and
20 jumps (19 jumps + 1 fall-through) to attack2. When we use the
bombing engine IV, it takes an average of 4.20 instructions before
the first bomb is thrown. The original quickscan needs only an
average of 3.20 instructions, because it doesn't need to prepare
the bombing (label "adjust").
This is the (more or less ;-) original bombing engine:
....
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; bombing engine V
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
qDist EQU (qTimes*qStep2 - 10)
qLoop mov qBomb, @ found
found mov qBomb, * qStep
sub # qStep2, found
djn qLoop, # qTimes
jmp boot ; start paper
qBomb dat.f { qDist, { 1
....
It scores as follows:
scaned pos.| Wilkies
-----------+------------------------------------------------------
2*27+1 | 131.728304 (W 28.069585%, T 47.519549%, L 24.410866%)
2*26+1 | 131.540828 (W 27.952079%, T 47.684592%, L 24.363330%)
2*25+1 | 131.337863 (W 27.827629%, T 47.854976%, L 24.317395%)
scaned pos.| WilFiz
-----------+------------------------------------------------------
2*27+1 | 112.777208 (W 24.472824%, T 39.358736%, L 36.168440%)
2*26+1 | 113.414413 (W 24.459471%, T 40.036000%, L 35.504529%)
2*25+1 | 114.162714 (W 24.455732%, T 40.795518%, L 34.748750%)
2*24+1 | 114.982588 (W 24.463210%, T 41.592958%, L 33.943832%)
2*23+1 | (to be calculated ...)
2*22+1 | (to be calculated ...)
2*21+1 | (to be calculated ...)
At the point some of you may have noticed, that the q^2-scanner of
Innocuous scores against WilFiz better than this q^3-scanner.
5.1 MiniQ^3
===========
As you have seen a complete q^3-scan may not result in the best
score. Fortunatly John Metcalf was so kind to trim the q^3-scan
to fewer locations (CoreWarrior #75). His MiniQ^3 scans 2*16+1
locations and has the advantage, that it no longer needs an extra
table for its decoder. All necessary values are nicely hidden
inside the quickscan:
....
;; quickscanner
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 52
dat.f 0, 0
rof
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect
seq found+2*qStep, found+2*qStep+qHop ; C-1
jmp > attack1, { attack2
seq found+3*qStep, found+3*qStep+qHop ; C
jmp > attack1
seq found+4*qStep, found+4*qStep+qHop ; C+1
jmp > attack1, } attack2
seq found+5*qStep, found+5*qStep+qHop ; B-1
jmp attack1, < qBomb
seq found+6*qStep, found+6*qStep+qHop ; B
jmp attack1
seq found+7*qStep, found+7*qStep+qHop ; B+1
jmp attack1, > qBomb
seq found+9*qStep, found+9*qStep+qHop ; A-1
djn.b attack1, { attack1
seq found+10*qStep, found+10*qStep+qHop ; B
jmp attack1, { attack1
seq found+12*qStep, found+12*qStep+qHop ; B*C-B
jmp attack2, { attack2
seq found+15*qStep, found+15*qStep+qHop ; B*C-C
jmp attack2, < qBomb
seq found+21*qStep, found+21*qStep+qHop ; B*C+C
jmp attack2, > qBomb
seq found+24*qStep, found+24*qStep+qHop ; B*C+B
jmp attack2, } attack2
seq found+27*qStep, found+27*qStep+qHop ; A*C-C
djn.b attack2, { attack1
seq found+30*qStep, found+30*qStep+qHop ; A*C
jmp attack2, { attack1
;; free scan + boot paper, if found nothing
sne found+18*qStep, found+18*qStep+qHop ; B*C
jmz.f boot, found+18*qStep+qHop-10
;; decoder
attack2 mul.ab # 3, found ; C=3
attack1 mul.b qBomb, @ attack2
;; choose between the two possible positions
qSelect sne.i (start-1), @ found
add.ab # qHop, found
;; bombing engine V
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
qDist EQU (qTimes*qStep2 - 10)
qLoop mov qBomb, @ found
found mov qBomb, * qStep
sub # qStep2, found
djn qLoop, # qTimes
jmp boot, > 10 ; A=10
qBomb dat.f { qDist, { 6 ; B=6
....
YAP with the original MiniQ^3 (and original bombing engine)
scores as follows:
Wilkies: 129.334380 (W 26.811199%, T 48.900782%, L 24.288019%)
WilFiz : 118.624749 (W 23.864462%, T 47.031364%, L 29.104175%)
6. Yet Another Paper III
========================
Just to have another reference point, here is YAP III. Is uses
a q^3-scan (2*18+1 locations) together with bombing engine IV
and 1-cycle-attacks. I've already sent it to Koenigstuhl. At the
moment of writing it was 340th with a score of 126.11. It scores
as follows against Wilkies and Wilfiz:
Wilkies: 130.187369 (W 27.325022%, T 48.212302%, L 24.462676%)
WilFiz : 119.077682 (W 24.473358%, T 45.657608%, L 29.869034%)
The only difference to the version in chapter 5 is, that this
version uses three 1-cycle-attacks. This little change results in
an improvement of about 0.077 points against Wilfiz.
;redcode-94nop
;name Yet Another Paper III
;author Jens Gutzeit
;strategy q^3 -> paper
;assert CORESIZE == 8000
ORG qGo
pStep1 EQU 3913
pStep2 EQU 3035
boot spl 1
spl 1
silk1 spl @ silk1, < pStep1
mov.i } silk1, > silk1
mov.i { silk1, < silk2
silk2 djn.f @ silk2, < pStep2
;;
;; quickscanner
;;
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 42
dat.f 0, 0
rof
;; decoding table
dat.f 15, 10 ; A, D
qTab dat.f 7, 4 ; B, E
dat.f 13, 11 ; C, F
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect, < found+1*qStep+qHop/2
seq found+3*qStep, found+3*qStep+qHop ; E-1
jmp > attack1, < qTab
seq found+4*qStep, found+4*qStep+qHop ; E
jmp > attack1, < found+4*qStep+qHop/2
seq found+5*qStep, found+5*qStep+qHop ; E+1
jmp > attack1, > qTab
seq found+6*qStep, found+6*qStep+qHop ; B-1
jmp attack1, { qTab
seq found+7*qStep, found+7*qStep+qHop ; B
jmp attack1, < found+7*qStep+qHop/2
seq found+8*qStep, found+8*qStep+qHop ; B+1
jmp attack1, } qTab
seq found+9*qStep, found+9*qStep+qHop ; D-1
djn.b > attack1, { attack2
seq found+10*qStep, found+10*qStep+qHop ; D
jmp > attack1, { attack2
seq found+11*qStep, found+11*qStep+qHop ; F
jmp > attack1, } attack2
seq found+13*qStep, found+13*qStep+qHop ; C
jmp attack1, } attack1
seq found+14*qStep, found+14*qStep+qHop ; A-1
djn.a attack1, { attack1
seq found+15*qStep, found+15*qStep+qHop ; A
jmp attack1, { attack1
seq found+18*qStep, found+18*qStep+qHop ; B*E+1-B-E
djn.f attack2, qTab
seq found+21*qStep, found+21*qStep+qHop ; B*E-B
jmp attack2, < qTab
seq found+24*qStep, found+24*qStep+qHop ; B*E-E
jmp attack2, { qTab
seq found+32*qStep, found+32*qStep+qHop ; B*E+E
jmp attack2, } qTab
;; free scan + boot paper, if found nothing
sne found+28*qStep, found+28*qStep+qHop ; B*E
jmz boot, found+28*qStep+qHop-12
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i -qStep2, @ qStep
add.f qIncr, found
djn.b throw, # 20
jmp boot, < 4000 ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
END
7. The Quickscanner-Hill
========================
To give the texts about quickscanners a home, I have decided
to put all texts on http://corewars.jgutzeit.de. At the moment
you will find there only links to my original postings to
rec.games.corewar. As soon as all parts of this text are
published, I'll start to rewrite them and publish a nice-looking
HTML-version. The URL of the English version will definitely be
http://corewars.jgutzeit.de/quickscanners/index.en.html. A german
translation will also be published.
Apart from the texts about quickscanners, there is also a hill
at http://corewars.jgutzeit.de/quickscanner_hill/index.en.html.
It is there to show the possibilities, that quickscanners offer.
The hill has similar rules as my little contest for YAP.
ATTENTION! Altough the rules are similar there are differences:
- Your warrior will fight a different benchmark.
- Your starting point is no longer YAP, but another warrior
(A Quickscanner's Paper), which is published at my homepage
and already at Koenigstuhl (currently 259th, 94nop-hill).
- You can use any quickscanner that you want.
- All rules can be found at
http://corewars.jgutzeit.de/quickscnner_hill/rules.en.html
If you have comments, questions or problems, send an email to
jens@jgutzeit.de (jens [at] jgutzeit [dot] de). Good luck!
8. Preview
==========
The next part (V) will deal with q^3- and q^4-scanners, new
bombing-engines and the a crude theory about where to hit.
Part VI will deal with quickscanners for non-standard cores,
especially for tiny and nano cores. Part VII will deal with
interactions between papers and quickscanners, quickscans for
'88-hills and everything, that I have forgotten to mention so
far. Comments and hints are always welcome and can be sent to
jens@jgutzeit.de (jens [at] jgutzeit [dot] de) or
rec.games.corewar.
At this point I would like to thank John Metcalf for directing
me to the right warriors while I was looking for good
quickscanners.
- Jens Gutzeit
9. Links
========
CoreWarrior 40 - Probe by Anton Marsden
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/040.txt
"Q^2 ala Franz" by Franz
- http://www.ociw.edu/~birk/COREWAR/94/HILL/q2alafranz.red
CoreWarrior 54 - On QScans and CoreWar Strategy
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/054.txt
CoreWarrior 71 - Fixed by Ken Espiritu
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/071.txt
CoreWarrior 71 - Innocuous by John Metcalf
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/071.txt
CoreWarrior 75 - nPaper II by Paul-V. Khuong and John Metcalf
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/075.txt
Aggression is a switch by M. Joonas Pihlaja
- http://www.ociw.edu/~birk/COREWAR/PSPACE/HILL/aggression.red
RetroQ by Paul Kline
- http://www.ociw.edu/~birk/COREWAR/94/HILL/retroq.red
Seven by John Metcalf
- http://www.ociw.edu/~birk/COREWAR/94/HILL/seven.red
KafuFFle by John Metcalf
- http://www.ociw.edu/~birk/COREWAR/94/HILL/kafuffle.red
Quickscanners - Part IV
=======================
This part will deal with improved q^2-scanners and the basics of
q^3-scanners.
------------------------------------------------------------------
ATTENTION! While writing this text I noticed, that accidentally my
WilFiz-benchmark is missing the file for Willow, i.e. all results
against the WilFiz-benchmark in part I, II and II are wrong :-(
The version at my homepage will eventually contain the corrected
values. In this part I use the correct benchmark.
------------------------------------------------------------------
1. Current status
=================
You can find the original YAP with a q^1-scanner now at Koenigstuhl
(http://www.ociw.edu/~birk/COREWAR/94/hill_rec.html). Currently it
is 435th with a score of 115.39. YAP II now can also be found at
Koenigstuhl. Its "simple" q^2-scan was enough for rank 372 with
a score of 122.23.
Just to see, where we are, I've benchmarked some of the better
versions of YAP against Wilkies and WilFiz using "pmars -P".
| Wilkies W T L
-------------+-----------------------------------------
original YAP | 116.571059 21.276118 52.752704 25.981178
YAP I | 127.828163 26.127526 49.445584 24.426890
YAP II | 128.609046 26.560697 48.926954 24.512349
| WilFiz W T L
-------------+-----------------------------------------
original YAP | 105.397278 16.747853 55.153720 28.098428
YAP I | 105.002030 18.891275 48.328206 32.780520
YAP II | 113.790433 22.365722 46.693266 30.941012
YAP I is the last version of YAP in part I (on Koenigstuhl as
Yet Another Paper), YAP II (on Koenigstuhl as Yet Another Paper II)
is the last version in part III.
2. Where to scan?
=================
The last part has dealt with a crude theory about where to scan.
The problem of the theory was, that it assumed, that our opponent
does not move (e.g. like imps) and does not place bombs or decoys,
but normal warriors do that all the time :-( That is why you should
probably fight a large amount of warriors to decide, whether your
quickscanner is better than another.
To improve your quickscanner, you might want to change the order
of the scanned positions. Both possibilities are quite easy to do
with YAP II. The easiest one should be to reverse the order of
scans:
....
;;
;; quickscanner
;;
start EQU boot
qStart EQU (start - 200)
qSpace EQU 7700
qNum EQU 18
qStep EQU (-qSpace/qNum)
qHop EQU (qStep/2)
....
This version scores against Wilkies about the same as YAP II, but
against WilFiz it scores more than 0.5 points better:
Wilkies: 128.612785 (W 26.718797, T 48.456394, L 24.824809)
Wilfiz : 114.404670 (W 22.571358, T 46.690595, L 30.738046)
It is easy to change the order of the scanned locations in a
q^2-scanner:
....
qGo sne.i qStart+0*qStep+0*qHop, qStart+0*qStep+1*qHop
seq.i qStart+0*qStep+2*qHop, qStart+0*qStep+3*qHop
jmp attack1, 0
sne.i qStart+2*qStep+0*qHop, qStart+2*qStep+1*qHop
seq.i qStart+2*qStep+2*qHop, qStart+2*qStep+3*qHop
jmp attack1, { attack1
sne.i qStart+4*qStep+0*qHop, qStart+4*qStep+1*qHop
seq.i qStart+4*qStep+2*qHop, qStart+4*qStep+3*qHop
jmp attack1, } attack1
....
becomes for instance:
....
qGo sne.i qStart+4*qStep+0*qHop, qStart+4*qStep+1*qHop
seq.i qStart+4*qStep+2*qHop, qStart+4*qStep+3*qHop
jmp attack1, } attack1
sne.i qStart+0*qStep+0*qHop, qStart+0*qStep+1*qHop
seq.i qStart+0*qStep+2*qHop, qStart+0*qStep+3*qHop
jmp attack1, 0
sne.i qStart+2*qStep+0*qHop, qStart+2*qStep+1*qHop
seq.i qStart+2*qStep+2*qHop, qStart+2*qStep+3*qHop
jmp attack1, { attack1
....
All you have to do is to permute the lines. (Actually you have
to permute complete 3-instruction-sets in this case.)
A random order might not seem better, but if a lot of warriors
use the same quickscanner with the same order of scans, you
might gain a little advantage that way. Especially if a new
quickscanner was published recently, the odds are high, that
the new scanner is used without modifications in your opponents.
3. A better Q^2?
================
As you well know, there are several "rules", that should be
followed, if you want to write a good warrior. (Of course you
can ignore them, if you want to write a better warrior ;-) One
is, that you should not waste a single instruction or even a
single field. Up until now, I have used the following:
....
qGo sne.i qStart+8*qStep+qHop, qStart+8*qStep+qHop
jmp attack1
....
As you can see, the B-field of the jump instruction is NOT used.
How about this version:
....
qGo sne.i qStart+8*qStep+qHop, qStart+8*qStep+qHop
jmp attack1, < qStart+8*qStep+qHop/2
....
This version has a good chance to change an instruction inside our
opponent just 1 cycle after a successful scan. Not much, but this
change is for free. For further reference I name this "attack"
1-cycle-attack.
3.1 One instruction
===================
YAP II has an average reaction time of (4+6.5) instructions, if it
finds something with attack1 and (5+6.5) instructions, if it finds
something with attack2. That's an average of 10.83 instructions
before the first bomb is thrown. Quite a long time. It seems to be
a good idea to change the quickscanner.
One instruction can be easily saved by doing the needed adjustments
for "attack2" during the scan:
....
sne.i qStart+10*qStep+0*qHop, qStart+10*qStep+1*qHop
seq.i qStart+10*qStep+2*qHop, qStart+10*qStep+3*qHop
djn.f attack1, attack1
add.ab # 12*qStep, found ; <-- NEW
sne.i qStart+12*qStep+0*qHop, qStart+12*qStep+1*qHop
seq.i qStart+12*qStep+2*qHop, qStart+12*qStep+3*qHop
jmp attack1, 0
sne.i qStart+14*qStep+0*qHop, qStart+14*qStep+1*qHop
seq.i qStart+14*qStep+2*qHop, qStart+14*qStep+3*qHop
jmp attack1, { attack1
sne.i qStart+16*qStep+0*qHop, qStart+16*qStep+1*qHop
seq.i qStart+16*qStep+2*qHop, qStart+16*qStep+3*qHop
jmp attack1, } attack1
....
dat.f 2*qStep, qStart+8*qStep-found
qTab dat.f 0*qStep, qStart+0*qStep-found
dat.f 4*qStep, qStart+6*qStep-found
attack1 add.ab qTab, qTab
add.b @ attack1, found
....
Now we need an average of 10.5 instruction before the attack
starts, but there is one extra instruction during the scan. The
results with are:
Wilkies: 128.327565 (W 26.458681, T 48.951523, L 24.589796)
WilFiz : 113.373820 (W 22.308572, T 46.448105, L 31.243324)
That seems to be slightly worse than the previous version.
3.2 Two possibilites
====================
When we use the sne/seq-trick, we have to choose between four
possible targets after a successful scan, which takes at the
moment an average of 6.5 instructions:
....
;; choose between the four possible positions
qSelect seq.i (start - 1), @ found
jmp adjust
add.ab # qHop, found
djn qSelect, # 4
....
Choosing between only two positions takes only an average of
1.5 instructions:
....
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
....
Let's see how the following version scores:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 18 ; number of scans
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 39
dat.f 0, 0
rof
;; fast attack
qGo seq.i qStart+0*qStep, qStart+0*qStep+qHop
jmp attack1, < qStart+0*qStep+qHop/2
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1, { attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, } attack1
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, > attack1
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp attack1, < attack1
seq.i qStart+5*qStep, qStart+5*qStep+qHop
djn.f attack1, attack1
;; slow attack
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, < qStart+6*qStep+qHop/2
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, { attack1
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp attack2, } attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack2, > attack1
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp attack2, < attack1
seq.i qStart+11*qStep, qStart+11*qStep+qHop
djn.f attack2, attack1
;; even slower attacks
seq.i qStart+12*qStep, qStart+12*qStep+qHop
jmp attack3, < qStart+12*qStep+qHop/2
seq.i qStart+13*qStep, qStart+13*qStep+qHop
jmp attack3, { attack1
seq.i qStart+14*qStep, qStart+14*qStep+qHop
jmp attack3, } attack1
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, > attack1
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, < attack1
seq.i qStart+17*qStep, qStart+17*qStep+qHop
djn.f attack3, attack1
jmp boot
;; choose target
dat.f 1*qStep, qStart+4*qStep-found
qTab dat.f 0*qStep, qStart+0*qStep-found
dat.f 2*qStep, qStart+3*qStep-found
attack3 add.ab # 6*qStep, found
attack2 add.ab # 6*qStep, found
attack1 add.ab qTab, qTab
add.b @ attack1, found
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
....
This version uses 18 scans (the same number as in YAP II), but
it scores better:
Wilkies: 129.411293 (W 26.923365%, T 48.641200%, L 24.435436%)
WilFiz : 116.761206 (W 23.730398%, T 45.570012%, L 30.699590%)
The first 6 scans need 5.5 instructions (1 jump to attack1,
2 at attack1, 1.5 at qSelect, 1 at adjust), the next 6 scans
need 6.5 instructions (1 at attack2, ...) and the last need
7.5 instructions (1 at attack3, 1 at attack2, ...) before the
bombing starts. That's an average of 6.5 instructions!
Now you might want to try to use a different number of scans,
for example with 22 scans and an additional "attack4" it scores
as follows:
Wilkies: 131.372580 (W 27.865017%, T 47.777529%, L 24.357454%)
WilFiz : 116.482395 (W 24.837094%, T 41.971115%, L 33.191792%)
3.3 The bad table
=================
As you well know, your opponent might have already altered your
code with his first instruction. If he has decremented one of
the 6 jumps to attack3, you could die, because now you could
jump to the last dat-instruction of "qTab" :-( The probability
of this event is very low, but it can be easily prevented.
You can change the dat-instruction to nop-instructions or
place the table at the end or some other safe location inside
your warrior.
You might even want to use a table like this:
mov.i < 1*qStep, < qStart+4*qStep-found
qTab nop 0*qStep, qStart+0*qStep-found
mov.i < 2*qStep, < qStart+3*qStep-found
and "attack" some locations of the core, when these instructions
are accidentally executed.
3.4 Another decoder
===================
So far we have used a quite simple decoder, but there are others,
for example the one of Probe by Anton Marsen. I've taken the
liberty to rewrite it in order to make it more easy to understand.
The decoder uses a set of three different add-instructions:
....
attack3 add.a qTab+1, qTab
attack2 add.ab @ attack3, found
attack1 add.b * attack3, @ attack2
;; choose between the two possible targets
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
....
found mov.i -qStep2, @ qStart ; <-- CHANGED!!
....
A first advantage is, that this decoder has the ability to
attack without any decoding at all, altough this is only possible
for the locations (qStart+0*qstep) and (qStart+0*qStep+qHop):
....
qGo seq qStart+0*qStep, qStart+0*qStep+qHop
jmp qSelect
....
(To make the code more readable, I won't use any 1-cycle-attacks.)
If this scan is successful, it directly starts by choosing the
correct target.
The new decoder uses the following table:
dat.f 10*qStep, 2*qStep
qTab dat.f 4*qStep, 1*qStep
daf.f 23*qStep, 3*qStep
Let's continue with the next scans:
....
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, { attack3
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, } attack3
....
That's nothing new so far.
....
;; "jump > attack1" jumps to attack2
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp > attack1
....
Up until now we have not thought about using the destination
of the jump for the correct calculation of the target, but it
works.
....
seq.i qStart+5*qStep, qStart+5*qStep+qHop
jmp attack2
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, { attack3
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, } attack3
;; "jmp < attack1" jumps to attack3
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp < attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack3
;; "jmp > attack1" jumps to attack2
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp > attack1, < attack3
seq.i qStart+11*qStep, qStart+11*qStep+qHop
jmp attack2, < attack3
seq.i qStart+12*qStep, qStart+12*qStep+qHop
djn.f attack2, attack3
....
Now there is a problem. There is no possiblity to decode
(13*qStep) with this decoder and this table. Probe uses a little
trick to make the decoder nontheless calculate this value.
It stores it somewhere else (see Probe for details).
For (14*qStep) even Probe has no solution. It simply skips this
scan.
....
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, < attack3
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, { attack3
....
And another problem. Probe uses the same trick to decode
(17*qStep) as to decode (13*qStep) :-(
Again Probe doesn't have a way to decode the values for (18*qStep)
and (19*qStep).
....
;; "djn.f < attack1, attack" jumps to attack3
seq.i qStart+20*qStep, qStart+20*qStep+qHop
djn.f < attack1, attack3
....
Again a trick to decode (21*qStep) :-(
....
seq.i qStart+22*qStep, qStart+22*qStep+qHop
djn.f attack3, attack3
;; "jmp > attack1" jumps to attack2
seq.i qStart+23*qStep, qStart+23*qStep+qHop
jmp > attack1, > attack3
seq.i qStart+24*qStep, qStart+24*qStep+qHop
jmp attack2, > attack3
....
Again Probe doesn't have a way to decode the value for (25*qStep),
(26*qStep) and (29*qStep).
....
;; "jmp < attack1" jumps to attack3
seq.i qStart+27*qStep, qStart+27*qStep+qHop
jmp < attack1, > attack3
seq.i qStart+28*qStep, qStart+28*qStep+qHop
jmp attack3, > attack3
seq.i qStart+30*qStep, qStart+30*qStep+qHop
jmp attack3, } attack3
....
Creating this quickscan must have taken an awful lot of time!
If we forget about Probe's trick, we get 21 positions from the
table plus one for free (qStart+0*qStep). Now we have this
quickscan:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 31
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 32
dat.f 0, 0
rof
qGo seq.i qStart+0*qStep, qStart+0*qStep+qHop
jmp qSelect
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack1
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack1, { attack3
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack1, } attack3
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp > attack1
seq.i qStart+5*qStep, qStart+5*qStep+qHop
jmp attack2
seq.i qStart+6*qStep, qStart+6*qStep+qHop
jmp attack2, { attack3
seq.i qStart+7*qStep, qStart+7*qStep+qHop
jmp attack2, } attack3
seq.i qStart+8*qStep, qStart+8*qStep+qHop
jmp < attack1
seq.i qStart+9*qStep, qStart+9*qStep+qHop
jmp attack3
seq.i qStart+10*qStep, qStart+10*qStep+qHop
jmp > attack1, < attack3
seq.i qStart+11*qStep, qStart+11*qStep+qHop
jmp attack2, < attack3
seq.i qStart+12*qStep, qStart+12*qStep+qHop
djn.f attack2, attack3
seq.i qStart+15*qStep, qStart+15*qStep+qHop
jmp attack3, < attack3
seq.i qStart+16*qStep, qStart+16*qStep+qHop
jmp attack3, { attack3
seq.i qStart+20*qStep, qStart+20*qStep+qHop
djn.f < attack1, attack3
seq.i qStart+22*qStep, qStart+22*qStep+qHop
djn.f attack3, attack3
seq.i qStart+23*qStep, qStart+23*qStep+qHop
jmp > attack1, > attack3
seq.i qStart+24*qStep, qStart+24*qStep+qHop
jmp attack2, > attack3
seq.i qStart+27*qStep, qStart+27*qStep+qHop
jmp < attack1, > attack3
seq.i qStart+28*qStep, qStart+28*qStep+qHop
jmp attack3, > attack3
seq.i qStart+30*qStep, qStart+30*qStep+qHop
jmp attack3, } attack3
;; found nothing -> boot paper
jmp boot
;; decoder table
dat.f 10*qStep, 2*qStep
qTab dat.f 4*qStep, 1*qStep
dat.f 23*qStep, 3*qStep
;; decoder
attack3 add.a qTab, qTab
attack2 add.ab @ attack3, found
attack1 add.b * attack3, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
....
There are 3 jumps to attack1, 9 to attack2, 9 to attack3 and
one to qSelect, i.e. it takes an average of 4.68 cycles before
the bombing starts. This quickscan together with YAP scores as
follows:
Wilkies: 131.207003 (W 27.885314%, T 47.551062%, L 24.563624%)
WilFiz : 117.635560 (W 25.191215%, T 42.061915%, L 32.746870%)
Probe uses another order of scans: 0, 1, 2, 3, (13), 4, 5, 6,
7, 10, 11, 12, 23, 24, (17), 8, 9, 15, 16, 20, (21), 22, 27,
28, 30. When we use this order (without 13, 17, 21), YAP scores
as follows:
Wilkies: 131.134363 (W 27.854869%, T 47.569756%, L 24.575375%)
WilFiz : 117.864697 (W 25.285220%, T 42.009037%, L 32.705743%)
Because of the inability of the decoder to generate certain steps,
there are gaps in in quickscan-pattern, that Probe uses. Fortunately
there is a way to minimize the gaps and distribute the scanned
positions more evenly.
Let's use (start + 200) as the first scanned position. I've written
a little program, that checks all values for qStep, i.e.
1 <= qStep <= 7999, whether they create a scan-pattern, that is
between the instruction 200 and 7900. In this list I've looked for
patterns with a good distribution.
With (qStep EQU 1250) the minimal gap between two scans is 250
and the maximal is 500. Together with (qHop EQU 120) and Probe's
order of scans, YAP scores as follows:
Wilkies: 131.365637 (W 27.891189%, T 47.692069%, L 24.416741%)
WilFiz : 117.782442 (W 25.230206%, T 42.091826%, L 32.677969%)
Now, that I think of the last three versions, there shouldn't be
much difference. They scan only different locations, but the rest
is the same. According to the "theory" of part III that is just
the way it should work.
3.5 Further q^2-decoders
========================
As you might have guessed by now, there are other decoders for
q^2-scanners.
3.5.1 Innocuous
===============
Innocuous by John Metcalf contains a quickscanner, that uses a
slightly bigger table than normal:
....
;;
;; quickscanner
;;
start EQU boot ; 1st instruction of warrior
qStart EQU (start + 200) ; 1st scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 29 ; number of scans
qStep EQU (qSpace/qNum) ; distance between 2 scans
qHop EQU (qStep/2) ; distance between 2 scan pos.
for 25
dat.f 0, 0
rof
qA dat.f 10*qStep, 10*qStep
qB dat.f 13*qStep, 13*qStep
qC dat.f 6*qStep, 6*qStep
qD dat.f 1*qStep, 1*qStep
qE dat.f 4*qStep, 4*qStep
;; decoder
nop { qB, { qE
attack3 add.f qD, qB
attack2 add.f @ attack3, found
attack1 add.f * attack3, found
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.f qHopAdd, found ; no, use 2nd! <-- CHANGED
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i qStart-qStep2, @ qStart ; <-- CHANGED
add.f qIncr, found
djn.b throw, # 20
jmp boot ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
qHopAdd dat.f # qHop, # qHop
....
As you can see the label "adjust" and its instruction is missing.
It is no longer necessary, because now the decoder correctly
initializes the bombing routine.
Now let's take a look at the scanner itself (without the 1-cycle-
attacks):
....
qGo seq qStart+0*qStep, qStart+0*qStep+qHop ; 0
jmp qSelect
....
Nothing new, but John Metcalf was so kind to indicate which part
of the table is used for the decoding. This scan needs no decoding
at all!
....
seq qStart+1*qStep, qStart+1*qStep+qHop ; D
jmp attack1
seq qStart+2*qStep, qStart+2*qStep+qHop ; DD
djn.b attack2, { attack2
....
(qStart+3*qStep) is not decoded. I think, that it is not possible
with this decoder, but I have not checked it.
....
seq qStart+4*qStep, qStart+4*qStep+qHop ; E
jmp attack1, } attack3
seq qStart+5*qStep, qStart+5*qStep+qHop ; DE
jmp attack2, { attack2
seq qStart+6*qStep, qStart+6*qStep+qHop ; C
jmp attack1, { attack3
seq qStart+7*qStep, qStart+7*qStep+qHop ; DC
jmp attack2, > attack3
seq qStart+8*qStep, qStart+8*qStep+qHop ; DDC
jmp attack3, > attack3
....
(qStart+9*qStep) is not decoded.
....
seq qStart+10*qStep, qStart+10*qStep+qHop ; A
djn.a attack1, { attack1
seq qStart+11*qStep, qStart+11*qStep+qHop ; DA
jmp attack2, < attack3
seq qStart+12*qStep, qStart+12*qStep+qHop ; DDA
jmp attack3, < attack3
seq qStart+13*qStep, qStart+13*qStep+qHop ; B
jmp attack1, { attack1
seq qStart+14*qStep, qStart+14*qStep+qHop ; DB
jmp attack2
seq qStart+15*qStep, qStart+15*qStep+qHop ; DDB
jmp attack3
seq qStart+16*qStep, qStart+16*qStep+qHop ; CA
djn.f attack2, attack3
seq qStart+17*qStep, qStart+17*qStep+qHop ; EB
jmp attack2, } attack3
....
(qStart+18*qStep) is not decoded.
....
seq qStart+19*qStep, qStart+19*qStep+qHop ; CB
jmp attack2, { attack3
....
(qStart+19*qStep) is not decoded.
....
seq qStart+21*qStep, qStart+21*qStep+qHop ; EEB
jmp attack3, } attack3
seq qStart+22*qStep, qStart+22*qStep+qHop ; CCA
djn.f attack3, attack3
seq qStart+23*qStep, qStart+23*qStep+qHop ; BA
djn.a attack2, { attack1
seq qStart+24*qStep, qStart+24*qStep+qHop ; DAB
djn.a attack3, { attack1
seq qStart+25*qStep, qStart+25*qStep+qHop ; CCB
jmp attack3, { attack3
seq qStart+26*qStep, qStart+26*qStep+qHop ; BB
jmp attack2, { attack1
....
(qStart+27*qStep) is not decoded.
....
seq qStart+28*qStep, qStart+28*qStep+qHop ; DDBB
jmp attack3, { attack1
....
This quickscan has 24 scans, it contains one jump to qSelect, 5
jumps to attack1, 10 jumps to attack2 and 8 jumps to attack3, i.e.
it executes an average of 3.54 instructions before an attack starts.
It scores as follows against Wilkies and WilFiz:
scans | Wilkies
------+-------------------------------------------------------
24 | 132.639512 (W 28.509700%, T 47.110413%, L 24.379887%)
23 | 132.367645 (W 28.431718%, T 47.072491%, L 24.495791%)
22 | 131.879994 (W 28.182818%, T 47.331539%, L 24.485643%)
scans | WilFiz
------+-------------------------------------------------------
24 | 117.597637 (W 25.973700%, T 39.676537%, L 34.349763%)
23 | 118.537687 (W 25.955006%, T 40.672670%, L 33.372324%)
22 | 119.224031 (W 25.910674%, T 41.492010%, L 32.597317%)
21 | 119.513524 (W 25.761120%, T 42.230163%, L 32.008717%)
20 | 119.997436 (W 25.631329%, T 43.103448%, L 31.265222%)
19 | 120.438619 (W 25.495663%, T 43.951630%, L 30.552707%)
18 | 120.064201 (W 25.087595%, T 44.801414%, L 30.110990%)
3.5.2 Aggression is a switch
============================
Aggression is a switch by M. Joonas Pihlaja uses a decoder, that
limits the maximal number of cycles before the bombing starts to
4.5 instructions. It needs an average of 4.17 cycles (24 scans)
before the bombing starts.
I will not describe this decoder here because this text is
already too long, but the version at corewars.jgutzeit.de will
eventually contain a full description. Let's simply assume, that
I was too lazy to try to understand this warrior, which is
probably the truth anyway ;-)
3.5.3 Other decoders?
=====================
There are probably other q^2-decoders out there. If you find one,
please let me know.
4. Results of the contest
=========================
In part III I've invited everybody to create the best quickscanner
(q^1 or q^2 only) for YAP. All warriors had to fight against WilFiz.
Unfortunately there wasn't much interest and I've go only one
entry :-( Anyway the winner is Zul Nadzri. Congratulations!
He has used YAP II along with a slightly modified bombing engine.
1. Zu Nadzri: 113.320408 (W 22.272251%, T 46.503653%, L 31.224095%)
Because of the low number of submissions, there won't be any new
contests for YAP. It would be nice to get good quickscanners for
YAP though.
5. Q^3-Scanners
===============
As you have seen q^2-scans have improved quite a lot over the time,
but are other possibilites. In May 1999 Leonardo Humberto and John
Metcalf published a new type of quickscanner - q^3 (Puddleglum). It
no longer decodes the correct position with a set of additions, but
with some multiplications:
....
;;
;; quickscanner
;;
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 25
dat.f 0, 0
rof
;; decoding table
dat.f 15, 10 ; A, D
qTab dat.f 7, 4 ; B, E
dat.f 13, 11 ; C, F
qGo ...
;; found nothing -> boot paper
...
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i -qStep2, @ qStart ; <-- CHANGED AGAIN
add.f qIncr, found
djn.b throw, # 20
jmp boot ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
....
I've taken the liberty to use the bombing engine IV, that we have
used along with the last versions of YAP. Puddleglum uses a 0.5c
negative bomber, which doesn't need the extra line at "adjust".
This means, that the average number of cycles before an attack
in Puddleglum starts is 1 cycle lower than in the version, that I
present here.
Let's look at the scans (without 1-cycle-attacks):
....
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect
....
This is the usual scan without decoding. During the following
scans there are a lot gaps, which the decoder cannot handle. I
will not mention this anymore, because you should be quite familar
with the problem now.
....
seq found+3*qStep, found+3*qStep+qHop ; E-1
jmp > attack1, < qTab
seq found+4*qStep, found+4*qStep+qHop ; E
jmp > attack1
seq found+5*qStep, found+5*qStep+qHop ; E+1
jmp > attack1, > qTab
seq found+6*qStep, found+6*qStep+qHop ; B-1
jmp attack1, { qTab
seq found+7*qStep, found+7*qStep+qHop ; B
jmp attack1
seq found+8*qStep, found+8*qStep+qHop ; B+1
jmp attack1, } qTab
seq found+9*qStep, found+9*qStep+qHop ; D-1
djn.b > attack1, { attack2
seq found+10*qStep, found+10*qStep+qHop ; D
jmp > attack1, { attack2
seq found+11*qStep, found+11*qStep+qHop ; F
jmp > attack1, } attack2
seq found+13*qStep, found+13*qStep+qHop ; C
jmp attack1, } attack1
seq found+14*qStep, found+14*qStep+qHop ; A-1
djn.a attack1, { attack1
seq found+15*qStep, found+15*qStep+qHop ; A
jmp attack1, { attack1
seq found+18*qStep, found+18*qStep+qHop ; B*E+1-B-E
djn.f attack2, qTab
seq found+21*qStep, found+21*qStep+qHop ; B*E-B
jmp attack2, < qTab
seq found+24*qStep, found+24*qStep+qHop ; B*E-E
jmp attack2, { qTab
seq found+32*qStep, found+32*qStep+qHop ; B*E+E
jmp attack2, } qTab
seq found+35*qStep, found+35*qStep+qHop ; B*E+B
jmp attack2, > qTab
seq found+39*qStep, found+39*qStep+qHop ; C*E-C
djn.b attack2, } attack1
seq found+52*qStep, found+52*qStep+qHop ; C*E
jmp attack2, } attack1
seq found+56*qStep, found+56*qStep+qHop ; A*E-E
djn.a attack2, { attack1
seq found+60*qStep, found+60*qStep+qHop ; A*E
jmp attack2, { attack1
seq found+63*qStep, found+63*qStep+qHop ; B*D-B
djn.b attack2, { attack2
seq found+66*qStep, found+66*qStep+qHop ; B*F-F
djn.a attack2, } attack2
seq found+70*qStep, found+70*qStep+qHop ; B*D
jmp attack2, { attack2
seq found+77*qStep, found+77*qStep+qHop ; B*F
jmp attack2, } attack2
....
In previous quickscanners the scanned locations were all
relative to the beginning of the warrior. Because we can no
longer add a value to the first scanned position, it is necessary
to make the scanned position relative to the label "found".
Now we find an interesting idea:
....
sne found+28*qStep, found+28*qStep+qHop ; B*E
jmz boot, found+28*qStep+qHop-10
....
Normally we would just add a "jmp boot" to the end of the scan, but
if the scan is immediately followed by the decoder, we have a
restricted free scan. It is restricted to a position near
(found+28*qStep+qHop), but it is free.
Before I start to benchmark this quickscan, I have to address a
problem when creating quickscanners. As you have seen they become
more and more complex and it is therefore quite probable, that they
contain bugs. If your quickscanner bombs the found position and
not only near it, there is a simple test for your quickscanner
(CoreWarrior #84).
Append your quickscanner to a "jmp 0" and let it fight against
a simple "jmp 0, 1" with "pmars -b -P -c 500 qscan.red jmp0.red".
If your quickscanner works correctly it should win exactly twice
the number of scanned locations.
Another problem of this quickscanner is, that it is no longer that
easy to assure, that all scanned positions are inside [200,7900],
but for example with (qStep EQU 5400) and (qHop EQU 1300) that is
the case.
Puddleglum's quickscan looks at 27*2+1 locations. This might be a bit
much. It scores as follows against Wilkies and WilFiz (the free scan
is always used and scans are removed from the end, i.e. beginning
with 77, 70, ...):
scaned pos.| Wilkies
-----------+------------------------------------------------------
2*27+1 | 131.955839 (W 28.590352%, T 46.184784%, L 25.224864%)
2*26+1 | 132.661945 (W 28.678481%, T 46.626501%, L 24.695018%)
2*25+1 | 132.218092 (W 28.442935%, T 46.889288%, L 24.667778%)
2*24+1 | 131.983613 (W 28.305132%, T 47.068218%, L 24.626650%)
2*23+1 | 131.836730 (W 28.228219%, T 47.152075%, L 24.619707%)
scaned pos.| WilFiz
-----------+------------------------------------------------------
2*27+1 | 113.860937 (W 25.200295%, T 38.260052%, L 36.539653%)
2*26+1 | 115.350062 (W 25.310858%, T 39.417489%, L 35.271653%)
2*25+1 | 116.271418 (W 25.300709%, T 40.369290%, L 34.330000%)
2*24+1 | 116.930522 (W 25.277208%, T 41.098898%, L 33.623894%)
2*23+1 | 117.677221 (W 25.262253%, T 41.890463%, L 32.847285%)
2*22+1 | 118.061787 (W 25.071572%, T 42.847071%, L 32.081357%)
2*21+1 | 118.561723 (W 25.011751%, T 43.526471%, L 31.461778%)
2*20+1 | 118.797804 (W 24.870743%, T 44.185575%, L 30.943682%)
2*19+1 | 118.991155 (W 24.692347%, T 44.914114%, L 30.393539%)
2*18+1 | 119.000235 (W 24.447186%, T 45.658676%, L 29.894138%)
2*17+1 | 118.976734 (W 24.239414%, T 46.258493%, L 29.502094%)
The full quickscan has 1 jump to qSelect, 6 jumps to attack1 and
20 jumps (19 jumps + 1 fall-through) to attack2. When we use the
bombing engine IV, it takes an average of 4.20 instructions before
the first bomb is thrown. The original quickscan needs only an
average of 3.20 instructions, because it doesn't need to prepare
the bombing (label "adjust").
This is the (more or less ;-) original bombing engine:
....
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; bombing engine V
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
qDist EQU (qTimes*qStep2 - 10)
qLoop mov qBomb, @ found
found mov qBomb, * qStep
sub # qStep2, found
djn qLoop, # qTimes
jmp boot ; start paper
qBomb dat.f { qDist, { 1
....
It scores as follows:
scaned pos.| Wilkies
-----------+------------------------------------------------------
2*27+1 | 131.728304 (W 28.069585%, T 47.519549%, L 24.410866%)
2*26+1 | 131.540828 (W 27.952079%, T 47.684592%, L 24.363330%)
2*25+1 | 131.337863 (W 27.827629%, T 47.854976%, L 24.317395%)
scaned pos.| WilFiz
-----------+------------------------------------------------------
2*27+1 | 112.777208 (W 24.472824%, T 39.358736%, L 36.168440%)
2*26+1 | 113.414413 (W 24.459471%, T 40.036000%, L 35.504529%)
2*25+1 | 114.162714 (W 24.455732%, T 40.795518%, L 34.748750%)
2*24+1 | 114.982588 (W 24.463210%, T 41.592958%, L 33.943832%)
2*23+1 | (to be calculated ...)
2*22+1 | (to be calculated ...)
2*21+1 | (to be calculated ...)
At the point some of you may have noticed, that the q^2-scanner of
Innocuous scores against WilFiz better than this q^3-scanner.
5.1 MiniQ^3
===========
As you have seen a complete q^3-scan may not result in the best
score. Fortunatly John Metcalf was so kind to trim the q^3-scan
to fewer locations (CoreWarrior #75). His MiniQ^3 scans 2*16+1
locations and has the advantage, that it no longer needs an extra
table for its decoder. All necessary values are nicely hidden
inside the quickscan:
....
;; quickscanner
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 52
dat.f 0, 0
rof
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect
seq found+2*qStep, found+2*qStep+qHop ; C-1
jmp > attack1, { attack2
seq found+3*qStep, found+3*qStep+qHop ; C
jmp > attack1
seq found+4*qStep, found+4*qStep+qHop ; C+1
jmp > attack1, } attack2
seq found+5*qStep, found+5*qStep+qHop ; B-1
jmp attack1, < qBomb
seq found+6*qStep, found+6*qStep+qHop ; B
jmp attack1
seq found+7*qStep, found+7*qStep+qHop ; B+1
jmp attack1, > qBomb
seq found+9*qStep, found+9*qStep+qHop ; A-1
djn.b attack1, { attack1
seq found+10*qStep, found+10*qStep+qHop ; B
jmp attack1, { attack1
seq found+12*qStep, found+12*qStep+qHop ; B*C-B
jmp attack2, { attack2
seq found+15*qStep, found+15*qStep+qHop ; B*C-C
jmp attack2, < qBomb
seq found+21*qStep, found+21*qStep+qHop ; B*C+C
jmp attack2, > qBomb
seq found+24*qStep, found+24*qStep+qHop ; B*C+B
jmp attack2, } attack2
seq found+27*qStep, found+27*qStep+qHop ; A*C-C
djn.b attack2, { attack1
seq found+30*qStep, found+30*qStep+qHop ; A*C
jmp attack2, { attack1
;; free scan + boot paper, if found nothing
sne found+18*qStep, found+18*qStep+qHop ; B*C
jmz.f boot, found+18*qStep+qHop-10
;; decoder
attack2 mul.ab # 3, found ; C=3
attack1 mul.b qBomb, @ attack2
;; choose between the two possible positions
qSelect sne.i (start-1), @ found
add.ab # qHop, found
;; bombing engine V
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
qDist EQU (qTimes*qStep2 - 10)
qLoop mov qBomb, @ found
found mov qBomb, * qStep
sub # qStep2, found
djn qLoop, # qTimes
jmp boot, > 10 ; A=10
qBomb dat.f { qDist, { 6 ; B=6
....
YAP with the original MiniQ^3 (and original bombing engine)
scores as follows:
Wilkies: 129.334380 (W 26.811199%, T 48.900782%, L 24.288019%)
WilFiz : 118.624749 (W 23.864462%, T 47.031364%, L 29.104175%)
6. Yet Another Paper III
========================
Just to have another reference point, here is YAP III. Is uses
a q^3-scan (2*18+1 locations) together with bombing engine IV
and 1-cycle-attacks. I've already sent it to Koenigstuhl. At the
moment of writing it was 340th with a score of 126.11. It scores
as follows against Wilkies and Wilfiz:
Wilkies: 130.187369 (W 27.325022%, T 48.212302%, L 24.462676%)
WilFiz : 119.077682 (W 24.473358%, T 45.657608%, L 29.869034%)
The only difference to the version in chapter 5 is, that this
version uses three 1-cycle-attacks. This little change results in
an improvement of about 0.077 points against Wilfiz.
;redcode-94nop
;name Yet Another Paper III
;author Jens Gutzeit
;strategy q^3 -> paper
;assert CORESIZE == 8000
ORG qGo
pStep1 EQU 3913
pStep2 EQU 3035
boot spl 1
spl 1
silk1 spl @ silk1, < pStep1
mov.i } silk1, > silk1
mov.i { silk1, < silk2
silk2 djn.f @ silk2, < pStep2
;;
;; quickscanner
;;
start EQU boot ; first instruction of this warrior
qStep EQU 5400 ; distance between two scans
qHop EQU 1300 ; scan distance within a scan
for 42
dat.f 0, 0
rof
;; decoding table
dat.f 15, 10 ; A, D
qTab dat.f 7, 4 ; B, E
dat.f 13, 11 ; C, F
qGo seq found+1*qStep, found+1*qStep+qHop ; 1
jmp qSelect, < found+1*qStep+qHop/2
seq found+3*qStep, found+3*qStep+qHop ; E-1
jmp > attack1, < qTab
seq found+4*qStep, found+4*qStep+qHop ; E
jmp > attack1, < found+4*qStep+qHop/2
seq found+5*qStep, found+5*qStep+qHop ; E+1
jmp > attack1, > qTab
seq found+6*qStep, found+6*qStep+qHop ; B-1
jmp attack1, { qTab
seq found+7*qStep, found+7*qStep+qHop ; B
jmp attack1, < found+7*qStep+qHop/2
seq found+8*qStep, found+8*qStep+qHop ; B+1
jmp attack1, } qTab
seq found+9*qStep, found+9*qStep+qHop ; D-1
djn.b > attack1, { attack2
seq found+10*qStep, found+10*qStep+qHop ; D
jmp > attack1, { attack2
seq found+11*qStep, found+11*qStep+qHop ; F
jmp > attack1, } attack2
seq found+13*qStep, found+13*qStep+qHop ; C
jmp attack1, } attack1
seq found+14*qStep, found+14*qStep+qHop ; A-1
djn.a attack1, { attack1
seq found+15*qStep, found+15*qStep+qHop ; A
jmp attack1, { attack1
seq found+18*qStep, found+18*qStep+qHop ; B*E+1-B-E
djn.f attack2, qTab
seq found+21*qStep, found+21*qStep+qHop ; B*E-B
jmp attack2, < qTab
seq found+24*qStep, found+24*qStep+qHop ; B*E-E
jmp attack2, { qTab
seq found+32*qStep, found+32*qStep+qHop ; B*E+E
jmp attack2, } qTab
;; free scan + boot paper, if found nothing
sne found+28*qStep, found+28*qStep+qHop ; B*E
jmz boot, found+28*qStep+qHop-12
;; decoder
attack2 mul.b qTab, found
attack1 mul.ab qTab, @ attack2
;; choose between the two possible positions
qSelect sne.i (start - 1), @ found ; use 1st position?
add.ab # qHop, found ; no, use 2nd!
;; prepare bombing
adjust add.ba found, found
;; bombing engine IV
qTimes EQU 20 ; number of bombs to throw
qStep2 EQU 4 ; distance between bombs
throw mov.i qBomb, @ found
mov.i qBomb, * found
found mov.i -qStep2, @ qStep
add.f qIncr, found
djn.b throw, # 20
jmp boot, < 4000 ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
END
7. The Quickscanner-Hill
========================
To give the texts about quickscanners a home, I have decided
to put all texts on http://corewars.jgutzeit.de. At the moment
you will find there only links to my original postings to
rec.games.corewar. As soon as all parts of this text are
published, I'll start to rewrite them and publish a nice-looking
HTML-version. The URL of the English version will definitely be
http://corewars.jgutzeit.de/quickscanners/index.en.html. A german
translation will also be published.
Apart from the texts about quickscanners, there is also a hill
at http://corewars.jgutzeit.de/quickscanner_hill/index.en.html.
It is there to show the possibilities, that quickscanners offer.
The hill has similar rules as my little contest for YAP.
ATTENTION! Altough the rules are similar there are differences:
- Your warrior will fight a different benchmark.
- Your starting point is no longer YAP, but another warrior
(A Quickscanner's Paper), which is published at my homepage
and already at Koenigstuhl (currently 259th, 94nop-hill).
- You can use any quickscanner that you want.
- All rules can be found at
http://corewars.jgutzeit.de/quickscnner_hill/rules.en.html
If you have comments, questions or problems, send an email to
jens@jgutzeit.de (jens [at] jgutzeit [dot] de). Good luck!
8. Preview
==========
The next part (V) will deal with q^3- and q^4-scanners, new
bombing-engines and the a crude theory about where to hit.
Part VI will deal with quickscanners for non-standard cores,
especially for tiny and nano cores. Part VII will deal with
interactions between papers and quickscanners, quickscans for
'88-hills and everything, that I have forgotten to mention so
far. Comments and hints are always welcome and can be sent to
jens@jgutzeit.de (jens [at] jgutzeit [dot] de) or
rec.games.corewar.
At this point I would like to thank John Metcalf for directing
me to the right warriors while I was looking for good
quickscanners.
- Jens Gutzeit
9. Links
========
CoreWarrior 40 - Probe by Anton Marsden
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/040.txt
"Q^2 ala Franz" by Franz
- http://www.ociw.edu/~birk/COREWAR/94/HILL/q2alafranz.red
CoreWarrior 54 - On QScans and CoreWar Strategy
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/054.txt
CoreWarrior 71 - Fixed by Ken Espiritu
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/071.txt
CoreWarrior 71 - Innocuous by John Metcalf
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/071.txt
CoreWarrior 75 - nPaper II by Paul-V. Khuong and John Metcalf
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/075.txt
Aggression is a switch by M. Joonas Pihlaja
- http://www.ociw.edu/~birk/COREWAR/PSPACE/HILL/aggression.red
RetroQ by Paul Kline
- http://www.ociw.edu/~birk/COREWAR/94/HILL/retroq.red
Seven by John Metcalf
- http://www.ociw.edu/~birk/COREWAR/94/HILL/seven.red
KafuFFle by John Metcalf
- http://www.ociw.edu/~birk/COREWAR/94/HILL/kafuffle.red
Facebook
Twitter
Instagram