Arimaa Forum - Print Page


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

        Arimaa >> Events >> Floating Tuple Elimination pairing algorithm
        
(Message started by: aaaa on Oct 28^th, 2009, 6:45pm)

Title: Floating Tuple Elimination pairing algorithm
Post by aaaa on Oct 28^th, 2009, 6:45pm

The phrase "Pair players with a similar number of losses against each other." is vague. Would it make sense to replace this constraint with a greedily minimizing approach like the one concerning repeated pairings, i.e. "Minimize the number of pairings where the number of losses differ by N, etc.", or does the algorithm already do this?

If such a change were to be made, should the constraint of giving a bye to the highest-seeded player then still have a higher priority than this? I'm not sure about this. On the one hand, lowering it would contribute to dampening the effects of seeding. On the other hand, a bye is a considerable windfall to bestow to someone constrained by a global consideration that already has a low priority of its own.

It's been pointed out that maximizing the sum of the squares of the differences in rank among remaining players is flawed insofar as one should not want to try to effect assumed differences in strength amongst players if they have a different number of losses. One would then actually want to protect those with more losses at the expense of those with less. However, to simply minimize the sum of the squares of the differences in seeding between these players would not take into account the possibility of one player both being seeded higher than another player whilst also having more losses. These scores actually cancel each other out for the purpose of having the algorithm make assumptions about the difference in strength between two players. My proposal is therefore to replace constraint 11 with something like the following:
"Based on a ranking of the remaining players primarily by least number of losses and secondarily by seed, maximize the sum of the squares of the differences in rank among paired players with equal losses minus the sum of the squares of the differences in rank among paired players with different losses."
This would also make the algorithm biased towards scheduling appropriate pairings for players with higher differences in losses compared to those with lower ones.

I would also propose that the color assignment used by the Continuous Tournament is applied in both championships and for their entire durations, i.e. including during the Swiss preliminary part of the human championship and any possible tiebreaker games, and that the pairing history carries over between the phases.

Since both championships make use of the same algorithm, only differing by how the players are seeded and the number of lives given to them at the start, I would suggest creating a separate (possibly parameterizable template) page on the wiki that is referenced by (or transcluded in) the pages about the respective championships.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by Fritzlein on Oct 31^st, 2009, 12:51pm

on 10/28/09 at 18:45:32, aaaa wrote:

I think it would make the most sense to have a strict hierarchy as you suggest, e.g. any number of one-loss-difference pairings would be preferable to even one two-loss-difference pairing. If I remember correctly, what is in place now is a factor for the square of the difference in losses, so that four one-loss-difference pairings would be equivalent to one two-loss-difference pairing. In a tournament with only eight players, like the Computer Championship, I believe there will never be a disparity between what is implemented and the strict hierarchy.

Quote:

If such a change were to be made, should the constraint of giving a bye to the highest-seeded player then still have a higher priority than this?

