Author |
Topic: Floating Tuple Elimination pairing algorithm (Read 3607 times) |
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
 |
Floating Tuple Elimination pairing algorithm
« on: Oct 28th, 2009, 6:45pm » |
 Quote  Modify
|
The phrase "Pair players with a similar number of losses against each other." is vague. Would it make sense to replace this constraint with a greedily minimizing approach like the one concerning repeated pairings, i.e. "Minimize the number of pairings where the number of losses differ by N, etc.", or does the algorithm already do this?
If such a change were to be made, should the constraint of giving a bye to the highest-seeded player then still have a higher priority than this? I'm not sure about this. On the one hand, lowering it would contribute to dampening the effects of seeding. On the other hand, a bye is a considerable windfall to bestow to someone constrained by a global consideration that already has a low priority of its own.
It's been pointed out that maximizing the sum of the squares of the differences in rank among remaining players is flawed insofar as one should not want to try to effect assumed differences in strength amongst players if they have a different number of losses. One would then actually want to protect those with more losses at the expense of those with less. However, to simply minimize the sum of the squares of the differences in seeding between these players would not take into account the possibility of one player both being seeded higher than another player whilst also having more losses. These scores actually cancel each other out for the purpose of having the algorithm make assumptions about the difference in strength between two players. My proposal is therefore to replace constraint 11 with something like the following:
"Based on a ranking of the remaining players primarily by least number of losses and secondarily by seed, maximize the sum of the squares of the differences in rank among paired players with equal losses minus the sum of the squares of the differences in rank among paired players with different losses."
This would also make the algorithm biased towards scheduling appropriate pairings for players with higher differences in losses compared to those with lower ones.
I would also propose that the color assignment used by the Continuous Tournament is applied in both championships and for their entire durations, i.e. including during the Swiss preliminary part of the human championship and any possible tiebreaker games, and that the pairing history carries over between the phases.
Since both championships make use of the same algorithm, only differing by how the players are seeded and the number of lives given to them at the start, I would suggest creating a separate (possibly parameterizable template) page on the wiki that is referenced by (or transcluded in) the pages about the respective championships.
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #1 on: Oct 31st, 2009, 12:51pm » |
Quote Modify
|
on Oct 28th, 2009, 6:45pm, aaaa wrote:| The phrase "Pair players with a similar number of losses against each other." is vague. Would it make sense to replace this constraint with a greedily minimizing approach like the one concerning repeated pairings, i.e. "Minimize the number of pairings where the number of losses differ by N, etc.", or does the algorithm already do this? |
|
I think it would make the most sense to have a strict hierarchy as you suggest, e.g. any number of one-loss-difference pairings would be preferable to even one two-loss-difference pairing. If I remember correctly, what is in place now is a factor for the square of the difference in losses, so that four one-loss-difference pairings would be equivalent to one two-loss-difference pairing. In a tournament with only eight players, like the Computer Championship, I believe there will never be a disparity between what is implemented and the strict hierarchy.
Quote:| If such a change were to be made, should the constraint of giving a bye to the highest-seeded player then still have a higher priority than this? |
|
My intuition on who should get the bye changed due to the 2006 Computer Championship. Check out this post by Ryan Cable explaining how assigning a bye can give one player a path to victory with two fewer wins over-the-board than another player has.
Swiss chess tournaments try to minimize the disruption of byes by giving them to the lowest player in the standings. The theory is that the standings at the top, where it matters, will be least affected by assigning byes in this way. For floating multiple elimination, in contrast, all players who are not in contention have already been eliminated. There is no non-disruptive way to assign a bye. Because of Ryan's argument, I would be opposed to flipping criteria 8 and 10, thereby potentially giving a bye to someone with more losses. I guess we agree on that.
You entertain the notion of flipping criteria 9 and 10, thereby potentially giving a bye to someone with equal losses but lower seeding, seems less critical, but I still lean toward respecting the seeding first, especially now that we have a better method of seeding the Computer Championships. However, I wouldn't complain too much if we switch the priorities of 9 and 10, because it is also a fairness issue to have fewer players playing across score boundaries.
Quote:| It's been pointed out that maximizing the sum of the squares of the differences in rank among remaining players is flawed insofar as one should not want to try to effect assumed differences in strength amongst players if they have a different number of losses. |
|
Yes.
Quote:| "Based on a ranking of the remaining players primarily by least number of losses and secondarily by seed, maximize the sum of the squares of the differences in rank among paired players with equal losses minus the sum of the squares of the differences in rank among paired players with different losses." |
|
I agree. I'm not sure how easy it is to change the implementation to make that happen, though.
Quote:| I would also propose that the color assignment used by the Continuous Tournament is applied in both championships and for their entire durations, i.e. including during the Swiss preliminary part of the human championship and any possible tiebreaker games, and that the pairing history carries over between the phases. |
|
I agree with this as well, but at a much lower priority. Most of the color assignments will be the same both ways, and color is not that important anyway.
Quote:| I would suggest creating a separate (possibly parameterizable template) page on the wiki that is referenced by (or transcluded in) the pages about the respective championships. |
|
I am not sure what your final suggestion means.
|
| « Last Edit: Oct 31st, 2009, 1:25pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #2 on: Oct 31st, 2009, 1:45pm » |
Quote Modify
|
Re-reading the thread from 2006 that I linked above made me realize I am no longer so skeptical of Fotland's proposal:
on Jan 28th, 2006, 12:42am, fotland wrote:| Why not combine round robin with triple elimination? Do a single round robin, then eliminate all bots with 3 or more losses, then another single round robin, then another elimination of all with 3 or more losses (total), etc. This eliminates the problem with assigning byes, and still lets you spend more playing time with the stronger bots playing. |
|
I pointed out that it could take more games:
on Jan 28th, 2006, 10:56am, Fritzlein wrote:| Already with 8 bots, however, there would start to be a significant number of extra games. FTE with 8 takes 21 to 23 games, but shrinking round robin triple elimination (SSRTE) will take 28 games even if a miracle decides things in the first round robin, and more likely will take 32 or more games, for an increase of 50% over FTE. |
|
However, the 2009 Computer Championship was held up in large part due to technical difficulties. When there is a game that has to be invalidated, the next round of FTE can't proceed until the game has been replayed, because the result of each game affects the future pairing.
For a single round-robin of the eight players, it is true that 28 games are required, but all 28 can be played back-to-back without replaying any invalidated games. If there is a situation that requires a ruling from the TD, who is not available, no problem, just go on and play the next game. The only time resolving an issue becomes a hangup is before the second round begins (i.e. when all bots with three losses are eliminated, and a new round-robin is started among the survivors, with losses carried forward.) So having those extra games might not slow things down at all.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #3 on: Oct 31st, 2009, 7:21pm » |
Quote Modify
|
on Oct 31st, 2009, 12:51pm, Fritzlein wrote:| I am not sure what your final suggestion means |
|
In MediaWiki, templates can be used to generate dynamic content. I guess what I was proposing was a bit too fancy of a solution to prevent multiple descriptions of the pairing algorithm from becoming desynchronized if changes are made to it. Maintaining a separate, referenced page on the algorithm should be good enough.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #4 on: Nov 3rd, 2009, 11:04pm » |
Quote Modify
|
Constraint 11 is also ambiguous in that it doesn't make clear whether for the purpose of calculation, players are reassigned collapsed ranks after any elimination has taken place.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #5 on: Nov 5th, 2009, 12:42pm » |
Quote Modify
|
on Nov 3rd, 2009, 11:04pm, aaaa wrote:| Constraint 11 is also ambiguous in that it doesn't make clear whether for the purpose of calculation, players are reassigned collapsed ranks after any elimination has taken place. |
|
On that score, I have never known what the code does.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #6 on: Nov 5th, 2009, 11:50pm » |
Quote Modify
|
I've coded my own implementation of the modified algorithm and discovered that there would still be some leeway in round 4 of the previous Computer Championship with the following alternative pairing:
| GnoBot | Badger | | OpFor | Bomb | | Zombie | Sharp |
Do we need additional constraints or are we humans also indifferent between that pairing and the one that was chosen?:
| GnoBot | Bomb | | OpFor | Sharp | | Badger | Zombie |
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #7 on: Nov 8th, 2009, 11:12am » |
Quote Modify
|
Interesting case. Since there are no repeat matches, the bye is clearly determined, and there is one mismatch of record in each case, we fall to criterion #11, based on the ranks of the players. I agree with your suggestion that differences in rank between bots with unequal losses should count against a pairing, while differences in rank between bots with equal losses should count for a pairing. But that still raises the question of how the players should be ranked.
If the ranking is by record first and pre-tournament rating second, the ranking going into round four was
GnoBot
Bomb
Badger
OpFor
Zombie
Sharp
Then the pairings score
GnoBot Badger +4
OpFor Bomb -4
Zombie Sharp +1
GnoBot Bomb +1
OpFor Sharp +4
Badger Zombie -4
Both have a net score of +1 for rank difference, so I guess I am indifferent. But the ranking of the bots before round 4 could be done better Swiss style, i.e. by record first, strength of schedule second, and pre-tournament rating third. Then the ranking before round 4 would be
Bomb
GnoBot
Badger
OpFor
Sharp
Zombie
which leads to the pairings scoring
GnoBot Badger +1
OpFor Bomb -9
Zombie Sharp +1
GnoBot Bomb +1
OpFor Sharp +1
Badger Zombie -9
Again the pairings are equal. So apparently I am indifferent again!
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #8 on: Nov 9th, 2009, 2:22am » |
Quote Modify
|
There would have been 3 different ways to schedule round 4 of the 2007 human championship:
| Fritzlein | chessandgo | | 99of9 | IdahoEv |
And either:
| robinson | Brendan | | PMertens | omar | | jdb | Chegorimaa |
Or:
| robinson | Chegorimaa | | PMertens | jdb | | omar | Brendan |
Or:
| robinson | PMertens | | omar | Brendan | | jdb | Chegorimaa |
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #9 on: Nov 10th, 2009, 7:53pm » |
Quote Modify
|
on Oct 28th, 2009, 6:45pm, aaaa wrote:| The phrase "Pair players with a similar number of losses against each other." is vague. Would it make sense to replace this constraint with a greedily minimizing approach like the one concerning repeated pairings, i.e. "Minimize the number of pairings where the number of losses differ by N, etc.", or does the algorithm already do this? |
|
I am not sure if it does or not. But the code is here if you want to dig for the answer:
http://arimaa.com/arimaa/wc/2010/floatDoubleElim
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #10 on: Nov 11th, 2009, 6:50am » |
Quote Modify
|
It's good that Fritzlein brought up the issue of rank differences between players with different number of losses because it's not just an academic point. Take a look at round 2 of the 2008 computer championship (ignoring colors):
| OpFor | Zombie | | Bomb | Loc | | Clueless | Sharp |
The lopsided pairing between Bomb (no loss, seeded 2nd) and Loc (1 loss, seeded 4th) wouldn't have happened under the proposed modified rules, although there would still have been two different possibilities:
| OpFor | Zombie | | Bomb | Clueless | | Loc | Sharp |
Or:
| OpFor | Clueless | | Bomb | Sharp | | Loc | Zombie |
After the championship, some disappointment was expressed over the fact that Sharp edged out OpFor for a place in the Challenge preliminaries. Who knows whether any of these alternative schedules would have better allowed OpFor to make a comeback after the rough start it had?
I have been able to make my implementation schedule a second round of a championship with 25 participants in a few minutes (for the (otherwise trivial) first round it already takes more than half an hour to schedule one with just 20 players). It's definitely not too late yet to adopt any suggested improvements regarding the floating tuple elimination rules for the upcoming championships, let alone ones concerning colors.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #11 on: Nov 11th, 2009, 4:13pm » |
Quote Modify
|
on Nov 11th, 2009, 6:50am, aaaa wrote:| It's definitely not too late yet to adopt any suggested improvements regarding the floating tuple elimination rules for the upcoming championships, let alone ones concerning colors. |
|
Would Omar (as tournament coordinator) be able to run your pairing code on his server?
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #12 on: Nov 14th, 2009, 7:40am » |
Quote Modify
|
I don't see why not. I'd have to know the interface of course.
I also wonder whether it's preferred to have the algorithm return any equally preferred schedule with equal probability or that it should be deterministic in its own unspecified way.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #13 on: Dec 6th, 2009, 9:59pm » |
Quote Modify
|
I have put up 3 C++ files on the wiki, one of which is a header file, colors.hpp, included by the other two.
Compiling colors.cpp will create an executable which will take any number of files as argument. All but the last are interpreted as containing past games, with each non-empty line consisting of the names of the players playing gold and silver respectively, separated by alternative whitespace. The last file should be in a similar format, supplying the names of the players in upcoming games whose colors are to be assigned. Color history will continue to be updated in the last file, so it's fine to schedule players more than once in it.
With fte.cpp, it's all but the last three arguments that are interpreted as past pre-elimination games (so that we can have the Swiss tournament games contribute to the color history). The third-to-last argument takes the number of lives each player starts out with before being eliminated. The second-to-last argument takes a file name containing the names of the qualified players separated by (any kind of) whitespace ordered from best-seeded to worst. Finally, the last argument takes the name of a file containing earlier games that were part of the elimination tournament (which must exist as an empty file if there hasn't been any games yet). It should be in the same game format, only with the addition of the name of the winner of the game as the third "word". It's OK for it to be present in the other mentioned contexts, where it's simply ignored.
In both cases, the output should speak for itself: gold player, then silver player. If anyone gets a bye, that player's name will appear alone in a line.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Floating Tuple Elimination pairing algorithm
« Reply #14 on: Dec 7th, 2009, 12:39am » |
Quote Modify
|
Thanks for providing this aaaa. I think I can write a wrapper around this to interface it with the new tournament management tool.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print