Author |
Topic: World Championship tournament format (Read 9309 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Re: World Championship tournament format
« Reply #120 on: Aug 4th, 2005, 7:34pm » |
 Quote  Modify
|
on Aug 4th, 2005, 12:30am, omar wrote:
Here's a trivial sounding math question for anyone who wants to take a crack at it:
If a player A can defeat player B with a probability p then what is the probability that player A will win if they play a series of N games?
|
|
As far as I know, Jeff's method of adding up factorials is the only way to get an exact answer. However, as the length of the match increases, the binomial distribution increasingly resembles (and can be approximated by) the normal distribution. To use Omar's example, say one player wins 60% of the time. In an 11 game match, he would be expected to win 6.6 games. For him to lose the match he would need to score 6.6-(11/2) = 1.1 wins or more below expected. Now one standard deviation is sqrt(Npq) = sqrt(11 * 0.6 * 0.4) = 1.6248, so a match loss is 1.1/1.6248 = 0.677 standard deviations below the mean. Consulting my stat function on my calculator, that occurs with probability 0.2492, so the favorite will win 75.08% of the time. Not a bad approximation of 75.35% as calculated by the program.
The approximation is better for larger values of N and values of p closer to 0.5.
|
| « Last Edit: Aug 4th, 2005, 7:36pm by Fritzlein » |
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #121 on: Aug 9th, 2005, 11:45am » |
Quote Modify
|
on Aug 1st, 2005, 8:25am, jdb wrote:
If a Swiss and FTE have the same number of rounds, and the number of participants is sufficiently large, the Swiss will perform better. While each individual game in the Swiss is not as effective at determining the winner, in the latter rounds, the Swiss has more total games. Which one is better for a 16 person tourny, I have no idea. 
|
|
I've been thinking about this recently and without having done any simulations with a swiss format I am starting to think that the floatTripElim (FTE) would still perform better than a swiss format even if they both had the same number of rounds; at least for the 16 player case.
First of all a typical swiss tournament has just a few more rounds than what single elimination requires; that is log2(N) where N is the number of players. I have not been able to find any good source on the web providing an exact way to determine the number of rounds for a given number of players. If you happen to come across this please let me know. One page that I found said you need about 1.3*log2(N) rounds:
http://www.scoutingresources.org.uk/ideabase_swiss.html
Now if we assume that a swiss tournament had exactly log2(N) rounds then it would be exactly the same as singleElimSlide. The maximum number of rounds a swiss tournament could possibly have N-1 since any two players cannot play more than once. With the maximum number of rounds it would be exactly the same as roundRobin. We know from the simulations that roundRobin performs better than singleElimSlide (about 30% compared to 25% for the 16 player case). Since the number of rounds in a typical swiss tournament is much closer to log2(N) than N-1 I would think that it would perform closer to singleElimSlide than to roundRobin.
Since the FTE has performed better than roundRobin with fewer rounds (at least up to the 16 player case) I think it is safe to conclude that FTE will perform better than swiss even if swiss used the same number of rounds as FTE.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #122 on: Aug 9th, 2005, 3:48pm » |
Quote Modify
|
While it is true that more total games means more information in general, it doesn't necessarily mean more information about who is the best. If I wanted to know who was best in a 16-player tournament, I'd lean towards a FTE over a 10-round Swiss. The "extra" games of the Swiss tournament are mostly between players who have no claim to the top spot. A 10-round Swiss might be pretty darn good at ordering all the players from best to worst, but in my guess will be slightly worse at determining who is the best.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #123 on: Aug 10th, 2005, 10:45am » |
Quote Modify
|
While trying to search for info on the Swiss tournament format I happened to come across this very interesting article. A must read for this topic:
http://www.oxfordcroquet.com/tech/appleton/index.asp
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #124 on: Aug 10th, 2005, 12:15pm » |
Quote Modify
|
A very interesting article.
If I understood correctly, the article's simulation method attempted to account for a player's strength varying from game to game.
The article described a tournament format called "Draw and Process". I had never heard of it before. It seems to have some good qualities.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #125 on: Aug 11th, 2005, 8:13pm » |
Quote Modify
|
That is an excellent article, Omar. I agree with JDB that the "draw and process" format is the most intriguing. For 16 players D&P takes 9 rounds unless one player wins both brackets, in which case it takes only 8. Therefore it probably takes about one more round on average than floating double elimination, which takes 7.7.
I am going to go out on a limb to predict that the D&P, in spite of having one more round than the FDE, will have a couple percentange points less chance of picking the best player as the winner.
|
| « Last Edit: Aug 11th, 2005, 8:14pm by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #126 on: Aug 11th, 2005, 8:39pm » |
Quote Modify
|
I've never heard of the Draw and Process format before either. Doing some searches for it brought me to this page:
http://www.magma.ca/~acna/cobclubch.htm
It seems like running a single elemination tournament two times but with different ordering of players and if the same player wins both time then that player is the winner. If different players win then maybe there are additional games between them to select a final winner.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #127 on: Aug 11th, 2005, 11:34pm » |
Quote Modify
|
Algorithmically, the draw and process can be modelled as a single elim tournament, with fixed pairings. Each person is entered twice, subject to the special seeding requirements. This would also work for three or more way draw and process, by adding byes to fill out the unused brackets. If the same person wins all the brackets, the extra games are meaningless, but don't change any of the results.
Another option would be to try random pairing.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #128 on: Aug 12th, 2005, 6:05pm » |
Quote Modify
|
As I understood it, the desired property of draw and process is that people who meet in the first round of one bracket can't meet until the finals of the other, people who meet in the second round of one bracket can't meet until the semi-finals of the other, etc. It seems, however, that there is more than one way to meet this requirement. For example, if the draw is
1-16--9-8----5-12--13-4--------3-14--11-6----7-10--15-2
then the process could be
1-2--3-4----5-6--7-8--------9-10--11-12----13-14--15-16
but it also could be
1-15--3-13----5-11--7-9--------8-10--6-12----4-14--2-16
I wonder whether one could build three brackets such that the D&P condition is satisfied for any pair. My example doesn't quite do that, because 1 could meet 3 in the second round of both of the latter two brackets.
I'm curious about it mostly as a math question, because I believe that a D&P with two brackets will be out-performed by a floating double elimination, and I beleive a D&P with three brackets will be out-performed by a floating triple elimination.
|
| « Last Edit: Aug 12th, 2005, 6:06pm by Fritzlein » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #129 on: Aug 12th, 2005, 6:27pm » |
Quote Modify
|
I'm working on coding up draw and process now. I'll let some of them run overnight and post the results in the morning.
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #130 on: Aug 13th, 2005, 8:21am » |
Quote Modify
|
Here are my results for a four way draw and process.
The brackets were paired, slide,fold,fold,slide.
run2 'formats/dap' 2000 16 500 50 10
1 39.2%
2 23.4%
3 14.7%
4 9.0%
5 6.2%
6 3.3%
7 2.1%
8 0.9%
9 0.4%
10 0.2%
11 0.3%
12 0.1%
13 0.1%
14 0.1%
Three way draw and process
Brackets paired fold,slide and random, with random getting bye into final.
run2 'formats/dap' 2000 16 500 50 10
1 35.5%
2 23.9%
3 17.2%
4 8.8%
5 5.8%
6 3.8%
7 2.0%
8 1.3%
9 0.9%
10 0.6%
11 0.1%
12 0.1%
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #131 on: Aug 13th, 2005, 6:09pm » |
Quote Modify
|
Looks like the 3-way D&P did about as well as quadruple floating elimination, which has about the same number of rounds (i.e. between 13 and 14). The four-way D&P would take up to 18 rounds (a little less on average due to final games begin unnecessary sometimes) so there is nothing to dircetly compare it to. One could get at least 5 and maybe six eliminations for that number of rounds.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #132 on: Aug 15th, 2005, 4:04pm » |
Quote Modify
|
on Aug 13th, 2005, 8:21am, jdb wrote:Here are my results for a four way draw and process.
The brackets were paired, slide,fold,fold,slide.
|
|
Thank Jeff.
Im just wondering how you handled ties for first place?
Also did you use any of the pre-tournament ratings to order the players?
|
| « Last Edit: Aug 15th, 2005, 4:06pm by omar » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #133 on: Aug 15th, 2005, 4:08pm » |
Quote Modify
|
on Aug 13th, 2005, 6:09pm, Fritzlein wrote:| Looks like the 3-way D&P did about as well as quadruple floating elimination, which has about the same number of rounds (i.e. between 13 and 14). |
|
FTE with 16 players averaged a little over 10 rounds. So I think it was a bit faster.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print