Wednesday, April 8, 2009

Side assignment algorithm found!

One of the most vexing problems in running a small tournament is assigning sides in odd rounds. If you assign the sides incorrectly in an odd round, there may be nothing but bad options left for the subsequent even round: break side constraints (a team is aff. rounds 3 and 4), break school constraints (force two teams from the same school to debate), or re-match two teams (two teams that have already met have to debate again).

For a round robin, there are very few possible solution in the third to last round. Say you have 8 teams, so before round 5 is paired, team A has three opponents remaining: B, C, and D. If A is assigned to the aff, then 2/3 of {B, C, and D} must be assigned to the neg side -- otherwise, it will be impossible to honor side constraints for rounds 5 and 6. This sounds easy until you realize that B, C, and D all have three opponents each remaining, 2/3 of whom must be assigned to the opposite side... There ends up being just a few ways to pair round 5 that are consistent with all side constraints and re-match constraints for round 6 too.

The complexity of this problem has lead tab programs to include a "schedule round robin" option that executes before any rounds have happened at all. Although round robins are the epitome of this problem, many small tournaments with heavy school constraints (many teams from the same school) also experience it, leading to late round pairings that violate many constraints -- and there's no option yet programmed that solves that. Even big tournaments suffer from a similar problem. Although there's no risk of a big tournament violating any constraints, there is always the question of how well mixed a tournament is. If the same group of teams always is aff in odd rounds {A, B, C, D, E...}, then there's no chance that A can debate B, B debate C, etc. The tournament is better mixed if round 1 affs are {A, B, C, D, E...} and round 3 affs are {A, C, E...} and so on. The current assumption is that randomness is sufficient to mix a tournament well, which might be true, but it's nice to have an algorithm in hand that guarantees that.

Now, you may be tempted to think that a computer program can solve this sequentially: pair round 3, then have it look ahead to round 4 and see if there are any problems. This may just work at a tiny tournament, but the number of possibilities becomes daunting quickly, before becoming downright impossible, even for a supercomputer (and I don't believe many tab rooms would want to book time on the Roadrunner supercomputer). If you set a pairing for round 3, then look at all the possible round 4 options that follow, there are (n/2)! options, where n = number of teams. For 40 teams, there are 2.43 E 18 options. The world's fastest computer, by my rough estimation, would take 37 minutes to verify that all the options for round 4 were bad. To put it in perspective, 2.43 E 18 is about how many stars we can see in the sky. There is a better way, and it's to do a clever simultaneous approach.

Here's the gist of what I found. The mixing issue and the constraints issue are actually two sides of the same coin. If in round 1 team A aff. defeats team B neg., and in round 2 team B aff. defeats C neg., then the computer should be able to reject several possible side assignments out of hand. The best mixed, least conflicted option is actually to put {A, B, C} on the aff. for round 3. A and B can't debate again, so they might as well be on the same side; ditto for B and C. The only possible round that's lost is A vs. C, but any other way to assign the sides rules out more possible rounds. A smart use of this fact enables the algorithm to quickly toss out many possible options and reduce it to a manageable number.

Does the algorithm actually work? Yes. I tested it on a regular laptop, and it will pair a round robin on the fly. Without giving the program any prior knowledge that a tournament will be a round robin, it just picks the best round each time in a few seconds -- and pairs the round robin correctly and completely. The algorithm itself is not complex, but I'll save it for this document:

No comments:

Post a Comment