A Numeric Approach to Diversity Hills

Abstract

I like a lot the idea of a Diversity Hill for Corewar Warriors (Note 1). There is a thread about Diversity Hills on rec.games.corewar and I already posted some of my ideas there. Anyway, I think that an example that uses real warriors and real numbers can lead to clearer ideas for anyone interested in the thread.

In order to start the game, I used the published warriors on John Metcalf's Infinite Tiny Hill. I defined two distances on the warriors' space and tried to define a numeric discriminant, in order to decide if a new challenger succeeds or not in entering the hill, and which warrior should be pushed off the hill after a new successful challenge.

I tried to compare other distances and discriminants; many questions arise, and I tried to answer to some of them. Most questions still miss a satisfying answer.

Definitions

In order to have a fast and simply result, I defined a Tiny Hill in the usual way (Note 2); I decided to make only 2 fights of 250 rounds each, including self-fights. The hill contains 20 slots.

Then I defined the distances between two warriors; I used the classic "euclidean distance" between the points identified by the wins/losses/ties scored against all the warriors on the hill, including the two, as the first distance; I considered only the wins/losses scores for the second distance (Note 3).

Initialization

I entered the least 20 warriors listed on John Metcalf's Pure Infinite Tiny Hill in reverse order (i.e. starting from the last) and this is what I got:

Diversity Tiny Hill after challenger #20 tinyak47.red

According to both distances, the nearest warriors on the hill are tinytom.red and tinyever.red. The header lines in the warriors are:

;name Tiny Tom
;author M Joonas Pihlaja
;strategy clear, clp

;name Tiny Everclear S
;author Franz
;strategy  jmz scan -> spl/spl/dat clear

If you read the code, you indeed can guess that the claims are correct; anyway, they score "nearly the same" in this hill. The first question arise: why do a P-switcher and an oneshot score so similar?

Maybe the answer is that the claims in the ;strategy lines and the further inspection of the warriors' code are not enough to classify the warriors, and we must inspect their behaviour, too: it seems like "clear, clp" was not a good choice for a P-switcher (Note 4).

The next challenge

This is what I got when I entered the 21st challenger:

Diversity Tiny Hill after challenger #21 silkligh.red

And now what happens? Should the tiny-p.red warrior get pushed off the Hill? "Of course not", because I am going to have this hill as a diversity hill. In fact, right now tiny-p.red is the most diverse of all warriors on the hill, in both distances, and must be rewarded for this. So, who will be pushed off the hill?

Discriminant #1

Let it be the less scoring between the new entry and the nearest warrior.

In this case, the nearest warrior is pergamen.red in both distances. If we read the headers:

;name Silk Light
;author Christian Schmidt
;strategy Paper

;name Pergament
;author Christian Schmidt
;strategy silk/imps

we understand that this is a fine choice; not that good, because pergamen.red is not a pure paper, but fine.

Anyway, we can notice that the nearest warrior to pergamen.red, according to both distances, is not the new challenger, but tinybarb.red, a stone/imp. And why are they so similar? Maybe because the imp part is predominant in both warriors. In my opinion, it seems like that comparing silkligh.red and pergamen.red is not a correct choice.

And more, what happened if the new challenger were tiny-p.red instead? It would not enter the hill! It is "randomly" compared to tinybrut.red, and loses (Note 5). This means that the order in which we submit the warriors to the hill is important in determining the hill itself. This is not correct in my opinion, and this is definitely the reason why I reject this rule (Note 6).

Discriminant #2

Let it be the less scoring of the two nearest warriors, regardless of if the new entry is one of the two or not.

According to both distances, this would be tinyever.red as compared to tinytom.red; the new challenger silkligh.red is distant enough from the other warriors, and gets its place on the hill.

But again let's think about what happened if the new challenger were tiny-p.red instead. It has a far distance from any of the warriors on the hill, but its score is the lowest one. Should it enter the hill, and incidentally push off tinyever.red? Its distance is a good hint that the new challenger should get its place on the hill, but its score is a good hint that it should not! (Note 7)

Another question arise: silkligh.red enters the hill at 9th, and pushes off tinyever.red at 15th; anyway, if by chance the nearest warriors were tinybarb.red and pergamen.red instead (compare the distances), then pergamen.red would be the loser, and it would be pushed off at 11th! Why?

This new rule seems good, but it does not answer these questions, yet. It seems like we need to define a numeric discriminant, in order to assert that we choose the correct warriors on a numeric base. (Note 8)

The Numeric Discriminant

I defined a numeric discriminant as the product of the score by the minimum distance (Note 9).

This is what I got when I ordered the warriors by the numeric discriminant defined by distance 1:

Numeric Discriminant 1 after challenger #21 silkligh.red

