Welcome, Guest. Please Login or Register.
May 17th, 2024, 10:09am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Minimum-weight perfect matching »


   Arimaa Forum
   Arimaa
   Events
(Moderator: supersamu)
   Minimum-weight perfect matching
« Previous topic | Next topic »
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Minimum-weight perfect matching  (Read 8949 times)
Hippo
Forum Guru
*****




Arimaa player #4450

   


Gender: male
Posts: 883
Re: Minimum-weight perfect matching
« Reply #30 on: Feb 11th, 2010, 1:23am »
Quote Quote Modify 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: male
Posts: 147
Re: Minimum-weight perfect matching
« Reply #31 on: Feb 11th, 2010, 7:30am »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #32 on: Feb 11th, 2010, 9:03am »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #33 on: Feb 11th, 2010, 10:38am »
Quote Quote Modify 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 Quote Modify 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: male
Posts: 75
Re: Minimum-weight perfect matching
« Reply #35 on: Feb 12th, 2010, 9:57am »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #36 on: Feb 12th, 2010, 1:54pm »
Quote Quote Modify 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.  Smiley 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: male
Posts: 1016
Re: Minimum-weight perfect matching
« Reply #37 on: Feb 12th, 2010, 2:35pm »
Quote Quote Modify 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 Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #39 on: Feb 12th, 2010, 4:02pm »
Quote Quote Modify 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: male
Posts: 1016
Re: Minimum-weight perfect matching
« Reply #40 on: Feb 12th, 2010, 4:17pm »
Quote Quote Modify 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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #41 on: Feb 15th, 2010, 2:48pm »
Quote Quote Modify 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. Tongue)  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

   
Email

Gender: male
Posts: 5928
Re: Minimum-weight perfect matching
« Reply #42 on: Feb 15th, 2010, 3:07pm »
Quote Quote Modify 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 Quote Modify Modify

Here's how my hybrid score would have evolved during the Swiss part of the current championship:
 
Before the tournament:
Fritzlein2568
chessandgo2561
Adanac2319
99of92227
Tuks2199
ChrisB2095
omar2012
PMertens2004
The_Jeh1987
naveed1859
woh1851
Simon1799
Nevermind1756
Nombril1753
fritzlforpresident1658
Hippo1581

After round 1:
Fritzlein2601
chessandgo2580
Adanac2370
Tuks2254
Simon2140
omar2086
PMertens2063
Nombril2058
The_Jeh1954
99of91886
naveed1840
woh1800
ChrisB1790
Nevermind1701
fritzlforpresident1584
Hippo1522

After round 2:
Fritzlein2647
chessandgo2625
Adanac2490
Tuks2352
Simon2122
PMertens2090
omar2037
The_Jeh2021
99of91966
Nevermind1848
Nombril1847
Hippo1718
woh1636
fritzlforpresident1514
ChrisB1497
naveed1476

After round 3:
chessandgo2802
Adanac2674
Fritzlein2491
Tuks2394
Nombril2116
Nevermind2057
The_Jeh2050
99of92015
Simon2009
PMertens1896
omar1778
woh1736
Hippo1670
naveed1583
ChrisB1356
fritzlforpresident1338

After round 4:
Adanac2909
chessandgo2671
Fritzlein2498
99of92231
Tuks2205
The_Jeh2160
Simon2123
Nombril2077
Nevermind1917
woh1899
PMertens1855
omar1759
Hippo1602
naveed1528
ChrisB1416
fritzlforpresident1151

After round 5:
Fritzlein2641.4
chessandgo2640.5
Adanac2624
99of92236
The_Jeh2177
Tuks2165
woh2078
Simon1937
Nevermind1883
PMertens1870
Nombril1821
Hippo1791
omar1729
naveed1590
ChrisB1349
fritzlforpresident1064

Let's see whether anyone will manage to feel offended by this as well. Tongue
IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Minimum-weight perfect matching
« Reply #44 on: Feb 18th, 2010, 11:01pm »
Quote Quote Modify Modify

on Feb 17th, 2010, 6:14pm, aaaa wrote:
After round 5:
Fritzlein2641.4
chessandgo2640.5
Adanac2624
99of92236
The_Jeh2177
Tuks2165
woh2078
Simon1937
Nevermind1883
PMertens1870
Nombril1821
Hippo1791
omar1729
naveed1590
ChrisB1349
fritzlforpresident1064

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.Fritzlein12742b352b2
2.chessandgo16133154b131
3.Adanac115210416b2e
4.99of9961732e
5.The_Jeh10386271e
6.Tuks841259103e
7.woh15111485e
8.Simon695147e
9.Nevermind4815136e
10.PMertens516133116e
11.Nombril31471210e
12.Hippo115611e
13.omar142109e
14.naveed1311168e
15.ChrisB7129e
16.fritzlforpresident21014e
IP Logged
Pages: 1 2 3  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.