Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Events >> Floating Elimination Pairing Algorithm
        
(Message started by: Fritzlein on Jan 20^th, 2006, 1:43pm)

Title: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 20^th, 2006, 1:43pm

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by 99of9 on Jan 21^st, 2006, 6:15am

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 21^st, 2006, 10:33am

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...

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 21^st, 2006, 3:10pm

on 01/21/06 at 10:33:18, 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...

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 21^st, 2006, 3:13pm

on 01/21/06 at 15:10:15, doublep wrote:

you could proceed like this (forgot the algorithm name)

Ah, in Russian it's something like "the method of branches and limits."

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 21^st, 2006, 3:15pm

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 21^st, 2006, 3:17pm

on 01/21/06 at 15:13:15, 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.)

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 21^st, 2006, 4:05pm

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? :P

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 21^st, 2006, 9:54pm

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. :-)

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 22^nd, 2006, 1:31pm

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 :)

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 22^nd, 2006, 1:37pm

Ah, yes, and the player who receives the bye (if any) goes before the first game, as can be seen in the example.

Title: Re: Floating Elimination Pairing Algorithm
Post by fotland on Jan 23^rd, 2006, 1:33am

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

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 23^rd, 2006, 4:10am

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by jdb on Jan 23^rd, 2006, 8:48am

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 23^rd, 2006, 10:30am

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.

Title: Re: Floating Elimination Pairing Algorithm
Post by Ryan_Cable on Jan 23^rd, 2006, 11:53am

I dislike round robins for awarding a serious title. I think it puts too much importance on how strong players do against weak players rather than focusing on how the strong players do against each other. It is a bit less of a problem for bots and for drawless games, but I still don’t like it.

I think using doublep’s global search pairing would resolve many of the obvious problems with the floating elimination tournament pairing, but I think there will always be an element of pairing luck in any elimination tournament, particularly when the ranking of bots is essentially random. The best way to deal with this is to increase the number of eliminations.

With two games per day is there any reason the tournament shouldn’t be allowed to go for three weeks? Personally, I would like to see F5E. It would require at most 24 games for 5 bots, and 39 games for the maximum 8 bots. You could also make an argument for a single elimination tournament with best of 7/9 matches, but given that the ranking of bots is almost random, I think F5E is clearly better. Also, F5E is much more interesting than single elimination since many different bots play each other.

I think the putting the assignment of byes into the global search would produce the same results as our current assignment process if the weights for byes were fairly chosen. Assigning byes is likely to always be a problem when the number of bots is less than the number of rounds.

Title: Re: Floating Elimination Pairing Algorithm
Post by doublep on Jan 23^rd, 2006, 2:02pm

Feel free to experiment with my program :) It currently has bye penalty larger than the sum of game penalties (equivalent to first assigning a bye, then looking at the pairings), but this can be changed. The order of penalty importance should probably be like this:

Make byes go only to the players with least byes so far.
Make byes go to the player with the least number of losses.
Make the number of repeating games in this round the least possible.
Make the bye go to the player with the highest rating.
Make the players with similar W/L record play against each other.
Make the ratings of each pair opponents as different as possible.

Maybe some of the items above should not dominate the others completely.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 23^rd, 2006, 5:00pm

I am abjectly sorry for the way the pairings are working out for this Computer Championship, based on the pairing algorithm I proposed. Bomb is clearly the top dog so far, so it just isn't fair to Clueless to have to play Bomb three times before Aamira has to play Bomb once. I guess the algorithm worked so amazingly well for the World Championship only because we had 2^4 players then.

That said, I quite agree with Ryan in my general preference for elimination tournaments rather than round robins, for several reasons. (1) Round robins are too likely to end tied. For example, the 2005 Computer Championship was double round-robin, with poor results. Clueless and Bomb each beat all the other bots, but split their two games with each other. (2) Our equipment limits the number of games (not rounds) that can be played, so it is better to use the games to determine finer distinctions among the top bots than to have lots of lopsided wins between top bots and bottom bots. (3) We want a completely correct champion more than we want a completely correct ordering top-to-bottom. (4) In human tournaments especially, it can skew the outcome for a player to fight hard until mathematically eliminated, and then play remaining games perfunctorily, if at all. Also collusion may rear its ugly head.

So if we can improve the structure of the elimination tournament somehow, that's what I'd prefer. Yet I agree with Grey0x2a's comment in chat today that a transparent system is extremely important. Players are always going to get unfavorable pairings, even in the best possible system, so the rules need to be crystal clear. In particular, clarity requires the levels of weights to be absolute. If there is anything like 2.371 repeat pairings being worth a bye out of turn, it will make the pairings impossible to understand without a computer, never mind impossible to generate.