My intuition on who should get the bye changed due to the 2006 Computer Championship. Check out this post by Ryan Cable (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=events;action=display;num=1249654740;start=13#13) explaining how assigning a bye can give one player a path to victory with two fewer wins over-the-board than another player has.

Swiss chess tournaments try to minimize the disruption of byes by giving them to the lowest player in the standings. The theory is that the standings at the top, where it matters, will be least affected by assigning byes in this way. For floating multiple elimination, in contrast, all players who are not in contention have already been eliminated. There is no non-disruptive way to assign a bye. Because of Ryan's argument, I would be opposed to flipping criteria 8 and 10, thereby potentially giving a bye to someone with more losses. I guess we agree on that.

You entertain the notion of flipping criteria 9 and 10, thereby potentially giving a bye to someone with equal losses but lower seeding, seems less critical, but I still lean toward respecting the seeding first, especially now that we have a better method of seeding the Computer Championships. However, I wouldn't complain too much if we switch the priorities of 9 and 10, because it is also a fairness issue to have fewer players playing across score boundaries.

Quote:

It's been pointed out that maximizing the sum of the squares of the differences in rank among remaining players is flawed insofar as one should not want to try to effect assumed differences in strength amongst players if they have a different number of losses.

Yes.

Quote:

"Based on a ranking of the remaining players primarily by least number of losses and secondarily by seed, maximize the sum of the squares of the differences in rank among paired players with equal losses minus the sum of the squares of the differences in rank among paired players with different losses."

I agree. I'm not sure how easy it is to change the implementation to make that happen, though.

Quote:

I would also propose that the color assignment used by the Continuous Tournament is applied in both championships and for their entire durations, i.e. including during the Swiss preliminary part of the human championship and any possible tiebreaker games, and that the pairing history carries over between the phases.

I agree with this as well, but at a much lower priority. Most of the color assignments will be the same both ways, and color is not that important anyway.

Quote:

I would suggest creating a separate (possibly parameterizable template) page on the wiki that is referenced by (or transcluded in) the pages about the respective championships.

I am not sure what your final suggestion means.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by Fritzlein on Oct 31^st, 2009, 1:45pm

Re-reading the thread from 2006 that I linked above made me realize I am no longer so skeptical of Fotland's proposal:

on 01/28/06 at 00:42:47, fotland wrote:

Why not combine round robin with triple elimination? Do a single round robin, then eliminate all bots with 3 or more losses, then another single round robin, then another elimination of all with 3 or more losses (total), etc. This eliminates the problem with assigning byes, and still lets you spend more playing time with the stronger bots playing.

I pointed out that it could take more games:

on 01/28/06 at 10:56:15, Fritzlein wrote:

Already with 8 bots, however, there would start to be a significant number of extra games. FTE with 8 takes 21 to 23 games, but shrinking round robin triple elimination (SSRTE) will take 28 games even if a miracle decides things in the first round robin, and more likely will take 32 or more games, for an increase of 50% over FTE.

However, the 2009 Computer Championship was held up in large part due to technical difficulties. When there is a game that has to be invalidated, the next round of FTE can't proceed until the game has been replayed, because the result of each game affects the future pairing.

For a single round-robin of the eight players, it is true that 28 games are required, but all 28 can be played back-to-back without replaying any invalidated games. If there is a situation that requires a ruling from the TD, who is not available, no problem, just go on and play the next game. The only time resolving an issue becomes a hangup is before the second round begins (i.e. when all bots with three losses are eliminated, and a new round-robin is started among the survivors, with losses carried forward.) So having those extra games might not slow things down at all.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Oct 31^st, 2009, 7:21pm

on 10/31/09 at 12:51:41, Fritzlein wrote:

I am not sure what your final suggestion means

In MediaWiki, templates can be used to generate dynamic content. I guess what I was proposing was a bit too fancy of a solution to prevent multiple descriptions of the pairing algorithm from becoming desynchronized if changes are made to it. Maintaining a separate, referenced page on the algorithm should be good enough.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Nov 3^rd, 2009, 11:04pm

Constraint 11 is also ambiguous in that it doesn't make clear whether for the purpose of calculation, players are reassigned collapsed ranks after any elimination has taken place.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by Fritzlein on Nov 5^th, 2009, 12:42pm

on 11/03/09 at 23:04:04, aaaa wrote:

Constraint 11 is also ambiguous in that it doesn't make clear whether for the purpose of calculation, players are reassigned collapsed ranks after any elimination has taken place.

On that score, I have never known what the code does.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Nov 5^th, 2009, 11:50pm

I've coded my own implementation of the modified algorithm and discovered that there would still be some leeway in round 4 of the previous Computer Championship with the following alternative pairing:

GnoBot	Badger
OpFor	Bomb
Zombie	Sharp

Do we need additional constraints or are we humans also indifferent between that pairing and the one that was chosen?:

GnoBot	Bomb
OpFor	Sharp
Badger	Zombie

Title: Re: Floating Tuple Elimination pairing algorithm
Post by Fritzlein on Nov 8^th, 2009, 11:12am

Interesting case. Since there are no repeat matches, the bye is clearly determined, and there is one mismatch of record in each case, we fall to criterion #11, based on the ranks of the players. I agree with your suggestion that differences in rank between bots with unequal losses should count against a pairing, while differences in rank between bots with equal losses should count for a pairing. But that still raises the question of how the players should be ranked.

If the ranking is by record first and pre-tournament rating second, the ranking going into round four was

GnoBot
Bomb
Badger
OpFor
Zombie
Sharp

Then the pairings score

GnoBot Badger +4
OpFor Bomb -4
Zombie Sharp +1

GnoBot Bomb +1
OpFor Sharp +4
Badger Zombie -4

Both have a net score of +1 for rank difference, so I guess I am indifferent. But the ranking of the bots before round 4 could be done better Swiss style, i.e. by record first, strength of schedule second, and pre-tournament rating third. Then the ranking before round 4 would be

Bomb
GnoBot
Badger
OpFor
Sharp
Zombie

which leads to the pairings scoring

GnoBot Badger +1
OpFor Bomb -9
Zombie Sharp +1

GnoBot Bomb +1
OpFor Sharp +1
Badger Zombie -9

Again the pairings are equal. So apparently I am indifferent again!

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Nov 9^th, 2009, 2:22am

There would have been 3 different ways to schedule round 4 of the 2007 human championship:

Fritzlein	chessandgo
99of9	IdahoEv

And either:

robinson	Brendan
PMertens	omar
jdb	Chegorimaa

Or:

robinson	Chegorimaa
PMertens	jdb
omar	Brendan

Or:

robinson	PMertens
omar	Brendan
jdb	Chegorimaa

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Nov 10^th, 2009, 7:53pm

on 10/28/09 at 18:45:32, aaaa wrote:

I am not sure if it does or not. But the code is here if you want to dig for the answer:

http://arimaa.com/arimaa/wc/2010/floatDoubleElim

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Nov 11^th, 2009, 6:50am

It's good that Fritzlein brought up the issue of rank differences between players with different number of losses because it's not just an academic point. Take a look at round 2 of the 2008 computer championship (ignoring colors):

OpFor	Zombie
Bomb	Loc
Clueless	Sharp

The lopsided pairing between Bomb (no loss, seeded 2nd) and Loc (1 loss, seeded 4th) wouldn't have happened under the proposed modified rules, although there would still have been two different possibilities:

OpFor	Zombie
Bomb	Clueless
Loc	Sharp

Or:

OpFor	Clueless
Bomb	Sharp
Loc	Zombie

After the championship, some disappointment was expressed over the fact that Sharp edged out OpFor for a place in the Challenge preliminaries. Who knows whether any of these alternative schedules would have better allowed OpFor to make a comeback after the rough start it had?

I have been able to make my implementation schedule a second round of a championship with 25 participants in a few minutes (for the (otherwise trivial) first round it already takes more than half an hour to schedule one with just 20 players). It's definitely not too late yet to adopt any suggested improvements regarding the floating tuple elimination rules for the upcoming championships, let alone ones concerning colors.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by Fritzlein on Nov 11^th, 2009, 4:13pm

on 11/11/09 at 06:50:10, aaaa wrote:

It's definitely not too late yet to adopt any suggested improvements regarding the floating tuple elimination rules for the upcoming championships, let alone ones concerning colors.

Would Omar (as tournament coordinator) be able to run your pairing code on his server?

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Nov 14^th, 2009, 7:40am

I don't see why not. I'd have to know the interface of course.

I also wonder whether it's preferred to have the algorithm return any equally preferred schedule with equal probability or that it should be deterministic in its own unspecified way.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Dec 6^th, 2009, 9:59pm

I have put up 3 C++ files on the wiki, one of which is a header file, colors.hpp, included by the other two.

Compiling colors.cpp will create an executable which will take any number of files as argument. All but the last are interpreted as containing past games, with each non-empty line consisting of the names of the players playing gold and silver respectively, separated by alternative whitespace. The last file should be in a similar format, supplying the names of the players in upcoming games whose colors are to be assigned. Color history will continue to be updated in the last file, so it's fine to schedule players more than once in it.

With fte.cpp, it's all but the last three arguments that are interpreted as past pre-elimination games (so that we can have the Swiss tournament games contribute to the color history). The third-to-last argument takes the number of lives each player starts out with before being eliminated. The second-to-last argument takes a file name containing the names of the qualified players separated by (any kind of) whitespace ordered from best-seeded to worst. Finally, the last argument takes the name of a file containing earlier games that were part of the elimination tournament (which must exist as an empty file if there hasn't been any games yet). It should be in the same game format, only with the addition of the name of the winner of the game as the third "word". It's OK for it to be present in the other mentioned contexts, where it's simply ignored.

