Sunday, May 20, 2018

Round Robin Roundabout

In National Lampoon's European Vacation, Clark Griswold drives his family around the Lambeth Bridge roundabout for hours, unable to maneuver his car to an escape road. I tried to find an alliterative synonym for obsession, but the English language has only so many words and none seemed to fit the bill, so I went for this English landmark for a more figurative version of being stuck in a rut.

Last year, during the club championship qualifier, I looked up the round robin tables. In the past, while assisting with the organization of the chess club, I had typed the numerical pairings found in the USCF Rulebook into an Excel spreadsheet and then done search-replace operations to make pairings using the players' names instead of just their seed number. While laboring to retype a 7-player double round robin and a 16-player single round robin, Mother Necessity whispered into my ear, "This should be automated by a computer." But I could not find a website through a Google search that specifically generated the Crenshaw pairings used in chess.

So I set about writing one of my own. The reference that was most useful was Wikipedia's page on round-robin tournament. In it, the process for Standard, Berger, and Crenshaw round robin pairings is described. Using javascript, I implemented algorithms that generated these 3 types of tables. During the process, I learned many items of minutiae, which is the meat of this post. Those of you who are already bored can read this list and quit, since the remainder of this post is going to be tracing and retracing my steps on my own mental roundabout.

  • Standard round robin uses incremental rotation, while Berger rotates the field halfway around the circle. Crenshaw pairings are just Berger pairings in reverse chronological order.
  • The USCF 4-player and 6-player round robin tables are not generated by the Crenshaw algorithm. The 4-player printed in the rulebook is Standard algorithm. The origin of the 6-player table is shrouded in myth with advantages and disadvantages.
  • The reversal table is only used when the round robin has an even number of players and one player withdraws before playing half of the games. It is possible to create an algorithm to make the reversal tables as well as the pairing tables.
  • Generating the tables and the reversals helped me detect about a dozen typographical errors in the Fifth and Sixth Editions of the USCF Rulebook.
  • A man named Warren J. Porter has created his own round robin system and on his own website placed his name among Berger and Crenshaw, but Wikipedia and the USCF have yet to recognize his innovation.

The most basic way to set up a round robin uses a Standard Algorithm. Put player 1 in a stationary chair. Line up the first half of the n competitors next to him, 2 through n/2. Then come back in reverse order pairing n/2+1 against n/2 until n is facing #1. Next round, everybody rotates clockwise by 1 seat except #1, so that #1 plays n-1 and n sits next to 1 and plays against n-2. The Wikipedia article has good pictures to see this rotation. The Berger tables use a different set of iterative steps. The field is laid out like the Standard, but after round 1, the last player is held constant, while everybody rotates clockwise by n/2 seats. The Crenshaw tables, at least for n>6, are basically identical to the Berger schedule, just in reverse chronological order. In Javascript, these algorithms translate into the following statements:

var seeds = [1, 2, 3, 4, 5, 6, 7, 8];
var half = seeds.length / 2;
var rounds = seeds.length - 1;
var schedule = [];
for (var i = 0; i < rounds; i++) {
  var top = seeds.slice(0, half);
  var bottom = seeds.slice(half, seeds.length);
  bottom.reverse();
  schedule[i] = [];
  for (var j = 0; j < half; j++) {
    var pair = top[j] + "-" + bottom[j];
    schedule[i].push(pair);
  }
  //now we rotate
  var addon = seeds.splice(-1); //Standard algorithm rotates the last player...
  seeds.splice(1, 0, addon[0]); //...into the second position
  //Berger and Crenshaw rotate the field halfway around
  if ((type == "Berger") || (type == "Crenshaw")) seeds = bottom.slice(1).reverse().concat(top).concat(addon);
}
if (type == "Crenshaw") schedule.reverse();

At the end of the algorithm, the pairings will be stored in a two-dimensional array named "schedule[r][b]" where the first index refers to the zero-based round number and the second index refers to the zero-based board number.

Once I got the algorithm to work and output to a readable form, I noticed a couple discrepancies in the USCF tables for 4-player and 6-player round robins. The 4-player table is simply the Standard 4-player table. The 6-player table is weird in that seeds 1-2 meet in round 1 while they meet in the penultimate round for tables 8-24. This would seem to be a defect of the table, especially if you have seeded players into the round robin in descending rating order. However, the USCF tables also carry a not-so-useless provision that if a player drops out of an even round robin before playing 50% of the games, late-round reversals can help mitigate color imbalances.

  • The custom 6-player round robin table, unlike most round robin tables pairs seeds 1-2 in round 1 instead of the penultimate round like all the rest of the tables. This would seem to be a defect with the pairings if you have chosen to seed your players by rating order instead of by lot. However, the reversal table has all the reversals in the final round 5. When the 6-player table is generated by algorithm, some of the reversals occur as early as round 3 of 5.
  • Aside from the idiosyncrasies of the 4-player and the 6-player, the algorithm generates tables with players 8-24 with basically no error.
  • The reversal tables of the 10-player and the 14-player are sorted in such a manner that my algorithm is at a loss for matching it.
  • In the Fifth Edition USCF rulebook, on page 296, it should say, "Color reversals should be made in the last three rounds if someone withdraws before playing five games."
  • Also in 5th Ed., on page 298, the 14-player PAIRING table, round 1, board 1, should say, "7-14" as the pairing, not "7-4".
  • In 6th Ed(p 323) and 5th Ed(p 301), in the 18-player REVERSAL table, when #13 withdraws, the first pairing to reverse should be 18-1 instead of 8-1 (1-8 is a round 10 pairing). Also, when #14 withdraws, the second pairing to reverse should be 13-6 instead of 13-16 (13-16 is a round 7 pairing).
  • In 6th Ed(p 325) and 5th Ed(p 303), in 20-player REVERSAL table when #10 withdraws, the pairing to reverse should be 15-6 instead of 15-16 (15-16 is a round 9 pairing).
  • In 6th Ed(p 326) and 5th Ed(p 304), in the 22-player PAIRING table, in the 18th round, the second to last pairing should be 1-4 instead of 1-14 (1-14 is a round 8 pairing).
    • In 6th Ed(p 328) and 5th Ed(p 306), in the 24-player PAIRING table, many pairings in rounds 21-23 have typos, specifically:
    • In round 21, 10-17, 11-16, 12-15, and 13-14 instead of 0-17, 1-16, 2-15, and 3-14.
    • In round 22, the second to last pairing should be 23-3 instead of 23-2 (2-23 is a round 23 pairing).
    • In round 23, 10-15, 11-14, and 12-13 instead of 0-15, 1-14, and 2-13.

I have made a web application that produces the tables and reversals algorithmically at http://www.symbiosis.elementfx.com/projects/roundrobin2/RoundRobin.htm.

No comments: