|
||||
|
Title: 2007 Championship Tournaments Format Post by Fritzlein on Mar 30th, 2006, 5:39pm Last April I opened a discussion of what would be a good tournament format for the World Championship, and it led to a slew of simulations that showed floating triple elimination is pretty darned good at picking the best player with high probability in a small number of games. The 2006 Computer Championship highlighted two problems that weren't considered in the simulations, namely the difficulty in assigning second place, and the unfairness of assigning some pairings repeatedly and others not at all. Repeated pairings are particularly unfair when the ratings aren't transitive, but as far as I know, all the simulations assumed ratings transitivity. Therefore I decided to kick off this year's discussion with a non-transitive simulation. I had four players: A, B, C, and D. The win probablities were A beats B 60%, B beats C 70%, C beats A 70%, and all three of them beat D 80%. I started with a double round robin (12 games) because I could do an exact calculation rather than just a simulation. I was stunned to discover that there was a tie for first place a whopping 30% of the time! Apparently the tie we had in the 2005 Computer Championship was no fluke. However, if I split the point between the tied parties when there was a tie for first, the winning percentage for the four participants was A: 26.8% B: 39.9% C: 32.0% D: 1.3% So double round-robin does a decent job of selecting the strongest bot in a non-transitive situation. Still, I suspect that floating triple elimination (less than 11 games on average) would do a better job, even if the pairing algorithm were altered to avoid repeat matchups as a higher priority than giving the bye to the player with fewest losses. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Mar 30th, 2006, 6:00pm Let me also summarize the discussion of a few months ago. The advantages of a round robin format are: * Good ordering top to bottom * Absolutely fair strength of schedule * No problems with byes * No problem with repeated pairings The advantages of a floating elimination format are: * Fewer games necessary * Better chance the best overall player wins * No chance of a tie * No chance of collusion * Players with no chance of winnning don't need to play "pointless" games. The main propsals on the table seemed to be: (1) Mitigate the defects of the round robin format by having a "shrinking round robin" i.e. a multiple round-robin in which players with too many losses in the early rounds don't progress to later rounds. (2) Mitigate the defects of the floating elimination format by having a better pairing algorithm and a better way of determining second and third place. (3) Use option (1) for small tournaments and option (2) for large tournaments. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by omar on Apr 1st, 2006, 6:59pm The FTE performed really well for selecting first place, but it wasn't designed to select second place; and that was never one of our criteria in selecting a tournament format. So perhaps we could try for option 2; modifying the FTE to do better pairing in terms of repeated matches. The easiest would be to go with option 3; use double round robin when there are 6 or less players and FTE when there are more. Another option would be to redfine how second place is determined with the FTE. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Microbe on Jun 14th, 2006, 8:55am Can somebody actually explain floating double/triple elimination please? I've yet to fully understand it. ??? |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Jun 14th, 2006, 1:14pm on 06/14/06 at 08:55:21, Microbe wrote:
Sure thing. The main idea behind elimination tournaments is that you always control own destiny. You are never dependent on the outcome a game you aren't playing. You can only be knocked out by losing a game; otherwise you can always win the rest of your games and become champion. (This incidentally removes the possibility of collusion that exists in round robins, and also eliminates having to play "pointless" games.) In a double elimination you play until you have lost twice, and in a triple elimination you play until you have lost three times. In a floating elimination tornament there is no fixed bracket. The pairings are assigned round to round. Everyone plays in every round, unless an odd number of players remain, in which case one player gets a bye. The main idea behind floating pairings rather than a fixed bracket is to require everyone to win the same number of games in order to win the tournament. In a 16-player floating double elimination tournament, each player will have to win exactly six games to win the tournament, regardless of the order of wins and losses. In a 16-player fixed-bracket double elimination tournament, winning through the winners' bracket takes only five wins, whereas winning through the losers' bracket takes eight wins. The inequity is even greater in a 32-player fixed-bracket double elimination tournament: six wins through the winners' bracket and ten wins through the losers' bracket. Floating triple elimination is the most important variation, because there is no way that I know of to do fixed-bracket triple-elimination. If you want more than two eliminations in your elimination tournament, then you are forced to used floating pairing. The disadvantage of floating elimination tournaments is that a complicated formula is necessary to pair each round. Essentially the pairing must be done by a computer looking at all possible pairings and picking the best pairing according to certain criteria. These are the criteria that I like: * 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 similar W/L record against each other. * Give the bye to the player with the highest rating. * Maximize the sum of the squares of the rating differences. Meeting the goal of each level is subordinate to all higher levels, thus a pairing which is beautiful in all respects except that it gives a bye to someone who has already recieved a bye is worse than a pairing which violates all other constraints but which gives a bye to someone who hasn't gotten a bye yet. The priorities in the pairings are first to make everyone play the same number of games, and second to avoid repeat matchups. After that there is debate about what the priorities should be, and the above list simply reflects my ideas. I hope this makes sense; please ask more questions if it doesn't. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by chessandgo on Jun 14th, 2006, 2:38pm What is fixed bracket, Karl ? |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by jdb on Jun 14th, 2006, 3:18pm Quote:
Take a standard double elimination tournament, with the winners bracket and losers bracket. Add a double losers bracket that catches everyone that gets eliminated from the losers bracket. The brackets are all fixed. Quote:
A fixed bracket tournament has all the pairings determined ahead of time. An example of a single elimination fixed bracket tournament would be the French Open tennis tournament. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Jun 14th, 2006, 4:21pm on 06/14/06 at 15:18:42, jdb wrote:
I don't think this works very well. Consider a 16-player tournament. After one round there are 8 winners and 8 losers. In double elimination, the 8 winners play and 8 losers play, leaving 4 winners, 8 losers, and 4 double-losers. Next the 8 losers play again, leaving 4 winners, 4 losers and 8 double-losers. By having the losers play two rounds for every one round of the winners, you keep equal numbers of winners and losers the rest fo the way. But what would the double-losers bracket look like? If the initial 4 double-losers play, there would only be 2 of them left when the second batch of 4 double-losers arrives, which will leave a odd number when the 6 play off. On the other hand, if you wait for the second batch of double-losers to arrive, so that you can play with an even 8, then you've created a strange situation whereby records of LL, LWL, and WLL are all on an equal footing, i.e. losing the first two is just as good as winning two of the first three. I guess the latter is what you would have to do, even if it is strange. Then you could have 4 winners, 4 losers, and 4 double-losers. That could be reduced to 2 winners, 2 losers, and 2 double-losers if the winners played once, the losers twice, and the double-losers three times. It's just unattractive that winning one of the first three games is the worst way to start, because if you had just lost your first two you would have gotten a bye in the double-losers' bracket instead of expending the energy to play a third game. Now that I think about it, a fixed-bracket quadruple elimination would work with no additional glitches beyond the bye in the double-losers' bracket, because after the first games in the double-losers' bracket the triple-losers' bracket gets 4 players, and thus can be in synch with all the other brackets. Hmm... obviously it isn't as impossible as I thought. But even so I like the "equal number of wins to be champion" property of floating pairing. In the 16-player fixed-bracket quadruple-elimination format it seems one could be champion with 5 wins through the winners' bracket or be champion with 18 wins through the triple-losers' bracket. :-) |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Jun 14th, 2006, 4:23pm on 06/14/06 at 14:38:18, chessandgo wrote:
See http://www.foosballheaven.com/pdf/tournament16c.pdf There you can count the eight wins a first-round loser needs to become champion: six wins to be winner of the losers' bracket plus two wins against the winner of the winners' bracket. This contrasts to the easy path of winning four to be winner of the winners' bracket plus one win against the winner of the losers' bracket for five total wins to become champion. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by chessandgo on Jun 14th, 2006, 5:43pm actually one can object that, assuming that there's some strength order respected by the partial results, winning 5 straight games then losing one is a better performance than losing one then winning 5, as the latter makes you play every game with people having already lost once, which should be easier than playing leading players who had won everything before playing yourself. Now if you obeject that it doesn't compensate for the 2 extra wins needed I won't contradict you ... Still this phenomenon of losing early and having a easier tournament is a very usual one in swiss pairing systems used for most chess tournaments ... so I'd rather say that favouring better tournament starting is not a bad feature .... |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by chessandgo on Jun 14th, 2006, 5:46pm on 06/14/06 at 16:23:39, Fritzlein wrote:
Thanks ! Now I understand ... but I don't see why floating system is any different ... |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Jun 14th, 2006, 6:15pm on 06/14/06 at 17:43:27, chessandgo wrote:
It isn't a terrible feature if all the seedings are correct, but if two top players face off in an early round the loser is unreasonably punished. Consider the example that all the seedings are correct except that the #16 seed and the #1 seed are equally good. Whichever of the top two players loses in the first round is unreasonably punished. Suppose that all the favorites win until the best two players face off again for the title. In that case the winner will have to vanquish seeds #8, #4, and #2 to get to the championship game, whereas the loser will have to beat seeds #9, #7, #6, #4, #3, and #2. The six games are nearly as tough on average as the three games the winner played, except there are twice as many of them! Of course, when the top two meet again in the final, the first-round loser will have to win two games whereas the first-round winner will only have to win one game. This is exactly as it should be, because it exactly compensates for the first-round loss. Given that the exactly correct punishment for the first-round loss is built into the championship game(s) at the end, it is absurd to have the additional punishment of having to play three extra games in between. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by chessandgo on Jun 14th, 2006, 7:54pm OK, Karl, you're right, it's disproportionate ... so the floating double or triple elimination is a good one ? :) |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by Fritzlein on Jun 14th, 2006, 8:53pm on 06/14/06 at 17:46:53, chessandgo wrote:
You can look at the rounds of the 2006 World Championship http://arimaa.com/arimaa/wc/2006/showGames.cgi to see the difference. In Round 3 all twelve remaining players had to play, whereas in fixed-bracket double-elimination the four winners would all get a bye, waiting for the eight losers to play a round and reduce to four. In fixed-bracket double-elimination, the winners get every alternate round as a bye, but in the floating pairing nobody got a bye until Round 5 when there were an odd number of players left. It worked out neatly (because there were exactly 16 players) that the top finishers got one bye each, and that anyone, with or without one loss in any round, would have had to win six games to be champion. |
||||
|
Title: Re: 2007 Championship Tournaments Format Post by chessandgo on Jun 14th, 2006, 9:10pm indeed ... then it seems alright ? :) |
||||
|
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |