Where to scan? A practical approach

This chapter won't deal with new quickscanners, but with the questions "Where to scan?" and "Where and how to hit?".

To 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

        END

Sitting 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

        END

A 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

        END

Now 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 approach

Now it is time to name some variables:

s - 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/L

v/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/L

For 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?

We know, that our enemy is L instructions long. Having found nothing, the best guess we can make, is, that we havn't scanned a position inside our opponent. If that is true, the enemy warrior is not inside a radius of L instructions from the scanned position.

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?

The possibility of finding a warrior at a "high-value" position in a normal core is (having a maximal-length opponent):

        100/7801 * v/L = 0.0128 * v/L

In a tiny core it is:

        20/761 * v/L = 0.0263 * v/L

In a nano core it is:

        5/71 * v/L = 0.0704 * v/L

In an experimental core it is:

        200/55041 = 0.0036 * v/L

It seems, that a quickscanner can find the opponent far more better in nano-cores than in normal cores.

Where to hit?

Upon a successful scan, all we know is that at the scanned position is a visible instruction. The probability, that this is a yet-to- be-executed enemy instruction is quite high. We should hit that instruction instantly!

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

Let's take the best quickscan so far and use it along with different bombing engines. Our warrior won't be our beloved YAP, but a simple "jmp 0". That way, we can be sure, that all kills are done by the quickscanner. Here is the basic version:

;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

        END

How 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

You can find YAP now at Koenigstuhl (94nop: 419th, open: 623th) and on the Beginner's hill at SAL (19th). Here is YAP together with the new bombing engine:

;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

        END

This 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

CoreWarrior 45 - Qscan bombing engines by M. R. Bremer