'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 II) Where to scan? A practical approachTo decide, how good a quickscanner is, you should fight against a benchmark with all possible positions. Using the the usual settings there are 15602 possible (pmars -P). That would take a lot of time. That is why I'll use the Tiny Hill settings (coresize: 800, max. cycles: 8000, max. length: 20, max. process: 20). Later I'll show, that there are quite good other methods. Let's take the following enemy: ;redcode-tiny ;name Sitting Duck ;assert CORESIZE == 800 ORG start start nop # 10, # 11 for 18 nop # 10, # 11 rof jmp start ENDSitting Duck has a length of 20 instructions, doesn't change the core, i.e. places no decoys, bombs, ... and can be killed with one simple dat-bomb. Now the hero of this part: ;redcode-tiny ;name Killer ;assert CORESIZE == 800 ORG wait wait jmp 0 for 19 dat.f 0, 0 rof ENDA fight between these two warrior should alway tie. A "pmars -s 800 -c 8000 -l 20 -d 20 -S 20 -b -P Killer.red SittingDuck.red" results in 1522 ties. But why 1522? The size of the core is 800, 760 without our two warriors. That's why there are (760 + 1) different positions of your two warriors. Apart from that you have to decide, who starts and that make 761*2 = 1522. Now we start changing our hero: ... ORG start target EQU 20 start mov.i bomb, target wait jmp 0 bomb dat.f 0, 0 for 17 dat.f 0, 0 rof ENDNow it hits the first possible enemy position with a bomb. Now Killer wins 2 fights and 1520 ties, because if "Sitting Duck" is at position 20 it is killed regardless of who has executed the first instruction. Using "target EQU 21" results in 4 wins and 1518 ties. If "Sitting Duck" is at position 20 or 21 it gets killed. Using "target EQU 22" results in 6 wins, ..., using "target EQU 25" results in 12 wins, ..., using "target EQU 38" results in 38 wins, using "target EQU 39" results in 40 wins. From now on the value of wins will no longer increase :-( Using "target EQU 781" we have 38 wins and the number of wins starts to decrease. What did we learn? We get the best killing rate, if we throw our bomb somewhere between position 39 and 780. Since "Sittind Duck" dies on being hit by a bomb, we maximize the possibility of finding (!) our enemy with one scan, if the scans somewhere between position 39 and 780. Where to scan? A theoretical approachs - coresize d - minimal distance between the first instructions of the warriors L - maximal length of a warrior v - number of non-"dat 0, 0"-instruction of the enemy warrior (v <= L) (from now on: number of visible instructions)Let's assume, that d = L (standard setting), the initial position of our warrior is randomly chosen from all possible positions, the visible instructions are equally distributed inside the enemy warrior. Note, that the last assumption is NOT true for normal warriors :-( All positions are our from now on relative from the first instruction of our warrior. Apart from that, let's assume, that the enemy uses the maximal possible length. Then there are (s-2*d+1) different positions of the enemy warrior. We have seen, that our chances of finding a warrior are suboptimal, if we scan the first (d-1) or the last (d-1) positions. For scan positions sPos with d <= sPos <= 2*(d-1) the probability of finding the enemy is (sPos - d + 1)/(s - 2 * d + 1) * v/Lv/L is the possibility of finding a visible instruction, IFF (if and only if) the scan position is already inside (!) the enemy warrior. Let's call that value "visibility" from now on. (sPos - d + 1) is the number of scan positions, where we are inside the warrior. That is why the probability of beeing inside the warrior is (sPos - d + 1)/(s - 2 * d + 1).For scan positions sPos with -d + 1 <= sPos <= -1 the probability of finding the enemy is (|sPos|)/(s - 2 * d + 1) * v/LFor all other scan positions, i.e. 2*(d-1) < sPos < -d + 1, the probability of finding the enemy is L/(s - 2 * d + 1) * v/L = v/(s - 2 * d + 1)Now we now, where to place the first scan position, but what happens, if the first scan misses? Where to scan next?Let sPos1 be the first scanned position. Then the enemy must be somewhere between (sPos1 + L) and -1. Using the same arguments as in chapter 2, we should scan only the most probable positions, i.e. a position between (sPos1 + d) and (-d + 1). And now for the bad news. We cannot execute enough scans to cover the complete space between (s + 2 * d - 1) and (-d + 1), because there are practical limitations. We have already seen, that making our quickscanner big is a bad idea. For example there 7700 "high-value" position, when using the standard settings. Each scans covers a range of 100 instructions (best case). Then we would need 7700/100 = 77 scans, i.e. about 38 "double-scans" with seq or sne. But we have already seen, that 38 "double-scans" make our warrior to vulnerable to the opponent's scans :-( We can only space our scans among the "high-value" positions. Better cores?100/7801 * v/L = 0.0128 * v/LIn a tiny core it is: 20/761 * v/L = 0.0263 * v/LIn a nano core it is: 5/71 * v/L = 0.0704 * v/LIn an experimental core it is: 200/55041 = 0.0036 * v/LIt seems, that a quickscanner can find the opponent far more better in nano-cores than in normal cores. Where to hit?Apart from that, it is also very probable, that the enemy is inside a radius of L instructions, but hitting an instruction, that is about L instructions away, has a very low chance of killing the enemy. Hitting instructions near to the found instruction has the highest probability of killing the enemy. The further away we hit, the worse the chances of success become. Bombing engines;redcode-94nop verbose ;name NYAP (Not YAP) ;assert CORESIZE == 8000 ORG qGo ;; ;; quickscanner ;; start EQU qGo ; first instruction of warrior qStart EQU (start + 200) ; 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 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 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 attack1 add.ab qTab, qTab found add.b @ attack1, # 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 ;; bombing engine I throw mov.i qBomb, @ found sub.ab # qStep2, found djn throw, # qTimes jmp boot qBomb dat.f # 1, # 1 ;; ;; waiting to die ;-) ;; for 55 dat.f 0, 0 rof boot jmp 0 ENDHow to benchmark it? The quickscan doesn't take long. Let's say, that 3000 cycles are enough, i.e. we use "pmars -c 3000 -b -P". (I've tested it with 500, 1000, 2000, 3000 and 4000 cycles. After about 3000 cycles the number of wins doesn't increase that much any more.) Against Wilkies (quite old warriors) we win in about 4.61052% of all cases, against WilFiz (still quite old warriors ;-) we win in about 3.02467% of all cases. Let's see how to improve these values. Increasing the target range from 80 to 100 instructions (bDist), while using the same number of bombs, results in lower scores against Wilkies (4.399% wins) and WilFiz (2.677% wins). Let's try this variation: ... adjust sub.ab # (bDist/2), found ; start with bombing from above ;; bombing engine II throw mov.i qBomb, @ found add.ab # qStep2, found djn throw, # qTimes jmp boot ...Now we bomb from below the scanned position. Using the old values (qTimes EQU 20, bDist EQU 80) we have 3.50% wins against Wilkies and 2.33% wins against WilFiz. Bad idea! We already know, that we should hit the instruction we have found and all instructions near it. Let's bomb forwards and backwards: ... ;; choose between the four possible positions find seq.i (start - 1), @ found jmp adjust add.ab # qHop, found djn find, # 4 ;; bombing engine III adjust mov.ba found, found throw mov.i qBomb, @ found mov.i qBomb, { found add.f qBomb, found djn.b throw, # 20 jmp boot qBomb dat.f # -3, # 4 ...With this engine, we have 4.56565% wins against Wilkies (quite as good as engine I) and 6.88606% wins against WilFiz :-) And another engine (Tornado?): ... attack2 add.ab # 12*qStep, found attack1 add.ab qTab, qTab add.b @ attack1, found ; <--- CHANGED! ;; choose between the four possible positions find seq.i (start - 1), @ found jmp adjust add.ab # qHop, found djn find, # 4 ;; bombing engine IV qTimes EQU 20 ; number of bombs to throw qStep2 EQU 4 adjust add.ba found, found throw mov.i qBomb, @ found mov.i qBomb, * found found mov.i -qStep2, @ found add.f incr, found djn.b throw, # 20 jmp boot qBomb dat.f # 0, # qStep2 incr dat.f # -qStep2, # 2*qStep2 ...Now we have 4.94274% wins against Wilkies and 7.14943% wins against WilFiz. Yay! Yet Another Paper;redcode-94nop verbose ;name Yet Another Paper II ;author Jens Gutzeit ;strategy q^2 -> paper ;strategy Better quickscan and bombing engine ;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 + 200) ; 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 47 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 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 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 attack1 add.ab qTab, qTab add.b @ attack1, found ;; choose between the four possible positions find seq.i (start - 1), @ found jmp adjust add.ab # qHop, found djn find, # 4 ;; bombing engine IV qTimes EQU 20 ; number of bombs to throw qStep2 EQU 4 adjust add.ba found, found throw mov.i qBomb, @ found mov.i qBomb, * found found mov.i -qStep2, @ found add.f incr, found djn.b throw, # 20 jmp boot qBomb dat.f # 0, # qStep2 incr dat.f # -qStep2, # 2*qStep2 ENDThis version scores 129.52 (W 27.00%, T 48.53%, L 24.47%) against Wilkies and 118.53 (W 22.75%, T 50.28%, L 26.97%) against WilFiz. Links |