Author |
Topic: Floating Elimination Pairing Algorithm (Read 2535 times) |
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender: 
Posts: 138
|
 |
Re: Floating Elimination Pairing Algorithm
« Reply #15 on: Jan 23rd, 2006, 11:53am » |
 Quote  Modify
|
I dislike round robins for awarding a serious title. I think it puts too much importance on how strong players do against weak players rather than focusing on how the strong players do against each other. It is a bit less of a problem for bots and for drawless games, but I still don’t like it.
I think using doublep’s global search pairing would resolve many of the obvious problems with the floating elimination tournament pairing, but I think there will always be an element of pairing luck in any elimination tournament, particularly when the ranking of bots is essentially random. The best way to deal with this is to increase the number of eliminations.
With two games per day is there any reason the tournament shouldn’t be allowed to go for three weeks? Personally, I would like to see F5E. It would require at most 24 games for 5 bots, and 39 games for the maximum 8 bots. You could also make an argument for a single elimination tournament with best of 7/9 matches, but given that the ranking of bots is almost random, I think F5E is clearly better. Also, F5E is much more interesting than single elimination since many different bots play each other.
I think the putting the assignment of byes into the global search would produce the same results as our current assignment process if the weights for byes were fairly chosen. Assigning byes is likely to always be a problem when the number of bots is less than the number of rounds.
|
|
 IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #16 on: Jan 23rd, 2006, 2:02pm » |
