Maximum weighted matching algorithm for arena pairings

[antma]

Lichess uses maximum weight matching algorithm for arena parings.

The edge weight could be cumulative sum of some of these heuristics:

• minimize number of games already played between given two players in arena. Peoples don't like to play with same opponent many times
• minimize absolute rank difference between players (as Lichess does)
• minimize absolute rating difference between players (as Lichess does)
• minimize absolute rating deviation (RD), since some players don't like to play with players with unstable rating. See #986.
• minimize absolute difference of berserk rate between players. Zerkers don't like play with fair (not zerkers) peoples and vice versa.
• don't include in graph edge between player with 3 straight white games and player with 3 straight black games (color balancing)

Before summation heuristics should be normalized (multiplied by hand crafted coefficients). Since rank difference is more valuable than rating difference.

Minimal Weighted Matching problem could be solved by Maximal Weighted Matching algorithm by negation weights (replacing by MAXW - W(i,j), where MAXW - maximal weight among all edges in graph, W(i, j) - old weight for edge (i, j)).

Python implementation for the algorithm could be found here. Problem description for proposed implementation could be found here.

[gbtami]

Possible we should use networkx. It has max_weight_matching(), see in https://github.com/JeffHoogland/pypair

[antma]

I confirm that network implementation is equally slow for python3 as implementation I had mentioned before (around 90 seconds for graphs with 500 vertices). But I don't think that so much waiting players will be in pychess arena. Or for such marginal cases pychess could take only first 100 players sorted by ranking in the pool of waiting players and start next wave of pairing immediately.

Link to networkx documentation.