Subject: How to win with a losing warrior From: Corey_Lynn_Nelson@cup.portal.com Date: 15 Feb 92 06:51:39 GMT Message-ID: <9202142251.1.28716@cup.portal.com> --- The non-transitive nature of Corewar, - or - how to win with a losing warrior. My purpose in writing this is to point out one the problems with determining the "best" warrior, and possibly suggest some answers to a problem involved with it. Basically the problem is the non-transitive nature of Corewar. While writing this, it occurred to me that there is no precise definition of how warriors are scored against each other. For this piece I use the concept of "average score" to describe how two warriors perform against each other. The average score for a warrior is theoretically computed by pitting the warriors against each other, going both first and second, from every possible distance. The scores for all these battles are then averaged. (A win is worth three, a tie one, a loss zero.) In practice I calculated the average by running only about 100 battles. When talking about tournaments, I assume that each warrior actually receives the average score when it is pitted against another, when actually in a tournaments, each warrior is pitted against the others only a few times. In a tournament with several warriors this is so close to the same score that the difference is negligible. For those who are not familiar with the concept, I'll define what I mean by non-transitive as it relates to Corewar. Stated simply, Non-transitive means that if A beats B, and B beats C then A does NOT necessarily beat C. For a more concrete example, consider the warriors Chalk, Dumbo and Echo. (See the example code at the end of this message.) It is easy to see that Chalk beats Dumbo, Dumbo beats Echo, and Echo beats Chalk. There is no clear "Best" warrior of these three. The non-transitive nature of Corewar makes it very difficult (some might say impossible) to pick the best warrior from a group. The non-transitive nature of Corewar can yield bizarre results. For instance, Consider a contest between Alpha, Chalk And Dumbo. When Alpha fights Chalk, Alpha's average is 3.0. When Chalk fights Dumbo, Chalk's average is 3.0. When Alpha fights Dumbo, Alpha's average is about 2.3 and Dumbo's is about 0.7. The average tournament score for Alpha is therefore 2.7 ((3+2.3)/2). The average for Chalk is 1.5 ((0+3)/2). The average for Dumbo is 0.3 ((0+.7)/2). It seems clear that Alpha is the better warrior, (after all it beats Both of the others), but consider what happens when not one, but ten Dumbos are entered. The average score for Alpha is now 2.32 ((3+10*2.25)/11), the average for each Dumbo is 1.3 ((0+.75+9*1.5)/11) and the Average for Chalk rises to 2.73! ((0+10*3.0)/11) Chalk is the winner! I will refer to the technique of winning by beating your own warriors as "Parasitism", and the warriors which lose to the parasite as "hosts", though "cheating" might be a more apt name for the whole process. Parasitism could be exploited to make even the most pathetic warrior a winning warrior. For example if one were to enter Dumbo and 10,000 copies of Echo, then Dumbo would almost certainly win the contest. The practice of splitting the tournament in two, with the top five warriors fighting separately seems to defeats this, but the same thing can still be done, though it's a bit harder. To defeat a two level tourney, one must have three warriors like Bravo, Chalk, and Dumbo. Bravo and Chalk beat Dumbo, averaging 3.0 against it. Bravo beats Chalk, so if Dumbo was entered 10,000 times, Chalk four times and Bravo once, Bravo and Chalk would be the Finalists, with Bravo winning in a close match at the end. Of course it's unlikely that anyone would even attempt to enter 10,000 copies of something, but even three or four Hosts could raise a Parasite's average enough to make the difference between second place and first. What can be done to prevent this? Limiting the number of warriors one is allowed to enter helps, though I suspect a dedicated person could find someone willing to enter warriors for him, or simply enter it "anonymously." In practice I can't imagine any tournament that would allow someone to enter even two copies of the same warrior (except maybe a computer moderated one). I think most people barely have time to work on one good warrior, without trying to work on three, so the problem is very rare in any case. One simple safeguard would be to have an extra elimination round. In the elimination round, eliminate all warriors which averaged 1.5 or less (winning half the time). Since a program can at best average 1.5 against itself, this would eliminate any warriors which didn't beat at least half of the other (non-copy) warriors. This doesn't guarantee that hosts will be eliminated, but it makes it very likely that they will be. ; Alpha - a wimpy varient of dwarf ALPHA MOV BOMB BOMB ADD #3 ALPHA JMP ALPHA BOMB DAT 0 END ALPHA ; Bravo - a speedy, but larger varient of mini-dwarf BRAVO MOV BOMB