And this is what I got when I ordered the warriors by the numeric discriminant defined by distance 2:

Numeric Discriminant 2 after challenger #21 silkligh.red

In either case, it is numerically clear that silkligh.red makes its way on the hill; anyway it pushes off tinyever.red in the first case, and snow.red in the second case. Incidentally, if the new challenger were tiny-p.red it would enter the hill in either case, too, and again it would push off the same warriors (Note 10).

Let's study the results of the challenge: we already noticed, in the first case, that tinyever.red is too similar to tinytom.red, and both are scoring low. The same holds in the second case: snow.red is the less scoring of a couple of similar warriors, and both are scoring low (the other one is stunner.red).

The result is that a paper enters the diversity hill and pushes off an undisclosed strategy warrior (maybe a scanner, if one inspects the code), because the latter is too similar to a bomber -> clear... This seems to make no sense! Maybe 20 slots are not enough to ensure a full diversity. Anyway, this makes me think (again) that the claims in the ;strategy lines are not always correct (Note 11).

The behaviour of a warrior against other warriors is the only numeric classification I can think of so far. The claims in the ;strategy lines of a warrior and the further investigations of its code are not enough to classify a warrior; this is even more true if the code of a warrior is undisclosed, as is the rule for the most popular hills.

Conclusions

The most positive aspect of the numeric discriminant is that if you submit a warrior that behaves almost identically to another one in the hill (possibly the same warrior), their distances will approach to 0, and so will do the discriminant; in this case, the less scoring of the two warriors will be pushed off the hill, leaving the hill as diverse as it was before the challenge. This answers one of the questions that arised in the thread on rec.games.corewar (Note 12).

We still have to answer a question: in fact, we should notice that a P-switcher behaves differently from the other warriors (not always better, but surely different). In this case, tinytom.red does not, in both distances. My first answer was that maybe the "clear, clp" strategy is not a good choice; but maybe the hill is not diverse enough, yet to allow a correct switch. This last consideration is not good, of course.

So again this is an open question: should we consider the distance comparing the results with a chosen benchmark, instead of comparing the results against the other warriors in the hill? I still do not think so, because other questions would arise: how to choose the warriors for the benchmark? And how to update the benchmark, in order to keep trace of the new strategies that possibly may arise?

The end of the game

I prefer the first distance, so I kept on inserting the warriors from John Metcalf's Infinite Tiny Hill in reverse order into the Diversity Hill defined by distance 1. Here are the summary of the results:

The starred warriors are those warriors being pushed off because they were too near to the new challenger. If the new challenger did not make it, I wrote the nearest warrior in parenthesis. Most of the results makes no wonder: see how oneshots and bishots keep pushing off other oneshots and bishots while approaching the top of the hill.

The resulting hill is:

Diversity Tiny Hill after challenger #90 easter.red

And the resulting numeric discriminant is:

Numeric Discriminant 1 after challenger #90 easter.red

The distances flattened since the first challenges; this makes me think that maybe 20 slots are too few. But the warriors are more or less equally spaced, and this is good. The most winning strategy gets the most warriors on the hill, as far as it allows many variants.

Anyway, 3 of the least 20 warriors survived 70 challenges! This means that the strategies in ricket.red, squirm.red, and sept.red are really diverse and maybe competitive! Maybe they just need some good implementation?

Notes

Note 1 A hill with many different strategies can help developing smarter warriors, and more important it can enhance the development of new strategies for Corewars. The developer of a new idea can find it frustrating to see his or her warrior continuously failing in entering a standard hill; finally, he or she would quit the idea. And maybe it was a good idea, but the hill was not diverse enough, it was just full of warriors based on the same strategy, and the new warrior failed against only that strategy. top

Note 2 CORESIZE==800 && MAXPROCESSES==800 && MAXCYCLES==8000 && MAXLENGTH==20 && MINDISTANCE==20. I used the -f flag of pMars in order to always replicate the same results. top

Note 3 As an example for the first distance: say warrior1 scores 200 180 120 against itself, scores 120 140 240 against warrior2, scores 160 160 180 against warrior3, and so on; say warrior2 scores 120 140 240 against warrior1, scores 180 180 140 against itself, scores 120 160 220 against warrior3, and so on; the distance between warrior1 and warrior2 is:

sqrt(
   (200 - 120)^2 + (180 - 140)^2 + (120 - 240)^2 //scores against warrior1
 + (120 - 180)^2 + (140 - 180)^2 + (240 - 140)^2 //scores against warrior2
 + (160 - 120)^2 + (160 - 160)^2 + (180 - 220)^2 //scores against warrior3
 //and so on with the scores against the other warriors on the hill
)

