'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^2 Quickscanner (Part III) Current statusJust 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.941012YAP 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. Where to scan?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. A better Q^2?... 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. One instructionOne 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. Two possibilites... ;; 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%) The bad tableYou 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-foundand "attack" some locations of the core, when these instructions are accidentally executed. Another decoderThe 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*qStepLet'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. Innocuous... ;; ;; 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%) Aggression is a switchLinksQ^2 ala Franz by Franz CoreWarrior 54 - On QScans and CoreWar Strategy CoreWarrior 71 - Fixed by Ken Espiritu CoreWarrior 71 - Innocuous by John Metcalf CoreWarrior 75 - nPaper II by Paul-V. Khuong and John Metcalf Aggression is a switch by M. Joonas Pihlaja RetroQ by Paul Kline Seven by John Metcalf KafuFFle by John Metcalf |