Path: ibmpcug!irene.pcug.co.uk!plug.news.pipex.net!pipex!dish.news.pipex.net!pipex!europa.chnt.gtegsc.com!usenet.eel.ufl.edu!gatech2!ncar!newsxfer.itd.umich.edu!agate!soda.CSUA.Berkeley.EDU!mconst
From: mconst@soda.CSUA.Berkeley.EDU (Michael Constant)
Newsgroups: rec.games.corewar
Subject: Theme (round 5 entry)
Date: 11 Nov 1995 06:09:37 GMT
Organization: Society for the Prevention of Cruelty to Vegetables, UC Berkeley
Lines: 125
Message-ID: <481en1$qrn@agate.berkeley.edu>
References: <1995Nov9.142248.3038@rhodes>
NNTP-Posting-Host: soda.csua.berkeley.edu
Randy Graham wrote:
>Well, I have finally gotten something written that will work in round
>5. Hopefully it is a unique idea, but I somehow doubt it. Anyway,
>I'm not really happy with my entry, but since I couldn't come up with
>a good idea, I decided to use what I could come up with. So, has
>anyone got any ideas that think could be done but aren't pursuing
>themselves?
Yup, that would be me. I came up with a neat idea, but didn't have time
to implement it properly. Basically, I spent all my time on the imp code
and I had to write the paper at the very last minute. I would love it if
someone could take Theme and rewrite the paper code -- the imp stuff is
awesome IMHO, but the paper was very much rushed and it shows.
But before I show you just how horrible the paper is, let me tell you
about the imps :-) Given any coresize not divisible by 30030, Theme can
find an imp-number that will work -- not only that, the spiral it creates
will always have <= 13 points. (The number 30030 can be raised to 510510
with a trivial addition, which adds only one line of code and doesn't slow
the program at all.) Not only that, it's *fast* -- the entire imp-number
calculation takes an average of about 30 cycles (and it takes none at all
once the result is stored in P-space, after the first round!). It uses
lots of number theory, though, which is not made any simpler to understand
by all my optimizations :-) But since it's really a pretty cool algorithm,
I'll explain it if anyone wants (post here if you want me to explain it).
A side note: Theme seems to me to be a step towards the "intelligent"
warriors that all the changes in corewar are designed to promote. It uses
quite a bit of math, which alone justifies the label "intelligent". But
more interesting is the fact that it uses some of the new corewar features
to very good effect: the much-maligned mul/div/mod instructions are
absolutely crucial for Theme, and it uses P-space to save ~30 cycles of
computation (more in certain coresizes). For me, the fact that Theme uses
P-space to save time in calculations rather than to simply switch between
standard strategies is evidence that P-space can be used to write more
intelligent warriors. And Theme would simply not be possible without the
mul, div and mod instructions, which is evidence that those instructions
are useful to help create more complex warriors.
Finally, the idea of combing paper with an imp is due to Mike Nonemacher,
who used it quite successfully some time ago in a warrior whose name I
have forgotten. Thus, any weaknesses in Theme are most likely due to my
implementation, rather than to the original idea.
Without further ado: Theme.
;redcode-94
;name Theme
;author Michael Constant
;strategy silk paper and dynamically launched imp-spiral
;strategy based on a wonderful idea by Mike Nonemacher
;assert CORESIZE % 30030
MAGIC equ 42
magicp ldp.ab #1, #0
seq.b magicp, #MAGIC ; is the magic number there?
jmp calc ; ... nope, we have to recalculate
ldp.ab #2, imp ; ... yup, we can start immediately
launch spl setup
spl 1
spl 1
spl 1
spl 1
spl 1
spl 2
jmp imp ; a fast imp-launcher would have been a
add.ba imp, -1 ; real pain to do dynamically
magic1 dat 0, 13
magic2 dat 0, 11
which dat endp+1, 7
sign dat 1, 5
dat 0, 3
endp dat 0, 2
setup spl 1
spl 1
spl 1
spl paper2
spl paper3
paper1 spl -11751, 0
mov.i >-1, }-1
mov.i <-2, {1
jmp -12015
paper2 spl -11560, 0
mov.i >-1, }-1
mov.i <-2, {1
jmp -12351
paper3 spl -11301, 0
mov.i >-1, }-1
mov.i <-2, {1
jmp -12511
calc mod.b {which, #-1 ; take CORESIZE-1 % p, where p is prime
add.ab #1, calc ; ... but we really wanted CORESIZE % p
seq.b calc, *which ; is p relatively prime with CORESIZE?
jmp euclid ; ... yes, we have a winner!
mov.ab #-1, calc ; ... no, restore calc and try again
jmp calc
euclid div.b *which, #-1 ; this works out to CORESIZE / p
mov.ba imp, magic2 ; store imp for later reuse
mul.b euclid, imp ; apply the inverse Euclidean algorithm
add.ab magic1, imp ; ... storing partial results in imp
mov.a magic2, magic1 ; magic1 is now the old value of imp
mov.b *which, euclid
mov.b calc, *which
mov.b euclid, calc
mod.b *which, calc ; apply the standard Euclidean algorithm
mul.a #-1, sign ; sign is the parity of the total pass count
jmn.b euclid, calc ; is the remainder zero yet?
mul.ab sign, imp ; ... yes, we're done -- prepare the imp
stp.b imp, #2 ; we've found the imp-number, let's store it
stp.ab #MAGIC, #1 ; ... and store MAGIC so we know it's real
jmp launch
imp mov.i #-5, 1 ; the -5 is to help against anti-vamps
--
Michael Constant (mconst@soda.csua.berkeley.edu)