Author |
Topic: World Championship tournament format (Read 9303 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
World Championship tournament format
« on: Apr 29th, 2005, 12:01pm » |
 Quote  Modify
|
Yes, I know it will be eight months before the next human World Championship tournament, but it can't hurt to get a discussion started early, and I have the time right now.
I think the format of the 2005 World Championship left something to be desired. Single-elimination makes the championship too short, and too prone to fluke upsets. I only had to win four games and then I was champ, which not only short-changes the spectators, but also raises the question of whether I just got lucky over a short run of games. We see these problems also in the chess world, where the recent FIDE World Championship knockout events haven't picked the best player as accurately as longer qualifying matches used to do. You can call Khalifman the World Champion on the basis of one big tournament if you like, but he wasn't even in the top ten in the world, much less number one.
On the other hand, elimination matches seem to be more fair than a round robin, and less prone to collusion. For example, if I see that I am already not going to win a prize, I could intentionally lose my game against someone I liked, while trying even harder against the people I don't like. A group of strong players working together has a great chance of making sure one of their own group wins overall. Bobby Fischer complained about the Soviets colluding in round-robin chess tournaments, and he had a point, which is why FIDE changed the format to have eliminations instead.
Now one way to extend the tournament while preserving the elimination format would be to have each round be the best two out of three, and the final round be best three out of five. That would already be an improvement over simple single elimination. But there is still a bit of room for improvement because of two minor flaws: At one game per week a tournament with as few as 9 players would take 14 weeks to complete. Also the seeding remains too important in that if you get paired with the #1 in the first round, that's probably the only person you get to play ever.
A different idea would be to have a standard double-elimination where one loss sends you to the loser's bracket and you have to win your way back up. Again, I like this idea better than single elimination, and it mostly fixes the flaw of getting knocked out by two losses to the same person. If the #1 seed beats you in the first round, at least to get to play someone else the next round where you have a better chance. Also it is shorter that the mini-match format, lasting only 9 weeks.
On the other hand, the traditional structure of the double-elimination leaves room for improvement because it is so hard on the losers. In a 16-player double-elimination bracket, a player who wins the first round can win the tournament with 4 straight wins, whereas someone who loses the first round needs 8 straight wins to win the tournament. That's not fair. To win the whole tournament, it should take a first round loser exactly one more win than a first round winner, not twice as many.
My attempt at solving all these difficulties is what I call "floating triple elimination". Maybe it isn't original to me, but I've never seen it laid out elsewhere, and I'm curious what people think about it. The basic idea is that you get to keep playing until you lose three times, but there is no fixed bracket. On every round you must play someone you haven't yet played, until there is no alternative but to repeat matchups. This means that except for the top few players, everyone who gets eliminated will have lost to three different players, rather than to one player multiple times. Also, since everyone plays every round, everyone needs the same number of total wins to become champion, no matter whether they win or lose in the first round. Finally, a full sixteen-player bracket would complete in 12 weeks, which is fewer rounds than the mini-match format even though in that format one can be knocked out in two game but in my proposed format everyone gets to play a minimum of three games.
|
| « Last Edit: Apr 29th, 2005, 12:02pm by Fritzlein » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #1 on: Apr 29th, 2005, 12:01pm » |
Quote Modify
|
As usual with my proposals there is an increase in complexity in exchange for everything else being ideal.  One problem is handling byes, because not only might there be an odd number of players to start out, but the way players are eliminated might create an odd number of players in a later round. Furthermore, when the time comes that it is inevitable to repeat a matchup, there needs to be a strict algorithm for which repeat matchups are assigned in order to keep things fair. I expect the pairings would be complicated enough that they would have to be done by machine algorithm rather than by hand. Still, for a programmer it should be easy enough to be worth doing if the goals of formatting the tournament are worth striving for. Here is my proposed algorithm:
Rule 1: When an even number of players remain, everyone plays the round. When an odd number remain, one player gets a bye. No player may get a second bye unless every remaining player has already recieved one bye. Similarly no player can get an (n+1)st bye unless all remaining players have n byes.
Rule 2: Subject to Rule 1, the pairings for each round must minimize the number of repeat matchups. A pairing which has a matchup for the (n+1)st time must be rejected in favor of any in which all matchups are occuring for the nth time or fewer.
These are absolute rules which are enough to ensure that the goals of the tournament are met, but if there are multiple pairings which meet the requirements, one might prefer one pairing to another based on things like:
* Minimizing the number of second-time matchups is desirable among all pairings which don't have any third-time matchups
* Matching players with the same record is desirable, i.e. it's better to have two 2-0 players matched and two 1-1 players matched than to have two matchups of 2-0 vs. 1-1.
* Giving a bye to the highest-rated player eligible for the bye is desirable.
* Perhaps as a tiebreaker between two pairings equal on all these counts, pick the one which minimizes the sum of the squares of the rating differences
Anyway, that's enough to give a flavor of what I'm proposing. I'm very open to comments, corrections, criticism, etc., and I would especially appreciate a reference if someone has heard of a similar proposal before.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #2 on: Apr 30th, 2005, 6:13pm » |
Quote Modify
|
It's a good point that if we have a long time, there are many good tournament formats. My "floating triple elimination" is an attempt to keep it fun, minimize fluke champions, and still keep the time frame somewhat compressed. I'm curious what Omar thinks would be the maximum acceptable length of the World Championship tournament. I was actually worried that he might think the worst case of 12 rounds for a 16-player tournament would already make the tournament too long.
You are absolutely right that new people can join and rapidly climb the ladder. For example, at the start of the Postal Championship, Robinson was ranked about #15 among humans, and now he's #3 and rising, while the tournament is still ongoing! Also the 2005 World Championship started only a bit more than three months after I played my first ever game of Arimaa on the server.
But that said, I don't think the changing landsacpe is the biggest reason to keep the tournament short. The main pressure is probably the time commitment required by the participants. We would like lots of participants, but what if several top players opted out because they couldn't commit to one game per week for 12 consecutive weeks? (Although it would be shorter than 12 weeks if fewer than 16 players signed up.)
So the time commitment has to be balanced against making the result meaningful. Single elimination is the shortest possible format, but very prone to upsets. A series of qualifying pools is not at all prone to upsets and very likely to pick the strongest player as champion, but would be very slow. I tried to aim for some middle ground with my proposal, but everything depends on what shape Omar would like the tournament to have. If time is no obstacle, then we should try something slower and simpler. On the other hand, if 12 weeks is already too long, there's no point even discussing the details of how my idea would work. 
But with that said, I know Omar likes to hear everyone's opinion before he lays down the law.
|
| « Last Edit: Apr 30th, 2005, 6:14pm by Fritzlein » |
IP Logged |
|
|
|
Robert
Forum Newbie
Arimaa player #970
Gender:
Posts: 3
|
|
Re: World Championship tournament format
« Reply #3 on: May 3rd, 2005, 6:46am » |
Quote Modify
|
just a bit in the defense of double elimination. i went through it quickly for 16 players and if you win every game it takes 5 wins, and if you lose your first game you have to win the next 7 games to win the match... so you can either win with a record of 5-0 or 7-1.
with your proposed system, isn't there a chance of the amount of rounds varying quite a lot, and would thus be kind of difficult to judge when the final would be, or what time limit to put on the tournement? and you might get a final where one player has to win three times to win, and another only has to win once?
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #4 on: May 3rd, 2005, 9:13am » |
Quote Modify
|
I'm pretty sure that in a sixteen-player double-elimination, if you lose the first round, you need to win the next eight in a row to win the tournament. Did you remember that the winner of the loser's bracket has to beat the winner of the winner's bracket twice in a row at the end?
As for the number of rounds varying in floating triple elimination, there is a little bit of uncertainty depending on on how the byes work out, but I think only +/- one round. A greater uncertainty comes from whether or not the eventual winner ever loses. If one player never loses, I believe that a 16-player triple-elimination will take at most ten rounds (contrasted with eight rounds for traditional double-elimination), but if everyone gets up to their maximum two losses it can take an extra two rounds (i.e. twelve for triple elimination versus nine for the traditional double-elimination.)
You are quite right, with triple-elimination you could get to a final situation where one player player has to win three times to win the match and the other only has to win once. But that happens all the time in sports, for example the NBA playoffs going on now. In a best-of-five playoff, if you lose twice you have to win the next three whereas your opponent only has to win once. And in a double-elimination tournament, the final *always* is a situation where one player has to win twice in a row and the other player only once. This is a consequence of each player being allotted a fixed number of losses.
In summary I think the variable number of rounds in floating triple-elimination is a minor disadvantage, but I contend it is not as big a flaw as traditional double-elimination making a first-round loser win twice as many more games to win the tournament as a first-round winner, i.e. 1-0 needs four more wins and 0-1 needs eight more wins. But now that I think about it, this problem also could be remedied by doing *floating* double-elimination, i.e. by having eveyone play every round as I proposed for triple elimination, in place of having more rounds in the loser's bracket than in the winner's bracket. This would solve the fairness issue and also keep it as short as possible.
|
| « Last Edit: May 3rd, 2005, 6:30pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #5 on: May 3rd, 2005, 6:13pm » |
Quote Modify
|
Quote:| i went through it quickly for 16 players and if you win every game it takes 5 wins, and if you lose your first game you have to win the next 7 games to win the match... so you can either win with a record of 5-0 or 7-1. |
|
on May 3rd, 2005, 9:13am, Fritzlein wrote:| I'm pretty sure that in a sixteen-player double-elimination, if you lose the first round, you need to win the next eight in a row to win the tournament. Did you remember that the winner of the loser's bracket has to beat the winner of the winner's bracket twice in a row at the end? |
|
I just tried it and although I've never been in one of these style tournaments, I agree with Robert. I personally think that 7-1 is about equivalent to 5-0 so this is a good system. Fritz can you point out what's wrong with these calculations?
R is the round number
N is the number of players in the normal round
E is the number of players in the elimination half of the round
O is the number of players who are totally out
R N E O
1 16 0 0
2 8 8 0
3 4 8 4
4 2 6 8
5 1 4 11
6 1 2 13
7 1----1 14
8* 1----1 14
A player who won all his/her games would play rounds 1, 2, 3, 4, and 7. In this case round 8 would not be played. Their final score would be 5-0.
A player who lost his/her first game and subsequently won all would play all 8 rounds, with one lost giving 7-1.
Not that this makes your triple-floating system bad of course. In part it all depends how many games you're willing to run to reduce the luck element, and how complicated you're willing to make the algorithm .
My main concern for this year is to not repeat the situation where the top ranked player plays all games as silver, and also where the top ranked player has to play a higher ranked player than the second ranked player in every round until they meet (or are knocked out).
|
| « Last Edit: May 3rd, 2005, 6:26pm by 99of9 » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #6 on: May 3rd, 2005, 7:05pm » |
Quote Modify
|
on May 3rd, 2005, 6:13pm, 99of9 wrote:
I just tried it and although I've never been in one of these style tournaments, I agree with Robert. I personally think that 7-1 is about equivalent to 5-0 so this is a good system. Fritz can you point out what's wrong with these calculations?
|
|
Sure thing. The way double-elimination traditionally has worked is that the losers' bracket plays more rounds.
For 16 players, after one round there are 8 winners and 8 losers. Next the losers play a round knocking 4 out and leaving 4, and the winners play a round, leaving 4 undefeated and creating 4 new losers. Before the winners play again, the 4 old losers play the 4 new losers, knocking out four and leaving only 4 losers.
So, apart from the first round, the losers have played two more rounds, and the winners have played one more round, leaving 4 winners and losers each. The process then repeats with the losers playing a round, the winners playing a round, and the old losers playing a round against the new losers. At this point, apart from the first round, the losers have played four more rounds, and the winners have played two more rounds, leaving 2 winners and losers each.
etc. etc. No matter what the size of the tournament, the losers play twice as many rounds as the winners. Let me try to do the bracket in ASCII
[pre]
-----
----| |----
| ----- |
----| |----
| | ----- | |
| ----| |---- |----
| ----- | |
----| ---- |
| | ----- |
| | ----| |---- |----
| | | ----- | | |
| ----| |---- | |
| | ----- | | | |
| ----| |---- |---- |----
| ----- | | |
----| ---- | |
| ----- | |
| ----| |---- ---- |
| | ----- | |
| ----| |---- |
| | | ----- | | |
| | ----| |---- |---- |----
| | ----- | | | |
----| ---- | | |
| ----- | | |
| ----| |---- |---- | |
| | ----- | | | | |
----| |---- | | | |
| ----- | | | | | |
----| |---- |---- |---- |----
----- | | |
---- | |
| |
---- |
|
|
|
----
[\pre]
LOL. That totally didn't work, but it is so funny I'm leaving it. Try this instead: http://www.foosballheaven.com/pdf/tournament16c.pdf
Anyway, it looks like what you were doing, 99of9, is almost having everyone play every round, i.e. almost what I am proposing.
|
| « Last Edit: Mar 30th, 2006, 4:04pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #7 on: May 3rd, 2005, 11:29pm » |
Quote Modify
|
OK thanks for the explanation. That makes sense.
I don't think robert's/my method is quite the same as your floating (double) elimination, but I agree it's close. In my scheme the E category (those with 1 loss) is strictly separated from the N category (those with 0 losses). The only time they play against each other is when both pools have found their winner. (The winner of pool N gets byes in rounds 4 and 5.)
I like your picture... at first glance I thought you'd drawn out an entire hypothetical triple-elimination to show me that it was not so complex .
|
| « Last Edit: May 3rd, 2005, 11:31pm by 99of9 » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #8 on: May 5th, 2005, 5:54pm » |
Quote Modify
|
on Apr 30th, 2005, 6:13pm, Fritzlein wrote:| But with that said, I know Omar likes to hear everyone's opinion before he lays down the law. |
|
And even after that Im still open for suggestions and changes
Im all for a system that requires more than a single elimination to avoid flukes. But I was using this in the past mostly so that it would not require a lot of time commitment from the players. I would hate to see one of the top ranked players not be able to play just because they couldn't make the time commitment. So the total number of games the winner has to play is still a bit of a concern for me.
Also it would be nice if we could fit something into about a two month time frame. Something that fits into a 3 month time frame is still OK with me, but would perfer something shorter if possible.
Im also open to the possibility of using ratings to limit the number of entries to reduce the number of rounds. For example only the top 8 players (based on ratings) are selected for the tournament.
I like the idea proposed by Karl where a player continues playing until losing at least three times. Does anyone want to try running some simulations with it. That is given a set of players and their measured (used for seeding and pairings) and true (used in simulating the outcome of a game) ratings where the measured ratings are within 100 points of the true ratings run the tournament many times to see what the probability is of the true highest rated player winning the tournament. Maybe we can also compare this to other formats like one, tow and four eliminations.
I would love to run some simulations like this, but I just can't right now. However, if no one else does it I know I eventually will.
I also came across this article which is of interest to this topic:
http://www.chesscenter.com/twic/sonas010704.html
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: World Championship tournament format
« Reply #9 on: May 6th, 2005, 12:35am » |
Quote Modify
|
Omar, thanks for the link to Sonas' article. It is interesting that top chess players don't like round-robins or even Swiss pairing for their championship matches due to the possibility of collusion. I quite agree, and there is an added point I discovered recently in a casual ping-pong tournament. The tournament was supposed to be round-robin, but the participants, as soon as they were eliminated from prize contention, quit and went home, forfeiting their remaining games.
The take-home message is that players shouldn't have any scheduled games after they no longer have a chance of winning. In a serious situation there may be cheating, and in a casual situation there may be apathy. Knockout-style formats are both more exciting and more fair.
Sonas' double-elimination proposal is interesting. It is more fair than usual double-elimination, because the matches for the winners are twice as long as for the losers. To use this for Arimaa, we would have to introduce a tiebreak into two-game matches, but maybe that is simple: the lower number of moves to victory. This balances out the effort one has to put into playing, i.e. everyone now plays the same number of games, but it still has a huge defect: It doesn't balance out winning chances, because folks in the losers bracket still have to face twice as many chances of being eliminated as folks in the winner's bracket.
With 16 players and Sonas-style double elimination, the whole tournament still takes only nine weeks because the extra games are coming from making the winners bracket play more games instead of resting while the losers bracket plays extra rounds.
Sonas calls a late-round bye "ugly", and I admit that there is a certain inelegance, but I think it is not so very unfair because the number of byes is equalised overall. In triple-elimination, most players who survive that long will have a turn at getting a bye. Moreover, the harsh penalty for losing early that exists in traditional double-elimination and persists in Sonas' double-elimination is more unfair (uglier) in my opinion than having players take turns receiving byes.
If we go with triple elimination as I poropse and limit the field to 8 players, by my calculation the tournament will last 8-10 weeks, i.e. about the same length of time as traditional double-elimination with 16 players. This raises the question of whether it is more desirable to eliminate fluke champions by having triple-elimination and only the top eight interested parties competing, or whether it is better to let sixteen people go at it and have only double-elimination.
My gut feeling is that it is nice to have the championship be as "open" as possible. If we must have a short tournament, then it's better to accept a slightly higher chance of upsets and give everyone a chance to play who wants to play.
At the moment, unemployed as I am, it actually seems the least of the evils to have an "open" triple-elimination and if it takes three months, so be it. But I can imagine that if I have a job come November, playing one tournament game every week for 12 straight weeks could become a burden.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #10 on: May 6th, 2005, 9:08am » |
Quote Modify
|
Just for the record I'm strongly against limiting the field for the WC at this early stage of arimaa's development. I can understand this may be necessary when there are hundreds of willing participants, but until then I really think the tournament should be open to all.
As one of those who had an "unexpected" loss in my first game of this years comp, you might expect me to be one of the ones railing for triple elimination to reduce the random/noise element. But personally I think a double elimination is sufficient warning in arimaa. If someone is really the best arimaa player, they probably shouldn't be losing twice in the course of 5-8 games.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: World Championship tournament format
« Reply #11 on: May 6th, 2005, 10:47am » |
Quote Modify
|
You are right if all the opponents are the same standard. But there will be plenty of easy games in that 5-8 games.
It seems to me that the arimaa field is quite spread out at the moment.
For comparison note that a win rate of 2/3 would have placed over 5th in the postal tourney with 16 players.
My statement is not intended as a hard and fast mathematical theorem which covers all possible outcomes and all possible player skill distributions. It's based on my opinion of how a tournament between current players would turn out. In the current conditions, 2 losses in 5-8 games would not cut it.
|
| « Last Edit: May 6th, 2005, 10:48am by 99of9 » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: World Championship tournament format
« Reply #12 on: May 6th, 2005, 11:39am » |
Quote Modify
|
In my opinion, one of the things that makes a tournament (in any sport) interesting is that anyone has a chance (however remote) of winning. Some tournaments are set up this way, on purpose, in order to encourage participation. (ie Slowpitch baseball)
One of the positive aspects of the single elimination tournament, is a weaker team still has a chance to advance far into the tournament. (ie NCAA basketball)
A double elimination still retains the feature that a weaker team still has a decent chance (although not as good as a single elimination). It also allows a strong team to get upset once and still be able to win. If a team gets upset twice, then they don't really deserve to win the tournament. Another nice feature of double elimination, is that two teams rarely have to play each other twice. It can happen, but not until very near the end of the tournament.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #13 on: May 6th, 2005, 6:37pm » |
Quote Modify
|
on May 6th, 2005, 11:39am, jdb wrote:In my opinion, one of the things that makes a tournament (in any sport) interesting is that anyone has a chance (however remote) of winning. Some tournaments are set up this way, on purpose, in order to encourage participation. (ie Slowpitch baseball)
|
|
I guess it really comes down to a question of what we want the World championship tournament to be.
I've always felt that the winner of a world championship tournament should be the person with the highest true rating (see my previous post for more on true rating).
But after seeing Jeffs posting, I am reconsidering my position. I'll post more after I've thought about it.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: World Championship tournament format
« Reply #14 on: May 18th, 2005, 5:17pm » |
Quote Modify
|
I've been thinking about this for a while and Im still a bit undecided.
On the one hand I feel the winner of the WC should be the player with the highest true rank. This is what I would expect the result of a WC tournment to produce. But it is hard to acheive, and it could take a lot of games if the true rating difference between the players is small.
The other possibility is that the winner should be one of the better players but not necessarily the best. Initially I would not have even considered this, but if we take into consideration more factors such as the time frame of the tournament, greater participation, and spectators, then it is worth considering. Such a tournament is interesting for even lower ranked players, since they have a higher chance of winning; so more players are likely to participate. It is interesting for spectators since the outcome is more unpredictable. And it can be acheived with short tournaments. Also this is what the results of most tournaments will be anyway (unless a lot of effort is put into selecting the best player).
I am so undecided on this that I think it might be better if we just have two seperate tournaments. One which is open to all and has the single-elimination format and another which is limited to just the 4 top rated players and has a more stringent format such as a double round-robin or Karl's format. The first would be like the "Open Classic" and the second would be the "World Championship". The purpose of the first is to have a fun tournament where anyone can participate and the winner is not necessarily the best player. The purpose of the second would be to select as best as possible the player with the true highest rank. The tournaments would not overlap so a player could play in both. Both tournaments will have prizes and will require a registration deposit (to ensure commitment) which will be refunded if no games are forfeited.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print