I had in mind the latter – that’s why I said “assign colors opposite to the way they were assigned in the last pairing I made.” I’m not so concerned about maintaining precise alternation, as I am about equalizing overall.
Bill Smythe
Mike’s question got me thinking about the differences between the pairing algorithm suggested by the rulebook and an algorithm which generates all possible pairings and then evaluates each pairing. Here’s a possible implementation of the latter approach.
For the first round pair as in the rulebook. For later rounds, generate all possible pairings, ignoring color. For each generated pairing assign one player as White and the other as Black per the rulebook. In the rare cases where the color assignment isn’t automatic generate two pairings, one for each color assignment.
For each generated pairing, compute four numbers:
Number of rematches
Sum of score group differences
Sum of triple color violations
Sum of rating differences compared with the natural pairings
The highest priority is to avoid rematches. Add one to this number for each pair of opponents in the generated pairing who have already played each other. A generated pairing which has more than the minimum number of rematches is automatically eliminated from consideration. This might save some computation.
The next priority is to minimize the number of players playing outside their score group. This might take some thought, but as a first attempt, add up the absolute values of the differences in scores between players paired against each other. A generated pairing which has more than the minimum sum of score group differences is eliminated from consideration.
Among the generated pairings which haven’t been eliminated because of rematches or excessive score group differences, we will minimize the number of times a player is assigned the same color three times in a row. For each generated pairing, add up the number of players who are assigned the same color three times in a row. Eliminate any pairing which has more than the minimum number of triple color assignments. (Maybe we should do the same thing for pairings where a player gets his 4th Black in 5 games etc.)
Finally, among the generated pairings which are left, minimize the rating differences between the generated pairings and the natural pairing. The natural pairing is defined as follows:
If there are an odd number of players in the section, give a full point bye to one of the players as described in the rulebook.
Then, for each score group:
If there are an odd number of players, pair the bottom player in the score group with the top player in the next score group, ignoring rematches and colors.
Pair the top half against the bottom half, ignoring rematches and colors.
To calculate the rating difference between a generated pairing and the natural pairing:
First, find the sum of the absolute value of rating differences on each board. For example, let’s say the natural pairing includes this:
1824 vs 1535
1810 vs 1520
The generated pairing we are evaluating includes:
1824 vs 1520
The 1824 is playing an opponent 15 points lower than in the natural pairing, while the 1520 is playing an opponent 14 points higher. Per the rulebook, this is considered a 14 point difference (smaller of the two differences taken as positive numbers). Add up the ratings differences on each board.
Next, look at colors. If a player has the wrong color because of alternation, add 80 points to the ratings difference for that board. If a player has the wrong color because of equalization, add 200 points to the ratings difference for that board.
The generated pairing with the lowest sum of rating differences becomes the actual pairing.
This algorithm doesn’t conform exactly to the rulebook, so it might have to be announced as a variation. I’m not sure how useful it is since it can only be used if the number of players in each section is small (less than 20 or so). Maybe a modified version of the algorithm could be used where instead of generating all possible pairings for a section it generates all possible pairings for a score group, or a set of score groups to allow for problems in choosing the odd man.
For example, given these natural pairings and color histories:
1824 W vs 1335 W
1610 B vs 1120 B
According to the rulebook the correct pairing should be (White on the left):
1335 vs 1824
1610 vs 1120
Transposing the 1335 and the 1120 would be a 214 point switch (1824 minus 1610), and the interchange of the 1610 and the 1335 would be 275 points.
The algorithm I gave would evaluate the pairings as:
1335 vs 1824; 1610 vs 1120: 400 point difference (two players have the wrong color for equalization).
1120 vs 1824; 1610 vs 1335: 428 point difference (214 on each board)
1610 vs 1824; 1120 vs 1335: 550 point difference (275 on each board)
The best pairing is the one chosen according to the rulebook, and for the same reason: because the transposition and the interchange are both more than 200 points. It’s O.K. that the rating differences are counted twice because so are the 200 point equalization penalties. So maybe this algorithm conforms better to the rulebook than I thought.
At the 2007 U.S. Championship one (very experienced) player complained that he was assigned Black for the fourth time in five games. Supervising arbiter (note not an official TD for this event) Bill Goichberg ruled that there was no rule against a player being assigned four blacks in five games, especially when he had had back to back Whites immediately before that sequence. The player asked for our ruling in writing and was duly given it.
Alex Relyea
So the player’s color history was something like WWBBWB and the player was assigned Black? Bill G. was right that there’s nothing in the rulebook that says a player shouldn’t be assigned a fourth Black in this situation. I threw in my parenthetical comment because Bill Smythe has argued that this is a pairing which should be avoided.
I’ve thought of one way my proposed algorithm doesn’t conform to the rulebook. The algorithm makes no distinction between transpositions and interchanges, while the rulebook says that a transposition that’s within 80 points is preferable to any interchange. So maybe there should be a penalty, like 80 points, added to the rating difference for any pairing where both players are in the top half of the natural score group, or both in the bottom half.
Come to think of it, I don’t think that’s the right way to do it. The two pairings would have the same score, so you’d still be faced with the problem of choosing one of them. Instead, if two players with no color history are paired against each other, set a flag saying that the color assignment is deferred. If that pairing is chosen as the actual pairing, assign the colors randomly or using some other algorithm, such as giving the higher rated player the color opposite to the color of the higher rated player on the next higher board, or equalizing colors of the higher rated players in the score group. That situation doesn’t appear to be addressed in the rulebook, so as far as I can tell it’s “roll your own.”
Another issue is that the rulebook (29D1c) says that an unrated player should only be dropped as the odd man if the entire score group is unrated, or (implicitly) if there’s no other way to pair the score group, so there needs to be another number calculated for each generated pairing: the number of unrated players paired against a player with a lower score. I’m not sure exactly what priority this rule has. My guess is: lower priority than the total number of score group differences, and higher priority than preventing a player from getting the same color three times in a row.
One man’s problem is another man’s strength.
The “balance of power” theory of color allocation?
Some people jog…
BTW - once you had this, did you attempt the pairing in any other pairing programs?