|
'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^1 Quickscanner Therefore it is needful to understand quickscanner, not only to use it to improve warriors, but also to learn how to handle them as effective as possible. As all other special techniques and strategies in corewar also quickscanner were constantly developed and improved. In the following tutorial we will discuss it in chronological order starting right from the first attempts until the latest, state-of-the-art Q^4.5-scanner.
;redcode-94nop verbose
;name Yet Another Paper (YAP)
;author Jens Gutzeit
;strategy paper
;assert CORESIZE == 8000
ORG boot
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
END
If you don't know what a paper is or how it works, we suggest, that
you read the paper-tutorial
at first.Don't think, that YAP is a good paper. It is simply used to show the usefulness of a quickscanner. The values for pStep1 and pStep2 are choosen after a very short session with an optimizer. It scores about 117.7 (W 21.68%, T 52.64%, L 25.68%) against Wilkies and about 110.2 (W 17.04%, T 59.13%, L 23.84%) against WilFiz. That is certainly not enough to enter any hill at koth.org, but it should be enough for the beginner's hill. The original quick-scan, as first used in Paul Kline's QuickFreeze, consists of alternating SEQ and MOV statements. It simply unrolls a normal scan-loop like this:
qGo seq.i 100, 200 ; are instructions at 100 and 200 equal?
mov # 100, found ; yes -> store 100
seq.i 300, 400 ; are instructions at 300 and 400 equal?
mov # 300, found ; yes -> store 3000
seq.i 500, 600
mov # 500, found
...
seq.i 7500, 7600
mov # 7500, found
seq.i 7700, 7800
mov # 7700, found
found jmz boot, # 0 ; start paper, if found nothing :-(
attack ...
That way we scan 2 positions per instruction, i.e. we scan at 2c.When the series of SEQ/MOV instructions is done executing, the process can then check the standard location referenced by the MOV instructions to see if any of the comparisons failed. If any did, then your program can take advantage of this knowledge by attacking whatever was found. Since what was found is very likely to be your opponent's original code, it is often possible to harm your opponent while they are still getting started. Let's see how well this works. Here is YAP with a simple quickscanner:
ORG qGo
boot ... ; nothing new here
;;
;; quickscan
;;
start EQU boot ; first instruction of this warrior
qStart EQU (start + 230) ; first scaned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 25 ; number of scans
qStep EQU (qSpace/qNum) ; distance between two scans
qHop EQU (qStep/2) ; distance betweens two scan positions
;; put as much space between the paper and the quickscan as possible
for (85 - 2 * qNum)
dat.f 0, 0
rof
qGo
i for qNum
seq.i qStart+(i-1)*qStep, qStart+(i-1)*qStep+qHop
mov.ab # qStart+(i-1)*qStep-found, found
rof
found jmz boot, # 0 ; B-Field != 0 -> quickscan found sth.
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
;; choose between the two scan positions
find sne.i (start - 1), @ found ; hit first position?
add.ab # qHop, found ; use second one
add.ab # (bDist/2), found ; start with bombing from above
;; bomb target
attack mov.i qBomb, @ found
sub.ab # qStep2, found
djn attack, # qTimes
jmp boot
qBomb dat.f # 1, # 1
END
If the quickscan finds something, it stores the lower scan position
at "found". If the b-field of "found" is non-zero, the attack starts
by choosing between the two possible scan positions ("find"). After
that the found position is bombed linearly from above with qTimes
bombs. There are better methods to bomb the enemy, but this methode
is good enought for new.Not counting the attack code, there are 85 instructions left for the quickscan, i.e. there are max. 42 scans possible. Using the Wilkies- benchmark we get the following scores: qTimes Wilkies gain 42 119.35 (W 23.66%, T 48.38%, L 27.97%) + 1.65 41 40 39 38 37 36 35 122.44 (W 24.47%, T 49.02, L 26.51%) + 4.74 34 33 32 31 30 29 28 27 26 127.23 (W 26.10%, T 48.93%, L 24.97%) + 9.53 25 128.68 (W 26.57%, T 48.96%, L 24.47%) +10.98 24 127.61 (W 26.23%, T 48.91%, L 24.86%) + 9.91 23 127.51 (W 26.13%, T 49.11%, L 24.76%) + 9.81 22 125.04 (W 25.41%, T 48.82%, L 25.78%) + 7.34 21 20 127.25 (W 25.89%, T 49.57%, L 24.53%) + 9.55 19 18 17 16 15 14 13 12 11 10 9 122.55 (W 23.80%, T 51.15%, L 25.05%) + 4.85 8 122.61 (W 23.93%, T 50.81%, L 25.26%) + 4.91 7 120.92 (W 23.13%, T 51.52%, L 25.35%) + 3.22 6 121.93 (W 23.57%, T 51.53%, L 25.00%) + 4.23 5 119.79 (W 22.62%, T 51.92%, L 25.46%) + 2.09 4 119.53 (W 22.51%, T 52.01%, L 25.48%) + 1.82 3 119.77 (W 22.50%, T 52.27%, L 25.22%) + 2.07 2 117.31 (W 21.53%, T 52.71%, L 25.76%) - 0.39 1 116.63 (W 21.45%, T 52.28%, L 26.27%) - 1.07Max. +11 points (qNum EQU 25) is not bad. In order to exclude the possibility, that the quickscan is useless and acts only as a good decoy, using "ORG boot" with the same quickscan results in a score of 116.84 (W 21.16%, T 53.37%, L 25.47%). It seems, that the quickscan does something good. Against Wilfiz we score 100.77 (W 17.29%, T 48.90%, L 33.81%) with qNum EQU 25. Oops! It seems to be, that our opponents find our warrior faster than we do. Using less scans (qNum EQU 15) is better against wilfiz: 111.65 (W 18.86%, T 55.05%, L 26.08%). Another trick would be to have two processes execute two separate quick-scans in parallel, as it was used in QuickFreeze. That way, the program won't be killed if a bomber drops a DAT onto one of the SEQ instructions in the quick-scan. However, we've excluded this idea and take the focus in the following the reduction of the response time.
...
for (83 - 2 * qNum)
dat.f 0, 0
rof
qGo
i for 5
seq.i qStart+(i-1)*qStep, qStart+(i-1)*qStep+qHop
mov.ab # qStart+(i-1)*qStep-found, found
rof
jmn find, found ; attack early, if found sth.
i for 5
seq.i qStart+(i+4)*qStep, qStart+(i+4)*qStep+qHop
mov.ab # qStart+(i+4)*qStep-found, found
rof
jmn find, found ; attack early, if found sth.
i for (qNum - 10)
seq.i qStart+(i+9)*qStep, qStart+(i+9)*qStep+qHop
mov.ab # qStart+(i+9)*qStep-found, found
rof
...
Now YAP scores 129.37 (W 27.21%, T 47.74%, L 25.05%) against Wilkies,
only because we have added two lines! Unfortunately we tie less, that's
why we only gain about 1 point. You could add even more early attacks
to your quickscan. It might increase your score.We've seen, that our quickscan is fast, but unfortunately it adds a lot of code to our warrior (2 lines per scan + attack code). The more positions we scan, the more likely it is, that other quickscanner might find us too. Therefore you should boot away quite fast after the quickscanner is finished. Fortunately our little paper moves away quite fast. Another possiblity is to shorten the scan without reducing the number of scans. How is that done? Here is the answer:
...
qGo sne.i # 100, # 200
seq.i # 300, # 400
mov.ab # 100, found
sne.i # 500, # 600
seq.i # 700, # 800
mov.ab # 500, found
...
found jmz boot, # 0
attack ...
What happens, if this quickscanner finds nothing? Positions 100 and
200 are equal. That is why seq.i is executed. Since position 300 and
400 are equal, the mov is skipped. We scan with 2c, but only need 3
instructions/2 scans instead of 4 instructions before.What happens, if this quickscanner finds something? If position 100 and 200 aren't equal, the seq is skipped and the mov is executed. If 100 and 200 are equal and 300 and 400 are not, the mov is executed. Either way, we can start attacking :-) The only problem is, that we don't know, where to hit. 100, 200, 300 oder 400? Before we start the attack, we have to decide which target to use. Here is the new version:
;;
;; quickscan
;;
start EQU boot ; first instruction of this warrior
qStart EQU (start + 230) ; first scaned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 9 ; number of scans
qStep EQU (qSpace/(2*qNum)); distance between two scans
qHop EQU (qStep/2) ; distance betweens two scan positions
;; put as much space between the paper and the quickscan as possible
for (83 - 3 * qNum)
dat.f 0, 0
rof
qGo
i for qNum
sne.i qStart+(2*i-2)*qStep,qStart+(2*i-2)*qStep+qHop
seq.i qStart+(2*i-2)*qStep+2*qHop,qStart+(2*i-2)*qStep+3*qHop
mov.ab # qStart+(2*i-2)*qStep-found, found
rof
found jmz boot, # 0 ; B-Field not 0 -> quickscan found sth.
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
;; select between the four scan 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
;; bomb target
attack ...
There (2*qNum) scans now. The attack code is little bit longer due
to the fact, that we have to choose between four possible scan positions.
If you have a bigger warrior that might be worth the longer reaction
time. Setting qNum to 9 results in a score of 127.00
(W 25.68%, T 49.95%, L 24.37%). Our old quickscanner used 50 scan
positions to gain a score of 128.7. The new version scans only 36
positions and scores almost quite as good.Now there is only one thing to do: add an early attack :-)
;;
;; quickscan
;;
start EQU boot ; first instruction of this warrior
qStart EQU (start + 230) ; first scaned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 10 ; number of scans
qStep EQU (qSpace/(2*qNum)); distance between two scans
qHop EQU (qStep/2) ; distance betweens two scan positions
;; put as much space between the paper and the quickscan as possible
for (81 - 3 * qNum)
dat.f 0, 0
rof
qGo
i for 2
sne.i qStart+(2*i-2)*qStep,qStart+(2*i-2)*qStep+qHop
seq.i qStart+(2*i-2)*qStep+2*qHop,qStart+(2*i-2)*qStep+3*qHop
mov.ab # qStart+(2*i-2)*qStep-found, found
rof
jmn find, found ; early attack
i for 3
sne.i qStart+(2*i+2)*qStep,qStart+(2*i+2)*qStep+qHop
seq.i qStart+(2*i+2)*qStep+2*qHop,qStart+(2*i+2)*qStep+3*qHop
mov.ab # qStart+(2*i+2)*qStep-found, found
rof
jmn find, found ; early attack
i for (qNum - 5)
sne.i qStart+(2*i+8)*qStep,qStart+(2*i+8)*qStep+qHop
seq.i qStart+(2*i+8)*qStep+2*qHop, qStart+(2*i+8)*qStep+3*qHop
mov.ab # qStart+(2*i+8)*qStep-found, found
rof
found ...
Now we have 128.63 (W 26.55%, T 48.98%, L 24.47%) against Wilkies.
Almost as good as the previous version.Just to see how good YAP is, I have submitted the following version to the biginners hill at SAL.
;redcode-94
;name Yet Another Paper
;version 1.0.0
;author Jens Gutzeit
;strategy quickscan -> 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
;;
;; quickscan
;;
start EQU boot ; first instruction of this warrior
qStart EQU (start + 230) ; first scaned position
qSpace EQU 7700 ; space to cover with quickscan
qNum EQU 10 ; number of scans
qStep EQU (qSpace/(2*qNum)); distance between two scans
qHop EQU (qStep/2) ; distance betweens two scan positions
;; put as much space between the paper and the quickscan as possible
for (81 - 3 * qNum)
dat.f 0, 0
rof
qGo
i for 2
sne.i qStart+(2*i-2)*qStep,qStart+(2*i-2)*qStep+qHop
seq.i qStart+(2*i-2)*qStep+2*qHop,qStart+(2*i-2)*qStep+3*qHop
mov.ab # qStart+(2*i-2)*qStep-found, found
rof
jmn find, found ; early attack
i for 3
sne.i qStart+(2*i+2)*qStep,qStart+(2*i+2)*qStep+qHop
seq.i qStart+(2*i+2)*qStep+2*qHop,qStart+(2*i+2)*qStep+3*qHop
mov.ab # qStart+(2*i+2)*qStep-found, found
rof
jmn find, found ; early attack
i for (qNum - 5)
sne.i qStart+(2*i+8)*qStep,qStart+(2*i+8)*qStep+qHop
seq.i qStart+(2*i+8)*qStep+2*qHop,qStart+(2*i+8)*qStep+3*qHop
mov.ab # qStart+(2*i+8)*qStep-found, found
rof
found jmz boot, # 0 ; B-Field not 0 -> quickscan found sth.
qTimes EQU 20 ; number of bombs to throw
bDist EQU 80 ; target range
qStep2 EQU (bDist/qTimes + 1)
;; select between the four scan 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
;; bomb target
attack mov.i qBomb, @ found
sub.ab # qStep2, found
djn attack, # qTimes
jmp boot
qBomb dat.f # 1, # 1
END
CoreWarrior 7 (There are more links, but these deal with simple quickscanners.) |