I dropped the ties score for the second distance because the ties score is not independent of the wins and the losses. While the most distant points using the first distance are 500 0 0, 0 500 0, and 0 0 500, the most distant points using the second distance are just 500 0 0 and 0 500 0. The "full ties score" is slightly nearer and half way between the "full wins" and "full losses"; this gives some kind of semantics to the second distance.

One could as well drop either the wins or the losses from the first definition and get two other distances; anyway, these distances have no semantics sense in my opinion. top

Note 4 There are other couples of warriors that are similar to each other and distant from the other warriors of the hill. The other couples are:

quickd.red (qscan -> dclear) and tinyak47.red (scan -> dclear) in both distances:

;name QuickD
;author Franz
;strategy qscan+dclear
;strategy qscan for tinyhill (no not Q^2)

;name Tiny AK-47
;author Franz
;strategy scanner->d-clear

tinybarb.red (stone/imp) and pergamen.red (paper/imp) in both distances:

;name Tiny Barbarian 3
;author Franz
;strategy stone/imp (continuous launching imp with kill fuse)

;name Pergament
;author Christian Schmidt
;strategy silk/imps

ugly.red (evolved stone/imp?) with euthin.red (qbomb -> clear) in the first distance, and with squirm.red (qbomb -> paper) in the second distance:

;name Ugly
;author John Regehr

;name Euthin
;author Philip Thorne
;strategy Nuthin with splits. i.e. stupid quick bomb/clear
;strategy John Metcalf 2002 Tournament Round 1, Warrior 1

;name Squirm13
;author Philip Thorne
;strategy tworm6, different engine.
;strategy i.e. silk-worm with chaotic core-copy
;strategy John Metcalf 2002 Tournament Round 1, Warrior 2

stunner.red (bomber -> clear) with snow.red (scanner?), in both distances:

;name Stunner
;author Sascha Zapf
;strategy Fast Incendiary Bomber, Twopass Coreclear
;strategy Two Bombing steps, Bootstrapping

;name Snow Castle
;author Compudemon

Except for quickd.red and tinyak47.red, these seem not to be couples of similar warriors, at first glance. Anyway, all of these couples are for sure a base for defining different "equivalence classes" for the warriors on the hill. This still needs more investigations. top

Note 5 I say "randomly" because tiny-p.red is the most "diverse" of the warriors in the hill; one can correctly state that tinybrut.red is the nearest warrior, but for sure it could be any of the other warriors in the hill for a really new strategy! See tinyspir.red and tinyclp.red, for instance, other "diverse" warriors: they are far distant from the warriors on the hill, and only chance is that the nearest ones are snake.red and tinybrut.red; this high value makes no sense for a really diverse warrior. top

Note 6 Note that all of these considerations are independent of the chosen distance. The involved warriors may vary as the distance varies; anyway, the results and considerations still hold. top

Note 7 What would happen if the new challenger were not tiny-p.red but a suicide dat.red? Here are the results:

Diversity Tiny Hill after challenger #21 dat.red

This is surely an impressive distance! But anyway the score is impressively poor! We know for sure what to do, that is we would keep tiny-p.red and instead we would discard dat.red; this means that we are using an intuitive threshold, but we need to numerically define this threshold, that would depend both on the score and the distance. top

Note 8 Again, you can note that all of these considerations are independent of the chosen distance. top

Note 9 Note that this definition is independent of the scales you use to compute the score and the distance; that is, if I used the "percent" scoring method instead of the full score, then ordering the warriors by the "percent" discriminant would give the same results as ordering by the numeric discriminant I used here.

The definition is not independent of the distance, of course. It is just independent of the scale. top

Note 10 Now let's see what happened if the new challenger were dat.red instead of tiny-p.red:

Numeric Discriminant 1 after challenger #21 dat.red

Numeric Discriminant 2 after challenger #21 dat.red

In either case, dat.red does not make its way to the hill; its diversity does not balance the poor score. This is the expected behaviour, as for the intuitive requirements of a previous note. top

Note 11 This is due to many reasons. Say the author is cheating; or the author is a newbie and does not know the exact meaning of the words; or the warrior is buggy, and behaves differently from the author's thoughts. top

Note 12 To test my claim, I introduced a minimum change in tinyak47.red (I simply shifted the warrior by 7) and I entered the resulting warrior into the hill in both cases:

Diversity Tiny Hill after challenger #22 copyak47.red

Numeric Discriminant 1 after challenger #22 copyak47.red

and

Diversity Tiny Hill after challenger #22 copyak47.red

Numeric Discriminant 2 after challenger #22 copyak47.red

Even if they are the highest scoring warriors, they are indeed too similar, and their numeric discriminant is the lowest one. Incidentally, the copy happens to be a bit better than the original, and becomes the new king of the hill. The old koth is pushed off! But this is what we expected. top