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)