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 :
- J. Edmonds, "An introduction to matching," Notes of Engineering Summer Conference,
Univ. of Michigan, Ann Arbor, 1967.
- C. Gerlach, Ein Mac-Mahon-Losungsprogram für "Go-Turniere unter Benutzung von Maximum Weight Perfect Matching", 1994.
- B. Korte, "Combinatorial Optimization", Springer, 2006, available on
Google books