Three-way transpositions

Running Chess Tournaments
1

Suppose there are six players in a score group, leading to the following “raw” (untransposed) pairings:

2120 BWB vs 1620 BWB 2010 WBW vs 1510 BWB 1900 WBW vs 1400 WBW
– but the 2010 has already played the 1510. On top of that, colors are bad in two of the three pairings.

Transposing the 1510 with either the 1620 or the 1400 would solve the first problem, but the TD would like to make the colors work, too. So he wants to make the following three-way transposition:

2120 BWB vs 1400 WBW 2010 WBW vs 1620 BWB 1900 WBW vs 1510 BWB
– but is worried that this might be a violation of the 200-point rule.

What is the proper way to evaluate a three-way transposition? Saying that this transposition evaluates to the lesser of 2120 minus 1900, or 1620 minus 1400 – both of which are 220 – seems a bit harsh.

With two-way transpositions, the rule is clear:

“raw” pairings: proposed pairings: A vs J A vs K B vs K B vs J

This transposition is evaluated at either A minus B, or J minus K, whichever is less:

“29E5c. Evaluating transpositions. All transpositions should be evaluated based on the smaller of the two rating differences involved.”

I guess the philosophy is that A, for example, has no legitimate beef as long as EITHER his “raw” opponent (J) and his proposed opponent (K) are close together, OR he himself is close to the player (B) who would now be paired against his (A’s) “raw” opponent.

What about three-way transpositions?

“raw” pairings: proposed pairings: A vs J A vs L B vs K B vs J C vs L C vs K

Here the rulebook throws up its hands:

“In larger groups, the situation is sometimes more complicated, as a permissible transposition may generate numerous additional transpositions … In such situations, the director may strictly observe the limits for transpositions or may be flexible. …”

But what if we try to apply the philosophy stated above? Then A would have no beef as long as either J is close to L, or A is close to B.

Calculating the potential beefs of all six players in a similar manner, we conclude that this transposition should be evaluated at either:

1. the lesser of A-B or J-L (A’s beef – also turns out to be J’s beef) 2. the lesser of B-C or J-K (B’s beef – also turns out to be K’s beef) 3. the lesser of A-C or K-L (C’s beef – also turns out to be L’s beef)
So that NO player has a legitimate beef, we of course must use the largest of the above three.

In the original example at the top of this post, this evaluation turns out to be 110 points, rather than the originally feared 220 points. So the proposed transposition seems acceptable.

Comments?

Bill Smythe

2

Bill, you’re a mathematician, surely there’s a way to deal with this using group theory. A friend of mine (now retired to Florida) used group theory for highly secure data encryption algorithms, this sounds less complex than that.

I have also wondered at times about using weighted priority goal programming techniques for pairing.

3

Hi,

I might suggest that a 3-way transposition is really nothing more than two 2-way transpositions. For example:

2120 - 1620
2010 - 1510
1900 - 1400

There are 2 possible ways to do a 3-way transposition with players 1620, 1510, and 1400. You can have variation 1 which is reached by first transposing 1620 with 1510, and then transposing 1620 with 1400:

2120 - 1510
2010 - 1400
1900 - 1620

Variation 2 is reached after first transposing 1510 with 1400, and then 1620 with 1400:

2120 - 1400
2010 - 1620
1900 - 1510

To arrive at either of these variations, I think you have violated the 200 point transposition rule. In both variations you needed to transpose 1620 with 1400 in the second step.

As much as we might want to have all the colors be correct in this scoregroup, I think it is important to realize why there is a 200 point rule and when transpositions are allowed. Transpositions are allowed when the rating differences are small or relatively insignificant. When the ratings are outside this allowed limit, then the scoregroup must be paired with “bad colors”.

There is another way of thinking about the transpostion differences. In the raw pairings, player 2120 was originally paired against 1620, but in variation 1 he is paired against a 1400, or a 220 point rating difference. In variation 2, the 1900 was originally paired against a 1400, but is now paired against a 1620, again a 220 point rating difference.

I would therefore suggest that the “best” pairings according to my interpretation of the rules is a single transposition:

2120 - 1620
2010 - 1400
1900 - 1510

Note, since the 2 single transpositions are exactly 110 points, I prefer the transposition in the lower half of the lower section (1510 with 1400) instead of the transposition in the upper half of the lower section (1620 with 1510), but either are “legal”.

Kind Regards,
Tom Ewers

4

There actually seems to be 3 ways to do a 2-step transpose depending upon which of the three players is settled first:

A. Fix 1510 first:
A1. Transpose 1510 with 1400.
A2. Transpose 1400 with 1620.
220 point difference in 2nd.

B: Fix 1400 first:
B1. Transpose 1400 with 1620.
B2. Transpose 1620 with 1510.
220 point difference in 1st.

C: Fix 1620 first:
C1. Transpose 1620 with 1510.
C2. Transpose 1510 with 1400.
110 point difference.
This would be the minimal one which is under the 200 point rule.

Basically you are doing a mini-max of the tree. Each multi-step transposition can be considered a tree of 2-way transpositions. The cost of a branch is the max of each of the 2-way transpositions along that branch. The cost of the tree is the minimum of all the costs of the branches.

5

Hi,

Your example has gotten me to thinking that maybe at each tranposition we need to consider a “cumulative” effect on the subsequent transpositions. For example:

