Author |
Topic: 2007 World Championship Format (Read 5293 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: 2007 World Championship Format
« Reply #15 on: Sep 10th, 2006, 4:25pm » |
 Quote  Modify
|
on Aug 23rd, 2006, 7:09am, Adanac wrote:| If Omar specifies is an upper limit maximum for the number of weeks, I would prefer a 128 double-elimination tournament rather than a triple-elimination with a smaller number of players. |
|
I totally agree. A 16-player triple-elimination and a 128-player double-elimination each last about 11 weeks. I would much rather keep the tournament open to all who want to play than have an extra elimination.
There is a balance between maximizing the chance of the best player to become champion on one hand, and keeping participation open on the other. I am extreme in favoring openness. If all you really want is to find the best player, then take the top four and play triple-round-robin. Sadly, in that scheme robinson wouldn't even have been allowed to compete last year, never mind win! Come to think of it, the best scheme for giving the World Championship to the best player last year would have been for Omar to give the title directly to me with no tournament at all. That would have eliminated the possibility of my being knocked out by a weaker player.
But no, it is much more friendly and fun to let everyone have a shot at the World Championship. If you wear the crown it shouldn't just mean that you are the best, it should mean you won the World Championship against all comers.
|
|
 IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: 2007 World Championship Format
« Reply #16 on: Sep 11th, 2006, 3:08pm » |
Quote Modify
|
wow .... now you are getting a bit overconfident 
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #17 on: Sep 11th, 2006, 6:32pm » |
Quote Modify
|
Is it possible to be overconfident about something that has already happened? You must mean I am getting arrogant  As for the coming tournament, who knows if I will even be the number one seed, never mind the eventual victor...
|
| « Last Edit: Sep 11th, 2006, 6:32pm by Fritzlein » |
IP Logged |
|
|
|
seanick
Forum Guru
SeaNICK
Gender:
Posts: 97
|
|
Re: 2007 World Championship Format
« Reply #18 on: Sep 12th, 2006, 4:04am » |
Quote Modify
|
re this statement: If you wear the crown it shouldn't just mean that you are the best, it should mean you won the World Championship against all comers.
what if you lose one? but everyone else loses at least 2, including the person you lost one game to. wouldn't that mean there was no champ? besides you don't have to be the best to go on a winning streak, nor do you have to be on a winning streak to be the best. for that matter, what does "best" mean anyway? best against humans, bots, both on average, most consistent, highest win percentage, nicest car, richest parents, ...?
whatever, its a dumb game anyway
(and if anyone actually thinks that I believe that, I also have a bridge for sale! please send the money in cash, unmarked non-sequential small bills in multiple standard-size briefcases, directly to 123 main street, anytown, usa. 78965. thanks! )
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: 2007 World Championship Format
« Reply #19 on: Sep 20th, 2006, 8:21am » |
Quote Modify
|
Pmertens stated:
Quote:| I propose a randomized pairing instead of the folded pairing of last year |
|
Here is my first draft at a randomized pairing system:
This description assumes two loses and the player is out. It can be extended to N losses.
Initially all players are placed in the zero losses pool.
1) If an odd number of players remain in the tournament, select a player randomly to receive a bye from those who have received the fewest byes.
2) If an odd number of players remain in the zero losses pool, select a player randomly from the one loss pool, to be paired with the zero losses pool, from those who have had to play "up" the fewest times.
3) Randomly pair the players in the zero losses pool, not allowing repeat pairings.
4) Randomly pair the players in the one loss pool, not allowing repeat pairings, unless everyone in the pool has played each other.
There is no guarantee that a valid pairing set is possible. So if no pairing is produced, try the algorithm again. After (say) 1000 tries if no valid pairing is produced, use the pairing produced by the last iteration.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #20 on: Sep 20th, 2006, 1:14pm » |
Quote Modify
|
On further reflection, I can see two possible benefits of not using the ratings for pairing. First, people won't inflate their ratings to get higher seeds. I don't think we should count this as a benefit, though, because there is a better way to achieve it. If you want to stop people from inflating their ratings by bot-bashing, a better method is for Omar to re-run his ratings algorithm on the games database, but using only HvH games, and seed the tournament based on those ratings.
The second possible benefit is fairness. I quite like the idea of everyone entering the tournament on an equal footing, with no handicaps to anyone. If low-rated players have to fight an uphill battle, that should be because they aren't as skilled as other players, not because they get terrible pairings, always against the toughest available opponent.
On the other hand, the principle of fairness conflicts with the principle of maximizing the probability of the best player becoming champion. Ratings don't in themselves accurately pick the best player, but they are a strong indiciator, and using ratings in folding pairing certainly improves the chances of the best players. If the Arimaa World Championship tournament seems to produce winners that are too random, the title of World Champion starts to lose respect. Look what happened when the international chess federation (FIDE) tried to say that Alexander Khalifman was the World Champion of chess, although he was rated around #40 in the world. Sure, he won the World Championship tournament, but nobody thought he was actually the best player, so it just made the title of World Champion look silly.
If we could have a triple-elimination format, then I guess I would go with fairness, because three losses should be enough for skill to win out even given rough pairings, but if we have only double-elimination, I think I have to cast my vote against random pairing. Seeding on the pre-tournament ratings is somewhat akin to having "the regular season" account for one elimination. If the seed are based on HvH games only, I don't think this is too unfair.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #21 on: Sep 20th, 2006, 2:04pm » |
Quote Modify
|
With floating double-elimination, and seeds based on HvH ratings, my preferred pairing algorithm for floating elimination remains:
* If an odd number of players remain, the bye must go to some player among the players with the fewest byes so far.
* Minimize the number of pairings occuring for the Nth time.
...
* Minimize the number of pairings occuring for the fourth time.
* Minimize the number of pairings occuring for the third time.
* Minimize the number of pairings occuring for the second time.
* Give the bye to the player with the fewest losses.
* Pair players with a similar number of losses against each other.
* Pair players with a similar number of wins against each other.
* Give the bye to the player with the highest rating.
* Maximize the sum of the squares of the rating differences.
Maximizing the sum of the squares of the rating differences (the lowest priority) is a way to insure folding pairing when nothing more important is going on. Notice that the ratings only influence pairings as the lowest two items on the list. Any way to increase the number of similar W/L pairings takes priority. Any way to reward in-tournament performace with a bye is higher priority than either of those. And any way to reduce the number of repeat pairings is higher priority than anything, except that you can never ever give byes unevenly.
Under this scheme, if there were an odd number of players, the highest-rated player would get the bye in the first round. In the second round the bye would go the the highest-rated winner from the first round.
If there were twice an odd number of players, there would be no bye in either the first or second round, but in the second round one winner would have to play one loser. The principle of maximizing the sum of squares of rating differences will mean that a high-rated winner plays a low-rated loser, while of course avoiding a repeat matchup. Since we already had #1 vs. #N and #2 vs. #(N-1) in the first round, it would probably be #1 vs. #(N-1) or #2 vs. #N, whichever gap is larger.
I believe that a human armed with pencil, paper, logic, and a little patience could implement this algorithm for the size of tournament we are talking about, even though it is theoretically exponential in the number of players, because in the early rounds only a couple of constraints are in play, and in the late rounds few players are left.
It's interesting to note that this algorithm would have made a slight difference in the World Championship tournament last year. The first five rounds would have been the same, but in round six the repeat matchup would have been avoided. Robinson had already beaten Adanac. Adanac had already beaten PMertens. So why did Adanac have to play Robinson again? I think it is slightly unfair that PMertens got the bye on the basis of a higher rating. Fairer would be make PMertens and Robinson play (NOT a repeat matchup) and give the bye to Adanac. So I think my current proposal would have done better for the WC.
For the Computer Championship, I formalized this algorithm precisely to prevent a repeat Bomb-Clueless pairing in the seventh round (indeed, already in the sixth round) in favor of a first-time Bomb-Aamira pairing. But I also want to point out again that my current proposal would have avoided a grave injustice already in round three of the Computer Championship. Loc, which had already lost to Aamira and Bomb, was paired against Aamira again, instead of against Clueless. If Loc happened to have some bug that only Aamira triggered, then it is an unfair advantage to Aamira to get a repeat matchup and also an unfair penalty to Loc. We didn't fuss about it much at the time, because Loc would probably have lost to any bot it played, but still it wasn't fair, and it wouldn't happen again with what I now propose.
What do you guys think, am I just too attached to the floating elimination format, or can it really work well if we do the pairings right?
|
|
IP Logged |
|
|
|
PMertens
Forum Guru
Arimaa player #692
Gender:
Posts: 437
|
|
Re: 2007 World Championship Format
« Reply #22 on: Sep 20th, 2006, 2:21pm » |
Quote Modify
|
I still dislike folding by ratingdelta² ... especially in round 1.
I see really no need in making it even harder for those less experienced/rated by putting them up against the worst possible opponent.
And you on the other hand do need a handicap and not a read carpet 
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #23 on: Sep 20th, 2006, 3:58pm » |
Quote Modify
|
on Sep 20th, 2006, 2:21pm, PMertens wrote:| And you on the other hand do need a handicap and not a read carpet |
|
Hmm... I guess when I argue for folding pairing, I'm arguing for my own benefit, since I temporarily have the #1 rating. Maybe I should recuse myself from the discussion, since I have a stake in the outcome.
Anyway, like I said, I can see both sides. I don't want the Arimaa World Championship title to become a joke, but the idea of everyone starting the tournament on a level playing field is attractive too. I'll be happy whatever Omar decides.
If ratings are not used in the pairings, I still want all the other pairing guidelines there, though, in the same priority, i.e.
1) Equal distribution of byes
2) No repeat pairings
3) Bye to player with fewest losses
4) Equal records play each other.
None of those give anyone a red carpet...
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: 2007 World Championship Format
« Reply #24 on: Sep 20th, 2006, 4:07pm » |
Quote Modify
|
Quote:If ratings are not used in the pairings, I still want all the other pairing guidelines there, though, in the same priority, i.e.
1) Equal distribution of byes
2) No repeat pairings
3) Bye to player with fewest losses
4) Equal records play each other.
|
|
I am curious what the rationale is for rule number three. I'm not offering an opinion for or against it, I just wish to know the reason for the rule. Thanks
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #25 on: Sep 20th, 2006, 7:26pm » |
Quote Modify
|
on Sep 20th, 2006, 4:07pm, jdb wrote:| I am curious what the rationale is for rule number three. |
|
The problem with assigning byes is that in some cases one player will be able to win the tournament with fewer total wins than another player. In the run-up to last year's tournament, I was expecting fewer than 16 players to participate. As I played out several scenarios for floating double elimination with fewer than 16 players, it became clear that some players would have to win six games to become champion, whereas players on a different path could become champion with only five wins. It made sense to me that if any player should get the easier path, it should be the one who has the best record so far in the tournament.
(By the way, contrast the difference between five and six wins in a twelve-player FDE with a fixed-bracket twelve-player double-elimination. In the fixed bracket a player who gets the early bye and wins out needs only four wins to become champion, but a first-round loser has to win seven to become champion. So the potential unfairness of floating double elimination is still less than of fixed-bracket double elimination.)
Anyway, to my surprise, it turned out that in a 16-player floating double elimination, with the first bye going to the one undefeated player after four rounds, there is perfect equity. Every player, no matter their seed or order of wins and losses, has to win six to become champion.
When David Levy proposed giving the bye to the lowest loser instead, Ryan Cable pointed out that it not only destroys the perfect equity, but could indeed result in a two-game disparity in winning path:
on Jan 25th, 2006, 7:44pm, Ryan_Cable wrote:If we had followed David Levy’s system in the WC, robinson would have had to win seven games if he went undefeated:
Round 5
Adanac - bye
robinson - PMertens
Fritzlein - 99of9
Round 6
Fritzlein/99of9 - bye
robinson - Adanac
Round 7
robnson - Fritzlein/99of9
But worse still, if in Round 5 PMertens beat robinson and Fritzlein beat 99of9, robinson would have to face PMertens again.
Round 6
Fritzlein - Adanac
robinson - PMertens
Round 7
Adanac/Fritzlein - PMertens/robinson
Perhaps the most horrible thing is that Adanac would be able to win the Championship with only 5 wins as a reward for being the lowest rated loser. |
|
My hope, although I haven't proven this by any means, is that by giving the bye to the player with the fewest losses, the disparity in the number of wins required to become champion is kept down to ONE at most, and furthermore, the player(s) with the championship route requiring one less win is(are) the player(s) getting an early bye for not having lost up to that point.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: 2007 World Championship Format
« Reply #26 on: Sep 20th, 2006, 10:19pm » |
Quote Modify
|
With our current FxE algorithm do pairing problems only occur in rounds where a bye is required or could they also occur in rounds where there are even number of players?
If the problem is only in rounds where a bye is required then I can have it cycle through giving a bye to each player to generate a set of possible pairings (equal to the number of players) and score each pairing and pick the one with the best score.
|
| « Last Edit: Sep 21st, 2006, 12:08pm by omar » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2007 World Championship Format
« Reply #27 on: Sep 21st, 2006, 8:33am » |
Quote Modify
|
I'm afraid the best pairing can be hard to find both when there is a bye to be given and when there isn't. It's not enough to try one pairing for each possible bye. For example, look at round three of the 2005 Computer Championship. Bomb is the obvious choice for a bye, because Gnobot and Clueless already had byes, while Aamira and Loc have losses, but Bomb is undefeated. However, There are three possible pairings of the other bots once Bomb has the bye, and only one of the three avoids repeat matchups. If you just create one pairing which gives Bomb the bye, you might incorrectly conclude that Bomb shouldn't be given the bye.
The good news is that with only five players (or six) there are only fifteen possible pairings total. We could look at all fifteen. The top priority (even distribution of byes) knocks out six with Gnobot and Clueless getting a bye compared to any of the nine where Bomb, Aamira, or Loc gets a bye. The second priority is repeat matchups, and of the remaining nine possibilities six are rejected for creating a repeat matchup, leaving only three. The third priority, giving a bye to a player with few losses, breaks the tie between those three, leaving only one possible pairing, and making the further criteria irrelevant.
Remember that Paul Pogonyshev wrote some branch-and-bound code to seek the best pairing, so you wouldn't have to start from scratch in getting a computer pairing algorithm:
on Jan 22nd, 2006, 1:31pm, doublep wrote:OK, I implemented an overkill solution (1000 lines of C++.) You can grab it at http://download.gna.org/quarry/tournament.cpp (modified BSD license, use as you please.)
Usage: compile and run with tournament data redirected to its stdin, e.g.
Code:
$ g++ tournament.cpp -o tournament
$ ./tournament <test-tournament
|
|
Data is in the following format:
Code:
tournament-scheme [parameters]
number-of-players-initially
player-name rating
...
number-of-rounds-player
player-1 player-2 winner
...
...
|
|
With ellipsis standing for repetition. E.g. for the WCC 2006 it would be:
Code:
elimination 3
5
bot_Gnobot 1667
bot_Loc 1586
bot_Aamira 1580
bot_Clueless 1574
bot_Bomb 1484
2
bot_Gnobot
bot_Loc bot_Bomb bot_Bomb
bot_Aamira bot_Clueless bot_Clueless
bot_Clueless
bot_Bomb bot_Gnobot bot_Bomb
bot_Aamira bot_Loc bot_Aamira
|
|
The penalties are not perfect, but produce more or less sensible results. Feel free to experiment. And happy reading, the code is almost uncommented  |
|
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: 2007 World Championship Format
« Reply #28 on: Sep 21st, 2006, 8:56pm » |
Quote Modify
|
Just wanted to add a note on my thoughts on the WC format goals (I thought I posted something similiar a year or so ago but can't find it at the moment).
I personally do not think the primary goal in determining the world championship tournament format should be to make it "fair". Rather the primary goal should be to make it accurate, i.e. having the greatest likelyhood that the truly best player in the world wins. Now in many ways I think this still leads to a "fair" tournament as I don't think it's at all out of the question with the current state of Arimaa for a relatively new player to be way underated and actually be the best player. But I don't think accuracy should be compromised for the goal of fairness. Of course determining the accuracy, or even relative accuracy, of given formats is not simple and probably very open for argument.
Also as a secondary goal I think the rules for any tournament should be as transparent as possible. Random pairing to me seems to be about the worst possible option in that regard. I think the FxE formats are already bad enough in that you can't "tell at a glance" if the pairings are correct1 but I think they make up for it by the gain in accuracy.
Janzert
1. e.g. not made as to give any player a special advantage. I was also going to say that the random pairing doesn't allow for independently checking the pairing, but this could probably be done by publishing the prng algorithm and seed for each round before the tournament begins.
|
| « Last Edit: Sep 21st, 2006, 10:51pm by Janzert » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: 2007 World Championship Format
« Reply #29 on: Sep 21st, 2006, 10:27pm » |
Quote Modify
|
Thanks for reminding me about Paul's program. I've downloaded it and started trying to work it into the tournament simulator.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print