Author |
Topic: World Championship tournament format (Read 9311 times) |
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
 |
Re: World Championship tournament format
« Reply #30 on: May 22nd, 2005, 6:56pm » |
 Quote  Modify
|
on May 22nd, 2005, 10:48am, omar wrote:
If we use measured ratings from the previous tournaments, what should we do about the true ratings. Should we just add a random number in the range of the rating inaccuracies to the measured rating and use that. Should the true ratings be changed from one trial to the next, or computed just once and used for all trials?
|
|
Here's my personal suggestion:
1) Add a random number selected from the gaussian (normal) distribution, with the standard deviation determined by how inaccurate you think the ratings are. As you mentioned before, this parameter can be varied and different simulations done. Actually though, I think that even using a standard deviation of 0 (where predicted rating == true rating), will produce interesting results of the type you are after.
2) Choose a set of (true,predicted) ratings. Don't change them until after you have tested all tournament formats with them. As long as all tournament formats get to see the same sets of ratings the same number of times, it is probably good to recalculate the real ratings in between iterations. In psuedocode:
get_predicted_ratings_from_old_tournament()
for (1<iterations<1000) {
get_real_ratings_from_predicted_ratings_and_normal_distribution()
for (1<tournament_method<Num_Methods) {
simulate_tournament()
is_winner_highest_real_rated()
}
}
|
|
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #31 on: May 23rd, 2005, 6:12pm » |
Quote Modify
|
on May 22nd, 2005, 6:46pm, 99of9 wrote:
One thing is clear about the sliding system, with no simulations necessary. In every round the top rated player has to play a harder opponent than the second rated player, until they meet. This creates a clear bias toward the chances of the 2nd top player winning the tournament.
|
|
True, but in a crossover (or folding) system the second rated player has to play a harder opponent in each round than the first rated player. So the top rated player is biased to win in this case. In the sliding system the rating difference between the pairs of players would on average be about the the same, but with the folding system, it would be much higher at the top than at the bottom. So I can see players complaining (especially the lower rated ones) that they had to play a much harder opponent than players who are rated higher than them. In a sliding system this complaint is not justified because the rating difference between the pairs of players would be about the same.
No matter what tournament system we pick there is going to be some players who don't like it. I don't want us to be in a situation where we are defending the system we picked based on vauge arguments. We should be able to say this is what our objects were for the system, we evaluated various systems objectively and picked the one that best met the objectives. Someone else should be able to come to the same conclusion by looking at that. If they differ about the objectives, that's a different story 
Anyways Im not against using a folding system. If the simulations show that it's better than we will have a valid justification for using it. If our objective is for the player with the highest true rating to win then it might well be a better system. But how much rating inaccuracy can this system tolerate. I don't know yet, but the simulations can help answer that.
|
| « Last Edit: May 23rd, 2005, 6:35pm by omar » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #32 on: May 23rd, 2005, 6:30pm » |
Quote Modify
|
on May 22nd, 2005, 6:56pm, 99of9 wrote:
Don't change them until after you have tested all tournament formats with them. As long as all tournament formats get to see the same sets of ratings the same number of times, it is probably good to recalculate the real ratings in between iterations.
|
|
Thanks for the suggestions.
The way Im doing it now is you have to type:
run [tournament format program] [other arguments]
and it runs all trials with one tournament format. You have invoke it again to run it on a different tournament format. This makes it easy to add new tourament formats without having to change the 'run' program directly.
But I guess we can seed the random number generator with the same value before running the next tournament format to get what you suggested.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #33 on: May 23rd, 2005, 6:41pm » |
Quote Modify
|
I took a look at the arimaa rating system and did a little analysis.
Rating Prob. of Winning
Difference 1 Game 3 Game Match
400 0.91 0.98
350 0.88 0.96
300 0.85 0.94
250 0.81 0.90
200 0.76 0.85
150 0.70 0.79
100 0.64 0.70
50 0.57 0.61
0 0.50 0.50
-50 0.43 0.39
-100 0.36 0.30
-150 0.30 0.21
-200 0.24 0.15
If the difference is under (say) 200 points the chance of an "upset" is still fairly common. The current arimaa rating list has about 10 players in the 1850-2050 range. A short tournament would have a tough time separating these players.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #34 on: May 23rd, 2005, 6:44pm » |
Quote Modify
|
on May 23rd, 2005, 6:12pm, omar wrote:| but in a crossover (or folding) system the second rated player has to play a harder opponent in each round than the first rated player. So the top rated player is biased to win in this case. |
|
That is definitely preferable if our aim is to select the player with the highest real rating. No matter how large the ratings inaccuracy parameter is, the player with the highest predicted rating is the *most likely* to have the highest real rating (unless there has been ratings manipulation). Therefore if you're going to give someone this "favouritism" of course it is better to give the #1 the easier run than to give it to #2. [Although i agree that in principle it would be even better still for them both to play opponents with an approximately equal total rating.]
On a pragmatic basis it is also better to favour the #1 so that the best player is not tempted to manipulate his/her rating to go into the tournament as #2. This is something that simulations will not tell us!
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #35 on: May 23rd, 2005, 6:50pm » |
Quote Modify
|
on May 23rd, 2005, 6:30pm, omar wrote:| But I guess we can seed the random number generator with the same value before running the next tournament format to get what you suggested. |
|
But that will only work if the random number generator is not used during each tournament itself. Different tournament schemes might call the RNG a different number of times.
Perhaps my warning was too strong anyway though - the disadvantage with the tournaments seeing different ratings lists is only that more samples will be required to obtain correct, low error averages. Perhaps your simulation will run fast enough to make these averages repeatable and accurate anyway.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #36 on: May 23rd, 2005, 7:03pm » |
Quote Modify
|
on May 23rd, 2005, 6:12pm, omar wrote:| So I can see players complaining (especially the lower rated ones) that they had to play a much harder opponent than players who are rated higher than them. In a sliding system this complaint is not justified because the rating difference between the pairs of players would be about the same. |
|
This complaint *is* justified in your scheme for #9, who as I outlined above has to play #1, when #8 gets to play against #16 !!! This difference between opponents of adjacent players is bigger than any that will occur in the crossover scheme. I think you've just put all your "opponent ratings divergence" eggs in one basket (#8 vs #9) rather than spreading them out throughout the field.
Anyway... how likely is it really that #16 is actually the best real-rated arimaa player If the aim is to select the best player, then it makes sense to me that the #16 is the most likely to get knocked out in the first round. In the sliding scheme #9 is just as likely to get knocked out as #16 (and perhaps *more* likely if the #1 happens to be way ahead of the field, rated at 2300 perhaps).
|
| « Last Edit: May 23rd, 2005, 7:08pm by 99of9 » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #37 on: May 23rd, 2005, 7:27pm » |
Quote Modify
|
on May 21st, 2005, 11:03am, omar wrote:| We can vary the distribution range as well and see how that effects the results. But keep in mind that we are not interested in the result of any one format, but rather a comparision between formats. So if format A is better than format B for the range I proposed, it will probably be better on a different range as well. |
|
This sounds like a guestimate to me . Actually I was more talking about the distribution shape than about the range. You assume a uniform-random distribution, but to me it seems more likely to have a long spread-out tail toward the higher ratings.
on May 21st, 2005, 11:03am, omar wrote:| Since there doesn't seem to be any volunteers to do this, I'll start on it. |
|
I admire your get-in-there-and-do-it work ethic! I think the results will certainly be interesting, but the coding of many different tournament schemes too time-consuming for my liking.
|
| « Last Edit: May 23rd, 2005, 7:28pm by 99of9 » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #38 on: May 23rd, 2005, 11:01pm » |
Quote Modify
|
on May 23rd, 2005, 6:41pm, jdb wrote:
A short tournament would have a tough time separating these players. |
|
Yep, that what Im finding also as I run the simulations.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #39 on: May 23rd, 2005, 11:56pm » |
Quote Modify
|
Well Toby, you will be happy to know that the crossover (or folding) variation of the single elimination tournament works relatively well.
Here's what Im finding:
2000 trials were done for each of the following type of tournaments. Each trial used 16 random players with a measured ratings in the range of 1500 to 2000 and a rating error of +-50.
seR: 28.8% single elim; random seeding of players
seO: 24.9% single elim; players ordered by ratings
seS: 28.0% single elim; slide method of pairing at each round
seF: 35.6% single elim; fold method of pairing at each round
rrS: 36.7% round robin single game between each pair
rrD: 37.6% round robin double; two games between each pair
Very interesting results. seF is almost as good as round robin and seS is no better than random seeding.
Suprisingly round robin, with all that extra effort is not much better than single elimination; and double RR is hardly any better than single.
But maybe there are still bugs in my programs. Right now, I can't seem to find them. But feel free to download the programs and try it out.
http://arimaa.com/arimaa/tourn/compare/sim.tar
or in ZIP format:
http://arimaa.com/arimaa/tourn/compare/sim.zip
|
| « Last Edit: May 23rd, 2005, 11:59pm by omar » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #40 on: May 24th, 2005, 2:42am » |
Quote Modify
|
Thanks for providing those Omar.
I have no idea about the language the programs are in, so I'll stick to testing them out.
One problem is:
run singleElimFold 1000 2 0 0 99999
1 100.0%
In other words if the 2 top players in a tournament both have the same rating, the program counts either of them winning as a successful tournament.
Here's another very strange result, but maybe it is legit...
run singleElimSlide 1000 16 500 0 99999
1 20.0%
2 20.8%
3 18.9%
4 13.2%
(all I've done is remove all possibility of draws and make the predicted ratings perfect)
Does the sliding mechanism really favour player #2 so much that they are *more* likely than #1 to win??
Omar is there a way to fix the ratings by hand and then simulate many tournaments with that set? (I've only skimmed readme.2nd - so just tell me if I should look at it harder)
|
| « Last Edit: May 24th, 2005, 2:42am by 99of9 » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #41 on: May 24th, 2005, 8:34am » |
Quote Modify
|
Quote:In other words if the 2 top players in a tournament both have the same rating, the program counts either of them winning as a successful tournament.
|
|
Sounds ok to me
Quote:Does the sliding mechanism really favour player #2 so much that they are *more* likely than #1 to win??
|
|
It can happen. Consider a 4 person tournament.
Mr. A rated 2000
Mr. B rated 1950
Mr. C rated 1945
Mr. D rated 1700
The fold seeding method favours Mr A
The slide seeding method favours Mr B
Although, I'm not sure if the slide method actually gives Mr. B a higher chance of winning than Mr. A.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #42 on: May 24th, 2005, 8:45am » |
Quote Modify
|
on May 24th, 2005, 8:34am, jdb wrote:
It can happen. Consider a 4 person tournament.
Mr. A rated 2000
Mr. B rated 1950
Mr. C rated 1945
Mr. D rated 1700
The fold seeding method favours Mr A
The slide seeding method favours Mr B
Although, I'm not sure if the slide method actually gives Mr. B a higher chance of winning than Mr. A.
|
|
If Mrs A was instead rated 1951 then you're right, B would definitely have a higher total chance than A. Good example.
About the 2 equal rated player thing - I'd prefer it to record 50% (as it would if the players were split by 1 rating point). That way accidents don't skew the overall averages. But actually the reason I want it is mostly because there was another calculation I wanted to do but couldn't the way it is currently set up.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #43 on: May 24th, 2005, 1:51pm » |
Quote Modify
|
on May 24th, 2005, 2:42am, 99of9 wrote:
I have no idea about the language the programs are in, so I'll stick to testing them out.
|
|
They are written in Perl. A good language for writting programs quickly if you don't care too much about the program running very fast. A perl program runs about 100 times slower than a C program, but you can probably write it 10 times faster in Perl.
Quote:
One problem is:
run singleElimFold 1000 2 0 0 99999
1 100.0%
In other words if the 2 top players in a tournament both have the same rating, the program counts either of them winning as a successful tournament.
|
|
I wanted to suggest a quick change that you could make to your copy to get that, but I don't see how to do it. Here is what's currently happening:
After a tournament completes we have an array with the names of the players that tied for first place. For each of these players we determine their rank based on their true rating. We maintain another array that is a histogram of what ranks have won the tournament. The result of 'run' is printed from that histogram array.
Quote:
Here's another very strange result, but maybe it is legit...
run singleElimSlide 1000 16 500 0 99999
1 20.0%
2 20.8%
3 18.9%
4 13.2%
|
|
Seems the slide method does give the second player a pretty good chance, but the advantage of 0.8% is just a fluke. When I ran it a couple of times the second rank came out a bit lower then the first.
Quote:
Omar is there a way to fix the ratings by hand and then simulate many tournaments with that set? (I've only skimmed readme.2nd - so just tell me if I should look at it harder) |
|
Yes, there is now. I ment to add that, but forgot. Download a new copy to get this feature. You can create a file with the player names and measured ratings and pass the name of that file in place of the 'number of players' argument.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #44 on: May 24th, 2005, 2:03pm » |
Quote Modify
|
Wow, a major break-through !!!!
I came up with a tournament format that is both short, and very good; it's even better than round robin; it has a percentage of about 64% compared to 37% for round robin for the 16 player case. I 've named this format the swissKnife
Download the new version:
http://arimaa.com/arimaa/tourn/compare/sim.tar
or
http://arimaa.com/arimaa/tourn/compare/sim.zip
and run it like this:
run swissKnife 1000 16 500 50
to see a detailed description of how it works type:
formats/swissKnife
Absolutely amazing
|
| « Last Edit: May 24th, 2005, 7:37pm by omar » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print