Let’s say that no player has played another in the group.

2120 - 1620
2010 - 1510
1900 - 1400

First, transpose 1400 with 1510.
Next, transpose 1620 with 1510.
Finally, transpose 1400 with 1510.

The result:

2120 - 1400
2010 - 1510
1900 - 1620

Hmmm. With only making 110 point transpositions, we have arrived at a pairing that I think most TDs would say violates the 200 point rule, since it is the same as just transposing 1620 with 1400 which is a 220 point difference!

Perhaps this is a puzzle with no solution!?

Kind Regards,
Tom Ewers

6

In dealing with the mini-max tree of transpositions, you probably also want to require that the trees be of the minimal height. That eliminates the problem of using 3 transpositions when one would work in your example.

7

…or we could invent a rule to require that transpositions must only be made with adjacent entries. This would take us back to my original evalutation that the 3 way transpostion should not be allowed! :open_mouth:

Kind Regards,
Tom Ewers

8

It is certainly true that any 3-way transposition can be constructed as the composite of two 2-way transpositions. For example, to achieve the proposed transposition (your “variation 2”):

[code] “raw” pairings: transposed pairings:

2120 BWB vs 1620 BWB 2120 BWB vs 1400 WBW
2010 WBW vs 1510 BWB 2010 WBW vs 1620 BWB
1900 WBW vs 1400 WBW 1900 WBW vs 1510 BWB[/code]
– we could switch 1510 with 1400, then 1620 with 1400.

The mirror-image transposition (your “variation 1”) can, likewise, be constructed from two 2-way transpositions.

But evaluating a 3-way transposition as a composite of 2-way transpositions can lead to questionable results. We could end up rejecting a transposition which “should” be allowed, or vice versa.

You are overlooking something.

A transposition does not violate the 200-point rule just because the players being transposed are more than 200 points apart. It is a violation only if the OPPONENTS are also more than 200 points apart:

“29E5c. Evaluating transpositions. All transpositions should be evaluated based on the smaller of the two rating differences involved.”

In the second step above, the players are indeed 220 points apart, but the opponents are only 110 points apart.

Therefore, if you want to argue that the proposed 3-way transposition is illegal, you will have to do so on some grounds OTHER than that one of the component 2-way transpositions is illegal.

Of course, you could argue that the evaluation should be based on the final composite rating switch. But, in a 3-way, what is the “composite”, and which “switch”? And don’t forget the “smaller of the two” provision from 29E5c.

First the 2-way case:

[code] “raw”: transposed:

A vs J A vs K
B vs K B vs J[/code]
The A vs J pairing was transposed by (J-K) or (A-B) rating points, WHICHEVER IS LESS. (A’s opponent was changed from J to K, while J’s opponent was changed from A to B.) Likewise, B vs K was transposed by the lesser of (J-K) or (A-B).

Now the 3-way case:

[code] “raw”: transposed:

A vs J A vs L
B vs K B vs J
C vs L C vs K[/code]
Here, the A vs J pairing was transposed by (J-L) or (A-B), WHICHEVER IS LESS. (A’s opponent was changed from J to L, while J’s opponent was changed from A to B.) Likewise, B vs K was transposed by the lesser of (J-K) or (B-C). And C vs L was transposed by the lesser of (K-L) or (A-C).

So, as long as all three of the following:

  1. lesser of (J-L) or (A-B)
  2. lesser of (J-K) or (B-C)
  3. lesser of (K-L) or (A-C)

– are 200 points or less, it seems reasonable to say that the overall transposition does not violate the 200-point rule.

In our example,

[code] “raw” pairings: transposed pairings:

2120 BWB vs 1620 BWB 2120 BWB vs 1400 WBW
2010 WBW vs 1510 BWB 2010 WBW vs 1620 BWB
1900 WBW vs 1400 WBW 1900 WBW vs 1510 BWB[/code]
the three “lesser’s” all evaluate to 110 points, so the transposition should be OK.

Bill Smythe

9

Hello,

recently I did some experiment with a maximum weighted matching algorithm for pairing. In principle to each pair in a score group is assigned a score penalty depending by the position (distance between player in the group) and color. Then the algorithm find the pairing that make maximum the sum over all the pairs. In this field the pioner was Snjólfur Ólafsson, Weighted matchings in chess tournaments, J. Opl. Res. Soc. 41, 1 (1990), 17-24 that coded the swiss FIDE Lim rules.

For the USCF it is relatively easy to generate the natural pairing (top half vs bottom half) with such a method, but taking into account the 80 and 200 rule to improve the color doesn’t seem so obvious, at least for me. The handy “look ahead” method can be coded in some manner but as pointed out in this thread there is always space for improvement and disagreement.
I agree with Nolan that a mathematical method could be the solution as will be difficult (impossible) to improve the pairing the computer found.
I am ready to collaborate with somebody with a mathematical background that would like to find a mathematical expression for the penalty function (or cost function) that include the color correction.

Thanks,
Luigi Forlano

10

Also see the thread Point Count Pairings, buried deep somewhere in this Tournament Direction forum.

Bill Smythe

11

Bill,

I was unaware of your previous posts in an other thread. It seems you have already solved the problem I was refering to. I’m going to move there to ask you some questions.

Regards,
Luigi