Author |
Topic: Minimum-weight perfect matching (Read 8949 times) |
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: Minimum-weight perfect matching
« Reply #30 on: Feb 11th, 2010, 1:23am » |
Quote Modify
|
There should be one more change with triple elimination format. Now we use different time controls for preliminary than for finals. In triple elimination only one time control can be used ... which?
|
|
IP Logged |
|
|
|
ChrisB
Forum Guru
Arimaa player #2339
Gender:
Posts: 147
|
|
Re: Minimum-weight perfect matching
« Reply #31 on: Feb 11th, 2010, 7:30am » |
Quote Modify
|
on Feb 11th, 2010, 1:23am, Hippo wrote:There should be one more change with triple elimination format. Now we use different time controls for preliminary than for finals. In triple elimination only one time control can be used ... which? |
| Another possibility would be to start with 60 secs. per turn for the early rounds and then increase the time control to 90 secs. per turn for the rounds having 8 or fewer remaining players. That approach would be consistent with our current approach.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #32 on: Feb 11th, 2010, 9:03am » |
Quote Modify
|
on Feb 11th, 2010, 7:30am, ChrisB wrote:Another possibility would be to start with 60 secs. per turn for the early rounds and then increase the time control to 90 secs. per turn for the rounds having 8 or fewer remaining players. That approach would be consistent with our current approach. |
| That makes sense to me. In a 16-player floating triple elimination, there would probably still be five "preliminary" rounds before reducing the field to eight players, just as this year. However, instead of having the slate wiped clean for the finals so that everyone has two lives left, we would more likely have one person with three lives left, two people with two lives left, and the other five with only one life left. The effect of carrying losses forward is to slightly shorten the "finals". Also FTE would avoid repeat pairings at all costs until they are unavoidable. For example, in 2010 we have chessandgo vs. The_Jeh and 99of9 vs. Tuks repeating from the preliminaries in the first round of the finals, but since we could avoid that by having chessandgo vs. 99of9 and The_Jeh vs. Tuks, there would be no repeat pairings if this were round 6 of FTE instead of round 1 of the finals. I consider that a decided advantage of FTE.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #33 on: Feb 11th, 2010, 10:38am » |
Quote Modify
|
I think the problem of giving too much advantage to the top seed can be solved simply by implementing sliding pairing, e.g. 1 vs 5 2 vs 6 3 vs 7 4 vs 8 Unfortunately, I'm not sure what the global criterion would be. Right now we maximize the sum of squares of rank difference to get folding pairing, e.g. 1 vs 8 2 vs 7 3 vs 6 4 vs 5 But if we instead minimize sum of squares of rank difference, we get the "process" pairing 1 vs 2 3 vs 4 5 vs 6 7 vs 8 which is a terrible way to refine the sorting of a list that is already mostly sorted. I guess with sliding pairing we are trying to set a constant size of mismatch and minimize the deviation from that size. Therefore to get sliding pairing we would need another kind of global calculation of how big each score group is and what size of mismatch is optimal within that score group.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Minimum-weight perfect matching
« Reply #34 on: Feb 12th, 2010, 7:23am » |
Quote Modify
|
Most single elimination tournaments, of which floating tuple is a generalization, have the winner of a game travel the same path regardless of who wins. This suggests a likewise extension here, where in case of an upset, defined as a lower seed beating a higher one, players trade seeds. That way, there would be less of a problem of the top seed(s) "vacuuming" giant killers. Fold pairing would then be desirable on the basis that one's (initial) seed would be quite variable and dependent on tournament results and thus be less predetermining by itself.
|
|
IP Logged |
|
|
|
Hannoskaj
Forum Guru
Arimaa player #3794
Gender:
Posts: 75
|
|
Re: Minimum-weight perfect matching
« Reply #35 on: Feb 12th, 2010, 9:57am » |
Quote Modify
|
Another possibility to avoid influence of the seed is simply to randomise. In the weights, we make appear only the scores of the players and who they have played, and we randomise the order of the players in input of the algorithm. If we have for example exactly two equivalent players, they will have the same chances of playing each given opponent during this turn. Alternatively and at much higher computational cost and programming complexity, we might try and choose between equivalent pairings by modeling the probability of result of the games, sampling or computing exactly, and choose the matching that leads usually to an easier matching on next turn.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #36 on: Feb 12th, 2010, 1:54pm » |
Quote Modify
|
Aaaa, your proposal of "stolen seeds" is intriguing, but I'm not sure how it would work in rounds past the second. If #15 steals the seed from #2, can that #2 be stolen from him by #7 later? If so, it seems that #7 could buy himself a better seed in round three on the basis of having beaten a worse opponent. I guess I would need to see some examples of your proposal in action to develop my intuition. PMertens was a big fan of randomizing pairings, or rather using only in-tournament information to make pairings so that seeding could not provide any advantage to the players. I think this is what Hannoskaj is suggesting. On the other extreme are people who don't mind giving a big advantage to the top seed as long as the seeding is accurate. It is fair to acknowledge the importance of the regular season in the playoffs, as most sports do. Omar showed us, however, that most of us wouldn't want to take that principle too far. He proposed the SwissKnife format, which turns out to be one of the most accurate means of crowning the best player as World Champion: simply give the title to the player with the highest rating. But nobody is willing to go to that extreme. We all want the World Championship to be at least partly, if not entirely, decided by a tournament. Even the way the finals of bowling tournaments are paired (or used to be) would probably be too extreme for us. They have #5 play #4, and then the winner plays #3, and then the winner of that plays #2, and the winner of that plays #1. Thus the number of times you need to win in order to win the tournament corresponds exactly to your seed entering the finals. We had broad consensus about one principle at least: everyone should need the same number of wins to become champion (within one because an odd number of players may force byes). But also we recognize that not all wins are equal. The assignment of opponents and byes leaves some range for giving an advantage the high seeds or not. In the 2007 World Chamionship, I was the #1 seed in a field of 20. Due to the folding pairing, I got to play the #20 seed in the first round. Of the ten winners in the first round, the lowest was #15, who had won by forfeit over the #6 seed, so I got the play the #15 seed. In the third round, there were an odd number of players left total, so I got a bye while other 2-0 players duked it out, i.e. chessandgo vs. robinson and 99of9 vs. PMertens. In the fourth round there were three 3-0 players, so one of us got to "play down". I was the lucky one again, getting to play the 13th seed, who was the lowest 2-1 player. Thus, entering the fifth round, chessandgo and I were both 4-0, but my opponents had been a bye, #20, #15, and #13, whereas his opponents had been #17, #8, #7, and #3. That's when a broad consensus emerged that the tournament format was giving too much advantage to the top-seeded player, even though it was requiring the same number of wins from both chessandgo and myself. (Fortunately, chessandgo won despite having the deck stacked against him. I would have felt bad winning that year.) So how much should the advantage of the top seed be weakened, and by what means? I tend to lean towards making the World Championship tournament as self-contained as possible. That should mean that I jump right on the "random pairing" bandwagon, which gives no advantage to anybody. However, intuitively I am afraid that it will randomly create just as much unfairness as I got by institutional means in 2007. Maybe we will have #1 vs. #20 and #2 vs. #3 in the first round just by luck. The principle I would like to see preserved is that when two 4-0 players meet in the fifth round, they had an approximately equally tough road to get there. The principle of "equally tough road" is enforced first and foremost by pairing winners against winners and losers against losers. Within that framework, however, there is a lot of room for improvement. In particular, I don't like that the #1 seed gets an easier pairing than the #2 seed in each round until they meet. Folding pairing is fine for the first round, but a harder pairing in one round should be balanced with an easier pairing in a later round. To some extent this problem can be alleviated using strength of schedule to order the players for the folding pairing. If the top player gets easier opponents in the first two rounds, by round three he might have a weaker SoS, thus losing his top seed, thus giving the advantages of the top seed to the #2 player. Fairly likely, though, SoS doesn't kick in that soon. With folding pairing it is very likely that the opponents of both #1 and #2 lost in the second round too, providing no discrimination. After the third round, though, SoS will definitely be in force, particularly if we use WHR which will probably break all ties by then. I guess I can stomach the #1 seed getting a break for two or three rounds in exchange for the #2 seed getting a break in the fourth round, when the break is more likely to be a significant one. So maybe I am leaning towards folding pairing throughout, but with pairing order determined by in-tournament WHR, not by seed except to break ties. If we do adopt folding pairing ordered by SoS, however, we have the detail to consider of what to do with an odd number of players in a score group. Who gets to play down, and who must play up? In keeping with the spirit of rewarding earlier tough pairings with later easy pairings, it should be the top member of a score group that gets to play down, and the bottom member of the next lower score group who has to play up. I know this is counter-intuitive and will draw some opposition, but I think it works quite well with the "equal road" principle. The bad case for this pairing that people are going to point out is an 18-player tournament where there are 9 winners and 9 losers after one round. In round 2, my proposal would have the top 1-0 play the bottom 0-1, which means the top seed will get a second easy game while the other 1-0 players have to duke it out with each other. BUT this will wreck the strength of schedule of the top seed, meaning that going in to round three he will get a much worse pairing, and that will happen at a time when having an easier/harder pairing will matter more. The karma comes back around in later rounds, which is the whole point of my proposal. So, that's the best I can do, and I am curious what people think. Folding pairing in every round, but ordering is by W-L first, SoS second, and seed only third, which will cause the pairing order to churn from the original seeding order. The bye goes to the top remaining player with no bye. The top player in a score group gets to play down, while the bottom player in a score group must play up. The top seed will have a huge advantage but only at first and will have to pay the price for any early-round benefits by getting hosed (e.g. not getting the bye) later on. (On second thought, I would probably prefer good old-fashioned SoS to WHR in this scenario. (SoS = sum of opponent wins, zero for bye, zero for forfeit win.) More ties in SoS mean that seeds are respected longer, which is OK in this format. Also WHR has issues with byes and forfeits which the traditional SoS handles better by zeroing out.) (The churning of the pairing order will introduce a lot of luck into the pairings, which is ironic because it will make it a lot more like the random pairing method I was trying to avoid. Oh, well. But I can see the case for using a simpler system (simply random) than a more complex system with a similar effect.)
|
« Last Edit: Feb 12th, 2010, 1:55pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Minimum-weight perfect matching
« Reply #37 on: Feb 12th, 2010, 2:35pm » |
Quote Modify
|
Sounds promising. It'd be nice if someone could code it up to run through the tournament simulator Omar has and check how it compares with the other formats that have been tried. Janzert
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Minimum-weight perfect matching
« Reply #38 on: Feb 12th, 2010, 3:47pm » |
Quote Modify
|
As a compromise, we could keep it as it is, except that for each round, the seeds are recalculated by considering all in-tournament games so far plus a quarter win and a quarter loss against an anchor player with the rating used for the initial seeding. Moreover, I believe a forfeit should be treated like any other game result, since it's reasonable to expect a bias towards forfeits by underdogs.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #39 on: Feb 12th, 2010, 4:02pm » |
Quote Modify
|
on Feb 12th, 2010, 2:35pm, Janzert wrote:Sounds promising. It'd be nice if someone could code it up to run through the tournament simulator Omar has and check how it compares with the other formats that have been tried. |
| Thanks, Janzert. It would be nice to have it coded up for simulations, so that we could step through some tournaments and see how it works. If I remember correctly, however, Omar's simulator wasn't measuring fairness or reasonableness; it was just measuring how often the best player actually won the tournament. Therefore I expect any proposal that reduces the advantages to the #1 seed will fare worse according to his way of measuring. If we are going to run the simulator at all, there should be a companion measurement, namely how often the best player wins the tournament if the initial seeds are totally random. That is to say, the format should work well both when the ratings are approximately accurate and when the ratings are 100% nonsense. But in any case I am less worried by how often the best player will win the tournament than I am worried whether there will be unforeseen strange pairings or bye assignments that appear unreasonable or unfair. The reason that we keep tweaking our World Championship format is not that it is failing to select worthy champions, but that we keep noticing things that strike us as unfair in some respect. For example, this year we had a few games in the last round of the preliminaries where one or both players had no incentive to win, or maybe even an incentive to lose. Since the slate is wiped clean between preliminary and final, taking a preliminary loss to jockey for final seeding position is a reasonable strategy. I can assure you, from my game against Adanac, that it is no fun to be in a position where if I lose, I will be suspected of losing on purpose. It's even worse to be in that position when I am behind on the board. In a unified triple-elimination, however, there will never (if it is properly structured) be a case where losing a game is better than winning. The three lives are too precious to be squandered for any kind of positioning in pairing. There will not be players who are "safe", nor will there be players who are "out" but still playing. The players who can no longer win, no longer play. All the players who are still playing have every reason to try to win. Despite all the wrinkles that we still need to work out in FTE, I would be happy to get back to an elimination format.
|
« Last Edit: Feb 12th, 2010, 4:03pm by Fritzlein » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Minimum-weight perfect matching
« Reply #40 on: Feb 12th, 2010, 4:17pm » |
Quote Modify
|
on Feb 12th, 2010, 4:02pm, Fritzlein wrote:Therefore I expect any proposal that reduces the advantages to the #1 seed will fare worse according to his way of measuring. |
| Yes, but what I want to know is how much worse. :} Quote:If we are going to run the simulator at all, there should be a companion measurement, namely how often the best player wins the tournament if the initial seeds are totally random. That is to say, the format should work well both when the ratings are approximately accurate and when the ratings are 100% nonsense. |
| If I'm remembering the how the simulator worked correctly, one of the parameters you gave it was the error size for the ratings. So you ended up with each player having a true rating that determined the outcome of games and an apparent rating that was used for the seeding. Looking at how well the different formats performed in the face of large errors in the apparent ratings was a key concern at the time since we were using straight gameroom ratings and knew that they were often quite far off and open to manipulation. Quote:For example, this year we had a few games in the last round of the preliminaries where one or both players had no incentive to win, or maybe even an incentive to lose. ... Despite all the wrinkles that we still need to work out in FTE, I would be happy to get back to an elimination format. |
| Yes, the way swiss tournaments can end up with terrible incentives for players is something I really dislike. Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #41 on: Feb 15th, 2010, 2:48pm » |
Quote Modify
|
on Feb 12th, 2010, 3:47pm, aaaa wrote:As a compromise, we could keep it as it is, except that for each round, the seeds are recalculated by considering all in-tournament games so far plus a quarter win and a quarter loss against an anchor player with the rating used for the initial seeding. |
| Calculating in-tournament ratings with a weak anchor will surely result in inversions between score groups. The players will tend to layer along fault lines where nobody below a line has beaten anybody above the line. For example, after three rounds of this year's preliminary tournament, there would be a fault line with Simon above it and 99of9 below it, even though Simon was 1-2 and 99of9 was 2-1. Thus Simon would probably be ranked higher than 99of9 by an in-tournament WHR with a weak anchor. But perhaps when you talk of only recalculating the seeds, you mean that we should also preserve pairing within score groups, in which case the in-tournament ratings would only re-order players within a score group and not globally. In that case, I would approve of some churn from the initial seeding, as long as it isn't so much as to simply randomize the players. If I understand the formula correctly, the churn could begin already on the second round. For fun I tried folding pairing on the first round of this year's tournament with the actual players and ratings. Supposing that the favorites had all won, the seeds would be re-calculated as follows: Seed Participant WHR New WHR New Seed ---- ----------- ---- ------- -------- 1 Fritzlein 2568 2572 1 2 chessandgo 2561 2568 2 3 Adanac . 2319 2353 3 4 99of9 . 2227 2277 4 5 Tuks . 2199 2263 5 6 ChrisB . 2095 2196 6 7 omar . 2012 2139 8 8 PMertens . 2004 2174 7 9 The_Jeh . 1987 1817 9 10 naveed . 1859 1731 12 11 woh . . 1851 1750 10 12 Simon . 1799 1734 11 13 Nevermind 1756 1706 14 14 Nombril . 1753 1718 13 15 fritzlforprez 1658 1650 15 16 Hippo . 1581 1577 16 There is not much change on the extremes, as it should be, because the difference between an opponent 900 points stronger and one 1000 points stronger is minimal. Towards the middle, however, PMertens had to face a significantly stronger opponent than omar did, and is rewarded with a better seed (and theoretically easier opponent from folding pairing) because of it. Similarly, naveed got a break in the first round compared to woh and Simon, playing a significantly easier opponent, but the penalty is to get knocked down a couple of seeds for round 2, earning a (probably) harder pairing then. Based on just this one test run, I like the way the idea is working. If you get an easier road in one round, you have to pay with a harder road next round. That's just the kind of equalization I would like to see. Unfortunately, my programming skills don't suffice to extend the simulation to a second round. (In fact, there's a fair probability that my skills didn't suffice for the first round. Believe my numbers at your peril. ) I would really like to see a couple of realistic simulations to step through the consequences of the proposed combination of seeding/SoS, because it is not a situation where my intuition has something to grab hold of.
|
« Last Edit: Feb 15th, 2010, 3:11pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Minimum-weight perfect matching
« Reply #42 on: Feb 15th, 2010, 3:07pm » |
Quote Modify
|
on Feb 12th, 2010, 3:47pm, aaaa wrote:Moreover, I believe a forfeit should be treated like any other game result, since it's reasonable to expect a bias towards forfeits by underdogs. |
| This goes completely against the notion of equalizing the toughness of the paths of players. A forfeit win is as easy a path as one could get, i.e. equivalent to a bye. If you had a forfeit win against a strong player, it would be absurd for it to increase your strength of schedule, earning you an easier pairing the following round. The exact opposite should happen, whereby a forfeit win earns you a tougher opponent the following round to keep you on par with other players of your same W/L record. If we use any kind of in-tournament WHR, I advocate that byes and forfeit wins each count as a win against an anchor player with rating 1000.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Minimum-weight perfect matching
« Reply #43 on: Feb 17th, 2010, 6:14pm » |
Quote Modify
|
Here's how my hybrid score would have evolved during the Swiss part of the current championship: Before the tournament: Fritzlein | 2568 | chessandgo | 2561 | Adanac | 2319 | 99of9 | 2227 | Tuks | 2199 | ChrisB | 2095 | omar | 2012 | PMertens | 2004 | The_Jeh | 1987 | naveed | 1859 | woh | 1851 | Simon | 1799 | Nevermind | 1756 | Nombril | 1753 | fritzlforpresident | 1658 | Hippo | 1581 | After round 1: Fritzlein | 2601 | chessandgo | 2580 | Adanac | 2370 | Tuks | 2254 | Simon | 2140 | omar | 2086 | PMertens | 2063 | Nombril | 2058 | The_Jeh | 1954 | 99of9 | 1886 | naveed | 1840 | woh | 1800 | ChrisB | 1790 | Nevermind | 1701 | fritzlforpresident | 1584 | Hippo | 1522 | After round 2: Fritzlein | 2647 | chessandgo | 2625 | Adanac | 2490 | Tuks | 2352 | Simon | 2122 | PMertens | 2090 | omar | 2037 | The_Jeh | 2021 | 99of9 | 1966 | Nevermind | 1848 | Nombril | 1847 | Hippo | 1718 | woh | 1636 | fritzlforpresident | 1514 | ChrisB | 1497 | naveed | 1476 | After round 3: chessandgo | 2802 | Adanac | 2674 | Fritzlein | 2491 | Tuks | 2394 | Nombril | 2116 | Nevermind | 2057 | The_Jeh | 2050 | 99of9 | 2015 | Simon | 2009 | PMertens | 1896 | omar | 1778 | woh | 1736 | Hippo | 1670 | naveed | 1583 | ChrisB | 1356 | fritzlforpresident | 1338 | After round 4: Adanac | 2909 | chessandgo | 2671 | Fritzlein | 2498 | 99of9 | 2231 | Tuks | 2205 | The_Jeh | 2160 | Simon | 2123 | Nombril | 2077 | Nevermind | 1917 | woh | 1899 | PMertens | 1855 | omar | 1759 | Hippo | 1602 | naveed | 1528 | ChrisB | 1416 | fritzlforpresident | 1151 | After round 5: Fritzlein | 2641.4 | chessandgo | 2640.5 | Adanac | 2624 | 99of9 | 2236 | The_Jeh | 2177 | Tuks | 2165 | woh | 2078 | Simon | 1937 | Nevermind | 1883 | PMertens | 1870 | Nombril | 1821 | Hippo | 1791 | omar | 1729 | naveed | 1590 | ChrisB | 1349 | fritzlforpresident | 1064 | Let's see whether anyone will manage to feel offended by this as well.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Minimum-weight perfect matching
« Reply #44 on: Feb 18th, 2010, 11:01pm » |
Quote Modify
|
on Feb 17th, 2010, 6:14pm, aaaa wrote:After round 5: Fritzlein | 2641.4 | chessandgo | 2640.5 | Adanac | 2624 | 99of9 | 2236 | The_Jeh | 2177 | Tuks | 2165 | woh | 2078 | Simon | 1937 | Nevermind | 1883 | PMertens | 1870 | Nombril | 1821 | Hippo | 1791 | omar | 1729 | naveed | 1590 | ChrisB | 1349 | fritzlforpresident | 1064 | |
| Let's make that final ranking dictate the outcome of every game in a simulated floating triple elimination tournament with reseeding. Then the pairings for each round would become: 1. | Fritzlein | 12 | 7 | 4 | 2 | b | 3 | 5 | 2 | b | 2 | 2. | chessandgo | 16 | 13 | 3 | 1 | 5 | 4 | b | 1 | 3 | 1 | 3. | Adanac | 11 | 5 | 2 | 10 | 4 | 1 | 6 | b | 2 | e | 4. | 99of9 | 9 | 6 | 1 | 7 | 3 | 2 | e | 5. | The_Jeh | 10 | 3 | 8 | 6 | 2 | 7 | 1 | e | 6. | Tuks | 8 | 4 | 12 | 5 | 9 | 10 | 3 | e | 7. | woh | 15 | 1 | 11 | 4 | 8 | 5 | e | 8. | Simon | 6 | 9 | 5 | 14 | 7 | e | 9. | Nevermind | 4 | 8 | 15 | 13 | 6 | e | 10. | PMertens | 5 | 16 | 13 | 3 | 11 | 6 | e | 11. | Nombril | 3 | 14 | 7 | 12 | 10 | e | 12. | Hippo | 1 | 15 | 6 | 11 | e | 13. | omar | 14 | 2 | 10 | 9 | e | 14. | naveed | 13 | 11 | 16 | 8 | e | 15. | ChrisB | 7 | 12 | 9 | e | 16. | fritzlforpresident | 2 | 10 | 14 | e |
|
|
IP Logged |
|
|
|
|