'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 The Idea behind Q^4 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-foundNormally 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 CORESIZENow we have: qc2-1 = (qTab3-found)*qM qc2 = (qTab3-found)*qM+1There 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+1Some 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+3Unfortunately 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+qmThat 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 ENDThis 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%) Some More Scans: The Q^4.5 ;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 ENDThis 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 :-( A final version of YAP;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 ENDYou 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%) |