Score Surfaces

Hi,

the score surface of YAP against Muskrat is complete! You can find it
at http://corewars.jgutzeit.de/score_surfaces/index.en.html . The raw
data will be available later today. Thanks to everybody, who has
contributed to this project!

Fizmo was so kind to create a little benchmark. YAP will fight each of
the warriors to get more information about how to choose good
constants. The distribution of the work will start later today or
tomorrow. This time I want to be sure, that no data will be computed
twice!

If you have ideas or comments, please post them at r.g.c.

- Jens Gutzeit

Brief analysis of YAP (against Muskrat) score surface
In this article, I'll use offseted flipped grayscale score image <a
href= "http://dcsnake.narod.ru/img_score.jpg" > </a>.
I'll deal with score, but most of argumentation also applies to
separate w/l/t surfaces. pStep1 will be denoted as x1 and pStep2 as x2.
Score distribution <a href= "http://dcsnake.narod.ru/img_hg.png"> </a>
It has one intense peak; however there are three other peaks near low
values + one more distant peak. These peaks corresponds to darkest
lines. As one would expect, distribution is skewed towards low values.
I'll discuss it's form and origination later. Now some stats (in points
and relative to mean):

Variable Value[pts] Value/Mean
Mean 182.1 1.000
Median 195.0 1.071
Mode 209.5 1.150
Max 254.3 1.396
Std. Dev 43.2 0.237

