Pairing Theory and tsh

Some background on how pairing systems work.

Updated 2014-05-26T12:00:00+05 for tsh 3.330.

This section discusses the theory behind scheduling pairings for tournaments and the details of the pairing systems implemented in tsh. See elsewhere the table of tsh’s pairing commands, and the discussion of how and when to use them.

Goals

The following are desirable properties of a pairing system. It is impossible to satisfy all of these properties simultaneously.

PropertyDescription
“Aristomachy” Top players should be paired with each other, especially toward the end of the tournament. King-of-the-Hill pairings do this best, Round Robin pairings do this worst.
Division Sizing Some pairing systems (notably round robin) require specific numbers of players. The number of players is usually not under the director’s control, though often their assignment to divisions is. A small number of large divisions permits smaller number of larger prizes but requires players to face opponents of more widely ranging ratings.
“Exagony” Players travelling together to a tournament do not like to play each other, as many players travel to vary their opponents. At the World Championships, unnecessarily pairing together players from the same country may make it difficult for them to earn an additional place at the next WSC.
Fairness The final ranking of players by the customary win-loss record and cumulative spread should be equivalent to a ranking according to their level of performance in the tournament. Three possible ways of measuring the latter are to average the final rankings of the opponents of each player (Average Opponent Ranking or AOR, to add the number of wins and spread of the opponents of each players (Sum of Opponent Scores, SOS or Buchholz), and uninitialised iterated performance ratings (IPR, the ratings that players would have if they had all arrived at the tournament unrated).
Implementability A good human director can pair 50–100 players by hand if a dynamic pairing system is not too computationally demanding. Computers can currently do brute-force exhaustive searches for optimal pairings up to groups of about 16 (for which there are 2,027,025 possible pairings), use smarter algorithms for very difficult pairing situations involving twice as many players, and can easily apply complex rules to larger groups to find pairings which match well-designed criteria.
Incentivization A player should not be placed in a position where tieing or losing is strategically preferably to winning. For example, a player who has clinched a place in a two-player final should not be paired with a possibly weak player whose victory would send him to the finals.
Inclusivity A player should not needlessly be excluded from contention for a prize by being paired with someone who is out of contention. For example, if with one round left to play the top three players have N, N and N–1 wins and the top two have a 500-point spread advantage over #3, then #3 needs to play #1 or #2 in order to have any reasonable chance of finishing first.
“Monagony” Players should play each other as few times as possible. Repeat pairings can prevent other players from catching up to the repeaters, and do not accurately measure the repeating players’ ability to defeat a wider field. Players also do not in general like playing each other in consecutive rounds.
Monotony A lower-ranked player should not be paired so as to make it more likely that he will become the overall winner than that a higher-ranked player will.
Suspense The outcome of the tournament should be determined as late as possible.

Gibsonization

David Gibson, the all-time top money winner in the history of Scrabble, has made a habit of clinching victory in major events without waiting for the final round. Because of this, players are said to be “Gibsonized” when after clinching, they are paired with lower-ranked players to avoid affecting the ranking of runners-up. tsh has two mechanisms for detecting Gibson situations.

The Chew pairing system automatically detects and assign Gibson pairings. Gibson situations are detected based on wins and generalised NASPA spread thresholds (a player may hope to win one game by 250 points, two games by an average of 175 points, and more games by an average of 150 points each, or as overridden by the “gibson_spread” configuration option). If there is more than one Gibson, as many of them as possible (all of them if the total number is even) are paired with each other KOTH minimizing rematches and consecutive rematches. If all players are still in contention for some sort of prize, it will pair any remaining Gibson with the lowest ranked player who has played him/her least often. If some players are out of contention for any prize, it will pair any remaining Gibson with the highest ranked such player who has played him/her least often.

If you specify “config gibson = 1” in your configuration file, tsh will also perform Gibsonization when using KOTH or Swiss pairings.

It is important to note that if you are using Fontes pairings, a Gibson situation may develop in round n, paired based on round n–2, as a result of games played in round n–1. tsh does not currently check for this situation, and in practice the players involved might already even have started playing round n before anyone notices what has happened. If you do find yourself in this situation, try to manually repair the top few boards, if they have not already started their games. If no one has started a game, use the UnPairRound command to remove your previously calculated pairings, use the PAIR command to manually pair the Gibson with a reasonable victim, then recompute the pairings for the rest of the division.

Pairing Systems

tsh currently supports the following pairing systems, in order of increasing sophistication. If you have a need for a different pairing system, please contact John Chew at least two months in advance of your tournament.

No Pairings

Although tsh began as a program for generating pairings and reports, it can also be used at events like crossword or Sudoku tournaments, where players compete separately to attain individual scores. If you specify “config pairing_system = 'none', all players effectively receive unscored byes, and after you enter their scores you can view standings reports.

Random Pairings

Random pairings match players based on a statistical hashing function of their name and player number. They are random in that who plays whom will not appear to follow any pattern, but only pseudorandom in the sense that if you do not change the names and order of your players the pairings will always be generated the same way.

You might want to use random pairings when assigning first-round pairings for a group of players who do not have a reliable past tournament record.

The general command for random pairings in tsh is “randompair repeats based-on-round division”. For example, to ask for random pairings with no repeats allowed, based on standings in round 7 for division D, use the command “rp 0 7 d”. This example is somewhat contrived though, as after the first round it would be foolish to use random pairings rather than some sort of standings-based pairings.

See also the “config initial_exagony” configuration variable for avoiding pairing players from the same team in the first round. If you use this variable and do not assign players to teams, pairings will fail because everyone will appear to belong to the same unnamed team.

As it does with other pairing commands, tsh will try to minimize repeats and avoid successive repeats where possible, though in the first round this is irrelevant.

Manual Pairings

Sometimes, you can’t use a computer to do all your pairings. For theatrical purposes you might have the first round’s pairings be done by a physical draw. You might need to tweak computer pairings because someone has taken ill after you’ve computed your pairings and some people have started to play. You might want to manually pair a few players and allow the rest to be automatically paired. Or something really weird and unexpected might have happened.

tsh provides two commands for manual pairings. If you’re just doing a few, then use “PAIR p1 p2 round division”. For example, “pair 1 2 5 a” pairs players 1 and 2 in round 5 in Division A. To assign a player a bye, pair them against the fictitious player 0.

If you need to do a lot of pairings, use the “PairMany round division” command. For example, “pm 3 b” lets you enter pairings for round 3, division B and prompts you to enter pairs of player numbers, one pair per line. If you enter a division name by itself, you will switch to entering pairings for that division. If you enter a round number preceded by an R and a space, e.g. “r 5” you will switch to entering pairings for that round. If you enter anything else, you will return to the main prompt.

You cannot assign pairings for a round until all previous pairings for both players have been assigned, and tsh will stop you if you try. You can reassign pairings for players who have already recorded scores, but should do so only with extreme caution, and you will likely need to use the “EditScores” or “DELETEscore” command. Use the “ShowPairings” command to check your pairings after any manual changes, to make sure that all players are paired and none are multiply paired (tsh will warn you of either situation).

If you want to pair partially manually and partially automatically, remember that tsh invokes its automatic and default pairing mechanisms when you use the “ShowPairings” command. Specify any manual pairings before using that command. If you forget and do a “ShowPairings” first, then use the “UnPairRound” command to un-pair all of the last round’s pairings from a division.

King-of-the-Hill Pairings

In King-of-the-Hill (KOTH) pairings, the top two players are paired with each other, then the next two, and so on.

KOTH pairings are often used in the final round(s) of a tournament to ensure that contenders face each other, often with an extra repeat permitted so that contenders face each other again even when they have already played each other.

The general command for KOTH pairings in tsh is “koth repeats based-on-round division”. For example, to ask for KOTH with one repeat allowed, based on standings in round 11 for division B, use the command “koth 1 11 b”.

If the players who are supposed to play each other have already played each other too often, tsh will look for the nearest available player, breaking ties to avoid consecutive repeats, match starts with replies and minimize repeats. If the number of players is odd, tsh will assign a bye to the lowest-ranked player who has had the fewest byes.

Quartile Pairings

Quartile pairings pair the top quartile of the field at random against a designated other quartile, and are typically used to begin large tournaments with unreliable rating data, such as the World Scrabble Championship.

The general command for quartile pairings in tsh is “PairQuartiles quartile repeats based-on-round division”. For example, to ask for the top quartile to be paired with the bottom, with no repeats allowed, based on standings in round 12 for division B, use the command “pq 4 0 12 b”.

Factored Pairings

Factored Pairings (FP) are the same as KOTH except that the optimum rank separation of players is some fixed number (the factor) greater than the value of one used in KOTH.

A version of FP is used in the (US) NSC in preliminary rounds, with factors gradually decreasing from 20 to 2, to artificially control the rate at which the contender pool shrinks. (At the NSC, pairing is done in groups of four to eight players, three or four rounds at a time.)

The general command for FP in tsh is “FactorPair distance repeats based-on-round division”. For example, to ask for FP(2) with no repeats allowed, based on standings in round 14 for division C, use the command “fp 2 0 14 c”. The “Pair1324” command is a synonym for “fp 2”.

If the players who are supposed to play each other have already played each other too often, tsh will look for the nearest available player(s) to the optimum opponent(s), breaking ties to avoid consecutive repeats, match starts with replies and minimize repeats. If the number of players is odd, tsh will assign a bye to the lowest-ranked player who has had the fewest byes.

Round Robin Pairings

In Round Robin (RR) pairings, every player plays every other player once.

RR pairings are used when the number of players is no more than one more than the number of rounds scheduled. If the number of players is a little less than that number, than the remaining rounds are often paired KOTH. While RR pairings are fair and give each player the widest possible field of opponents, if the skill levels of the players vary greatly then it may be more fair to use a more flexible system that will allow the top contenders to play each other more than once. It is also difficult but not always impossible to schedule an RR so that contenders face each other in the final round.

Where the number of rounds is much larger than the number of players, RR pairings can be repeated, either with players playing the same opponent consecutively, or interleaved (where one RR is completed before the next one begins).

The general command for RR pairings in tsh is “rr n division”. For example, to ask for a double set of RR pairings to be added to division A, use the command “rr 2 a”. If you leave out the number “n”, a single set of RR pairings will be added. If you want to override the default ordering of round robin rounds, use “config random_rr_order = 1” or “config round_robin_order = [2,3,4,5,6,7,8,9,10]”. If you want interleaved RR pairings, use “config interleave_rr = 1”.

There is also a specialized command for doing partial round robin pairings for use at Cambridge ON. Use the “camp division” command to add fixed pairings for a seven-round tournament with any number of players.

If you want to assign round robin groups to noncontenders toward the end of your tournament, you can use the “LowerRoundrobins starting-rank rounds division” command. For example, if you want players to play three-round round robins in groups of four if they are ranked 41st or below in Division B, use the command “lrr 41 3 b”. It is a better idea however to use Fontes pairings (either Swiss or Chew) instead, because they will not cause any greater delay in the running of your event, and they do not involve using as stale results.

In fact, if you want to assign round robins throughout the entire field (subject to the caveat in the preceding paragraph explaining why it is a bad idea to do so), you can use the the “LowerRoundRobins starting-rank rounds division” command with starting-rank 1. For example, if you want everyone in Division C to play five-round round robins in groups of six, use the command “lrr 1 5 b”.

If you have an even number of teams of equal size, and you would like each player to play every player on every other team you can use the “teamroundrobin repeats division” command. For example, if you want the teams in division C to play each other twice, use the command “trr 2 c”. If you want to do something like “LowerRoundRobins” for teams, see the “TeamMultipleRoundRobin” command.

Bracket Pairings

Bracket pairings match players in a single-elimination format, with players out of contention playing KOTH. They can be tuned using the configuration options “bracket_order, “bracket_prelims and “bracket_repeats.

There is a manual command “BRACKetpair” that implements the pairing system, but you should never need to use it. It is available so that it can be invoked if you specify a bracket-paired event by adding the line “config pairing_system = 'bracket'” to your configuration file.

Green Pairings

John Green’s tournaments in Florida use a system which pairs groups of six to eight players over six rounds, beginning with five fixed rounds.

There is a manual command “GREEN” that implements the pairing system, but you should never need to use it. It is available so that it can be invoked if you specify a Green-paired event by adding the line “config pairing_system = 'green'” to your configuration file.

Guelph Pairings

Andy Saunders’ tournaments in Guelph, Ontario use a system which pairs groups of six, eight or ten players over six rounds.

Six-player groups play a round robin followed by KOTH with repeats.

Eight-player groups play as follows. In rounds 1–3, 1458 (A) and 2367 (B) each play a round robin. In round 4: A1–B2 B1–A2 A3–B4 A4–B3. In round 5: A1–B1 A2–B2 A3–B3 A4–B4. In round 6: KOTH with infinite repeats and Gibsonization.

Ten-player groups play a depleted five-round round robin followed by KOTH with repeats.

There is a manual command “GUELPH” that implements the pairing system, but you should never need to use it. It is available so that it can be invoked if you specify a Guelph-paired event by adding the line “config pairing_system = 'guelph'” to your configuration file.

NAST Pairings

Steve Pellinen’s North American Scrabble Tour prescribes a specific hybrid pairing system for its satellite events. For most division sizes, this consists of four fixed rounds of pairings, one swiss-paired round with repeats allowed, and one KOTH round with unlimited repeats allowed.

There is a manual command “NAST” that generates the initial fixed schedule of four or five rounds, but you should never need to use it. It is available so that it can be invoked if you specify a NAST event by adding the line “config pairing_system = 'nast'” to your configuration file.

BASD Pairings

Ira Freehof’s Big Apple Showdown has its own pairing system. Players are divided into two round robin groups in a first phase, semifinalists play each other while everyone else plays small round robins in a second phase, and finalists play each other while everyone else plays factored pairings in a third and final phase.

This is implemented using the “config pairing_system = 'basd'” configuration option, which invokes the “BASDSemi” and “BASDFinal” pairings commands.

Swiss Pairings

In Swiss pairings, players are divided into “win groups” according to how many wins they have scored. The top half of each win group plays the bottom half, in order.

Several different systems of Swiss pairings are popular in Chess, where Swiss pairings originated. Swiss pairings work well for divisions where the number of players is large and the number of rounds is small.

Regular Swiss pairings cause delays in tournaments because the pairings for the next round cannot be computed until all the results are in for the previous round. Fontes (or Portland) Swiss pairings trade off some pairings accuracy for speed by computing pairings based on the second previous round’s results. As a compromise, some directors use regular Swiss pairings immediately after session breaks and Fontes Swiss pairings at other times.

The general command for Swiss pairings in tsh is “ns repeats based-on-round division”. For example, to ask for Swiss pairings with two repeats allowed, based on standings in round 17 for division C, use the command “ns 2 17 c”.

If you ask for Swiss pairings based on round 0, tsh will rank players by pretournament rankings, breaking ties randomly. This effectively pairs the top half of the field against the bottom, which may be something you want to do even if you aren’t pairing the rest of the tournament Swiss.

There is a special command for starting a Fontes Swiss tournament. Because you will need at least two rounds of scores before you can pair Fontes Swiss, the “InitFontes number-of-rounds division” command divides players into groups of four and schedules them to play in round robins. This takes three rounds (3 is the recommended value for number-of-rounds) and provides a fair start to the Swiss system, as well as giving you three hours to get used to doing data entry before you need to worry about pairings. If the number of players is not divisible by four, there may be a group of six players who play a partial round robin. The players in each group are chosen randomly, one from each quartile (or sextile).

Early in the tournament, you should use 0 repeats. At some point in a long tournament, you should start increasing the number of repeats or else the top players will begin playing much lower-ranked players because they have already all played each other. You can try simulating the outcome of the tournament to get a feel for when this is likely to happen, use your intuition based on past similar tournaments, or keep an eye on who the top-ranked player is playing each round and decide for example once they are paired with someone out of the top ten. Most Swiss tournaments end with one or two rounds of KOTH to ensure that contenders play each other often enough.

tsh chooses an opponent within the win group who (in decreasing order of importance): minimizes repeats, is not the previous round’s opponent, is due to play first if the current player is due to play second (and vice versa, but in either case only if “config track_firsts” is active), and is as close as possible to half a win group away in ranking. For the sake of computational efficiency, tsh looks for opponents first for those players who have the fewest candidate opponents (with ties broken by current ranking). If a win group is odd, the top player in the next group is promoted to join it. If a win group cannot be paired, two more players are promoted. If the entire division cannot be paired in one big group, an error message is displayed, and you should increase the number of allowed repeats. If the number of players is odd, tsh will assign a bye to the lowest-ranked player who has had the fewest byes.

By default, tsh pairs first the top win group, then the bottom win group, then the next win group at the top, then the next win group at the bottom, and so on. This saves time, because when the bottom players have all played each other, it saves tsh having to backtrack from every possible pairing of the higher ranked players. This optimization does however come at the cost of sometimes giving suboptimal pairings for mid-ranked players, especially in small divisions. To disable the optimization, use “config top_down_swiss = 1”.

By default, tsh pairs players within a win group by trying to match each player with an opponent who will balance firsts/seconds who is closest in rank to half the size of the win group away from the player. This behaviour can be changed using the “config swiss_order” configuration option, either to pair the top half in fixed order against the bottom half, or to minimize opponent rank distance.

Chew Pairings

Chew pairings draw on Swiss pairings and the two-victor “Basic Approach” pairing system developed for the 2003 CNSC and refined at the 2004 NSC, 2005 CNSC and 2005 NSC. Tournament simulations determine which players are still in contention; the minimum number of repeats required to pair those players is computed; the contenders are split into leaders and nonleaders so as to minimize the number of leaders while not increasing the required number of repeats. Beginning at the top, each leader is paired with the lowest-ranked other leader who can catch up to him/her; the nonleaders are paired Swiss.

Chew (or similar) pairings should be used in tournaments where after a number of preliminary rounds two or more top players are selected to compete in final rounds. They are also sufficiently flexible that they may be used in any sort of tournament, and are therefore used as tsh’s default pairing algorithm. As with Swiss pairings, they may be computed based on the immediately preceding round’s standings or those of the second preceding round, depending on event scheduling.

The general command for Chew pairings in tsh is “cp based-on-round division”. For example, to ask for Chew pairings based on round 5 in division D, use the command “cp 5 d”. As explained in the discussion on default pairings, if you do not specify any pairing system, manual or automatic, tsh will use Chew pairings. You must specify “config max_rounds” and should specify “config gibson_groups”, “config initial_schedule” and “config prize_bands” when using Chew pairings.

Here is a very sketchy version of how Chew pairing works. We calculate who is still in contention for top prize money and try to pair them with each other, pairing everyone else Swiss. The number of contenders is typically capped to 8 in the antepenultimate round, 4 in the penultimate round and 2 in the last round, making the last round KOTH at the top of the field, barring Gibsonization. The contenders are divided into two groups, called the leaders and the non-leaders, if this can be done without increasing the number of repeats. The leaders are paired by pairing each top unpaired player with the lowest ranked player who can catch him; the non-leaders are paired Swiss.

For example, suppose six people are in contention in the next-to-last round. This is too many for that round, so only the top four players are paired with each other. The top four players can be paired by allowing repeats but not threepeats. They can also be split into (1,2) and (3,4) without requiring threepeats, i.e. the 1-2, 3-4 pairing does not involve threepeats. So we pair 1-2 and 3-4. If (1,2), (3,4) did require threepeats, then (1,2,3,4) would be paired together. If 4 can still catch 1, then 1-4, 2-3; else if 3 can still catch 1 then 1-3, 2-4; else 1-2, 3-4.

Here is the Chew pairing algorithm in greater detail.