From: kwhyte@math.uchicago.edu (Kevin Whyte)
Subject: Re: dwarf optima
Organization: Dept. of Mathematics, Univ. of Chicago
Distribution: rec.games.corewar
Date: Fri, 10 Apr 1992 16:41:39 GMT

In article <1992Apr8.120720.27993@informatik.uni-erlangen.de> snroettg@faui09.informatik.uni-erlangen.de (Stefan Roettger) writes:
>>XTC uses 412 to scan the core s(412)=13.19
>>I have the feeling, that the bigger s(a) the better a to scan or bomb.
>>Clearly a=4 the worst choose.
>>I used an a with s(a)=17.11 in dwarf optima and it made to the first place.
>>It's possible that the choice of a really does not matter.
>
>I've run some tests on this and it clearly comes to mind
>that bombing core with a constant that has high s(a) values
>is more efficient. I think this is due to the fact that the core
>is bombed in a much more regular way. The best way I can think of
>is to bomb into the middle of two previously bombed core locations
>and high s(a) values produce something similar to this scheme.
>
>With core size=8000 #3044 and #3364 have the biggest s(a)
>value=17.11. The crux is that if one offset performs
>good with core size=8000 it does not necessary perform well with
>other core sizes. In fact I didn't find an offset that did equally
>well with different core sizes.
>
>Suggestions and comments welcome
>   Steff
>
>
>
>--
>Stefan Roettger
>Student of Computer Science
>snroettg@cip.informatik.uni-erlangen.de
>Xerox your live! If you lose one it's better to have a copy!


   I promised some serious analysis ... but I can't find it.  It
wasn't that hard, so I'll redo it right after my taxes.  Off the
cuff :

   Divide by coresize, so that we are using real # mod 1.  Now
we want the multiples to be as far away from zero as possible,
which amounts to asking the real to be badly approximable by
rationals.  In at least one sense, the worst approx. # is sqrt(1.25)/2
So something right around that fraction of core should be good
for most core sizes.  For N=8000 and asking that we bomb every
fourth memory location that gives either 4932 or 4948.

Unfortunately (I'll let someone else compute s(.) for those #'s),
that is the wrong notion of rational approx.  The function others
have defined is also not quite right.  The (main) reason bombing
with high numbers is useful is as follows:  If the opponent is 
(say) 10 lines long, then initially there are 8000 places in core 
the program could be (yes, they do overlap).  After 1 bomb that misses,
there are only 7990 places left it could be.  Every hit will remove
another 10 possible hiding places PROVIDED the distances between bombs
are no closer than 10.  If they are, then fewer places are removed.
Now we don't know how long our opponents are going to be, so we
have to design for a distribution of lengths.  The function s(a)
does not really take in to account that virtually all programs are
under length 30 ... s(a) is the function (almost) if you assume program
lengths are unif. dist. 1..Coresize.

   The other factor missing in s(a)  is that we care more about 
what happens early on.  A short gap after filling 3/4 of core is
MUCH better than one earlier.  Why?  Because the chances that the
fight will still be going after all that are much less, around
1/16 th as much.  This scaling should also be included.  Anyway, I
wrote this all up once - I can do it again (together with the ?
of how much to unroll a loop).  

  Kevin
 kwhyte@math.uchicago.edu
Newsgroups: rec.games.corewar