Things worth mentioning are: relatively high standard deviation and
high max/mean ratio. Now I'll state main thesis of this article and
then try to base it.
Statement: Score surface is a superposition of two factors:
independent step effects and steps interactions.
It could be written as: S[x1,x2] = c0*f1[x1]*f2[x2]*f12[x1,x2].
I achieved approximate f1 and f2 by averaging image along corresponding
axes.
<a href src= "http://dcsnake.narod.ru/img_f1.png"> </a>
<a href src= "http://dcsnake.narod.ru/img_f2.png"> </a>
f1 is just what it's supposed to be: fractal function (similar in some
aspects to Dirichlet's function) with depressions around x=coresize/n.
Smaller n - deeper depression. This is evidently caused by
self-overwriting. f2 is much more simplier, it's almost constant on 90%
of interval. There is no overwriting effect due to the fact that in
worst case, paper will overwrite it's already dead copies (against
scanners, this may have a positive effect). However, there are some
things worth mentioning: this function has a wide depresion near low
values (x = 50..230 ). Probably, it happens because larger values could
lead to better spreading. Anyway, depression isn't too deep: it's
magnitude relative to mean is only 6 percents. Second strange thing:
fourier spectrum of this function is quite smooth, but it has strange
peak (only one) at frequency corresponding to size of 8.25 . I have no
explaination for this (Muskrat peculiarities ?). Anyway, this effect is
very small: this harmonic's amplitude related to mean is only 2%.
Conclusion: x1 is MUCH more important than x2. You can have a good
constants with almost any x2, but you cant with any x1.
Actually, f1 and f2 are only approximations (we were not considering
f12 when averaging), and I think that real f2 is just a constant; there
must be no f2 multiplyer. Depression near x=0 is actually a property of
f12.
f12 is created by interactions between constants and visually seen as
set of lines. We can see a bundle of lines crossing zero point. They
have form x1=k*x2, k = 1..+inf and other lines, namely x1=0, x2=0,
x1=-x2. Origination of these lines is clear: self-overwriting. There
are no lines of form x2=k*x1 probably because (correct me if I'm wrong)
paper would overwrite copies that were already executing for some time
and overwriting is only partial (last part that is about to execute is
not modifyed). But there are many other lines, one may say.
Statement: there are NO other lines different to that mentioned above.
They just wrap around because we have circular core. Look at this:
<a href= "http://dcsnake.narod.ru/img_tile.jpg"> </a>
Now we're about to make a very important conclusion: f12 is fully
described as a superposition of these lines. At this point, I think
that I've described the nature of the surface. As you can see, there
are no good paper constants, there are bad paper constants
Consequences:
- This score surface is affected little by muskrat and originates from
just two mathematical factors: f1 and f12 (envelope + set of lines).
Benchmark would give almost identical result (maybe with exception of
x2=k*x1 lines)
- Factors that cause such a surface are scalable -> surface is
scalable. Surface for coresize 8000 looks almost identical (relative
line width is smaller). One can use this surface to optimize his paper
for any coresize (he only have to renormalize values).
- Surface could be calculated theoretically

To illustrate last statement, I've applied Hough transform to adjusted
score surface (only adjustment was inversion; it's needed for transform
to work properly). HT is quite simple: each point of image adds to a
point of accumulators array with corresponding shift and angle. All
points of a line would add to one cell of array -> If we have a line on
image, we'll se a bright point in array. Then I quantized the array
(only main lines were left) and drew these lines. Result is quite
similar to original surface. I used only a few lines and fact that they
wrap around was not used! Thus, more precious modelling is possible. <a
href= "http://dcsnake.narod.ru/img_ht.jpg"> </a>

So, is it smooth? (We're dealing with discrete stuff so don't try to
apply mathematical smoothness definitions) Neither f1 nor f12 is
smooth. Result isn't as smooth as I'd liked to. Local maximums are
chaotically scattered around. <a href=
"http://dcsnake.narod.ru/img_lmax.png"> </a> Gradient optimization is
hardly appliable: take a look at abs(grad) and arcsin(angle(grad)):
<a href= "http://dcsnake.narod.ru/img_gabs.jpg"> </a>
<a href= "http://dcsnake.narod.ru/img_gang.jpg"> </a>
But it's not that bad, it's still quite coherent (similar values are
groupped together). Bomber's score surface is much less smooth I guess.
Taking into account scalability hypothesys, my coherence length
estimation was correct.
That's all for now, I guess now KOTH will be flooded with papers having
constants lying in good areas

Hi inversed,

> Brief analysis of YAP (against Muskrat) score surface

I don't think you should call it a "brief analysis" Up until now I
didn't think that much about any kind of mathematical analysis of the
images. I just thought, that looking at the pictures is enough to draw
conclustions.

Thank you very much for this article!

> f12 is created by interactions between constants and visually seen as
> set of lines. We can see a bundle of lines crossing zero point. They
> have form x1=k*x2, k = 1..+inf and other lines, namely x1=0, x2=0,
> x1=-x2. Origination of these lines is clear: self-overwriting. There
> are no lines of form x2=k*x1 probably because (correct me if I'm wrong)
> paper would overwrite copies that were already executing for some time
> and overwriting is only partial (last part that is about to execute is
> not modifyed). But there are many other lines, one may say.
> Statement: there are NO other lines different to that mentioned above.
> They just wrap around because we have circular core.

For optimizing silk-style papers this means, that we only have
to check, that there is no k (or at least no small k) with pStep2 = k *
pStep1 and that pStep1 is not an obvious bad choice. Unfortunately we
have only the data for YAP. It contains only one frontend- and one
backend-silk. What about center-silks? I think, that the same rules for
choosing the center-silk constant are nontheless true.

While this method should result in good values against bombers, we have
to wait until we have further data about fights against scanners. Maybe
there are more restrictions for choosing constants.

Against silk-style papers we shouldn't get any further restrictions,
because, as you already know, they cannot kill each other effectively.
What about silk-style papers with bombs? How do the paper-bombs affect
the steps? (Probably another score-surface to calculate

- Jens Gutzeit

Some notes and additions:

> For optimizing silk-style papers this means, that we only have
> to check, that there is no k (or at least no small k) with pStep2 = k *
> pStep1 and that pStep1 is not an obvious bad choice.

Actually it doesn't: lines wrap around, so you have to check all
possible
step pairs having form (k1*step1, k2*step2), k1,k2=-inf..+inf if they
are close to step2=k*step1 lines. Everything becames even worse,
because different lines have different impact (they multiply score by
differeny factors, see below).

> Unfortunately we
> have only the data for YAP. It contains only one frontend- and one
> backend-silk. What about center-silks? I think, that the same rules for
> choosing the center-silk constant are nontheless true.
Centre-silk having form
spl @0, step
mov }-1, >-1
will behave similar to front silk, the only difference is interactions
with front silk (another score surface to plot?)

> While this method should result in good values against bombers, we have
> to wait until we have further data about fights against scanners. Maybe
> there are more restrictions for choosing constants.

As I said in my article, score surface is a result of factors not
depending on YAP's opponent; score surface for a scanner for example
would be very similar maybe with exception of x1 and x2 equal to scan
step. So it'd be more usefull to spent cycles on calculating
scanner/stone surfaces.

Update: changes in theory: actually, both f1 and f2 are constants!
Observed effect is fullly generated by f12. In other words, whole
surface is just a superposition of infinite set of lines wrapping
around. Dark blobs at x1=coresize/n are result of 'line interference':
indeed, lines having form x2=k*x1 would cross line x2=coresize/2 at
points x1=coresize/(2*k). Then they wrap around and cross this line
again at some other points, interfering with other lines and creating
these blobs. But what about these vertical lines, they can't come from
centre. This is what discouraged me and I was forced to introduce f1
and f2. But now I have a new hypothesys: whole vertical lines are
results of line-interference. It's quite hard to deal with such things
theoretically (discrete and fractal), so I'll give experimental basis:
1. I've projected theoretical surface graph (HT->quantize->inverse HT)
along x2 axis and resulting function looks very similar to real one
2. Resulting distribution of modeled image is very similar to real one.
This means that resulting distribution is just a superposition of
distributions created by single lines.
This hypothesys simplifies the theory making it more beautifull. Main
thesis is now formulated as:
Complete score-surface is a result of line-interference caused only by
lines having form x2=k*x1, k=-1 and k=1..+inf. Each line multiplies
values at points it crosses by a[k], where a[k] is an infinite series
and a[k]->1
Some approximate values for a[k]:
k a[k]
1 0.26
2 0.32
3 0.72
4 0.76
5 0.84
6 0.97

inversed

Oh sorry, just made a stupid mistake:
> indeed, lines having form x2=k*x1 would cross line x2=coresize/2 at
> points x1=coresize/(2*k). Then they wrap around and cross this line

This should look like:

indeed, lines having form x2=k*x1 would cross line x2=coresize at
points x1=coresize/k. Then they wrap around and cross this line

Hi inversed,

> Actually it doesn't: lines wrap around, so you have to check all
> possible step pairs having form (k1*step1, k2*step2), k1,
> k2=-inf..+inf if they are close to step2=k*step1 lines. Everything
> becames even worse, because different lines have different
> impact (they multiply score by differeny factors, see below).

I think, I didn't make myself clear enough. Of course you are right,
when you say, that it is necessary to check all values near
pStep2 = k * pStep1. But we have to take several limiting properties
of the core to take into account. At first a paper cannot create
a infinite number of copies of itself, because:

1. The number of processes and the number of instructions is limited.

(Limiting MAXCYCLES has the result, that certain values on
pStep2 = k * pStep1 won't be reached.)

2. The paper starts to overwrite itself.

When we assume, that we only operate in a tiny core (i.e.
800 instructions), we can limit your restrictions of
k = 1, ..., 799 (799 = -1!), because everything is calculated
mod 800.

What I wanted to say, is, that for practical restrictions of
the tiny core, we can probably find some value K, so that we
only have to check pStep2 = k * pStep2 for k < K (and probably
for k=799=-1) ... and of course the values near those pairs.

What do you think?

- Jens Gutzeit

> But we have to take several limiting properties of the core to take into account
Yes, and this is why lines with larger k aren't that intense.
K'th line's directing vector will have form (1,k), so this line will
wrap around k times. So for kth line we have to test k points: (x1,x2),
(x1,x2+coresize), ...(x1,x2+(k-1)*coresize). If we test only Kmax
lines, we will have to perform 1+2+3+...+k = k(k+1)/2 tests. So k=800
(actually 400) is a bit large. Of course it's it's possible to perform
80200 tests, but it's not advisable because:
- As can be seen from table of a[k], lines with large k affect surface
only a little (while not taking line interference into
account).Probably, Kmax=6 is enough
- If you use one rule for all lines (distance to a line must be
greater than some value), this would lead to over-estimation of
influence of some lines; With large number of lines, this effect would
be notable and you may get wrong estimation for locations of good
points
- It is hard to model line interference. So vertical lines
(x1=coresize/n) should be tested separately
Taking into consideration these notes, it should be possible to write a
simple program to calculate probably good areas. There aren't much
changes for 3 silks: our surface would have a greater dimension and
there would be not a bad lines but a bad planes (atually our score
surface is just a section of a hypersurface for 3 silks), so I think
such a theoretical optimization would be a nice tool (after estimating
good areas, you may test some points near them by brute force).
Ideally, method should use the fact that lines with larger k aren't
that bad, for example by decreasing penalty for them.