I would not establish more limits. I would remove the current limits and fix color problems even when they involve large rating differences. Players have earned their way into their respective score groups and their pre-tournament rating can take a back seat to equitable color distribution in pairings. I would keep the principle that the smallest rating differences determine the best transpositions and interchanges. There is still use for one of the existing 80-point rules, in that a transposition that involves a rating difference of less than 80 points is preferable to an interchange even when the rating difference of the interchange is smaller.
I gave a player three consecutive blacks last night (last round):
2114 3.0 BWW
1866 2.5 xBW
1942 1.5 xWB
1957 1.0 BWB
1940 1.0 WBB
1850 1.0 WBB
(…there was one withdrawal so a house player was no longer needed, explaining how four players had black in round 3)
I think that the only relevant previous opponents are:
1850 had already played 1942 and 1957
Pairings:
1866 vs 2114
1957 vs 1942
1940 vs 1850 (finished with 3 consecutive blacks)
A contributing factor was color issues from round three that were not resolved (following current limits).
It seems, that in the Dutch System (the FIDE rules for ratings-based Swiss pairings), the rules for pairings are:
(1) no players meet more than once
(2) a player who has received a point without playing (through a full-point bye or an opponent forfeit) should not be given a bye.
(3) no player’s color difference (whites - blacks) should become greater than 2 or less than -2;
(4) no player should receive the same color three times in a row.
The FIDE rules call for transpositions of the players in the score group and then changing “down floats” so as to achieve these four goals. The algorithm is to keep trying different transpositions until a pairing is found that meets these four constraints. If there is no such transposition, then a different floater is selected, and the transposition search starts over. Eventually, constraint (4) is relaxed and all possible transpositions, then down floats, etc are tried again. If still no luck, constraint (3) is relaxed, and so forth. There is a strict order for testing transpositions, then for testing different floaters.
Basically, how transpositions work is that the “top-half” is maintained in order, and the bottom half is permuted, with a defined order for permutations of the bottom half. If none of those work, a pair of players is exchanged between the top half and the bottom half, and more transpositions based on permuting the new “bottom half” are tried, again based on a strict order.
Once a transposition/down-float is found which meets the conditions which are still unrelaxed at that point, that is the pairing. Colors are then allocated according to the color preferences of the players. If they have the same color preference, the higher ranked player gets his preference.
There are no transpositions to improve color allocation (either equalization or alternation), other than to prevent three of the same color in a row or a color difference greater than 2 or less than -2. But those color problems are considered so severe as to require players to be floated to a different score group, if that is possible and there is no way to avoid the color problem without doing so.
A curiosity of the algorithm is that once a constraint is relaxed, it is relaxed. For example, suppose you had two players with three of the same color in a row. The rules would require that you try all transpositions, etc, to fix both of these imbalances. If you cannot fix both of them, that constraint is relaxed. Now the first transposition that meets the remaining conditions is valid. You no longer pay attention to three-colors-in-a-row. There is no notion that fixing one out of two of the problems is better than fixing neither of them. Either you are trying to fix both; or you have given up on three-colors-in-a-row entirely, and are not trying to fix any three-colors-in-a-row problems.
In summary: compared to the USCF rules, the FIDE rules ignore minor color problems, but if a color problem develops into a major one (such as an color imbalance of more than 2, or failure to alternate twice in a row), it takes more drastic measures to correct it.
I hope Chris Bird or some other knowledgeable person will jump in and correct me, if I got this wrong.
This is incorrect. When working through the FIDE algorithm one of the first things you do is calculate the value of “x”.
The (FIDE) Definition of “x”
The number of pairings which can be made in a score bracket, either homogeneous or heterogeneous, not fulfilling all color preferences, is represented by the symbol x.
x can be calculated as follows:
w = number of players having a colour preference white.
b = number of players having a colour preference black.
q = number of players in the score bracket divided by 2, rounded upwards.
If b >> w then x = b-q, else x = w-q.
p is the number of pairings in the score group. 2p is number of players paired in the score group. You can also say that p is the number of players in each “half”. So making it equal to x means that there will be a “remainder” in the score group, who will therefore float down. For example, if you had eight players in a score group, but x ended up being 3, the “top-half” would be 3 players, paired against a “bottom half” of 3 players, and players 7 and 8 would be the remainder and would float down. (If this didn’t work, then other down-floaters would be tried, and eventually if nothing worked, you would reduce p to 2, 1, and finally 0.) Is this right?
What I don’t see is how the color preferences come in once you have a value for p. If you try a transposition that pairs two players with a white preference against one other, that transposition is acceptable as long as neither has a white preference greater than 2, or would have the same color three times in a row. In other words, you boot players out of the score group so that you have an equal number of players with white and black preference. In theory, at this point you could pair all the white preference guys against black preference guys, because you have an equal number of each. But that is not what the the algorithm says to do. Rather, you try the transpositions in a strictly defined order, and once you come to one that meets the four conditions I gave above, you are done with this score group. However, this might not be a transposition that pairs the black preference people against the white preference people, though because of conditions (3) and (4) above it at least will not have a pairing that results in a color imbalance > 2 or three colors in a row.
So, what am I missing?
Sorry, I was trying to keep things simple and really over-simplified things. Saying that p should equal x was totally misleading and incorrect!
Rule B4 should always be kept in mind.
B.4 As many players as possible receive their color preference.
I think what you are doing is taking a very literal reading of rule C6, which says once you have a valid pairing in terms of rules B1 and B2 then you are ok to go with it and forgetting about B4 which is not mentioned in section C.
Rule C11 allows you to increase the value of x (bad color matchups) when p>x. This means if you cannot find pairings that work by maximizing the color preferences then you are allowed to increase the number of match-ups that have a bad colors.
Here is an example of players in one scoregroup that have not played each other:
- 2600 WB
- 2500 WB
- 2400 BW
- 2300 WB
- 2200 BW
- 2100 WB
- 2000 WB
- 1900 WB
- 1800 BW
To calculate the value of x we do the following:
number of players due white (w) = 6
number of players due black (b) = 3
number of players in score bracket divided by 2, rounded upwards (q) = 5
because w>b then x=w-q, x=6-5, x=1
This means there should be one pairing that cannot meet the color preferences of both players.
The straight pairing of S1 (top half) against S2 (bottom half) is as follows:
1-5
2-6
7-3
4-8
However, this pairing gives us two bad color match-ups, 2-6 and 4-8. We should only have one bad color match-up per the value of x and so we have to make adjustments. If we transpose players 8 and 9 at the bottom of S2 then we end up with the following pairings:
1-5
2-6
7-3
4-9
This gives us one bad color match-up, 2-6, but since we know we will have one bad color match-up then we can accept this pairing.
If you didn’t find a legal pairing where you only had one bad color match-up then that is what rule C11 is for, to increase the number of bad color match-ups to find you a legal pairing within the scoregroup.
Computers are very “literal”. Section C purports to be an algorithm which you follow step by step. This algorithm directly tests that conditions B.1 a+b and B.2 a+b (which are my four conditions 1-4) are satisfied. The operation of the algorithm ensures that B.3, B.5 and B.6 will be satisfied if possible. These are the constraints related to floats, which I didn’t mention previously because we are talking about color allocation. But there is nothing in the algorithm in C which really has anything to do with B.4, which states that “as many players as possible receive their colour preference.”
The algorithm you presented where a possible pairing that is being evaluated is rejected because the number of color mismatches exceeds x makes sense, but that is not the algorithm that is described in Section C.
In the actual Section C, there is no notion of rejecting a pairing because the number of color allocation problems exceed x. C.6, which is the crucial step, says “If now p pairings are obtained in compliance with B1 and B2 the pairing of this score bracket is complete”. Nothing said about checking B4 (which would require that the number of unfulfilled color preferences be equal to “x”).
The algorithm in Section C does not actually make any sense, because it goes to all the trouble to define and compute “x”, but then does not actually use it. Later, C.11 says that if you don’t have a valid pairing, you can increase “x” by 1 (up to a maximum of “p”) and cycle back, running again through all the transpositions. What would be the point of that because the key step in C.6 of evaluating the pairing which is produced ignores condition B.4 and makes no use of “x”.
Talk about a huge hole in the algorithm! I guess nobody actually bothers to read or follow this document. Silly me for thinking it would be correct.
I actually agree with this sentiment but B4 is there and is a key part of the pairing methodology. Section C11 is another way of saying that rule B4 can be relaxed to get a valid pairing but not completely ignored until x=p.
As you can see, the FIDE swiss pairing method is actually very favorable to having as many correct color match-ups for pairings as possible, and, going back to the original topic, does so by ignoring transposition limits although remember that FIDE does have a recommended order to perform transpositions and exchanges.
I guess so; if you can say that the FIDE Swiss paring method is the method actually followed by Arbiters and FIDE pairing programs, rather than what the FIDE pairing document actually says. How do people find out the real algorithm?
Maybe you can convince FIDE to make their swiss pairing system a little clearer. Sounds like just the cause to keep you busy for a while Brian.
The only thing I can guarantee is that when I do FIDE pairings I definitely take B4 (and the value of x) into account, per my example above. My hand pairings match the FIDE pairing programs I have used practically every time. The only time they didn’t was when I missed a “better” pairing in a complicated low number of players, high number of rounds event involving people being paired way out of their score groups.
Following this algorithm, with C.6 modified to take B.4 and “x” into consideration, how would you miss a “better” pairing? You mechanically follow the steps until you get to a pairing that satisfies the conditions. It doesn’t have to be the “best” pairing. It has to be the first pairing that you encounter in the search which meets the condition. The search order is defined.
The only waffling part is in C.13 “In case of the lowest score bracket [if no pairing is found], the pairing of the penultimate score bracket is undone. Try to find another pairing in the penultimate score bracket which will allow a pairing in the lowest score bracket.” This can lead to the penultimate bracket not being pairing and having to backup to the previous group, and so forth. This “try to find another pairing” is a bit vague. Does that mean, just reject the last pairing of the penultimate group and continue with the C algorithm to the next transposition in search order? If so, with C.13 the C algorithm becomes a backtracking type of algorithm and will be exponential, which is very bad. It will take unacceptable time if the round number is high in relation to the number of players. This means that pairing software almost certainly does something different than C.13 seems to be saying if the round number is high in relation to the number of players. This may be the situation where you fail to find a “better” pairing.
It was round 9 of a 24 player event and I had already undone various pairings at the bottom because players had already played each other. I was using pairing cards and apparently got a couple of players in the wrong order in their group but still came up with a “legal” pairing. Thankfully I was doing it as an exercise to see how close I could get to the pairings given by the FIDE pairing program we were using and so it didn’t affect anything.
Anyway, back to the topic at hand. Should the USCF change it’s transposition limits?
The description of the algorithm in section C is faulty, or at least does not agree with the algorithm as taught in the FIDE Arbiter seminar I took in July, 2010. The instructor’s explanation made clear that if the number of color allocation problems exceeded “x”, the arbiter continues making transpositions to look for better pairings.
I think the pairing rules we have now are fine. They could be improved but this would be at the expense of making them more complicated and therefore make it harder for players to predict their pairings and for TDs to make pairings manually.
I would vote against a motion to replace the USCF pairing rules with the FIDE rules becuase I think the FIDE rules put too much of an emphasis on giving players their due colors. I’d go along with a rule increasing the limit for transpositions and interchanges to prevent a player from getting four of the same color within the last five rounds, but only up to 200 points, not 600 points as Bill Smythe suggested.
If I may continue the digression a bit longer, did the FIDE instructor have any comment on the fact that the algorithm takes exponential time, and that it has no provision for the case where there is no pairing that satisfies conditions B.1 and B.2. Both of these are rather serious problems. Especially, exponential time means that the algorithm if programmed on a computer (which seems to be the intention) may not complete in anything like reasonable time if you are pairing beyond, for example, 12 rounds.
Coming back to the USCF transposition limits, they are illogical and should be abolished as a useless complication and source of confusion and dispute. Consider the following situation:
1 2000 vs 3 1750
2 1900 vs 4 1000
The 200 point rule says that 3 and 4 cannot be transposed because there is 750 point difference. However, 1 and 2 can be transposed because that is only a 100 point difference, despite the fact that this is completely equivalent to transposing 3 and 4. Where is the logic in that? Moreover 2 can be interchanged with 3 because that is only a 150 point difference, but 1 and 2 cannot be interchanged because it is 1000 point difference. However these are equivalent. How is that logical?
The 200 point rule only has an effect where there is a 200 point “gap” in the ratings in both the upper half and the lower half. In a score group like this:
1 2000 5 1525
2 1900 6 1500
-gap- -gap-
3 1600 7 1200
4 1550 8 1100
there are two “gaps” between 1-5,2-6 and 3-7,4-8 and transpositions can’t cross these gaps. They are blocked on both sides. So this kind of situation is the only one where the 200 pt rule might actually have any effect. If there was a “gap” only on one side the equivalent transposition could go ahead on the other side. But how many score groups are like this? For there to be 200 point gap in both the upper half and the lower half, the score group has to have a rating range of more than 400 points. In fact in this situation, even though transpositions are blocked, interchanges are still possible: 4 and 5 can be interchanged because they are only 25 points apart, circumventing both gaps. For the 200 pt rule really to have any effect, there would have to be a third “gap” between the top half and the bottom half: three gaps in all, and at least a 600 point rating range in the score group. This is typically going to happen, if at all, only in the early rounds of a Swiss when there aren’t that many color balance problems anyway, and the score groups are large enough to resolve any color balance problems without too much trouble. If you have score groups with 600 point rating ranges in the late rounds of your Swiss, you have serious problems with your tournament design, with or without the 80 and 200 point rules.
Another oddity of these rules is that the 80 pt and 200 pt restrictions apply only on the first transposition. There can be a second transposition of the same player, and this is not subject to the 80 pt and 200 pt rules. That means that a player could be transposed once within the 200 pt limit, and then all bets are off and the pairing algorithm can do any transpositions it wants to the player, ignoring the 200 pt limit. So what was the point of these limits in the first place?
Whatever it is that these transposition limits are supposed to be achieving, they aren’t achieving it, and I can’t even see what they are trying to achieve. What is the history of these limits? They are badly thought out, illogical, and, basically, stupid.
Hello Brian,
Your gap would stop the 200-point transposition, but interchanges go a different direction and are still possible (1600<->1525, 1550<->1525, 1550<->1500 are all within the 80-point limit).
Even if there was no gap (add 250 points each to the 1100 and 1200), and if the 2000, 1900, 1600 and 1525 were the four players due white then the 1525<->1500 interchange is superior to the 1525<->1350 transposition.
I don’t know of any good TD or pairing program that would allow cascading two 125-point transpositions to essentially get a 250-point transposition unless that 250-point transposition was otherwise necessary (such as to avoid playing the same person a second time).
Could be, but that is not in the rules.
Your point about the interchanges is valid. In fact, I was editing my post to cover that case, while you were typing your post, I guess.
Transposing 1 and 2 is equivalent to transposing 3 and 4. In both cases the 2000 player will be put on board 1. It’s considered a 100 point transposition because you look at the smaller of the two rating point differences. This is a change made in the 4th edition; in the 3rd edition rules this would be considered a 750 point transposition because you’d only look at the difference in the bottom half of the score group. The logic of the 3rd edition rule is that it’s more important to give the correct opponents to players in the top half of the score group because those players are more likely to win prizes. The logic of the 4th edition rule is that the 1900 player is only 100 points below the 2000 player, so the 2000 player is almost as eligible as the 1900 player to be given the weaker opponent (1000 instead of 1750).
I assume you meant that there is a 1000 point difference between players 1 and 4. The logic is that players 2 and 3 are close enough in rating that player 2 shouldn’t automatically get the 1000-rated opponent while player 3 is doomed to play the 2000-rated top seed. It’s a 150 point interchange: the smaller of the two differences in rating.
You’ve misread the rule, Brian. It’s simply not true that “all bets are off” after the first transposition. Rule 29E5 on page 149 says:
This isn’t the same as saying that “all bets are off.”
The original limit for transpositions and interchanges was 100 points and was introduced in the 3rd edition of the USCF rulebook on the basis on a statistical analysis that was done by Professor George Cunningham. Cunningham analyzed game result to determine how big of an advantage in terms of rating points it was for a player to have white rather than black. The theory is that a switch shouldn’t be made to improve colors if this will distort the natural pairings to the point where a player due for white would be better off being paired with black against his natural opponent.
All these features have not survived into the 5th edition. If the original aim was to lock in the natural pairings except for swaps which give all four players involved in the swap an opponent similar in rating to the opponent they had with the natural pairings, we no longer have that feature in the 5th edition rules. I stick with the statement that in their current form these rules are illogical and make no sense.
Most FIDE events are not that large. With one round a day, or maybe two, and a small event the pairings can get mberworked out fairly easily. WinTD already has a setting to change the rating limits to different numbers or turn off the ratings limits and pair in FIDE style.