Tournament pairing algorhitm

Question

I need to find ideal pairing amongst tournament players based on following rules:

• players with equal points score or similar should be matched
• two players can have only one mutual match in tournament
• all players must have a match in a round

Its basically a simplified Swiss tournament system.

I have followings standings:

[{
  "playerIndex": 0,
  "points": 0,
  "opponents": [3, 2, 4]
}, {
  "playerIndex": 1,
  "points": 3,
  "opponents": [4, 5, 2]
}, {
  "playerIndex": 2,
  "points": 3,
  "opponents": [5, 0, 1]
}, {
  "playerIndex": 3,
  "points": 4,
  "opponents": [0, 4, 5]
}, {
  "playerIndex": 4,
  "points": 6,
  "opponents": [1, 3, 0]
}, {
  "playerIndex": 5,
  "points": 2,
  "opponents": [2, 1, 3]
}]

Read as: first array item is player number (index) 0 that already played with players number (index) 3, 2 and 4 and gained 0 points, each item for one of six players in a tournament.

And I need to pick three matches for the fourth match. Following a rule that no two players can play a mutual match more than once I choose from following matches:

[ [ 0, 1 ], [ 0, 5 ], [ 1, 3 ], [ 2, 3 ], [ 2, 4 ], [ 4, 5 ] ]

Each of these six possible matches has a points difference between the two players as follows:

[3, 2, 1, 1, 2, 4]

So ideal pairing for the fourth round that gives each player a match in a round with lowest points difference between paired players is:

[ [0, 5], [1, 3], [2, 4] ]

Is there any way of finding these ideal pairings in real time? It is impossible to try all the possible combinations, because there can be more than 100 people in a tournament and the calculations would take forever.

I have been advised to use https://en.wikipedia.org/wiki/Edmonds%27_algorithm or https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm (both available in JS: https://www.npmjs.com/package/edmonds-blossom and https://github.com/sfentress/edmunds-karp). But I am not sure how to read the results.

Can somebody help please?

Answer 1

Edit: Hungarian algorithm fails if there is too many possible solutions. In my case after first round when there is a lot of players with same amount of points.

Edmond Blossoms algorithm performs much better (found this JS implementation available via NPM https://github.com/mattkrick/EdmondsBlossom).

Just had trouble understanding how to use it. The main difference is that you need to feed it with pairs and the points difference between pairs is higher for the pairs that should be preferred. So I use zero difference for pairs that already played before.

My final (hopefully) solution:

  var maxDiff = (roundIndex + 1) * this.config.pointsWin

  var possiblePairs = []
  availablePlayers.forEach(player => {
    availablePlayers.forEach(opponent => {
      if (
        player.playerIndex !== opponent.playerIndex // &&
        // player.opponents.indexOf(opponent.playerIndex) === -1
      ) {
        var match = [player.playerIndex, opponent.playerIndex]
        match.sort(function(a, b) {
          return a - b;
        })
        if (player.opponents.indexOf(opponent.playerIndex) === -1) {
          match.push(maxDiff - Math.abs(player.points - opponent.points))
        }
        else {
          match.push(0)
        }
        if (this.searchForArray(possiblePairs, match) === -1) {
          possiblePairs.push(match)
        }
      }
    })
  })

  var rawPairing = edmondsBlossom(possiblePairs)
  rawPairing.forEach((match, index) => {
    if (match !== -1 && match < index) {
      round.matches.push({
        home: match,
        home_score: '',
        away: index,
        away_score: '',
        referee: -1
      })
    }
  })

First I count max possible points difference amongst players (expecting someone could gain zero points and someone else all of them). Then create all possible combinations between players and mark them with MAX POSSIBLE POINTS - PLAYERS POINTS DIFFERENCE or ZERO for players that matched before.

Then feed the array to EdmondsBlossom function that returns array of integers...

[6,8,14,5,15,3,0,10,1,12,7,13,9,11,2,4]

...read as follows: player index 0 should be paired with player 6, player 1 vs 8, player 2 vs 14, player 3 vs 5... player 5 vs 3 (duplicates). Sometimes there is -1 value in the output that is simply skipped.

Here is my solution (deprecated):

Thanks to @VedPrakash's comment I found the Hungarian algorithm that solves my problem. Luckily there is also a JS implementation available on NPM https://github.com/addaleax/munkres-js.

The Munkers function needs a matrix as input. In my case it is players points difference on intersections of my matrix (see below). The pairs that already played each other have higher value that cant be achieved (9 in my case).

Input matrix:

[ [ 9, 4, 9, 9, 9, 3 ],
  [ 4, 9, 9, 2, 9, 9 ],
  [ 9, 9, 9, 2, 4, 9 ],
  [ 9, 2, 2, 9, 9, 9 ],
  [ 9, 9, 4, 9, 9, 5 ],
  [ 3, 9, 9, 9, 5, 9 ] ]

Output:

[ [ 0, 5 ], [ 1, 3 ], [ 2, 4 ], [ 3, 1 ], [ 4, 2 ], [ 5, 0 ] ]

The last thing to take care of is filter the Munkers output (that contains duplicates - both pairs 0vs1 and 1vs0) so i filter them simply by comparing first and second index.

My implementation:

  var maxDiff = (roundIndex + 1) * this.config.pointsWin

  // prepare matrix
  var matrix = [];
  for (var i = 0; i < availablePlayers.length; i++) {
    matrix[i] = new Array(availablePlayers.length);
    matrix[i].fill(0)
  }

  // fill matrix with players points diff
  for (var y = 0; y < availablePlayers.length; y++) {
    var playerY = availablePlayers[y]

    for (var x = 0; x < availablePlayers.length; x++) {
      var playerX = availablePlayers[x]

      if (x === y) {
        matrix[x][y] = maxDiff
      }
      else if (playerY.opponents.indexOf(x) !== -1) {
        matrix[x][y] = maxDiff
        matrix[y][x] = maxDiff
      }
      else {
        var value = Math.abs(playerX.points - playerY.points)
        matrix[x][y] = value
        matrix[y][x] = value
      }
    }
  }

  // console.table(matrix)
  // console.table(computeMunkres(matrix))
  // return

  // make pairing
  var rawPairing = computeMunkres(matrix)
  rawPairing.forEach(pairing => {
    if (pairing[0] < pairing[1]) {
      round.matches.push({
        home: pairing[0],
        home_score: '',
        away: pairing[1],
        away_score: '',
        referee: -1
      })
    }
  })