Pairing algorithm


OpenGotha's pairing system is based on an evaluation function and a maximum matching algorithm.
To pair a set of n players, OpenGotha first computes a cost for each pair of players, that is to say n*(n-1)/2 costs. The cost is computed by an evaluation function. A low cost means an undesirable pairing while a high cost means a desirable pairing. Then these n*(n-1)/2 costs are input to the maximum matching algorithm which finds the set of n/2 couples that gives the maximum sum of costs.

The maximum matching algorithm

OpenGotha's pairing system is based on an O(n^3) implementation of Edmonds' algorithm, as presented by Harold N. Gabow. The development is part of the UCSB JICOS project. Adaptation for OpenGotha has been made by Jean-François Bocquet.
Descriptions of Maximum matching algorithms, Edmond's algorithm and Gabow's implementation can be found in :