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.

Practical Rook Endgames 17: Cure a Vancura Amnesia

In the 1990 "Total Recall" starring Arnold Schwarzenegger, the main character encounters a video recording of himself lifting the veil on his amnesia, his real identity and the lie he was until recently living.

I was watching the St. Louis Chess Club's YouTube coverage of the 2018 U.S. Championships. In round 7, Zviad Izoria had this position with white to move against Hikaru Nakamura. Study the position and then watch 6 minutes of the broadcast from when White moves Rh8 until the game ends in a surprise.

FEN: 8/2k2K2/2P4R/2r4P/8/8/8/8 w - - 1 88

When Vancura was mentioned, I searched my memory and could only find a hazy mess despite having blogged about Vancura here and here. So I went back to a Vancura stem position with white: Ra8, Pa6, Kf4 and black: Ra1, Kg7, and this time I tried to create a more thorough treatise using the Shredder endgame tablebase and playing through plausibly interesting variations. The result of my effort is this one-page memory refreshment PDF tool of variations related to the Vancura position. It's not quite as vivid as Schwarzenegger's video recording, but this is the mnemonic device that should help stave off my next bout of Vancura amnesia. Now that I know a little more about Vancura, I'm going to comment on the commentators. Here is the blow-by-blow discussion with YouTube time indexes:

5:40:12 Maurice Ashley notices white playing 88. Rh8 dropping the c-pawn, going for an h-pawn win. Since the black king has the c-pawn blockaded, white's best chance for victory is the distant h-pawn.
5:40:16 Jennifer Shahade mentions a winning skewer trick. The Seventh Rank Skewer trick is one of the weapons in the stronger side's arsenal. It only comes into play when the weaker side tries to move his king to the pawn too early and steps on one of the two central files (d- or e-). The stronger king also tends to be out of the picture so that the skewering happens without interference. The skewer doesn't come into Izoria-Nakamura. I mentioned the skewer before in this blog post.
5:40:17 Yasser Seirawan says that the black king is so far away. In many variations, the draw or win depends upon a king race to a key Bishop-7 square. If the weaker king can stay within a knight's move of the stronger king, he can usually draw.
5:40:19 Awonder Liang on post-game interview couch suggests the position is "similar to Vancura". Similar to Vancura is as close as it gets.
5:40:27 Yasser disputes the closeness to Vancura. Awonder gives the line 88... Rxc6 89. h6 Kb7. 88... Rxc6 actually occurred. Had Izoria played 89. h6? Nakamura could have obtained a drawing Vancura with 89... Kb7!, the only move that draws! One of the reasons I find some of these endgames so fascinating is how moves can be both precise and counterintuitive at the same time. Vancura was only one move pair away from the actual game.
5:40:50 Yasser suggests 89. Re8 (build a lateral rook bridge) Building a lateral rook bridge is one technique to win. Usually, the defending rook has abandoned his order to keep the pawn under observation and is trying to get into Vancura lateral checking position.
5:40:54 Jennifer agrees 89. h6 might be the wrong move. 89. h6? is drawn with best play.
5:40:01 Yasser gives the line 89. Re8 Rh6 90. Re5 intending Kg7. The Shredder tablebase notes that 90. Re5! is the only move still winning for white.
5:41:10 Maurice adds 90. Re5 Kd6 91. Kg7 "just nails him". Yasser agrees "just nails him". Shredder says 91. Kg7? is drawn simply by 91... Kxe5! 92. Kxh6 Kf6!. The weaker king never allows the stronger king to move Kg7 or Kg8. If the stronger king does get Kg6, then he'd better be on his way to h8. e.g. 93. Kh7 Kf7 94. h6 Kf8! 95. Kg6 Kg8! and the weaker king can mindlessly play Kg8-Kh8-Kg8 until he gets stalemated. Shredder says 91. Rf5 keeps the win alive.
5:43:20 Yasser notices play continued 89. Kg7 Rc1. Jennifer starts analysis with 90. h6. 90. h6 is correct.
5:43:57 Maurice declares that "h6 is a draw." Shredder disagrees. In fact, at no point after 88. Rh8 did white let the win slip.
5:44:00 Yasser questions the draw assessment. Maurice says the black king might be close enough to draw. The black king is one tempo short of drawing.
5:44:11 Yasser extends the line 90. h6 Rg1+ 91. Kh7 Kd7 92. Rg8. The position of the stronger side's pieces is sometimes Pawn at rook 6, King at rook 7, and Rook at rook 8 while the weaker rook harasses from the knight file. The winning method often reorganizes these pieces starting with Rook to knight 8, King to knight 7 and if checked, King to rook 8 and then pawn to rook 7. It looks as if the king has castled by hand into a tight formation hugging the corner of the board. I used the moniker "Fortress of Solitude" for my mnemonic here. 92. Rg8! is the only move that wins.
5:44:29 Jennifer and Yasser agree that the black king is too far to draw. Correct.
5:45:11 Yasser comes up with the plan of Rg8, Rg6, Kg7, and queens. Black can throw a monkey wrench into this plan. Concretely, 92. Rg8! Rf1 93. Rg6? gives up a draw to 93. Ke7.
5:45:30 Maurice tries to draw with the plan 90. h6 Kd7. Yasser extends with 91. Rg8 Ke7 92. h7
5:45:44 Nakamura lets his clock run down to 2 seconds before recovering a 30-second increment. Maurice says "Nakamura's never going to flag." Never say never.
5:46:02 Maurice agrees that after 92. h7, the White King will win with a "laddering back" maneuver. With the weaker king at e7, the stronger king "ladders back" through harassing checks with Kg7-Kh6-Kg6-Kf5 and down to f2 if necessary.
5:46:20 Maurice mentions the queen versus rook ending. Jennifer asks, "Wait did you say there's a way to force queen versus rook?" Jennifer's question goes unanswered during the broadcast because of what happened next in the game. From the game continuation 90. h6 Rg1+ 91. Kh7 Kd7 92. Rg8! Rf1 93. Kg7 Rg1+ 94. Kh8 Rf1 95. h7 Ke6 96. Kg7 Rg1+ 97. Kf8 Rf1+ 98. Ke8 Rc1 99. Rg6+ Kf5 100. Rf6+ Kxf6 101. h8=Q+ Kg6 starts a complicated Queen versus Rook that is likely to become my next Endgame Obsession.
5:46:30 Nakamura flags just before playing 92... Re1. Maurice's head just about exploded when he learned that Nakamura had flagged.