It is currently Thu Mar 28, 2024 5:10 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 8 posts ] 
Author Message
Offline
 Post subject: Pairing Construction (aka: I have too much time on my hands)
Post #1 Posted: Tue Aug 09, 2011 10:14 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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(n3) 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:
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? :)


This post by HermanHiddema was liked by: Kirby
Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #2 Posted: Tue Aug 09, 2011 11:30 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
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.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #3 Posted: Tue Aug 09, 2011 12:11 pm 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
Kirby wrote:
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 13 is better than 1 x 23).

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?

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #4 Posted: Tue Aug 09, 2011 12:46 pm 
Lives in gote

Posts: 392
Liked others: 29
Was liked: 176
GD Posts: 1072
You need an addition criterion on how you deal with odd-sized score groups. Something along the lines of (in C/C++)
Code:
(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.

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #5 Posted: Tue Aug 09, 2011 1:15 pm 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
pwaldron wrote:
You need an addition criterion on how you deal with odd-sized score groups. Something along the lines of (in C/C++)
Code:
(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.

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #6 Posted: Tue Aug 09, 2011 2:28 pm 
Lives in gote

Posts: 392
Liked others: 29
Was liked: 176
GD Posts: 1072
HermanHiddema wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #7 Posted: Wed Aug 10, 2011 1:15 am 
Gosei
User avatar

Posts: 2011
Location: Groningen, NL
Liked others: 202
Was liked: 1087
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
pwaldron wrote:
HermanHiddema wrote:
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.

Top
 Profile  
 
Offline
 Post subject: Re: Pairing Construction (aka: I have too much time on my ha
Post #8 Posted: Wed Aug 10, 2011 3:40 am 
Lives in gote
User avatar

Posts: 655
Location: Czechia
Liked others: 29
Was liked: 41
Rank: 1d KGS
KGS: Laman
HermanHiddema wrote:
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

_________________
Spilling gasoline feels good.

I might be wrong, but probably not.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 8 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group