Swiss Pairing Algorithm

I needed a Swiss Pairing algorithm for a rewrite of the pairings code in gatherling.com. The existing code has a nasty habit of awarding the bye more than once to the same player or awarding more than one bye when things get tricky due to draws or drops or other complications.

A really good approach to the problem is described by Mark “Spike” Liu in Swiss Pairing: Leaguevine’s New Algorithm.

Some googling led me to Joris van Rantwijk’s Maximum Weighted Matching. This uses Edmonds’s Blossom algorithm. It takes a list of (index, index, weight) as inputs for every possible pairing and produces the highest scoring graph possible.

If you want to pair based on player/team skill things can get more complicated but I came up with a fairly simple weighting calculation that considers the following:

• Playing the same player twice
• Getting the bye twice
• Someone who is not the lowest scoring player who hasn’t had the bye getting the bye
• Getting paired down
• Pairing down better-performing players being much less desirable than pairing down worse-performing players

but not anything about the players/teams themselves.

def weight(highest_points, p1, p2):
    w = 0

    # A pairing where the participants have not played each other as many times as they have played at least one other participant outscore all pairings where the participants have played the most times.
    # This will stave off re-pairs and second byes for as long as possible, and then re-re-pairs and third byes, and so on …
    counter = Counter(p1['opponents'])
    if len(counter) > 0 and counter.get(p2['id'], sys.maxsize) < max(counter.values()):
        w += quality(highest_points, highest_points) + 1

    # Determine a score for the quality of this pairing based on the points of the higher scoring participant of the two (importance) and how close the two participant's records are.
    best = max(p1['points'], p2['points'])
    worst = min(p1['points'], p2['points'])
    spread = best - worst
    closeness = highest_points - spread
    importance = best
    w += quality(importance, closeness)

    return w

# importance and closeness are values in the range 0..highest_points
def quality(importance, closeness):
    # We add one to these values to avoid sometimes multiplying by zero and losing information.
    return (importance + 1 ** 2) * (closeness + 1 ** 2)

You can get the full working python code with a simple 8-player example at https://github.com/bakert/swiss