In both cases, the output should speak for itself: gold player, then silver player. If anyone gets a bye, that player's name will appear alone in a line.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Dec 7^th, 2009, 12:39am

Thanks for providing this aaaa. I think I can write a wrapper around this to interface it with the new tournament management tool.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Dec 7^th, 2009, 6:52am

Quote:

With fte.cpp, ... the last argument takes the name of a file containing earlier games that were part of the elimination tournament (which must exist as an empty file if there hasn't been any games yet).

Should the order of the games in this file be such that games from the most recent round are at the top; or should those games be at the bottom?

Same question for the past games file for colors.cpp.

Did some tests and it looks like the more recent games should be at the bottom.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Dec 7^th, 2009, 10:16am

Yes, in both applications all game files are interpreted as being in chronological order, which makes it congruous with the order in which the files are taken as arguments.

Hopefully you didn't take the code before I made that correction shortly after the upload.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Dec 7^th, 2009, 5:36pm

I downloaded the code this morning.

For the file that is the last argument to Fte.cpp how do you specify a bye.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Dec 7^th, 2009, 6:40pm

No mention of byes in earlier rounds is necessary; the algorithm looks at the number of times each player has played so far.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Dec 8^th, 2009, 8:28am

Thanks. I think I've got it working now with the tournament management tool. I simulated last years WC tournament. Here is the output:

http://arimaa.com/arimaa/events/showGames.cgi?e=aaaa1

In round 6 which is the first round when your program is invoked, it seems to be doing a fold pairing where as the pairing program we actually used did a slide pairing. It did a good job of preserving the color assignment from the swiss. Looks pretty good to me. Let me know if you notice any problems. If you want to experiment with it let me know and I'll set you up with an account.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by omar on Dec 8^th, 2009, 9:04am

Here is a simulation of the 2009 computer championship.

http://arimaa.com/arimaa/events/showGames.cgi?e=aaaa2

The pairing is the same (not considering color) up to round 3 and then it differs.

Title: Re: Floating Tuple Elimination pairing algorithm
Post by aaaa on Dec 8^th, 2009, 7:35pm

on 12/08/09 at 08:28:00, omar wrote:

In round 6 which is the first round when your program is invoked, it seems to be doing a fold pairing where as the pairing program we actually used did a slide pairing.

The already existing preference to maximize the sum of the squares of differences in rank in the current floating tuple elimination algorithm invariably implies a preference for a folding scheduling (where not overruled by higher priorities).