|
'88 Quickscanner: '94 Quickscanner: Description The Q^1-Scan The Q^2-Scan (I) The Q^2-Scan (II) The Q^2-Scan (III) The Q^3 and Mini-Q^3 The Q^4 and Q^4.5 Qscanner for Tiny Hill Qscanner for Nano Hill Webmaster: fizmo_master@yahoo.com Created by Christian Schmidt, 2002,2003,2004 |
The Q^4 Quickscanner A q^4-scanner uses a far more convoluted decoding scheme than we have met so far, but has the advantage, that it uses only one multiplication for decoding and a set of tables, that can be positioned almost freely inside your warrior. In the last chapters I have used names like qStep, qHop, ... for the various variables. While these names made sense in q^1- and q^2-scanners, it became more and more difficult to find the original meanings in more recent quickscanners. That is why I abandon theses names now, apart from "found" and "qSelect" and use new ones. We have now some tables (qTab1, qTab2, qTab3) with some values in it (qa1, qa2, qb1, qb2, qb2, qb3, qc2). Then there is the "magic value" qm and q0 and q1, which replace qAttack1, qAttack2, ... That is all so far. Let's start with the things, we already know and add later all new ideas. First the decoder and its tables:
...
;; tables for decoder
.... empty, qa1 ; empty points to "dat 0, 0"
qTab1 .... empty, qa2
...
... ..., qb1
qTab2 ... ..., qb2
... ..., qb3
...
qTab3 .... ...., qc2
;; decoder
q0 mul.b * q1, found
qSelect sne { qTab1, @ found
q1 add.b qTab2, found
... qTab3, ...
There isn't much new to see. Some constants, one multiplication
to decode the positions and the usual selection between two
possible locations, altough it is no longer directly compared with
a "dat 0, 0". There seems to be a requirement, that we need qTab3
in the A-field at the end. We will soon see why.Let's continue with some scans:
...
qGo seq.i found+qm, found+qm+qb2
jmp qSelect
...
This is the usual scan with no decoding at all.
...
seq.i found+qm*qc2, found+qm*qc2+qb2
jmp q0, } q0
seq.i found+qm*qa1, found+qm*qa1+qb2
djn.a q0, { q0
seq.i found+qm*qa2, found+qm*qa2+qb2
jmp q0, { q0
seq.i found+qm*qb1, found+qm*qb1+qb1
jmp q0, { q1
seq.i found+qm*(qb1-1), found+qm*(qb1-1)+(qb1-1)
djn.b q0, { q1
seq.i found+qm*qb3, found+qm*qb3+qb3
jmp q0, } q1
seq.i found+qm*qb2, found+qm*qb2+qb2
jmp decode
...
Here we use some addressing modes to change the decoder, but the
scanned locations are a little bit odd.Because we change the A-field of q0 during the first three scans, they are called "q0 mutations" and the next three are called "q1 mutations". The odd structure of the scans seems to indicate, that some math is involved. Let's try to understand it. There is only one problem! With scans so far we don't get any information about the values. It would work with any (!) values for qa1, qa2, ... We only have made everything more complicated. At the moment we scan 2*7 locations, which is pathetic. Fortunately we already know a way to squeeze in more scans. We use the sne/seq-trick. At this point David Moore had a very good idea. He wanted to use the scans itself to change the decoder! Let's ignore the the scans with no decoding and start with the first q0-mutation:
...
;; q0 mutations
sne.i found+qm*qc2, found+qm*qc2+qb2
seq.i < qTab3, found+qm*(qc2-1)+qb2
jmp q0, } q0
...
The first and the last line should be clear; the second line is the
interesting one. Let's assume, that at found+qm(qc2-1)+qb2 is a
non-dat-instruction. To decode that position, the decoder adds the
value at qTab2 (in this case qb2) to the first position. That is
why the first position must point to found+qm*(qc2-1). Now we know,
that
found+qm*(qc2-1) = qTab3+(qc2-1)
We use the value (qc2-1) instead of qc2, because "< qTab3" changes
qc2 into (qc2-1). Let's play a little bit:
qm*(qc2-1) = qTab3-found+(qc2-1)
qm*(qc2-1)-(qc2-1) = qTab3-found
(qm-1)*(qc2-1) = qTab3-found
Normally we would divide by (qm-1), but that is not possible, because
all calculations are done modulo CORESIZE :-( Fortunately we can
multiply with the inverse modulo COORESIZE :-) Let's therefore assume,
that
qM * (qm-1) = 1 mod CORESIZE
Now we have:
qc2-1 = (qTab3-found)*qM
qc2 = (qTab3-found)*qM+1
There are other scans:
...
sne.i found+qm*qa1, found+qm*qa1+qb2
seq.i < (qTab1-1), found+qm*(qa1-1)+qb2
djn.a q0, { q0
sne.i found+qm*qa2, found+qm*qa2+qb2
seq.i < qTab1, found+qm*(qa2-1)+qb2
jmp q0, { q0
;; q1 mutations
sne.i found+qm*qb1, found+qm*qb1+qb1
seq.i < (qTab2-1), found+qm*(qb1-1)+(qb1-1)
jmp q0, { q1
seq.i found+qm*(qb1-2), found+qm*(qb1-2)+(qb1-2)
djn.b q0, { q1
sne.i found+qm*qb3, found+qm*qb3+qb3
seq.i < (qTab2+1), found+qm*(qb3-1)+(qb3-1)
jmp q0, } q1
;; no mutations
sne.i found+qm*qb2, found+qm*qb2+qb2
seq < qTab2, found+qm*(qb2-1)+(qb2-1)
jmp q0
...
>From these scans we get the following conditions:
found+qm*(qa1-1) = (qTab1-1)+(qa1-1)
found+qm*(qa2-1) = qTab1+(qa2-1)
found+qm*(qb1-1) = (qTab2-1)+(qb1-1)
found+qm*(qb3-1) = (qTab2+1)+(qb3-1)
found+qm*(qb2-1) = qTab2+(qb2-1)
Or transformed as above:
qa1 = (qTab1-1-found)*qM+1
qa2 = (qTab1 -found)*qM+1
qb1 = (qTab2-1-found)*qM+1
qb2 = (qTab2 -found)*qM+1
qb3 = (qTab2+1-found)*qM+1
qc2 = (qTab3 -found)*qM+1
Some may ask now, why the second q1-mutation does not use the
sne/seq-trick. For an additional scan we would need the value
(qb1-3). That would lead to another condition:
found+qm*(qb1-3) = (qTab2-1)+(qb1-3)
(qm-1)*(qb1-3) = (qTab2-1-found)
qb1-3 = (qTab2-1-found)*qM
qb1 = (qTab2-1-found)*qM+3
Unfortunately this is not the same as the first condition for
qb1 :-(There is another problem. The first scan uses the locations (found+qm) and (found+qm+qb2). The last scan uses (found+qm*qb2) and (found+qm*qb2+qb2). Now:
found+qm*qb2 = found+qm*((qTab2-found)*qM+1)
= found+qm*qM*qTab2-qm*qM*found+qm
= found+qTab2-found+qm
That is why the distance between (found+qm*qb2) and (found+qm) is
only (qTab2-found). As we already know the distance between any
two scans should be at least MINDISTANCE in order to maximize our
chances of finding something. Unfortunately this is not possible.
That is why you should put as much space between qTab2 and found.Here is YAP together with this quickscan:
;redcode-94nop verbose
;name Yet Another Paper IV - test I
;author Jens Gutzeit
;strategy q^4 -> paper
;assert CORESIZE == 8000
ORG qGo
;; paper constants
pStep1 EQU 3913
pStep2 EQU 3035
;; quickscanner constants
start EQU (boot-1)
qTab2 EQU boot
;; qM * (qm-1) = 1 mod 8000
qm EQU 2108
qM EQU 243
qa1 EQU ((qTab1-1-found)*qM+1)
qa2 EQU ((qTab1 -found)*qM+1)
qb1 EQU ((qTab2-1-found)*qM+1)
qb2 EQU ((qTab2 -found)*qM+1)
qb3 EQU ((qTab2+1-found)*qM+1)
qc2 EQU ((qTab3 -found)*qM+1)
;; boot
dat.f 0, < qb1
boot spl 1, < qb2
spl 1, < qb3
;; paper
silk1 spl @ silk1, < pStep1
mov.i } silk1, > silk1
mov.i { silk1, < silk2
silk2 djn.f @ silk2, < pStep2
for 26
dat.f 0, 0
rof
empty dat.f 0, 0
dat.f empty, qa1
qTab1 dat.f empty, qa2
for 28
dat.f 0, 0
rof
;;
;; quickscanner
;;
qGo seq.i found+qm, found+qm+qb2
jmp qSelect
; q0 mutations
sne.i found+qm*qc2, found+qm*qc2+qb2
seq.i < qTab3, found+qm*(qc2-1)+qb2
jmp q0, } q0
sne.i found+qm*qa1, found+qm*qa1+qb2
seq.i < (qTab1-1), found+qm*(qa1-1)+qb2
djn.a q0, { q0
sne.i found+qm*qa2, found+qm*qa2+qb2
seq.i < qTab1, found+qm*(qa2-1)+qb2
jmp q0, { q0
;; q1 mutations
sne.i found+qm*qb1, found+qm*qb1+qb1
seq.i < (qTab2-1), found+qm*(qb1-1)+(qb1-1)
jmp q0, { q1
seq.i found+qm*(qb1-2), found+qm*(qb1-2)+(qb1-2)
djn.b q0, { q1
sne.i found+qm*qb3, found+qm*qb3+qb3
seq.i < (qTab2+1), found+qm*(qb3-1)+(qb3-1)
jmp q0, } q1
;; no mutations
sne.i found+qm*qb2, found+qm*qb2+qb2
seq < qTab2, found+qm*(qb2-1)+(qb2-1)
jmp q0
jmp boot
;; decoder
q0 mul.b * q1, found
qSelect sne { qTab1, @ found
q1 add.b qTab2, found
;; prepare bombing
add.ba * qTab3, 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, @ qm
add.f qIncr, found
djn.b throw, # qTimes
jmp boot ; start paper
qBomb dat.f # 0, # qStep2
qIncr dat.f # -qStep2, # 2*qStep2
qTab3 dat.f # found, # qc2
END
This program scores as follows:
Wilkies: 126.818677 (W 25.676729%, T 49.788489%, L 24.534782%) WilFiz : 117.143635 (W 22.830406%, T 48.652416%, L 28.517177%)That is a nice result. We only have 2*14 scanned locations with an average of 3.43 instructions before the first bomb is thrown. There are three advantages of this quickscanner. 1. It is small, because we often use the sne/seq-trick. 2. Altough we use the sne/seq-trick, we need only an average of 1.5 instructions to choose among the possible locations. 3. The tables can almost freely be positioned inside the warrior. Before we try to improve that, let's examine, which locations are scanned. Unfortunately we get some complex expressions, which "only" depend on the positions of found, qTab1, qTab2, qTab3 and of course of qm and qM. The scanned locations are:
found+qm found+qm+qb2
found+qm*qc2 found+qm*qc2+qb2
found+qm*(qc2-1) found+qm*(qc2-1)+qb2
found+qm*qa1 found+qm*qa1+qb2
found+qm*(qa1-1) found+qm*(qa1-1)+qb2
found+qm*qa2 found+qm*qa2+qb2
found+qm*(qa2-1) found+qm*(qa2-1)+qb2
found+qm*qb1 found+qm*qb1+qb1
found+qm*(qb1-1) found+qm*(qb1-1)+(qb1-1)
found+qm*(qb1-2) found+qm*(qb1-2)+(qb1-2)
found+qm*qb3 found+qm*qb3+qb3
found+qm*(qb3-1) found+qm*(qb3-1)+(qb3-1)
found+qm*qb2 found+qm*qb2+qb2
found+qm*(qb2-1) found+qm*(qb2-1)+(qb2-1)
That means, that this quickscanner (YAP IV - test I) looks at the
following locations:
693, 1401, 1557, 1645, 1697, 1889, 1941, 2201, 2802, 3202, 3289, 3342, 3509, 3586, 3665, 3753, 3776, 3805, 3846, 3997, 4049, 4911, 5310, 5398, 5450, 5694, 5885, 7293.You can see, that some locations are too close to each other. The minimal distance between two scans is 23! And we know, that it should be at least MINDISTANCE to have a optimal chance to find the opponent. If we search through all possibilites of (qm, qM), we finally find the pair (1212, 3891). With these values the following positions are scanned: 386, 657, 1305, 1474, 1598, 2029, 2465, 2686, 3061, 3241, 3334, 3677, 3840, 4057, 4274, 4494, 4925, 5053, 5270, 5487, 5706, 5921, 6137, 6357, 7133, 7349, 7445, 7569.What makes them so different? The minimal distance between any two locations is now 93 (the best possible!). And there are only two pairs with a difference lower than 100. Keep in mind, that the optimal numbers for (qm, qM) depend on the positions of found, qTab1, qTab2 and qTab3! You have to recalculate them, if you've changed these positions. YAP IV - test I with the new values scores as follows: Wilkies: 128.386318 (W 26.446930%, T 49.045528%, L 24.507542%) WilFiz : 119.141777 (W 23.674849%, T 48.117229%, L 28.207922%)+1.57/+2.00 points :-) Let's try another bombing engine ... just for fun.
...
;; decoder
q0 mul.b * q1, found
qSelect sne { qTab1, @ found
q1 add.b qTab2, found
;; bombing engine VI
qOffset EQU -86
qTimes EQU 19 ; number of bombs to throw
qStep EQU -7 ; distance between bombs
throw mov.i qTab3, @ found
found mov.i qBomb, } qm
sub # qStep, found
djn throw, # qTimes
jmp boot ; start paper
qBomb dat.f > qOffset, > qc2
END
...
Together with 32 DATs instead of 28 above, qm = 460 and qM = 3939
the new version (YAP IV - test II) scores as follows:
Wilkies: 127.600628% (W 26.092274%, T 49.323805%, L 24.583921%) WilFiz : 122.595394% (W 25.290561%, T 46.723711%, L 27.985728%)
;redcode-94nop verbose
;name Yet Another Paper IV - test III
;author Jens Gutzeit
;strategy q^4 -> paper
;assert CORESIZE == 8000
ORG qGo
;; paper constants
pStep1 EQU 3913
pStep2 EQU 3035
;; quickscanner constants
start EQU (boot-1)
qTab2 EQU boot
qTab3 EQU qBomb
;; qM * (qm-1) = 1 mod 8000
qm EQU 460
qM EQU 3939
qa1 EQU ((qTab1-1-found)*qM+1)
qa2 EQU ((qTab1 -found)*qM+1)
qb1 EQU ((qTab2-1-found)*qM+1)
qb2 EQU ((qTab2 -found)*qM+1)
qb3 EQU ((qTab2+1-found)*qM+1)
qc2 EQU ((qTab3 -found)*qM+1)
dat.f 0, < qb1
boot spl 1, < qb2
spl 1, < qb3
silk1 spl @ silk1, < pStep1
mov.i } silk1, > silk1
mov.i { silk1, < silk2
silk2 djn.f @ silk2, < pStep2
for 26
dat.f 0, 0
rof
empty dat.f 0, 0
dat.f empty, qa1
qTab1 dat.f empty, qa2
for 28
dat.f 0, 0
rof
;;
;; quickscanner
;;
qGo ; q0 mutations
sne.i found+qm*qc2, found+qm*qc2+qb2
seq.i < qTab3, found+qm*(qc2-1)+qb2
jmp q0, } q0
sne.i found+qm*qa1, found+qm*qa1+qb2
seq.i < (qTab1-1), found+qm*(qa1-1)+qb2
djn.a q0, { q0
sne.i found+qm*qa2, found+qm*qa2+qb2
seq.i < qTab1, found+qm*(qa2-1)+qb2
jmp q0, { q0
;; q1 mutations
sne.i found+qm*qb1, found+qm*qb1+qb1
seq.i < (qTab2-1), found+qm*(qb1-1)+(qb1-1)
jmp q0, { q1
sne.i found+qm*qb3, found+qm*qb3+qb3
seq.i < (qTab2+1), found+qm*(qb3-1)+(qb3-1)
jmp q0, } q1
;; no mutation
sne.i found+qm*qb2, found+qm*qb2+qb2
seq < qTab2, found+qm*(qb2-1)+(qb2-1)
jmp q0
;; qm mutation
seq.i > found, found+qm+(qb2-1)
jmp qSelect, < found
;; q0 mutation
seq.i found+(qm+1)*(qc2-1), found+(qm+1)*(qc2-1)+(qb2-1)
jmp q0, } q0
seq.i found+(qm+1)*(qa2-1), found+(qm+1)*(qa2-1)+(qb2-1)
jmp q0, { q0
seq.i found+(qm+1)*(qa1-1), found+(qm+1)*(qa1-1)+(qb2-1)
djn.a q0, { q0
;; no mutation (free scan)
jmz.f boot, found+(qm+1)*(qb2-1)+(qb2-1)
;; decoder
q0 mul.b * q1, found
qSelect sne { qTab1, @ found
q1 add.b qTab2, found
;; bombing engine VI
qOffset EQU -86
qTimes EQU 19 ; number of bombs to throw
qStep EQU -7 ; distance between bombs
throw mov.i qTab3, @ found
found mov.i qBomb, } qm
sub # qStep, found
djn throw, # qTimes
jmp boot ; start paper
qBomb dat.f > qOffset, > qc2
END
This version scans the following locations:
found+qm*qc2 found+qm*qc2+qb2
found+qm*(qc2-1) found+qm*(qc2-1)+qb2
found+qm*qa1 found+qm*qa1+qb2
found+qm*(qa1-1) found+qm*(qa1-1)+qb2
found+qm*qa2 found+qm*qa2+qb2
found+qm*(qa2-1) found+qm*(qa2-1)+qb2
found+qm*qb1 found+qm*qb1+qb1
found+qm*(qb1-1) found+qm*(qb1-1)+(qb1-1)
found+qm*qb3 found+qm*qb3+qb3
found+qm*(qb3-1) found+qm*(qb3-1)+(qb3-1)
found+qm*qb2 found+qm*qb2+qb2
found+qm*(qb2-1) found+qm*(qb2-1)+(qb2-1)
found+qm found+qm+(qb2-1)
found+(qm+1)*(qc2-1) found+(qm+1)*(qc2-1)+(qb2-1)
found+(qm+1)*(qa2-1) found+(qm+1)*(qa2-1)+(qb2-1)
found+(qm+1)*(qa1-1) found+(qm+1)*(qa1-1)+(qb2-1)
found+(qm+1)*(qb2-1)+(qb2-1)
With qm = 460 and qM = 3939 the following locations are scanned:
215, 315, 555, 1203, 1430, 1675, 1795, 1890, 2135, 2255, 3348, 3469, 3590, 3695, 3809, 3930, 4051, 4155, 5089, 5210, 5345, 5490, 5590, 5735, 5950, 6050, 6195, 6289, 7355, 7476, 7611, 7755, 7855.The minimal distance between any two of theses locations is 94. It scores as follows: Wilkies: 128.884652 (W 26.725740%, T 48.707431%, L 24.566829%) WilFiz : 124.425287 (W 26.394052%, T 45.243131%, L 28.362817%)How you might ask, why you cannot simply add even more scans to this one. Try it! Using the same ideas the quickscanner already provides, you either decode the wrong position or get a position, that was already scanned or is too near to one :-(
;redcode-94nop verbose
;name Yet Another Paper V
;author Jens Gutzeit
;strategy qscan -> paper
;assert CORESIZE == 8000
ORG qGo
;; boot constants
pAway1 EQU 2000
pAway2 EQU 6000
decoy EQU 4000
;; paper constants
pStep1 EQU 3913
pStep2 EQU 3035
;; quickscanner constants
qTab2 EQU boot
qTab3 EQU qBomb
qm EQU 160
qM EQU 6239 ;; qM * (qm-1) = 1 mod 8000
qa1 EQU ((qTab1-1-found)*qM+1)
qa2 EQU ((qTab1 -found)*qM+1)
qb1 EQU ((qTab2-1-found)*qM+1)
qb2 EQU ((qTab2 -found)*qM+1)
qb3 EQU ((qTab2+1-found)*qM+1)
qc2 EQU ((qTab3 -found)*qM+1)
;;
;; boot
;;
dat.f 0, < qb1
boot spl 1, < qb2 ; qTab2
spl 1, < qb3
;; make two copies of the paper
mov.i { silk1, { pBoot1
pBoot1 spl pAway1, < decoy
mov.i } pBoot1, > pBoot2
pBoot2 spl pAway2, pAway2
;; paper
silk1 spl @ silk1 + 4, < pStep1
mov.i } silk1, > silk1
mov.i { silk1, < silk2
silk2 djn.f @ silk2, < pStep2
for 22
dat.f 0, 0
rof
empty dat.f 0, 0
dat.f empty, qa1
qTab1 dat.f empty, qa2
for 28
dat.f 0, 0
rof
;;
;; quickscanner
;;
qBomb dat.f > qOffset, > qc2
qGo ; q0 mutations
sne.i found+qm*qc2, found+qm*qc2+qb2
seq.i < qTab3, found+qm*(qc2-1)+qb2
jmp q0, } q0
sne.i found+qm*qa1, found+qm*qa1+qb2
seq.i < (qTab1-1), found+qm*(qa1-1)+qb2
djn.a q0, { q0
sne.i found+qm*qa2, found+qm*qa2+qb2
seq.i < qTab1, found+qm*(qa2-1)+qb2
jmp q0, { q0
;; q1 mutations
sne.i found+qm*qb1, found+qm*qb1+qb1
seq.i < (qTab2-1), found+qm*(qb1-1)+(qb1-1)
jmp q0, { q1
sne.i found+qm*qb3, found+qm*qb3+qb3
seq.i < (qTab2+1), found+qm*(qb3-1)+(qb3-1)
jmp q0, } q1
;; no mutation
sne.i found+qm*qb2, found+qm*qb2+qb2
seq < qTab2, found+qm*(qb2-1)+(qb2-1)
jmp q0, < found+qm*qb2
;; qm mutation
seq.i > found, found+qm+(qb2-1)
jmp qSelect, < found
;; q0 mutation
seq.i found+(qm+1)*(qc2-1), found+(qm+1)*(qc2-1)+(qb2-1)
jmp q0, } q0
seq.i found+(qm+1)*(qa2-1), found+(qm+1)*(qa2-1)+(qb2-1)
jmp q0, { q0
seq.i found+(qm+1)*(qa1-1), found+(qm+1)*(qa1-1)+(qb2-1)
djn.a q0, { q0
;; no mutation (free scan)
jmz.f boot, found+(qm+1)*(qb2-1)+(qb2-1)
;; decoder
q0 mul.b * q1, found
qSelect sne { qTab1, @ found
q1 add.b qTab2, found
;; bombing engine VI
qOffset EQU -86
qTimes EQU 19 ; number of bombs to throw
qStep EQU -7 ; distance between bombs
throw mov.i qTab3, @ found
found mov.i qBomb, } qm
sub # qStep, found
djn throw, # qTimes
jmp boot, < 4000 ; start paper
END
You can find YAP V already at Koenigstuhl (183th) with a score of
140.07. On August 13, 2005 it entered the 94nop-hill at koth.org
as 18th and died one day later at the age of 8. I've never exptected
it to enter the hill :-)
Just to have a reference, it scores as follows against Wilkies and
WilFiz:
Wilkies: 138.487053 (W 28.778362%, T 52.151965%, L 19.069671%) WilFiz : 135.584113 (W 29.262274%, T 47.797291%, L 22.940435%) |