Quote Modify
|
Feel free to experiment with my program  It currently has bye penalty larger than the sum of game penalties (equivalent to first assigning a bye, then looking at the pairings), but this can be changed. The order of penalty importance should probably be like this:
- Make byes go only to the players with least byes so far.
- Make byes go to the player with the least number of losses.
- Make the number of repeating games in this round the least possible.
- Make the bye go to the player with the highest rating.
- Make the players with similar W/L record play against each other.
- Make the ratings of each pair opponents as different as possible.
Maybe some of the items above should not dominate the others completely.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #17 on: Jan 23rd, 2006, 5:00pm » |
Quote Modify
|
I am abjectly sorry for the way the pairings are working out for this Computer Championship, based on the pairing algorithm I proposed. Bomb is clearly the top dog so far, so it just isn't fair to Clueless to have to play Bomb three times before Aamira has to play Bomb once. I guess the algorithm worked so amazingly well for the World Championship only because we had 2^4 players then.
That said, I quite agree with Ryan in my general preference for elimination tournaments rather than round robins, for several reasons. (1) Round robins are too likely to end tied. For example, the 2005 Computer Championship was double round-robin, with poor results. Clueless and Bomb each beat all the other bots, but split their two games with each other. (2) Our equipment limits the number of games (not rounds) that can be played, so it is better to use the games to determine finer distinctions among the top bots than to have lots of lopsided wins between top bots and bottom bots. (3) We want a completely correct champion more than we want a completely correct ordering top-to-bottom. (4) In human tournaments especially, it can skew the outcome for a player to fight hard until mathematically eliminated, and then play remaining games perfunctorily, if at all. Also collusion may rear its ugly head.
So if we can improve the structure of the elimination tournament somehow, that's what I'd prefer. Yet I agree with Grey0x2a's comment in chat today that a transparent system is extremely important. Players are always going to get unfavorable pairings, even in the best possible system, so the rules need to be crystal clear. In particular, clarity requires the levels of weights to be absolute. If there is anything like 2.371 repeat pairings being worth a bye out of turn, it will make the pairings impossible to understand without a computer, never mind impossible to generate.
I like doublep's list of priorities, but I would raise the repeated pairing priority even further:
* Give the bye 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.
To be clear, I'm now proposing that any betterment in avoiding repeat matchups should trump the assignment of the bye between players with an equal number of byes. If you have to give the bye to the bottom player in the field to avoid a repeat, so be it.
Also I'm proposing that avoiding one third-time matchup is worth accepting any number of second-time matchups, etc.
I have purposely put in pre-tournament ratings only in the bottom two criteria. Both in the World Championship and in the Computer Championship there were some seriously skewed pre-tournament ratings, so I want ratings to be relied on as little as possible.
If my current proposal were put into force immediately, then the round six bye could not possibly go to Aamira (on the basis of rating) or even to Bomb (on the basis of W-L record). Since all three bots have received one bye, we should look first at repeat pairings. Bomb and Clueless have played twice, Aamira and Clueless have played once, but Bomb and Aamira have never played. In my mind, to pair Bomb and Aamira while Clueless gets the bye is clearly the fairest pairing.
JDB, if you protest my pairing algorithm to Don Dailey, requesting that Round 6 be forced to be Bomb vs. Aamira, I will wholeheartedly support your claim.
|
| « Last Edit: Jan 23rd, 2006, 6:09pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #18 on: Jan 23rd, 2006, 5:23pm » |
Quote Modify
|
Incidentally, the CC tournament pairing algorithm is simplified from what I originally proposed in April. If we go back to what I said in April, before Omar asked for an easy implementation, then we also get Bomb-Aamira in round 6. So arguably, the intent of the algorithm was clear all along, and what we settled on was a buggy implementation more than a different philosophy.
on Apr 29th, 2005, 12:01pm, Fritzlein wrote:
I expect the pairings would be complicated enough that they would have to be done by machine algorithm rather than by hand. Still, for a programmer it should be easy enough to be worth doing if the goals of formatting the tournament are worth striving for. Here is my proposed algorithm:
Rule 1: When an even number of players remain, everyone plays the round. When an odd number remain, one player gets a bye. No player may get a second bye unless every remaining player has already recieved one bye. Similarly no player can get an (n+1)st bye unless all remaining players have n byes.
Rule 2: Subject to Rule 1, the pairings for each round must minimize the number of repeat matchups. A pairing which has a matchup for the (n+1)st time must be rejected in favor of any in which all matchups are occuring for the nth time or fewer.
These are absolute rules which are enough to ensure that the goals of the tournament are met, but if there are multiple pairings which meet the requirements, one might prefer one pairing to another based on things like:
* Minimizing the number of second-time matchups is desirable among all pairings which don't have any third-time matchups
* Matching players with the same record is desirable, i.e. it's better to have two 2-0 players matched and two 1-1 players matched than to have two matchups of 2-0 vs. 1-1.
* Giving a bye to the highest-rated player eligible for the bye is desirable.
* Perhaps as a tiebreaker between two pairings equal on all these counts, pick the one which minimizes the sum of the squares of the rating differences
|
|
|
| « Last Edit: Jan 23rd, 2006, 6:12pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #19 on: Jan 23rd, 2006, 6:43pm » |
Quote Modify
|
on Jan 23rd, 2006, 5:00pm, Fritzlein wrote:| I am abjectly sorry for the way the pairings are working out for this Computer Championship, based on the pairing algorithm I proposed. Bomb is clearly the top dog so far, so it just isn't fair to Clueless to have to play Bomb three times before Aamira has to play Bomb once. I guess the algorithm worked so amazingly well for the World Championship only because we had 2^4 players then. |
|
To be fair to you, you have also been hurt by the fact that a buggy version of bomb was playing all December, and thus obtained the lowest pre-tournament rating. If that rating had been accurate, clueless would actually be enjoying playing bomb three times (assuming buggy-bomb had luckily obtained the undefeated tournament record its tournament counterpart has).
|
| « Last Edit: Jan 23rd, 2006, 6:49pm by 99of9 » |
IP Logged |
|
|
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender:
Posts: 138
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #20 on: Jan 24th, 2006, 2:17am » |
Quote Modify
|
First, one thing that seems to have been overlooked in all of this is that despite the imperfect pairing algorithm, the FTE is performing its design purpose wonderfully. It is now essentially a certainty that the True Champion (Bomb) will win the CC, and do so by facing and defeating all 4 opponents. Only Aamira has any notable chance of beating Bomb. In the unlikely event that Aamira (or Clueless) manages to win one game or more against Bomb, first and second place should be undisputed. Thus, the following assumes that Bomb goes undefeated. (Personally, I think this has a 98%+ chance anyway.)
Under the pairing procedure specified in the rules, the next game will be Aamira v Clueless. If Aamira beats Clueless, Clueless will be eliminated with a 2-3 record and being 1-1 against Aamira; Aamira would then lose 2 in a row to Bomb and be eliminated with a record of 4-3. In this case, Aamira takes second place unambiguously.
However, if Clueless beats Aamira, then Aamira gets a bye, while Clueless is beaten by Bomb and eliminated with a 3-3 record. Aamira is then the last bot to be eliminated, losing to Bomb and finishing with a 3-3 record. The rules don’t specify how second place is determined (or first place for that matter), but conventionally the last bot eliminated is given second place in an elimination tournament. Also, (I assume) the last player eliminated (Adanac) was given second place in the WC. Still the fact that Clueless is 2-0 against Aamira makes it seem unjust to have Aamira get second place, just because it got a bye, just because it was rated 6 points above Clueless.
If we go with Fritzlein’s suggestion and have Bomb play Aamira, Bomb gives Aamira its second loss, then Clueless plays an elimination game against Aamira, and finally the survivor is eliminated by Bomb. The important thing to notice is that these are the exact same games as above, just in a different order. As both a practical matter and a philosophical matter, the order in which the games are actually played doesn’t make any difference.
Ultimately, it all comes down to whether we think Aamira should be awarded second place (and the $200 that comes with it) even if it loses to Clueless for a second time. This is marginally ambiguous, since it was never specifically stated in the rules that second place goes to the last player eliminated, but I think this was widely assumed. My personal sense of fairness says that we have to play the ball as it lies, even though the rules and the pairings have clearly treated Clueless very harshly. Others have different opinions.
Still, laying the blame for this on FTE or on Fritzlein’s imperfect pairing algorithm is a mistake. FTE was not designed to do a particularly good job of picking second place, and like all elimination tournaments, pairing luck plays a large part in the assignment of second place. A globally optimal pairing algorithm would have performed better, but fixing the huge errors in the bot rankings is going beyond the call of duty anyway. If we had gone with a single elimination tournament (with games or matches), fourth ranked Clueless would have faced fifth ranked Bomb and been the first bot eliminated. Second ranked Loc would lose to third ranked Aamira, while Bomb beats first ranked Gnobby. Then Bomb would win the tournament knocking out Aamira in second place. This would be significantly less fair than FTE, but it would probably also be less disputed simply because people are more familiar with how single elimination tournaments work.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #21 on: Jan 24th, 2006, 8:20am » |
Quote Modify
|
Excellent points, Ryan. The CC tournament format is apparently doing well at picking first place, and only second place is at issue. Single-elimination does a terrible job of picking second place, yet everyone accepts it as fair because they are used to it. In single-elimination with these terrible seedings, Clueless would have taken fifth!
If Aamira can beat either Bomb or Clueless even once before being eliminated, then Aamira has as good a claim to second place as Clueless, and there is no problem. Unfortunately, the probable scenario is, as you say, Clueless beats Aamira, Bomb beats Clueless, Bomb beats Aamira. If neither Clueless nor Aamira can beat Bomb, but Clueless is 2-0 against Aamira, then Clueless is clearly the second-strongest bot.
If second place were inferred directly from the results and awarded contrary to the order of elimination, then there would be no problem, but unfortunately second place is implicitly defined by order of elimination. Although it isn't explicitly stated who takes second, it would bend the rules just as much to not give second place to the last bot eliminated as it would bend the rules to change the order of the games. Playing the ball as it lies will probably mean that the second-strongest tournament performance will be awarded third place.
Therefore I stand by advocating for changing the order of the games. Bomb and Aamira should play in round six, and if Bomb wins, Clueless and Aamira can play an elimination match for second place. I am not advocating this just because it happens to avoid a problem in this tourament scenario, but also because it is the way pairings should work always. Indeed, it is the way I originally advocated the pairings work when I first proposed Floating Triple Elimination. Avoiding repeat pairings isn't a tweak to the system, it is part of the fundamental philosophy.
|
| « Last Edit: Jan 24th, 2006, 10:13am by Fritzlein » |
IP Logged |
|
|
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender:
Posts: 138
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #22 on: Jan 24th, 2006, 1:10pm » |
Quote Modify
|
on Jan 24th, 2006, 8:20am, Fritzlein wrote:| If second place were inferred directly from the results and awarded contrary to the order of elimination, then there would be no problem, but unfortunately second place is implicitly defined by order of elimination. Although it isn't explicitly stated who takes second, it would bend the rules just as much to not give second place to the last bot eliminated as it would bend the rules to change the order of the games. Playing the ball as it lies will probably mean that the second-strongest tournament performance will be awarded third place. |
|
Yes, I meant only to note that these two ways of bending the rules are functionally equivalent, not to say that one was better than the other or to advocate either. Also, I was trying to make the point that if we want to bend the rules, we only need to rearrange the order of the games on paper; they don’t really have to be rearranged in actual spacetime.
Personally, I think that when the letter of the rules gives second place to Aamira without more than very minor ambiguity, it is improper to give second place to Clueless, despite the fact that Clueless manifestly outperformed Aamira in the CC, and despite the fact that the pairing algorithm written in the rules did not perform to the spirit of its design. Still, this is only my opinion; it is Don Dailey’s opinion that matters.
In keeping with the spirit of sportsmanship that people showed in the WC (such as when people technically forfeited by being late for games), it is my hope that some compromise can be reached between the owners of these bots, so that second prize is not simply awarded by a ruling. While Clueless scored two crushing wins against Aamira in the tournament, the overall record is 7-4 in favor of Aamira, so maybe a tiebreaker game would be acceptable to both sides. Just throwing the idea out there.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print