Pairing Construction (aka: I have too much time on my hands)

[HermanHiddema]

So, I've recently been writing some code to do pairings for go tournaments, and reading up on some theory.

Both Gerlach's MacMahon and OpenGotha use a pairing method based on running the "Maximum Weight Perfect Matching" algorithm on a completely connected graph of the players. That means they assign weights to each and every possible pair of players indicated how (un)desirable it is for them to play, and then run a global optimization algorithm that is guaranteed to find the pairing with the highest possible overall weight in O(n³) time.

Some of the things that go into the weight are:

• Have these players played before? (very bad pair!)
• What is the difference in (McMahon) Score between these players? (higher difference is worse)
• What are the players' positions without their group (for fold or slide pairing)
• How often have these players had which color (can we increase color balance?)
• Are they from the same club? Same country?

The point of this post is to highlight the second point: What is the score difference.

By default, in Gerlach's MacMahon, the score difference is squared to give it its weight. That means that the program considers pairing two players with 2 points difference (weight 4) as bad a making four pairings with difference 1 (4 times weight 1).

To illustrate this point, I have constructed the following tournament table:

Code: Select all

Pos Name   Rank  r1   r2   r3   r4  Pt  SOS
1.  Alice   5d   9+   7+   4+   2+   4   7
2.  Bob     5d   8+   4+   5+   1+   3   9
3.  Chris   4d   5-   9+  10+   8+   3   5
4.  Dave    2d   7+   2-   1-   5+   2  10
5.  Emma    2d   3+   6+   2-   4-   2   9
6.  Frank   3d  10+   5-   8-   7+   2   5
7.  Gina    3d   4-   1-   9+   6-   1   9
8.  Helen   2d   2-  10-   6+   3-   1   9
9.  Isaac   1d   1-   3-   7-  10+   1   9
10. Joe    2d   6-   8+   3-   9-   1   7

(This is where the "too much time on my hands" comes in. Took me many many hours to get that just right)

Now, here are two possible ways the next round could be paired:

1-3, 2-6, 4-10, 5-9, 7-8

1-5, 2-3, 4-6, 7-10, 8-9


In the first pairing, there are four games that have a score difference of 1, the first four games.

In the second, only the first pair spans groups, but it spans two of them. All the other pairings are within their own group.

So, according to MacMahon, these pairings are exactly equally good, where score difference is concerned.

Personally, I would prefer the first pairing, as it gives the tournament leader a closer opponent, and I feel that the pairings that affect the tournament outcome are more important than those lower down. What do you think?

[Kirby]

In this example, with the information given, I like the first pairing better for the reason that you mention. This would be particularly true if prizes were on the line.

In practice, perhaps you could use the score difference to generate a list of candidate pairings, and use some weighting based on the other criteria that you listed to select a pairing from that list.

Still, though, out of the factors that are listed here, I think that score difference is most relevant. I like the first pairing the best.

[HermanHiddema]

In practice, perhaps you could use the score difference to generate a list of candidate pairings, and use some weighting based on the other criteria that you listed to select a pairing from that list.

Still, though, out of the factors that are listed here, I think that score difference is most relevant. I like the first pairing the best.

Yes, this is what the MacMahon program does. The weight for "have already played" is much much higher than that for "score difference", which is again much higher than that for the other criteria (they are listed in order of importance).

In this case, MacMahon might decide is likes the second pairing better because of the fact that the pairing within the group of players with one point conforms exactly to a fold pairing. Or it might decide it likes one or the other pairing better based on color balance, same club or same country. With the score difference weight in balance like this, its pretty much a toss up.

Which is, of course, why I posted it.

MacMahon does, BTW, allow you to change the way it processes score difference. You could set it to raise score difference to the third power, instead of squaring it, in which case the first pairing would be much preferred (4 x 1³ is better than 1 x 2³).

Of course, a related question is: Suppose that these are just the bottom 10 players of a McMahon tournament. There are 20 stronger players above this table which have already been paired. Would you then feel the same way about which pairing is preferable?

[pwaldron]

You need an addition criterion on how you deal with odd-sized score groups. Something along the lines of (in C/C++)

Code: Select all

(score1 == score2) ? (0) : abs(position1 - position2) * weight

This has the effect of preferentially finding a stronger opponent if one at the same McMahon score isn't available.

[HermanHiddema]

You need an addition criterion on how you deal with odd-sized score groups. Something along the lines of (in C/C++)

Code: Select all

(score1 == score2) ? (0) : abs(position1 - position2) * weight

This has the effect of preferentially finding a stronger opponent if one at the same McMahon score isn't available.

Yes, this is what the current algorithms do, except they additionally squares the score difference.

There's also the issue of whom to pair up or down. The players with the highest/lowest SOS? The middle one? randomly?

OpenGotha allows you to set it as a preference.

[pwaldron]

There's also the issue of whom to pair up or down. The players with the highest/lowest SOS? The middle one? randomly?

I don't know if anyone has studied this, and it's not at all clear to me that you want to do it by SOS.

The chess world sorts players by entry rating and then pairs the bottom player from the higher score group with the top player of the next group down. It provides the opportunity for the nominally stronger player (i.e. the higher rated one) to get back into contention as quickly as possible.

[HermanHiddema]

There's also the issue of whom to pair up or down. The players with the highest/lowest SOS? The middle one? randomly?

I don't know if anyone has studied this, and it's not at all clear to me that you want to do it by SOS.

The chess world sorts players by entry rating and then pairs the bottom player from the higher score group with the top player of the next group down. It provides the opportunity for the nominally stronger player (i.e. the higher rated one) to get back into contention as quickly as possible.

Yes, more generally I meant to say: The highest/lowest by chosen tie breakers. Where the tie breaker could be SOS, or prior rating, or other things (e.g. CUSS, Modified Median, etc). Using prior rating is only viable if you have a good rating system, of course.

There are several philosophies on this, and I guess it also depends on whether you use Swiss or McMahon and on the skill range of the players. If the skill range of the higher group is 5d-1d, and that of the lower group 1k-3k, then I guess there is not too much value in getting some 1 kyu into contention.

For McMahon, I would in fact prefer to make the McMahon groups a fixed size, say 8 or 16, depending on the number of rounds, so that pairing up or down happens as little and as late as possible.

[Laman]

There's also the issue of whom to pair up or down. The players with the highest/lowest SOS? The middle one? randomly?

one strategy is to pair the first player from the upper group and the last player from the lower group - to protect the supposedly strongest player in competition by pairing him against the supposedly weakest player from the lower group

the opposite also makes sense, as pwaldron points out

it really matters only in the top group(s), in the main pool i think random is as good as anything

the algorith should also (more importantly) consider how many times was a player already paired up / down - to avoid repeatedly pairing one player in the same direction. and one other criterion could be number of wins - to pair a player with high NBW preferably up and player with low NBW preferably down