From: Jens Gutzeit
Subject: Quickscanners - Part III
Date: Thu, 14 Jul 2005 17:07:59 +0200
Message-ID:
Quickscanners - Part III
========================
I'm really sorry to say, that I lied. This part won't deal with new
quickscanners, but with the questions "Where to scan?" and "Where
and how to hit?".
There might be logical errors in this text. Please assume, that
most of the math is bogus. You have been warned!
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.
1. Where to scan? A practical approach
======================================
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.
2. 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?
3. 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.
4. 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.
6. 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.
7. 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!
9. 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.
8. Contest
==========
Let's make a little contest. I want to see how far YAP can be optimized.
All you have to do, is to take the basic YAP-engine:
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
and append either a normal quickscanner (see part I) or a q^2-scanner
(see part II) and a bombing engine for the quickscanner. The version,
that scores best against the WilFiz-benchmark will be published in part
III.
Rules:
- The score of the warrior will be calculated using "pmars -P"
- You are only allowed to change the values of pStep1 and pStep2 of
the paper.
- The bombing engine may throw max. 100 bombs. After that the paper
has to be booted, but no stones, scanners, ... (You know, what
I'm aiming at.)
- One entry per person only.
- Only q^1- or q^2-scanners.
- I'm the one, who decides.
- Deadline: August, 1st 2005 - 00:00 GMT
- Send all warriors to jens@jgutzeit.de (Subject: Quickscanners)
Good luck!
9. Links
========
CoreWarrior 45 - Qscan bombing engines by M. R. Bremer
- http://pauillac.inria.fr/~doligez/corewar/corewarrior/045.txt
10. Preview
===========
The next part will deal with new q^2- and q^3-scans.
- Jens Gutzeit