| Main index | Tournaments index | About author |
Julian D. A. Wiseman, January 2007
Abstract: Twelve teams wish to play each other in an all-play-all format at six venues over eleven rounds. How can this be arranged?
Contents: Introduction; Presentations and file formats; Technical notes (permutation score; left-right asymmetry measure).
Publication history: Earlier versions of most of the designs here have previously been made available in paper form by Dr Nicholas F. J. Inglis, for the use of ETwA and CUTwC tournament organisers. This is believed to be the only publication on the web. Usual disclaimer and copyright terms apply.
i ii iii iv v vi
1 F:C L:E G:I K:D H:A B:J
2 D:E J:H K:C B:I L:F G:A
3 H:I K:F D:L A:J G:B E:C
4 G:J I:A H:B C:L E:K F:D
5 B:F C:J I:D H:E A:L K:G
6 C:G F:I A:K L:B J:E D:H
7 J:D B:K L:G F:A C:H I:E
8 K:H A:D B:E I:C F:G J:L
9 E:A H:L F:J D:G K:I C:B
10 I:L E:G C:A J:K B:D H:F
11 A:B D:C E:F G:H I:J L:K
|
Twelve teams are all to play all the others. Each team has to play eleven games, so this tournament requires at least eleven rounds. With six games happening simultaneously, there must be at least six venues. On the right can be found an example 12-player all-play-all at six venues over eleven rounds. All-play-all tournament designs are published for all numbers of players from twenty-six down to the (trivial) one: 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2 and 1.
There are ‘excess-venue’ designs (defined below) for 8 on 8, 8 on 7, 8 on 6, 8 on 5 (as well as the minimal-venue 8 on 4), 7 on 6, 7 on 5, 7 on 4 (and minimal-venue 7 on 3), 6 on 6, 6 on 5, 6 on 4 (6 on 3), and 5 on 3 (5 on 2).
Also see the complete list of all-play-all links.
The precise meaning of some of the terms can vary according to the game being played.
A “player” might actually be a pair or even a team of players. Players are labelled with upper-case roman letters: A, B, C, D, etc.
The specific meaning of the word “venue” will depend on context. In snooker or billiards, a venue refers to a particular table; in tiddlywinks (for which these tournament designs were originally devised), to a particular mat; in tennis to a court; in croquet to a lawn or to a set of balls; and in other games to a location or set of equipment as appropriate. Venues are always labelled with lower-case Roman numbers: i, ii, iii, iv, etc.
Several games happen simultaneously during a “round”. Rounds are always labelled with an Arabic numeral: 1, 2, 3, 4, etc.
A particular game might be described as “A:B”, meaning that player A is to play against player B (in a particular round and at a particular venue). However, “A:B” is not necessarily the same as “B:A”. In tiddlywinks, the left player should take the dominant corners. In chess, left should play white, and in other games in which one player starts, left starts. In card games left deals first. In general, the left player should have the advantage, but each game will have its own meaning for left and right, in a manner to be determined by the tournament organiser. To encourage consistency, tournament organisers are invited to inform this author of any conventions which may be agreed.
Each of these all-play-all tournaments is published in a number of different presentations and file formats.
Embedded in the master HTML file for each size of all-play-all is a PRE-formatted text grid, giving the description of which game takes place in each round at each venue. This is also available in a separate text file.
A similar description of the game schedule is available in PDF, with versions optimised for A4, A3 and US Letter (USL).
A score-sheet is available in PDF, again in A4, A3 and USL. Players go both horizontally and vertically; enter into each cell the score achieved by the player of that row when playing against the player of that column. Each cell shows the game description, as well as the round and venue.
A more detailed score-sheet is available in PDF (in A4, A3 and USL), with extra columns into which a player’s running total of scores may be entered. With a large number of players the extra columns can crowd the page. The running-total cells show the description of the game just played.
Both the less- and more-detailed score sheets are also available in ‘blank variants’, which don’t have the game descriptions in the cells.
Finally, each tournament is available in a machine-readable text format, with one row per game. Each row is in the form RR VV A:B, where RR is the round, VV is the venue (for ease of machine-readability exceptionally shown in ‘Arabic’ numerals rather than lower-case Roman numbers), and A:B is the game description. It is from this file that the others are generated: readers sending improved tournament designs are asked to do so in this format.
There can be many ways to set out an all-play-all tournament of any particular size. A particular one is chosen using some constraints and two optimisations.
For ≥6 players, it is constrained that no player may play two consecutive games at the same venue. A particular snooker table or tiddlywinks mat or croquet lawn will have certain foibles, and as one plays on the venue one’s shot-play will become accustomed to those foibles. So playing two consecutive games at the same venue would be an advantage, and hence this is not permitted. Note that this prohibition applies even if the two games are separated by a bye. (However, these constraints must be relaxed for the 6- and 7-player cases.)
That still leaves a lot of flexibility, in that it will typically be possible to re-arrange the rounds and the players. What is wanted is for ‘important’ games to come late in the tournament, where important games are those between the best players. So the players are seeded, with A being the best-ranked player, then B, etc, and we want games such as A:B to come late. The optimisation is then performed as follows. Assign numerical values to each player: A=0, B=1, C=2, etc. Number the rounds starting at zero, so the round numbers are one lower than in the human-readable form. If the game x:y is in round r, then calculate the permutation score as the sum over all games of ( r / (x*x+y*y) ) ^ 4, and maximise this. The maximisation is done by permuting both rows (subject to the above constraint) and permuting players. For all cases up to 12 players it is believed that the optimum has been found; beyond 12 players the design is likely to be near-optimal, but may not be the exact optimum.
Which still leaves undecided the left-right assignments. We constrain the left-right assignments, so that no player plays more than once on any given side (left or right) of any venue. (This constraint was motivated by tiddlywinks, so that no player uses any set of corners more than once.)
That does not uniquely determine the left-right assignments. So consider the position of a player in a tournament: what would be to that player’s advantage? The player is to play left and right approximately equally (in a tournament with an even number of players each plays an odd number of games, in which case there is a one game mismatch). How could these lefts and rights be distributed to maximum advantage? Clearly it’s best to have the advantage in close games, where it might make a difference. Most players will lose against the best players, whether playing left or right; and will win against the bunnies, whether playing left or right. But against similar players an advantage is most valuable. So the tournament design should ensure that this advantage is as evenly spread as possible, and we start by calculating an asymmetry measure for each player. Assign the same numerical values to each player as above. For each game x:y, add to x’s score 1/(1+|x-y|), and for each game y:x, subtract this same term. This term is of largest magnitude for close games. Total these terms for each player, and square. If a player has a fair balance of left and right in close games, and hence in non-close games, this sum will be nearly zero. If a player has a mismatch, this squared-sum will be large. Now calculate the weighted total of these squared sums, where the weight is the number of players minus that player (‘n-x’), and call this the left-right asymmetry measure. So this left-right asymmetry measure has the largest weight on A’s squared sum, as fairness is most important amongst those with a large chance of winning. Minimise the left-right asymmetry measure (subject to the above constraint that no player plays more than once on any given side of any venue). There will be two minima, one being the reverse-everything opposite of the other. Choose the minimum containing A:B rather than B:A. For all numbers of players except 17 and 24, it is believed that the actual minimum of the left-right asymmetry measure has been found. For 17 and 24 players, the proffered design is at least close to the minimum.
The excess-venue types were designed in order to speed up tournaments by reducing the number of times that a game is held up because the venue is unavailable. For example, though it is possible to devise an 8-player all-play-all at 4 venues, if there are as many as eight venues, these could be used to speed play. Such a design is here called “8 on 8”. In such designs the number of times a venue is used in two consecutive rounds is minimised. Over the range used here, this means ensuring that no venue remains idle for two consecutive rounds, as well as minimising the maximum number of consecutive rounds in which any venue is used. For example, in 7 on 4 no venue is used four times consecutively, and it is easy to see that this is the best possible. Subject to this, the number of times each player plays at each venue has been made as equal as possible. For the special case where the number of venues is one less than the number of players, it might be asked whether we can arrange it so that each player plays exactly once at each venue; such a design is called a Room Square. This is not possible if the number of players is odd, nor if the number of players is 4 or nor 6. That leaves 8, but the 8-player Room Square violates the above “no venue idle twice consecutively” constraint. Subject to this, the formats chosen have each player either once or twice at each venue; or twice at one venue, no times at another, and once at the others. For the more sparse formats, where there are lots of idle venues, there has been some attempt to maximise the minimum length of time between the two games featuring a given player at a given venue. this done, the above optimisations, to permute players and left-right, are then applied.
| Main index | Top | About author |