I like doublep's list of priorities, but I would raise the repeated pairing priority even further:

* Give the bye to some player among the players with the fewest byes so far.
* Minimize the number of pairings occuring for the Nth time.
...
* Minimize the number of pairings occuring for the fourth time.
* Minimize the number of pairings occuring for the third time.
* Minimize the number of pairings occuring for the second time.
* Give the bye to the player with the fewest losses.
* Pair players with similar W/L record against each other.
* Give the bye to the player with the highest rating.
* Maximize the sum of the squares of the rating differences.

To be clear, I'm now proposing that any betterment in avoiding repeat matchups should trump the assignment of the bye between players with an equal number of byes. If you have to give the bye to the bottom player in the field to avoid a repeat, so be it.

Also I'm proposing that avoiding one third-time matchup is worth accepting any number of second-time matchups, etc.

I have purposely put in pre-tournament ratings only in the bottom two criteria. Both in the World Championship and in the Computer Championship there were some seriously skewed pre-tournament ratings, so I want ratings to be relied on as little as possible.

If my current proposal were put into force immediately, then the round six bye could not possibly go to Aamira (on the basis of rating) or even to Bomb (on the basis of W-L record). Since all three bots have received one bye, we should look first at repeat pairings. Bomb and Clueless have played twice, Aamira and Clueless have played once, but Bomb and Aamira have never played. In my mind, to pair Bomb and Aamira while Clueless gets the bye is clearly the fairest pairing.

JDB, if you protest my pairing algorithm to Don Dailey, requesting that Round 6 be forced to be Bomb vs. Aamira, I will wholeheartedly support your claim.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 23^rd, 2006, 5:23pm

Incidentally, the CC tournament pairing algorithm is simplified from what I originally proposed in April. If we go back to what I said in April, before Omar asked for an easy implementation, then we also get Bomb-Aamira in round 6. So arguably, the intent of the algorithm was clear all along, and what we settled on was a buggy implementation more than a different philosophy.

on 04/29/05 at 12:01:29, Fritzlein wrote:

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

Title: Re: Floating Elimination Pairing Algorithm
Post by 99of9 on Jan 23^rd, 2006, 6:43pm

on 01/23/06 at 17:00:38, Fritzlein wrote:

To be fair to you, you have also been hurt by the fact that a buggy version of bomb was playing all December, and thus obtained the lowest pre-tournament rating. If that rating had been accurate, clueless would actually be enjoying playing bomb three times (assuming buggy-bomb had luckily obtained the undefeated tournament record its tournament counterpart has).

Title: Re: Floating Elimination Pairing Algorithm
Post by Ryan_Cable on Jan 24^th, 2006, 2:17am

First, one thing that seems to have been overlooked in all of this is that despite the imperfect pairing algorithm, the FTE is performing its design purpose wonderfully. It is now essentially a certainty that the True Champion (Bomb) will win the CC, and do so by facing and defeating all 4 opponents. Only Aamira has any notable chance of beating Bomb. In the unlikely event that Aamira (or Clueless) manages to win one game or more against Bomb, first and second place should be undisputed. Thus, the following assumes that Bomb goes undefeated. (Personally, I think this has a 98%+ chance anyway.)

Under the pairing procedure specified in the rules, the next game will be Aamira v Clueless. If Aamira beats Clueless, Clueless will be eliminated with a 2-3 record and being 1-1 against Aamira; Aamira would then lose 2 in a row to Bomb and be eliminated with a record of 4-3. In this case, Aamira takes second place unambiguously.

However, if Clueless beats Aamira, then Aamira gets a bye, while Clueless is beaten by Bomb and eliminated with a 3-3 record. Aamira is then the last bot to be eliminated, losing to Bomb and finishing with a 3-3 record. The rules don’t specify how second place is determined (or first place for that matter), but conventionally the last bot eliminated is given second place in an elimination tournament. Also, (I assume) the last player eliminated (Adanac) was given second place in the WC. Still the fact that Clueless is 2-0 against Aamira makes it seem unjust to have Aamira get second place, just because it got a bye, just because it was rated 6 points above Clueless.

If we go with Fritzlein’s suggestion and have Bomb play Aamira, Bomb gives Aamira its second loss, then Clueless plays an elimination game against Aamira, and finally the survivor is eliminated by Bomb. The important thing to notice is that these are the exact same games as above, just in a different order. As both a practical matter and a philosophical matter, the order in which the games are actually played doesn’t make any difference.

