Tuesday, January 6, 2015

Round Robins

As engine development can be a bit frustrating from time to time I jump a bit between trying to improve my engine and playing with a GUI prototype.

Lately I worked on a pairing algorithm for round robin tournaments. Here each engine plays all other engines for a given number of rounds.

The algorithm should create a pairing with a certain number of constraints like
  1. Work with both an odd and even number of players
  2. Let each engine play equally with White and Black (as close as possible) even if the number of rounds is 1 or odd.
  3. If an engine played one game with White it should play the next game with Black (in most cases against a different opponent)
  4. If the number of rounds is even, create for each other round the same engine pairings with colors reversed and assign the same opening id.
  5. Create a pairing sequence where an engine does not play a lot of games in a row (e.g. avoid a sequence where first engine A plays all the N-1 opponents and then engine B plays N-2 opponents etc.)
This seems like a really difficult problem. Luckily there exists a method used in over the board tournaments that helps here. In this method 1 player is fixed and the others after each match walk clockwise around a series of tables until the original setup would appear again.

It still requires some care to match all of the above constraints but the is solves most of them naturally.

Here is an extract of a pairing of 5 players (named 0, 1, 3, 4 and 5). The number in brackets is the opening id used in this pairing.