This 'article' provides an overview of my thoughts so far on providing an implementation for the WUDC Draw Rules. It is not meant as a full description of either those thoughts, or the resulting algorithm, but rather as (1) enough evidence to support the claim that Tabbie's algorithm is currently the world's best and (2) enough stepping stones for further development of better algorithms. The expected level of the reader is high - i.e. Software Developer or Algorithm Developer.
Correctness
The definition of correctness is given in the WUDC rules sections 3a - 3g (3h is simply a reiteration) and will not be repeated here.
An automatic check for correctness is part of Tabbie. This check follows the definition given here and can be inspected at validate_debates_in_brackets and create_brackets.
Trivial Correct Implementation
In fact, any algorithm that is correct under this definition and does not take into account anything other than the amount of points a team has scored so far and the positions this team has taken can be used at a WUDC-rules tournament.
Such an algorithm can easily be found, for example by taking all teams, ordering them by number of points so far, and them placing them into debates without paying any regard to the position they are taking. This algorithm is included in Tabbie (but not used) and can be inspected in the Subversion Repository.
Scoring
To define a 'good' allocation of teams to positions, and to be able to compare different correct solutions to the draw, we need some form of scoring the solutions. The scoring algorithm used has the following properties:
1. The more unequal the distribution of positions, the higher the score.
2. The differences between increasingly unequal distributions increase, i.e. it is more worthwhile to fix a grave problem than a small one.
I have found a function that satisfies these two properties and imported it as a map into PHP. The various scores can be inspected in the code
Calculation of a score using the above calculation, are run by Tabbie after the draw has been calculated. The user is notified of the score and warned if any algorithm does not provide a correct solution. The score calculation can be verified at debates_badness.
Further Demands to a good Algorithm
Furthermore, any algorithm that makes its way into Tabbie as a WUDC algorithm should have the following property: though it's results must be random, they must yield the same results for every created draw. (This can be achieved by using semi-randomness and a fixed seed) This is important for two reasons. Firstly, this makes sure that no one can temper with the draw by trying another draw for the same round to benefit certain teams or for other reasons. Secondly, only if the algorithm yields the same result every time can it be meaningfully compared to other algorithms.
General Observations
An algorithm that considers all possible distributions of teams over positions may easily take exponential time. This is because, as long as pools are connected by pull ups, any change at any place may influence all other teams.
If brackets / pools have a clean break (i.e. there is no pull up), the two halves above and below this break may be calculated seperately. This can drastically decrease execution times.
Some things can be ignored. It doesn't matter for a (algorithm's) score in which debate on a particular level/bracket a team is located. The problem can therefor be reduced to a number of openings for "Opening Government", etc. on a certain bracket.
It's not interesting to consider the position's names ("Opening Government", etc.). These can simply be referred to as "0", "1", "2" and "3".
The Silver Line Algorithm
The Silver Line Algorithm is the best known implementation worldwide of an algorithm that computes the draw within reasonable time. In fact, the only other implementations I know are the Cragie Tab (which does not take all options into account as will be demonstrated below) and the Tournaman system (which has closed source code). I'm open for debate on this claim, but will leave it here as long as it goes uncontested.
The most recent version of the algorithm's source code can be always be found in the subversion repository, or simply by downloading Tabbie and opening the relevant files.
Implementation
The Algorithm starts with the above trivial implementation that provides a correct, but not optimal solution. After this, Silver Line "just keeps swapping" teams that can be swapped. Teams that can be swapped have either:
* The same number of points
* Are in a debate of the same level (bracket/pool)
If such a swap improves the overall score it will be executed. If there are no more swaps that directly improve the score, the algorithm terminates. Siler Line never terminates if there is a better solution available by swapping just two teams. The proof of this is left as an exercise to the reader.
Limitations
Silver Line can (though not easily and not often) get stuck in a local optimum. This occurs when no swap of two teams actually directly benefits the score, and the algorithm terminates. However, it is thinkable that swapping one team with another would allow for another swap that does increase the score. (This of course applies recursively).
Copyright Klaas van Schelven, GPL 2.0.
