Author |
Topic: World Championship tournament format (Read 9304 times) |
|
Tarr
Forum Newbie
Arimaa player #1239
Gender: 
Posts: 5
|
 |
Re: World Championship tournament format
« Reply #90 on: Jul 6th, 2005, 1:22pm » |
 Quote  Modify
|
on Jul 5th, 2005, 6:56pm, Tarr wrote:
1) The winner of A1 vs. C1
2) The winner of B1 vs. D1
3) The loser of A1 vs. C1
4) The loser of C1 vs. D1
5) The higher ranked of (A2 vs. D3 winner) and (D2 vs. A3 winner)
6) The higher ranked of (C2 vs. A3 winner) and (A2 vs. C3 winner)
7) The lower ranked of (A2 vs. D3 winner) and (D2 vs. A3 winner)
8) The lower ranked of (C2 vs. A3 winner) and (A2 vs. C3 winner) |
|
Uh... yeah, that's not quite right.
1) The winner of A1 vs. C1
2) The winner of B1 vs. D1
3) The loser of A1 vs. C1
4) The loser of B1 vs. D1
5) The higher ranked of (A2 vs. C3 winner) and (C2 vs. A3 winner)
6) The higher ranked of (D2 vs. B3 winner) and (B2 vs. D3 winner)
7) The lower ranked of (A2 vs. C3 winner) and (C2 vs. A3 winner)
8) The lower ranked of (D2 vs. B3 winner) and (B2 vs. D3 winner)
Quote:| We can also add additional external information by making use of the ratings the players already have. Such formats perform extrealy well. roundRobinRated does this. Doing this significantly improves the performance of a tournament in picking the true best player. But it runs the risk of players manipulating their ratings prior to the start of the tournament. roundRobinRatedRanked tries to minimize this by resetting the initial ratings so that they are equally spaced based on the rank from the inital ratings. |
|
How about a Bayesian approach? Let everyone come in with a "tournament" ranking equal to their true ranking, but give it only a small weight (maybe two or three games worth). As they play in the tournament, their rating will change.
|
|
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #91 on: Jul 7th, 2005, 10:33pm » |
Quote Modify
|
on Jul 6th, 2005, 1:22pm, Tarr wrote:
How about a Bayesian approach? Let everyone come in with a "tournament" ranking equal to their true ranking, but give it only a small weight (maybe two or three games worth). As they play in the tournament, their rating will change. |
|
Yes, this is exactly what the RoundRobinRank and SwissOmaticRank formats are doing.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #92 on: Jul 8th, 2005, 2:06pm » |
Quote Modify
|
on Jul 6th, 2005, 1:22pm, Tarr wrote:
Uh... yeah, that's not quite right.
1) The winner of A1 vs. C1
2) The winner of B1 vs. D1
3) The loser of A1 vs. C1
4) The loser of B1 vs. D1
5) The higher ranked of (A2 vs. C3 winner) and (C2 vs. A3 winner)
6) The higher ranked of (D2 vs. B3 winner) and (B2 vs. D3 winner)
7) The lower ranked of (A2 vs. C3 winner) and (C2 vs. A3 winner)
8) The lower ranked of (D2 vs. B3 winner) and (B2 vs. D3 winner)
|
|
Tarr I don't think I will be able to try this out soon. Things have gotten a bit busy for me again. If someone else wants to code this and send it to me I'll include it in the results.
Also if anyone is trying out another format, please post the results soon. I've got to start on the pages for the up coming events (including the human WC) soon.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #93 on: Jul 26th, 2005, 4:14pm » |
Quote Modify
|
on Jun 11th, 2005, 10:17am, omar wrote:
I have not tried out the double or triple eliminations formats proposed by Toby and Karl yet since they are not easy to implement.
|
|
I thought about this a bit, and I realized I also can't think of a way to do the pairing for my brand of triple-elimination without looking at all possible pairings and seeing which is least bad. For a tournament of even moderate size, looking at all possible pairings is prohibitively time-consuming.
Just so that my triple elimination can be compared with the other formats at all, let me present an algorithm for triple-elimination. It won't meet my ideal criteria, but it can at least run.
1) Everyone plays until they have lost three times. At the end of each round, any player who has lost for the third time is eliminated.
2) At the beginning of each round, if an odd number of players remain, a bye must be assigned. The bye goes to the player who has recieved the fewest byes so far, with ties broken in favor fewest losses so far, and further ties broken in favor of highest pre-tournament rating.
3) The players who don't get a bye are paired iteratively as follows: Select the unpaired player with the fewest losses (ties broken by highest pretournament rating), and pair him with the player in the field he has played the least number of times, with ties broken in favor of having fewest losses, and further ties broken in favor of lower pre-tournament rating.
If all favorites win in every round, the pairings in a 16-player tournament will be
1v16, 2v15, 3v14, 4v13, 5v12, 6v11, 7v10, 8v9
1v8, 2v7, 3v6, 4v5, 9v16, 10v15, 11v14, 12v13
1v4, 2v3, 5v11, 6v12, 7v9, 8v10, 13v15, 14v16
1v2, 3v8, 4v7, 5v6, 9v14, 10v13, 11v12
1bye, 2v5, 3v4, 6v10, 7v11, 8v9
1v3, 2v8, 4v6, 5v7
2bye, 1v5, 3v4
3bye, 1v2
1bye, 2v3
1v2
The only avoidable glitch is that 8 and 9 wouldn't have had to play for the second time in the fifth round, but that's the price for algorithmic efficiency.
If all favorites win in every round, the pairings in a 15-player tournament will be
1bye, 2v15, 3v14, 4v13, 5v12, 6v11, 7v10, 8v9
2bye, 1v8, 3v7, 4v6, 5v15, 9v14, 10v13, 11v12
3bye, 1v5, 2v4, 6v10, 7v11, 8v15, 9v13, 12v14
1v3, 2v9, 4v8, 5v7, 6v12, 10v11
1v2, 3v6, 4v5, 7v9, 8v10
1v4, 2v3, 5v8, 6v7
1v6, 2v5, 3v4
1bye, 2v3
1v2
1v2
In this case, no pairing occurred more than once until the very end. Everyone got to play at least three games, against three different opponents, and many close pairing occurred.
I conclusion, I still love my triple elimination, even when it has to be impaired slightly in the name of efficiency. If someone would code and test it, I bet it would do as well at picking a winner as any format which makes no use (apart from seeding) of pre-tournament ratings.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #94 on: Jul 27th, 2005, 7:47am » |
Quote Modify
|
Thanks for describing the tournament this way Karl, it makes it much more easier to implement.
Im assuming the color assignment would be random.
I probably won't be able to get to this for a few weeks. If someone has a litte time maybe they can take a crack at it. It would definitely be fun to code this up.
|
| « Last Edit: Jul 28th, 2005, 7:23am by omar » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #95 on: Jul 27th, 2005, 11:45am » |
Quote Modify
|
on Jul 27th, 2005, 7:47am, omar wrote:Thanks for describing the tournament this way Karl, it makes it much more easier to implement.
Im assuming the color assignment would be random.
|
|
I'm glad this version of "floating triple elimination" is at least implementable. It's amusing that, although I thought I kicked off this discussion way earlier than necessary, you still may not be able to change the format in time for the next World Championship.  At least the ideas will be in play for the following year, though.
As for color assignment, that didn't factor into your testing of other schemes, did it? Fortunately color assignment doesn't seem to have a large effect on winning percentage, according to the database statistics. Still, for the sake of fairness, I would suggest that, within each pairing, whoever has played Gold fewer times so far in the tournament should get to play Gold for that game, with ties broken randomly. That won't entirely even out color assignments, but will be more fair than, say, "higher rated player always gets Silver". One reason to keep it even is that we aren't even positive which color has the advantage!
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #96 on: Jul 27th, 2005, 4:58pm » |
Quote Modify
|
on Jul 27th, 2005, 11:45am, Fritzlein wrote:One reason to keep it even is that we aren't even positive which color has the advantage!
|
|
Another is to keep people like me happy who are convinced that they are worse with a particular colour.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #97 on: Jul 31st, 2005, 1:07am » |
Quote Modify
|
I was trying to learn Ruby and I figured this would be a good chance to try implementing Karl's floating triple elimination format.
Here's a sample run to check if it is implemented correctly.
##### Player List #####
player true measured
p1 1796 1804
p2 1533 1536
p3 1815 1788
p4 1780 1811
p5 1766 1748
p6 1887 1873
p7 1894 1859
p8 1842 1812
p9 1887 1929
p10 1755 1724
p11 1884 1881
p12 1851 1867
p13 1577 1584
p14 1733 1761
p15 1580 1605
p16 1626 1672
#######################
* p9 1929 0
* p11 1881 0
* p6 1873 0
* p12 1867 0
* p7 1859 0
* p8 1812 0
* p4 1811 0
* p1 1804 0
* p3 1788 0
* p14 1761 0
* p5 1748 0
* p10 1724 0
* p16 1672 0
* p15 1605 0
* p13 1584 0
* p2 1536 0
* Round 1
pick p9 p2 winner p9
pick p11 p13 winner p11
pick p15 p6 winner p6
pick p12 p16 winner p16
pick p10 p7 winner p10
pick p5 p8 winner p8
pick p14 p4 winner p4
pick p3 p1 winner p3
===============================
* p9 1929 0
* p11 1881 0
* p6 1873 0
* p12 1867 1
* p7 1859 1
* p8 1812 0
* p4 1811 0
* p1 1804 1
* p3 1788 0
* p14 1761 1
* p5 1748 1
* p10 1724 0
* p16 1672 0
* p15 1605 1
* p13 1584 1
* p2 1536 1
* Round 2
pick p16 p9 winner p9
pick p10 p11 winner p11
pick p6 p3 winner p3
pick p4 p8 winner p4
pick p2 p12 winner p12
pick p7 p13 winner p7
pick p1 p15 winner p15
pick p5 p14 winner p5
===============================
* p9 1929 0
* p11 1881 0
* p6 1873 1
* p12 1867 1
* p7 1859 1
* p8 1812 1
* p4 1811 0
* p1 1804 2
* p3 1788 0
* p14 1761 2
* p5 1748 1
* p10 1724 1
* p16 1672 1
* p15 1605 1
* p13 1584 2
* p2 1536 2
* Round 3
pick p3 p9 winner p9
pick p4 p11 winner p11
pick p6 p16 winner p16
pick p12 p15 winner p12
pick p7 p5 winner p5
pick p8 p10 winner p8
pick p2 p1 winner p2
pick p13 p14 winner p14
===============================
* p9 1929 0
* p11 1881 0
* p6 1873 2
* p12 1867 1
* p7 1859 2
* p8 1812 1
* p4 1811 1
* p3 1788 1
* p14 1761 2
* p5 1748 1
* p10 1724 2
* p16 1672 1
* p15 1605 2
* p2 1536 2
* Round 4
pick p9 p11 winner p9
pick p5 p12 winner p12
pick p8 p16 winner p8
pick p4 p3 winner p4
pick p2 p6 winner p6
pick p15 p7 winner p7
pick p14 p10 winner p10
===============================
* p9 1929 0
* p11 1881 1
* p6 1873 2
* p12 1867 1
* p7 1859 2
* p8 1812 1
* p4 1811 1
* p3 1788 2
* p5 1748 2
* p10 1724 2
* p16 1672 2
* Round 5
pick p9 BYE winner p9
pick p11 p8 winner p8
pick p12 p4 winner p4
pick p6 p10 winner p6
pick p16 p7 winner p7
pick p3 p5 winner p5
===============================
* p9 1929 0
* p11 1881 2
* p6 1873 2
* p12 1867 2
* p7 1859 2
* p8 1812 1
* p4 1811 1
* p5 1748 2
* Round 6
pick p4 p9 winner p9
pick p8 p7 winner p7
pick p11 p5 winner p11
pick p6 p12 winner p12
===============================
* p9 1929 0
* p11 1881 2
* p12 1867 2
* p7 1859 2
* p8 1812 2
* p4 1811 2
* Round 7
pick p9 p8 winner p8
pick p7 p11 winner p7
pick p12 p4 winner p12
===============================
* p9 1929 1
* p12 1867 2
* p7 1859 2
* p8 1812 2
* Round 8
pick p7 p9 winner p9
pick p8 p12 winner p8
===============================
* p9 1929 1
* p8 1812 2
* Round 9
pick p8 p9 winner p9
===============================
result p9 1
===============================
I'll update the table on page 6 with the results of running 2000 trials.
|
| « Last Edit: Jul 31st, 2005, 1:09am by omar » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #98 on: Jul 31st, 2005, 1:33am » |
Quote Modify
|
Karl's floatingTripElim format is definitely the best of the elimination formats and even better than a round robin. Way better than the singleElimSlide format we used last year.
The swiss formats I came up with (not to be confused with real swiss formats) are better than the FTE, but they require 16 rounds if there are 16 players. The FTE requires only 10 rounds with 16 players. My swiss formats also depend on knowing the inaccuracy of the rating system.
This looks like a very good format to use for WC type tournaments in the future.
|
| « Last Edit: Jul 31st, 2005, 2:41pm by omar » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #99 on: Jul 31st, 2005, 10:20am » |
Quote Modify
|
on Jul 31st, 2005, 1:07am, omar wrote:Here's a sample run to check if it is implemented correctly.
|
|
The sample run of floating triple elimination looks like it was implemented correctly. Also, for that particular run, it performed beautifully. Nobody had to play the same opponent twice until the very last round! That's exactly the way I had envisioned a tournament running, with a bunch of quality games for everyone.
I'm glad it also picks the best player a high percentage of the time, and that you are considering it for the upcoming championship. Of course, you know how biased I am, since I started this whole thread by advocating this format. Thanks for at least taking the suggestion seriously.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #100 on: Jul 31st, 2005, 2:10pm » |
Quote Modify
|
I found an error in my roundRobinDouble format. For even number of players it was running just like a single round robin. The one test that I did to check it initially used an odd number of players and I assumed it was working right.
I've run the simulations for this format again and updated the table on page 6.
Also I've added the number of rounds each format takes.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #101 on: Jul 31st, 2005, 6:31pm » |
Quote Modify
|
Hi Omar,
Since you've already coded Fritz's Floating-Triple-algorithm, perhaps it would not be hard for you to modify it to try the Floating-Double?? For easiest comparison I'd propose exactly the same rules as Fritz, but change the 3-loss condition (1) into a 2-loss condition.
Obviously it will not perform as accurately, but it will use less games. As Tarr points out, this is a common trade off, and the best choice depends on what the tournament timetable can handle. If it's not too hard I'd add a column to your table on page six stating the average number of games used per tournament in each format (for a particular standard number of players).
If you really want you could try a Quadruple-Elim ... etc just to get a feel for how fast it converges on perfect .
|
| « Last Edit: Jul 31st, 2005, 6:33pm by 99of9 » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #102 on: Jul 31st, 2005, 6:37pm » |
Quote Modify
|
Oh Sorry, I just read the table again and saw that as always you are one step ahead of me. You have already done Floating-Quadruple.
I'm still interested in Floating double, because I think it is better than the folding-double Fritz explained earlier.
You've also put in the average number of rounds, which is interesting, but I think average number of games would also be of interest.
|
| « Last Edit: Jul 31st, 2005, 6:40pm by 99of9 » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #103 on: Jul 31st, 2005, 9:03pm » |
Quote Modify
|
Hi Toby, I didn't see your postings till just now. But I guess we are thinking alike since I did already try the Quad and Double formats.
It does seem like there is something "right" about triple elimination. The jump in percentage between double and triple elimination is significant and worth the extra rounds. But when going from triple to quadruple the increase in percentage is not much and not worth adding three more rounds.
I also tried a slight variation which I called floatTripElim2. It is identical to the original except that when selecting the second player in the pairing we chose a player having the most loses instead of least loses. It seems to perform about the same as the original, but adds an additional round.
I also compared selected tournament formats using an inaccuracy of 400. The floatingTripElim holds up very well at these levels. The formats which relied very heavily on accurate ratings which had performed better than FTE at lower inaccuracy levels start to drop rapidly at these levels. Most noticable is swissKnife which basically becomes randomSelection.
I also compared the FTE against a double RR for the 4 player case (as in the computer championships). Here's the results:
Rating inacc 50 200 400
FTE (6.7) 66.0% 62.9% 65.4%
DRR (6.0) 55.2% 56.9% 56.4%
It's almost 10% better with only about one extra round. I think FTE is also a good format for the computer championship. It eliminates having to break ties based on moves per game as we encounted in the last tournament. Also it can scale up nicely by keeping the number of rounds fairly low if we allow for more players.
In evaluating various tournament formats we did not try out real swiss style tournaments.
http://en.wikipedia.org/wiki/Swiss_tournament
Within brackets of players with equal score they use the slide method for pairing the upper and lower half. Also the tournament runs for a fixed number of rounds and no players are eliminated. After all the rounds are over the player who won the most games (actually scored the highest) wins. The number of rounds is long enough so that one player can acheive a higher score than the rest of the field (about 2*log(N)/log(2)). Ties are usually broken by sum of opponents scores. I will venture to guess that the performance of a real swiss style tournament will be about equal to the floatingDoubleElim format. Also a swiss tournament lacks the climax ending of a knockout style format.
So in many ways the FTE format looks like a good option.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #104 on: Jul 31st, 2005, 10:48pm » |
Quote Modify
|
The advantage/disadvantage of traditional Swiss is that everyone plays the same number of rounds. In high school chess tournaments, it was great to know that, after driving halfway across the state, everyone in the van was going to get to play five rounds no matter what. Also, you never had to face the same guy twice no matter what.
In floating triple elimination, the advantage is that you can go home after you are eliminated. Also, as the players drop out, repeat pairings are eventually mandatory, so you will get another crack at someone who beats you if you both keep winning.
But the hugest advantage of elimination formats is that your fate remains in your hands until elimination. Until you get the third loss, you can always rest secure in the knowledge, "If I win the rest of my games I will still be champion." Each player retains the power to single-handedly vanquish the field. In traditional Swiss this is not true: if you are behind you need to win plus you need the leaders to lose. In some of the rating-based schemes Omar proposed this is not true. And in round-robin tournaments it is very not true, as many players must slog on long after hope is gone.
I realize this has nothing to do with percentage chance of a tournament being won by the best player, but psychologically it seems very important, and in the best spirit of sports and competition.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print