Author |
Topic: 2011 World Championship (Read 21185 times) |
|
omar
Forum Guru
Arimaa player #2
Gender: 
Posts: 1003
|
 |
Re: 2011 World Championship
« Reply #60 on: Jan 4th, 2011, 11:56pm » |
 Quote  Modify
|
on Jan 4th, 2011, 12:01pm, jdb wrote:
It looks like the scheduler thinks 12:00am is at night. I did select 12 noon on Sunday as a time . Maybe the game room time means 12 noon? At any rate, I cannot play on Sunday at midnight, there is a prior commitment.
To be clear, I selected slots 90 and 102. I did not select slot 78, which I think the game is scheduled for. |
|
Sorry Jeff, I think you encountered the same problem as Toby. If you agree to a different time with your opponent please let me know and I will change it manually.
If anyone else encountered this, please let me know the new time you agreed to with your opponent.
I've made a change to the programs so that this does not happen in future years.
|
|
 IP Logged |
|
|
|
ginrunner
Forum Guru
Arimaa player #5449
Gender:
Posts: 163
|
|
Re: 2011 World Championship
« Reply #61 on: Jan 4th, 2011, 11:57pm » |
Quote Modify
|
I got off work to play my game lol ... actually i just traded shifts but still ... I am committed lol
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: 2011 World Championship
« Reply #62 on: Jan 5th, 2011, 12:22am » |
Quote Modify
|
on Jan 4th, 2011, 11:21pm, Fritzlein wrote:
My preference would be to get rid of the gap between the preliminaries and the finals. Why have a playoff to determine who is in the playoff? Why not instead unify the tournament into an open triple-elimination?
The original justification for having a preliminary and a finals was to provide an event in which everyone could participate and have a good time. That made some sense when there were no other events all year to have fun in, but now we have the Arimaa World League and one-day tournaments. We don't have to make the World Championship serve a double purpose.
|
|
Yes, I think with more events throughout the year the WC can be focused more on trying to selecting the best player. Maybe we should consider a format change for next year.
The only problem with floating-triple-elimination is it takes longer to finish. I would like the WC to not take more than a maximum of 12 weeks. That's why I tend to favor floating-double-elimination. I would consider floating-triple-elimination, but we would have to restrict entry to just the 8 highest rated players who register. Maybe this will be OK because players who don't make this will still have opportunities to play in other events during the year.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2011 World Championship
« Reply #63 on: Jan 5th, 2011, 1:16am » |
Quote Modify
|
on Jan 5th, 2011, 12:22am, omar wrote:| The only problem with floating-triple-elimination is it takes longer to finish. I would like the WC to not take more than a maximum of 12 weeks. |
|
Wait, what does your simulator say about the length of FTE for 32 players? By my calculation our current format takes 11 or 12 rounds for 32 players, whereas FTE takes 11, 12, or 13 rounds for 32 players. How many weeks would it add on average to switch to FTE? Less than one additional week?
|
|
IP Logged |
|
|
|
Sconibulus
Forum Guru
Arimaa player #4633
Gender:
Posts: 116
|
|
Re: 2011 World Championship
« Reply #64 on: Jan 5th, 2011, 1:16am » |
Quote Modify
|
I really don't like the idea of only the top 8 ratings making it, that would discourage people from playing games they think they might lose if they're on the cusp. And it's hard to imagine that a combination of swiss and double elimination is less round-intensive than triple elimination. According to approximate predictions after the six rounds we'd be down to 12 players rather than 8, but about half of them would only have one loss remaining, and only one might have more than the two lives double elimination gives now.
The primary problem I see with this is the games won prize. There would no longer be a clear and distinct point for it to start, although perhaps you'd earn a 'win' for each game you were above .500?
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: 2011 World Championship
« Reply #65 on: Jan 5th, 2011, 3:01am » |
Quote Modify
|
I would like tripple elimination with (given number of rounds played at all cases) I hope it's possible ... it would give order in "preliminary" as well as "dependence only on your behaviour".
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: 2011 World Championship
« Reply #66 on: Jan 5th, 2011, 10:42am » |
Quote Modify
|
on Jan 5th, 2011, 1:16am, Fritzlein wrote:
Wait, what does your simulator say about the length of FTE for 32 players? By my calculation our current format takes 11 or 12 rounds for 32 players, whereas FTE takes 11, 12, or 13 rounds for 32 players. How many weeks would it add on average to switch to FTE? Less than one additional week? |
|
Here are the results of running 100 FTE tournaments with 8 player (using aaaa's program); a rating distribution range of 500; rating inaccuracy of 50 and 0.0 percent probability of draws:
Code:
run4 formats/floatTripElimAaaa 100 8 500 50 0.0
run4 'formats/floatTripElimAaaa' 100 8 500 50 0.0
1 53.0%
2 22.0%
3 11.0%
4 10.0%
5 3.0%
6 1.0%
average number of rounds = 9.07
minimum number of rounds = 7
maximum number of rounds = 11
average rating from best = 34.6
|
|
16 players:
Code:
run4 formats/floatTripElimAaaa 100 16 500 50 0.0
run4 'formats/floatTripElimAaaa' 100 16 500 50 0.0
1 35.0%
2 30.0%
3 16.0%
4 10.0%
5 2.0%
6 3.0%
7 2.0%
8 1.0%
9 1.0%
average number of rounds = 10.36
minimum number of rounds = 9
maximum number of rounds = 12
average rating from best = 33.7
|
|
It gets stuck on pairing round 3 when I try it with 32 players. Running one tournament with 20 players takes about 8 seconds. When I go to 22 players it gets stuck (I waited for 5 minutes) on pairing round 2.
Here are the results of running 10 tournaments with 20 players:
Code:
time run4 formats/floatTripElimAaaa 10 20 500 50 0.0
run4 'formats/floatTripElimAaaa' 10 20 500 50 0.0
1 10.0%
2 40.0%
3 20.0%
4 10.0%
6 10.0%
10 10.0%
average number of rounds = 10.90
minimum number of rounds = 9
maximum number of rounds = 12
average rating from best = 55.4
108.388u 0.471s 1:52.66 96.6% 0+0k 0+0io 0pf+0w
|
|
Assuming we can cross the technical hurdle I think you are right; a 32 player FTE would on average be less than 12 rounds and worst case 13 rounds. It sounds doable!!
At least we can go up to 20 players with the current algorithm.
|
|
IP Logged |
|
|
|
ocmiente
Forum Guru
Arimaa player #3996
Gender:
Posts: 194
|
|
Re: 2011 World Championship
« Reply #67 on: Jan 5th, 2011, 12:46pm » |
Quote Modify
|
The question about a FTE tournament style has been discussed before, about 5 years ago.
I would prefer a FTE tournament also.
The one thing I would add is maybe that people who reach the 3 loss limit be thrown into a swiss style bracket so that they can continue playing scheduled games against other participants of similar skill levels until the tournament is over. People should be able to bow out of the tournament after their third loss, so they wouldn't have to continue playing if they did not want to.
|
| « Last Edit: Jan 5th, 2011, 12:49pm by ocmiente » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2011 World Championship
« Reply #68 on: Jan 5th, 2011, 3:03pm » |
Quote Modify
|
on Jan 5th, 2011, 12:46pm, ocmiente wrote:
Also in 2010 the cutoff between the preliminaries and the finals produced some dissatisfaction. In particular, I and a couple of other players who were guaranteed a spot in the finals prior to our last-round preliminary game had incentives to lose that last game to manipulate the seedings of the finals. Since losses aren't carried forward between the preliminaries and the finals, losing on purpose could have increased overall winning chances. I am pretty sure that nobody intentionally lost a game, but the awareness of the incentive to do so generated a lot of support for changing the tournament format to floating triple elimination.
Unfortunately, the FTE pairing code provided by doublep runs in exponential time. We can't use it to run a large World Championship, as Omar alludes to:
on Jan 5th, 2011, 10:42am, omar wrote:| It gets stuck on pairing round 3 when I try it with 32 players. Running one tournament with 20 players takes about 8 seconds. When I go to 22 players it gets stuck (I waited for 5 minutes) on pairing round 2. |
|
Fortunately, aaaa managed to clear the technical hurdle with a polynomial-time algorithm eleven months ago. It remained only to work out the technical details of which pairings we would consider most desirable. We are not far from a solution. However, in light of past conflict between aaaa and myself, I would request that someone other than me work with aaaa to perfect his FTE pairing algorithm.
Quote:| The one thing I would add is maybe that people who reach the 3 loss limit be thrown into a swiss style bracket so that they can continue playing scheduled games against other participants of similar skill levels until the tournament is over. People should be able to bow out of the tournament after their third loss, so they wouldn't have to continue playing if they did not want to. |
|
I quite like the option of letting eliminated players either drop out or continue playing in a parallel swiss-style consolation tournament until the conclusion of the World Championship. The main polynomial-time FTE pairing algorithm could be adapted to pair this tournament as well.
|
|
IP Logged |
|
|
|
ocmiente
Forum Guru
Arimaa player #3996
Gender:
Posts: 194
|
|
Re: 2011 World Championship
« Reply #69 on: Jan 5th, 2011, 3:12pm » |
Quote Modify
|
What if you ran the tournament as a swiss tournament, except that when a player has lost 3 times, they are removed from main tournament bracket and moved to a second bracket that would allow them to keep playing.
As people dropped out, the remaining players in the tournament bracket from which the winner would come would have to start replaying each other - which is not strictly Swiss - and which is what you usually get in a regular double elimination type tournament. Seems like this would make the tournament shorter than 13 rounds.
[Edit]
Except add one other thing... in the pairings for the main tournament bracket, require that all matches be made between players that have an equal number of wins, or a difference of only one win between them. Again, this is not strictly Swiss because rematches would very likely occur, but would serve to bound the number of rounds in the tournament.
[Edit]
And... you would only match players with different number of wins if there was an odd number of players with some number of wins. That is, for the most part, you always want to match players with the same number of wins, and only want to match players with different number of wins if you have to.
hmmm... I had no idea that these tournament systems could be so complicated.
|
| « Last Edit: Jan 5th, 2011, 3:34pm by ocmiente » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2011 World Championship
« Reply #70 on: Jan 5th, 2011, 3:45pm » |
Quote Modify
|
on Jan 5th, 2011, 3:12pm, ocmiente wrote:| As people dropped out, the remaining players in the tournament bracket from which the winner would come would have to start replaying each other - which is not strictly Swiss - and which is what you usually get in a regular double elimination type tournament. |
|
Yes, that's exactly what we are discussing. Floating triple elimination is like a Swiss where you allow repeat pairings and stop pairing people with three or more losses. I discovered, however, that it was easier to clearly delineate the concept than to implement the algorithm. How exactly is the pairing done?
Quote:| Seems like this would make the tournament shorter than 13 rounds. |
|
A 32-player FTE can end in eleven rounds. The reason it can go more rounds than you think is that lots of byes might have to be assigned.
|
|
IP Logged |
|
|
|
ocmiente
Forum Guru
Arimaa player #3996
Gender:
Posts: 194
|
|
Re: 2011 World Championship
« Reply #71 on: Jan 5th, 2011, 8:28pm » |
Quote Modify
|
well, I have some code that will do it... rough draft of course... could be bugs.
This is a variant of a Swiss Tournament. Maybe the 'Foy System'?
It's written in C#.
With 33 players I ran the simulation 50 times and had 3 times when it took 13 rounds. The others took 11 or 12. It also runs quickly - less than a second.
And 1024 players took 18 rounds, and with 10,456 players it took 22 rounds 
If someone has been matched with a player before, the algorithm should probably try to find a different player who they have not played before, with the same number of losses. I suspect that that is why other matching algorithms might take a long time to complete, but I'd have to implement it to be sure. I'm also not sure how much of a difference it would make in the pairings. It would be worth experimenting with, if anyone else thinks this might be a useful tournament pairing process.
Also, color assignment has to be considered.
|
| « Last Edit: Jan 6th, 2011, 12:25am by ocmiente » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: 2011 World Championship
« Reply #72 on: Jan 6th, 2011, 8:25am » |
Quote Modify
|
on Jan 5th, 2011, 8:28pm, ocmiente wrote:| If someone has been matched with a player before, the algorithm should probably try to find a different player who they have not played before, with the same number of losses. I suspect that that is why other matching algorithms might take a long time to complete, but I'd have to implement it to be sure. |
|
You have stated the problem in a nutshell. Perhaps in the past we should not have let the perfect be the enemy of the good, but our feeling was that we shouldn't have a pairing that included repeat matchups if there existed an alternative pairing that didn't have repeat matchups. Actually, I had a slew of criteria that Omar has encapsulated in the tournament rules:
Quote: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 occurring for the Nth time. ...
Minimize the number of pairings occurring for the fourth time.
Minimize the number of pairings occurring for the third time.
Minimize the number of pairings occurring for the second time.
Give the bye to the player with the fewest losses.
Give the bye to the player with the best ranking in the preliminary.
Minimize the number of pairings between players whose number of losses differ by N, etc.
Based on a ranking of the non-eliminated players primarily by least number of losses and secondarily by seed, maximize the sum of the squares of the differences in rank among paired |
|
One interesting question is how many of these principles can be guaranteed by a simple, fast algorithm. For example, it is easy to guarantee that the bye goes to a player who isn't ahead on byes (e.g. to make it impossible for some player to get two byes while another player hasn't yet had his first bye). One can simply assign the bye to an eligible player first, and then pair the remaining players. But this immediately comes into conflict with minimizing the number of repeat pairings. Perhaps there are multiple players who are equally eligible for a bye, and giving the bye to one such player forces repeat pairings whereas giving the bye to another such player allows repeat pairings to be avoided.
Intuitively, one must suspect that finding an "optimal" pairing can't be done quickly. It seems reasonable that meeting a stringent list of desirability criterion would necessarily have exponential running time, i.e. would in essence be equivalent to examining every possible pairing and seeing which is best. Miraculously, however, as long as you can assign a concrete weight to each pairing saying how undesirable it is (e.g. a repeat pairing is more undesirable than pairing a 3-1 player against a 1-3 player), then there is a sophisticated algorithm which finds the optimal pairing in polynomial time. The problem is called minimum-weight perfect matching.
Once you have an algorithm that can do minimum-weight perfect matching, the good news is that you can assign the "badness weight" of each pairing however you like. We can debate the rules of perfect pairing, and reach a decision as to precisely what we want. Once we have set criteria as to the ideal pairing, the algorithm is guaranteed to find the pairing that is the closest possible to that ideal. The bad news is we have to debate what is ideal. It turns out to be somewhat tricky; in particular, the last criterion in the above-quoted list is problematic when players with unequal records must be paired against each other.
Of course, we can at any time decide to give up on the "ideal" pairing and use a simpler algorithm to pair FTE. Maybe we should have done that long ago.
on Jan 5th, 2011, 8:28pm, ocmiente wrote:| Also, color assignment has to be considered. |
|
This is one respect in which we are fortunate. For chess tournaments, color assignment is important, indeed it is important enough that tournament directors may use it to alter pairings. For example, if a pairing pits two players against each other who are both "due white" and two other players who are both "due black", the TD can break up the bad pairings and repair so that color assignment works out properly, even if the alternate pairing is less desirable in some other respect, for example because it respects folding pairing less. Playing white is so much of an advantage in chess that equalizing color must take precedence over some other things.
In Arimaa, we can't tell whether Gold or Silver has the advantage, so we have the luxury of respecting all other principles of pairing first. We don't really care if both players are "due Gold"; we can flip a coin if need be. In past Arimaa tournaments, participants have felt mistreated by various pairing issues or by strength of schedule, but no one has claimed of mistreatment based on color assignment. (Well, there was one issue of a non-participant calling the tournament results into question based on color assignment, but neither the players involved nor the TD nor anyone else involved saw a problem.)
The upshot is that we all seem content to do the pairings without considering color assignment at all, and then do the color assignment later as a separate process.
|
| « Last Edit: Jan 6th, 2011, 9:37am by Fritzlein » |
IP Logged |
|
|
|
ocmiente
Forum Guru
Arimaa player #3996
Gender:
Posts: 194
|
|
Re: 2011 World Championship
« Reply #73 on: Jan 6th, 2011, 1:09pm » |
Quote Modify
|
I've updated the code to prefer matches that have not happened before to ones that have.
That was simpler than I expected.
The number of rounds for a 33 person tournament broke down as follows:
10 rounds: 2.3%
11 rounds: 21.4%
12 rounds: 47.6%
13 rounds: 28.6%
preferring to avoid previous matches appears to have made 13 rounds happen more frequently - but I'd have to run a lot more simulations to confirm that - and these simulations are based on the chosen method of deciding who wins each match.
Regarding the criteria you mention, with respect to byes, they are granted to the player with the fewest number of byes so far. At the beginning of the tournament, the bye is assigned to the player with the most losses and lowest initial rating. Once the tournament reaches a point when there is only one undefeated player, or no undefeated players, the bye goes to the player with the fewest byes, then the fewest losses, then the highest initial rating.
As far as avoiding previously matched opponents, the algorithm puts a priority on matching players with an equal number of losses (or at most a difference of one loss between then). Rematches are avoided when possible.
With respect to the sum of the squares of... the matching function does the match using the basic Swiss method (I think that's fair to say). That is, it splits a group of players with the same number of losses (with maybe one extra if there was a leftover from the previous group) in half, and matches the first player in the upper half to the first player in the lower half. If this match has already happened, it will look for the next player that hasn't been matched in the second group, and go through the first group in reverse order if necessary to make a match. So, there's no standard deviation calculations, but I suspect that a very similar result is obtained.
|
|
IP Logged |
|
|
|
Hippo
Forum Guru
Arimaa player #4450
Gender:
Posts: 883
|
|
Re: 2011 World Championship
« Reply #74 on: Jan 6th, 2011, 3:14pm » |
Quote Modify
|
on Jan 6th, 2011, 8:25am, Fritzlein wrote:
Intuitively, one must suspect that finding an "optimal" pairing can't be done quickly. It seems reasonable that meeting a stringent list of desirability criterion would necessarily have exponential running time, i.e. would in essence be equivalent to examining every possible pairing and seeing which is best. Miraculously, however, as long as you can assign a concrete weight to each pairing saying how undesirable it is (e.g. a repeat pairing is more undesirable than pairing a 3-1 player against a 1-3 player), then there is a sophisticated algorithm which finds the optimal pairing in polynomial time. The problem is called minimum-weight perfect matching.
|
|
It would be nice to have minimum-weight perfect matching with lexicographical list of criterias. Wow, now when I read Omar's conditions, they are formulated such that each edge could have been assigned the "badness vector" ... so it could really work.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print