From: Jens Gutzeit
Subject: Quickscanners - Part II
Date: Sat, 09 Jul 2005 00:52:12 +0200
Message-ID:
Quickscanners - Part II
=======================
This part deals only with the second generation of quickscanners. You
have to wait for part III before I try to cover the more recent
improvements.
1. Better response time
=======================
The main problem, despite the "early attacks", is, that it still takes
too many cycles before an attack starts. Why not jump to the attack
right after a successful scan?
qGo seq.i 100, 200
jmp attack
seq.i 300, 400
jmp attack
...
jmp boot ; found nothing -> start warrior
attack ...
The only problem is, that now we don't know where to attack :-(
Fortunatly all you need is a little table and some addressing modes.
qGo seq.i 100, 200
jmp attack, 0
seq.i 300, 400
jmp attack, { attack
seq.i 500, 600
jmp attack, } attack
seq.i 700, 800
jmp attack, < attack
seq.i 900, 1000
jmp attack, > attack
Here is a first version of the new quickscanner together with our
beloved YAP.
;redcode-94nop verbose
;name Yet Another Paper (YAP)
;author Jens Gutzeit
;strategy 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 warrior
qStart EQU (start + 230) ; first scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 6 ; number of scans
qStep EQU (qSpace/qNum) ; distance between two scans
qHop EQU (qStep/2)
for 68
dat.f 0, 0
rof
qGo seq.i qStart+0*qStep, qStart+0*qStep+qHop
jmp attack, 0 ; A
seq.i qStart+1*qStep, qStart+1*qStep+qHop
jmp attack, { attack ; B
seq.i qStart+2*qStep, qStart+2*qStep+qHop
jmp attack, } attack ; C
seq.i qStart+3*qStep, qStart+3*qStep+qHop
jmp attack, > attack ; D
seq.i qStart+4*qStep, qStart+4*qStep+qHop
jmp attack, < attack ; E
seq.i qStart+5*qStep, qStart+5*qStep+qHop
djn.f attack, attack ; F
jmp boot
;; choose target
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
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
attack add.ab qTab, qTab
found mov.b @ attack, # 0
;; choose between the two possible positions
sne.i (start - 1), @ found ; use first position?
add.ab # qHop, found ; no, use second one
add.ab # (bDist/2), found ; start with bombing from above
;; bomb target
throw mov.i qBomb, @ found
sub.ab # qStep2, found
djn throw, # qTimes
jmp boot
qBomb dat.f # 1, # 1
END
How does it work? Let's examine each scan. When the scanner finds
something, it jumps at once to "attack" and while jumping, it might
change the fields at "attack". The attack-instruction calculates the
correct position. The next instruction moves the result into the
"found"-field, that we need for our attack.
Forget the "...-found"-part in qTab. They are only there to make the
result, which is copied to "found", point to the correct position.
Using jump A, there are no changes made. The A-field of qTab (0*qStep)
is added to the B-field of qTab (qStart+0*qStep), resulting in
(qStart+0*qStep). The next instruction moves this result to our old
friend "found". And now we have the correct value at the right position.
Using jump B, we need the value (qStart+1*qStep). The jump changes our
attack-instruction to "add.ab qTab-1, qTab", which adds (1*qStep) to
(qStart+0*qStep). After the next instruction, we have (qStart+1*qStep)
at "found".
Using jump C, we need the value (qStart+2*qStep). The jump changes our
attack-instruction to "add.ab qTab+1, qTab", which adds (2*qStep) to
(qStart+0*qStep). After the next instruction, we have (qStart+2*qStep)
at "found".
Using jump D, we need the value (qStart+3*qStep). The jump changes our
attack-instruction to "add.ab qTab, qTab+1", which adds (0*qStep) to
(qStart+3*qStep). After the next instruction, we have (qStart+3*qStep)
at "found".
Using jump E, we need the value (qStart+4*qStep). The jump changes our
attack-instruction to "add.ab qTab, qTab-1", which adds (0*qStep) to
(qStart+4*qStep). After the next instruction, we have (qStart+4*qStep)
at "found".
Using jump F, we need the value (qStart+5*qStep). The jump changes our
attack-instruction to "add.ab qTab-1, qTab-1", which adds (1*qStep) to
(qStart+4*qStep). After the next instruction, we have (qStart+5*qStep)
at "found".
Well, it seems to work. This version of YAP scores 121.97 (W 23.47%,
T 51.54%, L 24.98%) against Wilkies with just 6 scans. Our first version
with 6 scans (see part I) scored 121.93 (W 23.57%, T 51.53%, L 25.00%)
against Wilkies.
How long does it take, before the first bomb is thrown? Having found
something, we execute a jump to the attack, a possibly changed
"add.ab qTab, qTab" and a "mov.b @ attack, # 0". After that, we have
to decide, which position to use (1.5 instructions) and change the
target-pointer "found". That makes an average of 5.5 instruction
before the attack starts.
2. More scans
=============
With 6 scans YAP scores only 4 points better than the original version
without a quickscanner. As you already know, we can do better. We use
the sne/seq-trick introduced in part I.
...
;;
;; quickscanner
;;
start EQU boot ; first instruction of warrior
qStart EQU (start + 230) ; first scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 12 ; number of scans
qStep EQU (qSpace/qNum) ; distance between two scans
qHop EQU (qStep/2)
for 60
dat.f 0, 0
rof
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 attack, 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 attack, { attack
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 attack, } attack
sne.i qStart+6*qStep+0*qHop, qStart+6*qStep+1*qHop
seq.i qStart+6*qStep+2*qHop, qStart+6*qStep+3*qHop
jmp attack, > attack
sne.i qStart+8*qStep+0*qHop, qStart+8*qStep+1*qHop
seq.i qStart+8*qStep+2*qHop, qStart+8*qStep+3*qHop
jmp attack, < attack
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 attack, attack
jmp boot
;; choose target
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
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
attack add.ab qTab, qTab
found mov.b @ attack, # 0
;; choose between the four possible positions
find seq.i (start - 1), @ found
jmp adjust
add.ab # qHop, found
djn find, # 4
adjust add.ab # (bDist/2), found ; start with bombing from above
...
Apart from using the sne/seq-trick, we have to change qTab and to
choose between four values now, but you already know that from
part I. Using 12 scans now, YAP scores 124.94 (W 24.93%,T 50.16%,
L 24.91%) against Wilkies. The old version with sne/seq-Trick
with no early attack and 12 scans scored 125.54 (W 25.12%, T 50.19%,
L 24.69%).
3. Even more scans
==================
Now you might want to remind me, that in part I we already had a
version, that scored 129.37 and our best version so far scores only
124.94. Here is a better version:
;;
;; quickscanner
;;
start EQU boot ; first instruction of warrior
qStart EQU (start + 230) ; first scanned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 18 ; number of scans
qStep EQU (qSpace/qNum) ; distance between two scans
qHop EQU (qStep/2) ; distance between two scan positions
for 50
dat.f 0, 0
rof
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
sne.i qStart+6*qStep+0*qHop, qStart+6*qStep+1*qHop
seq.i qStart+6*qStep+2*qHop, qStart+6*qStep+3*qHop
jmp attack1, > attack1
sne.i qStart+8*qStep+0*qHop, qStart+8*qStep+1*qHop
seq.i qStart+8*qStep+2*qHop, qStart+8*qStep+3*qHop
jmp attack1, < attack1
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
;;
;; ---> NEW PART <---
;;
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 attack2, 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 attack2, { 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 attack2, } attack1
jmp boot
;; choose target
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
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
attack2 add.ab # 12*qStep, found ; <--- NEW INSTRUCTION
attack1 add.ab qTab, qTab
found add.b @ attack1, # 0 ; <--- CHANGED INSTRUCTION
...
The first 12 scans work as before. If something is found, they jump
to attack1, where the correct position is calculated. The instruction
at "found" no longer moves the position to be b-field, but adds the
result to zero. Fortunately this has the same effect.
I've added 6 scans, that execute only one additional instruction,
when they lead to an attack. They jump to "attack2", which adjusts
the b-field of "found". It contains now the value (12*qStep), which
is the offset of the first new scan. Then the normal decoding is
done, the value is added to (12*qStep) and we get the desired
position.
Using 16, 18 and 20 scans, we score as follows against Wilkies:
16 scans: 126.63 (W 25.43%, T 50.33%, L 24.24%)
18 scans: 129.01 (W 26.38%, T 49.87%, L 23.75%)
20 scans: 128.37 (W 26.29%, T 49.50%, L 24.21%)
4. Links
========
CoreWarrior # 37
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/037.txt
The Fugitive by David Moore (simple and quite clear q^2)
- http://www.ociw.edu/~birk/COREWAR/94/HILL/fugitive.red
5. The next part ...
====================
... will deal with better decoding routines for q^2-scanners and
maybe with the basics of q^3-scanners.
I've already decided to republish all parts once they are finished
to correct errors and possibly incorporate more tips. Please send
all comments and ideas to r.g.c.
- Jens Gutzeit