Author |
Topic: Floating Elimination Pairing Algorithm (Read 2536 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Floating Elimination Pairing Algorithm
« on: Jan 20th, 2006, 1:43pm » |
 Quote  Modify
|
I just noticed a possible breakdown in the pairing algorithm as for the 2006 Computer Champoinship. Suppose it goes like this:
Seeding
1667 Gnobot
1586 Loc
1580 Aamira
1574 Clueless
1484 Bomb
Round 1
Gnobot bye
Bomb def. Loc
Clueless def. Aamira
Round 2
Clueless bye
Bomb def. Gnobot
Aamira def. Loc
Now for round three, Bomb must get the bye. Aamira has played Loc and Clueless, so the only pairing that avoids repeat matchups is Aamira vs. Gnobot and Clueless vs. Loc.
Unfortunately, since Clueless is undefeated, the algorithm attempts to pair Clueless first. Aamira is out of the question, since Clueless has played Aamira previously. Since Gnobot is 0-1 and Loc is 0-2, the algorithm prefers the one with fewer losses, and settles on Clueless vs. Gnobot, which then forces the repeat matchup Aamira vs. Loc.
In other words, when we locally give Clueless the best pairing, it doesn't result in the globally best pairing. Obviously we can't change the rules in the middle of a tournament, but thinking ahead to next year's WC and CC, we might want to look at a pairing algorithm which finds the global optimum.
The bad news is that the general problem of minimum-weight, maximum-cardinality matching is NP-complete. It would polynomially solvable if the graph were bipartite, e.g. if there were two teams and each game were between one player from Team A and another player from Team B, but in our pairings anything goes.
Still, despite the intractibility of the general problem, we might be able to exploit the specifics of our situation. For example, rather than giving a repeat pairing a big weight and a 3rd-time pairing a really big weight, etc., it might help to do a finite number of unweighted matching problems under different constraints, accepting the first perfect matching (i.e. the first feasible tournament pairing) we find as constraints are gradually loosened.
Alternatively, if we can't find a reasonable general solution, it might at least help to have a better heuristic than at present. If bad pairings can't be algorithmically avoided, we might at least make them less probable.
I'm really interested in this problem, because I'm afraid that the lack of a good pairing algorithm could negate the acceptance of floating triple elimination even if FTE with optimal pairings would be the best tournament format ever.
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #1 on: Jan 21st, 2006, 6:15am » |
Quote Modify
|
Even if the problem is NP-complete, that wouldn't be that bad in a 5 bot tourney. It might be more difficult for 16 humans I suppose.
It looks like we're well on the way to your scenario coming true.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #2 on: Jan 21st, 2006, 10:33am » |
Quote Modify
|
OK, it looks like the bad scenario has come to pass. Loc will have to play Aamira again, even though a pairing exists which avoids repeat matchups. This isn't a terrible tragedy: After Clueless slaughtered Aamira and Aamira slaughtered Loc, it isn't extra mean to Loc that it doesn't get to play Clueless. Still, in principle it would be nice to get the best possible pairing.
Maybe exhaustive search is simplest and best. Here's a table of the number of possibile pairings given the number of players:
2 1
4 3
6 15
8 105
10 945
12 10395
14 135135
16 2027025
18 34459425
20 654729075
22 13749310575
But the problem is, I'd like to see next year's WC have 24 players...
|
| « Last Edit: Jan 21st, 2006, 3:14pm by Fritzlein » |
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #3 on: Jan 21st, 2006, 3:10pm » |
Quote Modify
|
on Jan 21st, 2006, 10:33am, Fritzlein wrote:...
Maybe exhaustive search is simplest and best...
But the problem is, I'd like to see next year's WC have 24 players... |
|
It could be implemented more efficiently without much more effort. If you define some penalty function p(X) that is the sum of penalties for all the pairs (plus, maybe, the penalty of the bye receiver), you could proceed like this (forgot the algorithm name):
- Split the set A of all possible pairings into a few subsets A1, ..., An.
- Find the lower limit of p(X) on each of the subsets.
- Split the subset with the lowest lower limit further and recompute the limits for the new, smaller subsets.
- Repeat this until you get a subset of a single pairing X0.
- Now, if p(X0) is smaller or equal to all the lower limits of all the subsets you have, you are done and X0 is the answer. Else repeat from step 2.
The lower limit mustn't be precise, of course.
So, say you number the bots 1, ..., N. Start with subsets {bot 1 paired with 2}, {bot 1 paired with 3}, ... {bot 1 paired with N}. (And, probably, {bot 1 gets a bye}.) Your lower limit would be the sum of penalties all `fixed' pairings in a subset. Further subsplitting follows the same scheme: pick a bot that isn't part of a fixed pairing and create subsets of it paired with every possible (not yet fixed) bot.
Phew...
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #4 on: Jan 21st, 2006, 3:13pm » |
Quote Modify
|
on Jan 21st, 2006, 3:10pm, doublep wrote:| you could proceed like this (forgot the algorithm name) |
|
Ah, in Russian it's something like "the method of branches and limits."
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #5 on: Jan 21st, 2006, 3:15pm » |
Quote Modify
|
Yeah, and in our case, the penalty for any given pair must be non-negative, else the estimation of the lower limit will be incorrect.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #6 on: Jan 21st, 2006, 3:17pm » |
Quote Modify
|
on Jan 21st, 2006, 3:13pm, doublep wrote:| Ah, in Russian it's something like "the method of branches and limits." |
|
Yes, we say "branch and bound". It is generally much more efficient than exhaustive search if one branches sensibly, but not guaranteed to be efficient.
Now that I think about it, branching on the pairing of the top seed, say, is quite likely to be efficient. To implement it, we would just have to come up with appropriate penalties for each pairing.
It makes sense to me to assign byes ahead of time, and then pair the remaining players. If the bye is fixed, then we have three types of penalties, in decreasing order of importance:
*Penalty for repeating a pairing
*Penalty for playing someone of a different WL record
*Some penalty to encourage folding pairing (i.e. top versus bottom, 2nd vs. 2nd last, etc.)
|
| « Last Edit: Jan 21st, 2006, 3:44pm by Fritzlein » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #7 on: Jan 21st, 2006, 4:05pm » |
Quote Modify
|
To ensure folding pairing, we could maximize the sum of the squares of the rating differences d^2. If we must minimize, could we let D be the maximum rating difference, and have the penalty per pairing be D^2 - d^2 ?
If there are 2N players, then all those penalties together can't be more than ND^2, so the additional penalty for playing someone of a different record could be ND^2 times the difference in record r. (I guess I would define r to be half the difference in wins plus half the difference in losses.
Finally we could define M to be the most all of those two kinds of penalties could be, approximately the number of rounds times N^2 times D^2. Then a repeat pairing could have an additional penalty of M, and a third-time pairing a penalty of NM, etc.
Then we minimize the sum of penalties using branch and bound. Easy, hey? Does someone want to code this and test it for a floating triple elimination of 17 players? 
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #8 on: Jan 21st, 2006, 9:54pm » |
Quote Modify
|
Hehe, Ryan, I just noticed that the penalities I proposed would probably pair the second round of an 18-player tournament with the top first-round winner versus the bottom first-round loser, just as you advocate. I guess I wouldn't want to mess with weights which are otherwise working just to get my way in that particular dispute. 
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #9 on: Jan 22nd, 2006, 1:31pm » |
Quote Modify
|
OK, I implemented an overkill solution (1000 lines of C++.) You can grab it at http://download.gna.org/quarry/tournament.cpp (modified BSD license, use as you please.)
Usage: compile and run with tournament data redirected to its stdin, e.g.
Code:
$ g++ tournament.cpp -o tournament
$ ./tournament <test-tournament
|
|
Data is in the following format:
Code:
tournament-scheme [parameters]
number-of-players-initially
player-name rating
...
number-of-rounds-player
player-1 player-2 winner
...
...
|
|
With ellipsis standing for repetition. E.g. for the WCC 2006 it would be:
Code:
elimination 3
5
bot_Gnobot 1667
bot_Loc 1586
bot_Aamira 1580
bot_Clueless 1574
bot_Bomb 1484
2
bot_Gnobot
bot_Loc bot_Bomb bot_Bomb
bot_Aamira bot_Clueless bot_Clueless
bot_Clueless
bot_Bomb bot_Gnobot bot_Bomb
bot_Aamira bot_Loc bot_Aamira
|
|
The penalties are not perfect, but produce more or less sensible results. Feel free to experiment. And happy reading, the code is almost uncommented :)
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #10 on: Jan 22nd, 2006, 1:37pm » |
Quote Modify
|
Ah, yes, and the player who receives the bye (if any) goes before the first game, as can be seen in the example.
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #11 on: Jan 23rd, 2006, 1:33am » |
Quote Modify
|
I've always thought that the fairest system for small tournaments is double round robin, where each bot plays each of the others twice, once with each color.
If that's not enough, then after the double round robin, the weakest bots can be eliminated and a new round robin played.
This year's pairing system seems somewhat complex and brittle. It's likely to create pairings that will seem unfair.
David
|
|
IP Logged |
|
|
|
doublep
Forum Guru
Badger author
Gender:
Posts: 82
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #12 on: Jan 23rd, 2006, 4:10am » |
Quote Modify
|
For small number of participants round robins are OK, but the number is slowly growing each year... I think the problem with the double Aami-ra vs. Loc pairing is not inherent to elimination scheme, it's just the problem of the current algorithm. With `globally-best' pairing scheme, I think, the elimination tournaments are generally more interesting, since the weaker bots drop out early, leaving most games for the best of the field.
|
| « Last Edit: Jan 23rd, 2006, 4:11am by doublep » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #13 on: Jan 23rd, 2006, 8:48am » |
Quote Modify
|
If I understand the current pairing system correctly, if Bomb and Clueless split their upcoming games, they will have to play a third time, while Aamira gets two consecutive byes.
If you wish to preserve the "drama" of a championship game, after the round robin portion, a seeded elimination tournament works well.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Floating Elimination Pairing Algorithm
« Reply #14 on: Jan 23rd, 2006, 10:30am » |
Quote Modify
|
I agree that a double round robin starts to be a lot of games. This year we might have had bot_weiser and bot_haizhi in the mix, which would mean 42 games in a double round robin. Given that the games can't run concurrently, keeping the numbers of games reasonably small is important.
On the other hand, I agree that some of the pairings we are getting are intuitively awful. Bomb and Clueless playing three times in a row just doesn't seem right.
I'm not sure at this point whether the pairing algorithm can be fixed to make triple elimination work. If it can work, I guess the assignment of byes needs to come into the formula, rather than being automatic. We need to deliberate and experiment some more...
One thought that occurs to me is that triple elimination will work pretty well if the number of players is larger, because repeat matchups will be less of a problem. With that in mind, one might decided to do double-round robin for 5 bots or fewer, and triple elimination for 6 bots or more.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print