Ultimately, it all comes down to whether we think Aamira should be awarded second place (and the $200 that comes with it) even if it loses to Clueless for a second time. This is marginally ambiguous, since it was never specifically stated in the rules that second place goes to the last player eliminated, but I think this was widely assumed. My personal sense of fairness says that we have to play the ball as it lies, even though the rules and the pairings have clearly treated Clueless very harshly. Others have different opinions.

Still, laying the blame for this on FTE or on Fritzlein’s imperfect pairing algorithm is a mistake. FTE was not designed to do a particularly good job of picking second place, and like all elimination tournaments, pairing luck plays a large part in the assignment of second place. A globally optimal pairing algorithm would have performed better, but fixing the huge errors in the bot rankings is going beyond the call of duty anyway. If we had gone with a single elimination tournament (with games or matches), fourth ranked Clueless would have faced fifth ranked Bomb and been the first bot eliminated. Second ranked Loc would lose to third ranked Aamira, while Bomb beats first ranked Gnobby. Then Bomb would win the tournament knocking out Aamira in second place. This would be significantly less fair than FTE, but it would probably also be less disputed simply because people are more familiar with how single elimination tournaments work.

Title: Re: Floating Elimination Pairing Algorithm
Post by Fritzlein on Jan 24^th, 2006, 8:20am

Excellent points, Ryan. The CC tournament format is apparently doing well at picking first place, and only second place is at issue. Single-elimination does a terrible job of picking second place, yet everyone accepts it as fair because they are used to it. In single-elimination with these terrible seedings, Clueless would have taken fifth!

If Aamira can beat either Bomb or Clueless even once before being eliminated, then Aamira has as good a claim to second place as Clueless, and there is no problem. Unfortunately, the probable scenario is, as you say, Clueless beats Aamira, Bomb beats Clueless, Bomb beats Aamira. If neither Clueless nor Aamira can beat Bomb, but Clueless is 2-0 against Aamira, then Clueless is clearly the second-strongest bot.

If second place were inferred directly from the results and awarded contrary to the order of elimination, then there would be no problem, but unfortunately second place is implicitly defined by order of elimination. Although it isn't explicitly stated who takes second, it would bend the rules just as much to not give second place to the last bot eliminated as it would bend the rules to change the order of the games. Playing the ball as it lies will probably mean that the second-strongest tournament performance will be awarded third place.

Therefore I stand by advocating for changing the order of the games. Bomb and Aamira should play in round six, and if Bomb wins, Clueless and Aamira can play an elimination match for second place. I am not advocating this just because it happens to avoid a problem in this tourament scenario, but also because it is the way pairings should work always. Indeed, it is the way I originally advocated the pairings work when I first proposed Floating Triple Elimination. Avoiding repeat pairings isn't a tweak to the system, it is part of the fundamental philosophy.

Title: Re: Floating Elimination Pairing Algorithm
Post by Ryan_Cable on Jan 24^th, 2006, 1:10pm

on 01/24/06 at 08:20:30, Fritzlein wrote:

If second place were inferred directly from the results and awarded contrary to the order of elimination, then there would be no problem, but unfortunately second place is implicitly defined by order of elimination. Although it isn't explicitly stated who takes second, it would bend the rules just as much to not give second place to the last bot eliminated as it would bend the rules to change the order of the games. Playing the ball as it lies will probably mean that the second-strongest tournament performance will be awarded third place.

Yes, I meant only to note that these two ways of bending the rules are functionally equivalent, not to say that one was better than the other or to advocate either. Also, I was trying to make the point that if we want to bend the rules, we only need to rearrange the order of the games on paper; they don’t really have to be rearranged in actual spacetime.

Personally, I think that when the letter of the rules gives second place to Aamira without more than very minor ambiguity, it is improper to give second place to Clueless, despite the fact that Clueless manifestly outperformed Aamira in the CC, and despite the fact that the pairing algorithm written in the rules did not perform to the spirit of its design. Still, this is only my opinion; it is Don Dailey’s opinion that matters.

In keeping with the spirit of sportsmanship that people showed in the WC (such as when people technically forfeited by being late for games), it is my hope that some compromise can be reached between the owners of these bots, so that second prize is not simply awarded by a ruling. While Clueless scored two crushing wins against Aamira in the tournament, the overall record is 7-4 in favor of Aamira, so maybe a tiebreaker game would be acceptable to both sides. Just throwing the idea out there.