From: mconst@OCF.Berkeley.EDU (Michael Constant) Subject: MNCT Round 1 Results Date: 12 Nov 1993 05:40:18 GMT Message-ID: <2bv7k2$pra@agate.berkeley.edu> -------------------------------------- - Michael's New Corewar Tournament - - - - Round 1 Results - -------------------------------------- Round 1 was a success! I received 12 submissions total, all of which used interesting strategies. Without further ado, here are the scores: Rank Name Author %W %L %T Score ___________________________________________________________________________ 1 BackTrack 7 Stefan Strack 97 3 0 14538 2 Kill challenge 1 100% Anders Ivner 96 4 0 14399 2 No Challenge Michael Constant 96 4 0 14356 4 Smite White P.Kline 94 5 1 14147 4 Four Eyes Alex MacAulay 94 5 1 14129 6 round1 nandor sieben 92 5 3 13974 6 Lookout Wayne Sheppard 92 7 1 13882 8 Niche 1.0 Bill Shubert 88 10 1 13330 8 Fast Intangible Worm ---who?--- 87 10 3 13244 10 Safe v2.0 Marcus Williams 78 19 3 11793 11 fork J.Layland 71 27 2 10805 12 Achilles Jonathan Wolf 48 30 21 8287 The best program was Stefan Strack's Backtrack 7, which backtracked along Challenge's bombing pattern to find the actual program. Several other programs (No Challenge, Smite White, Niche 1.0, and possibly others which I haven't checked yet) use this strategy. Detailed strategy comments (with source code) will be forthcoming. The worst was Jonathan Wolf's Achilles, but it must be pointed out that Jonathan submitted another program which would have been much better, but since he currently doesn't have any sort of MARS, he couldn't test it and it didn't work. :-( _How_The_Scores_Were_Calculated_ Each program submitted was run in 5000 battles vs. Challenge 1. They were scored with the standard 3-1-0 KotH system. (So far, so good :-) Then, I looked at the scores. I noticed that there were several programs whose scores were very close. Hmmm, I thought, maybe to be fair these programs should be tied. But also to be fair, there must be a mathematical basis for anything I am going to do. (Anyone who doesn't like math or doesn't care about the details of this tournament's scoring stop reading here!) So, I decided arbitrarily that any ranking between two programs that I gave (i.e. Program A is better than Program B) would have to be statistically significant at the 90% level. That is, I wanted to be 90% sure that Program A was actually better than Program B, and the difference in scores was not simply due to chance. I decided (with a little help from a book and a statistics professor) that the best way to decide whether one program was significantly better than another was to use the following formula: _ _ x - x A B ---------------------- sigma sqrt (2/5000) p _ _ where x and x were the average scores of the respective programs FOR ONE A B ROUND, i.e. from 0 to 3. sigma (the pooled standard deviation) is the sum p of the squared differences from the mean of program A's scores (just like to calculate a regular standard deviation), plus the squared differences from the mean (B's mean this time) of program B's scores, all over the total number of trials (10000 in this case) minus 2, then square root the entire thing. Once this entire formula is calculated, it must be compared to the number 1.645, which is the number of standard deviations required to contain 90% of the data in a t-distribution (a t-distribution of data is like a normal distribution, but it's a little bigger at the edges i.e. slightly more probability of data far from the mean. t-distributions are used when you're dealing with pooled standard deviations like we are here). If the value of the formula is less than 1.645, then the two scores are not significantly different at the 90% significance level. Then, I set out to actually calculate these numbers. Well, it's a time- consuming process. Being lazy, I decided to make a small approximation and use the same pooled standard deviation for all pairs of programs. I approximated the average program submitted as getting scores of 4400 500 100 (remember there were 5000 rounds). From this I calculated that a significant difference between scores was one bigger than 152.95 points. However, applying this to the actual scores produced a problem. If you look at the scores above, you will notice that the first program's score is within 153 points of the second, and the second program's score is also within 153 points of the third, but the first and the third are further than 153 points. This is a problem! I can't just say that all three tie, because the first and the third are significantly different. But I can't not tie either the first and the second or the second and the third, because each of those differences is small enough to be insignificant. So, I decided that whenever this problem came up, I would look at the way the rankings would come out if I decreased the significance level, thus decreasing the maximum distance (normally 153 points) between programs which were to tie. I would use these rankings for that set of three programs. Basically, this means that the two with the closer scores would tie, and the other one would receive a different rank. I believe this is a fair system. ========== End of mathematical discussion ============= Oh, by the way, you may notice that I submitted a program to this round. DO NOT PANIC! This program does not count. I do not get any points. I just thought it would be fun to try. Also, there has been more discussion about round 2. Fibonacci numbers are too easy. Optima numbers are too hard. Digital root is not very interesting. I'm beginning to think prime numbers was a good choice all along! However, I've come up with one more idea. It is prime factorization. You are given a number and you must come up with a list of its prime factors (with repititions if there are any). I think this would work well. There is quite a bit of room for optimization (unlike digital root), I don't think it's too easy, and it's not too hard either. I'm still open to suggestions though. -- - Michael Constant mconst@ocf.berkeley.edu