Round Robin pairings generator.

[Ajedrecista]

Hello to everybody:

I had a doubt yesterday on how to schedule pairings in a Round Robin tournament. I guess that there are programmes such as Swiss-Manager or Swiss Perfect that can handle those pairings without any difficulty, as expected. But they are not freeware IIRC, so I searched a handmade method for schedule the pairings, until I found one of them: the Schurig algorithm, sometimes called 'Berger tables'. Here are two links (in Spanish) with the explanation of the algorithm, and other link with Berger tables:

http://ajedrezmagico.blogspot.com.es/20 ... ontra.html

http://ajedrezpueblonuevo.com/ajedrez/i ... 43:general

http://www.portaldeajedrez.cl/berger.htm

This algorithm is very easy to use by hand, but writing a programme of it is another story, specially for a non-programmer as me. I struggled for getting the correct sequence for any number of players until I got it yesterday! Minor aesthetic changes came today. My code is fully original so it may contain errors although I do not expect them because I have checked many tables generated by my programme (using the Schurig algorithm) with other trusted tables, and pairings match one by one without exception... it is a good start!

Round_Robin_pairings_generator is programmed in Fortran 95 and it is relatively fast in my computer: the maximum number of supported players is 64 (which is a parameter that can be easily enlarge in the source code, then recompile it) and this extreme case usually takes around 0.6 seconds in my computer; obviously: less players imply less elapsed time. Here is an example of how Round_Robin_pairings_generator looks when a double click is done on the executable and the desired data is input:

Code: Select all

Round_Robin_pairings_generator, ® 2012.

Write down the number of players of the Round Robin tournament (up to 64):

64

Write down the clock rate of the CPU (in GHz), only for timing the elapsed time of the calculations:

3

End of the implementation of Schurig algorithm. Approximated elapsed time:  599 ms.

The pairings have been saved in Pairings.txt file.

Thanks for using Round_Robin_pairings_generator. Press Enter to exit.

Here are two examples of Pairings.txt output file: the first one with an odd number of players and the second one with an even number of players:

Code: Select all

Pairings in a round robin tournament with  5 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:   10 games.
b) Double Round Robin tournament:   20 games; the second half has the same pairings (colour reversed).
 
An odd number of players means that player  6 is fictional and it must be understood as a bye.
 
---------
 
Round  1:
 
 1- 6
 2- 5
 3- 4
 
---------
 
Round  2:
 
 6- 4
 5- 3
 1- 2
 
---------
 
Round  3:
 
 2- 6
 3- 1
 4- 5
 
---------
 
Round  4:
 
 6- 5
 1- 4
 2- 3
 
---------
 
Round  5:
 
 3- 6
 4- 2
 5- 1
 
---------
 
End of the implementation of Schurig algorithm. Approximated elapsed time:   35 ms.
 
Thanks for using Round_Robin_pairings_generator.

Code: Select all

Pairings in a round robin tournament with  8 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:   28 games.
b) Double Round Robin tournament:   56 games; the second half has the same pairings (colour reversed).
 
---------
 
Round  1:
 
 1- 8
 2- 7
 3- 6
 4- 5
 
---------
 
Round  2:
 
 8- 5
 6- 4
 7- 3
 1- 2
 
---------
 
Round  3:
 
 2- 8
 3- 1
 4- 7
 5- 6
 
---------
 
Round  4:
 
 8- 6
 7- 5
 1- 4
 2- 3
 
---------
 
Round  5:
 
 3- 8
 4- 2
 5- 1
 6- 7
 
---------
 
Round  6:
 
 8- 7
 1- 6
 2- 5
 3- 4
 
---------
 
Round  7:
 
 4- 8
 5- 3
 6- 2
 7- 1
 
---------
 
End of the implementation of Schurig algorithm. Approximated elapsed time:   40 ms.
 
Thanks for using Round_Robin_pairings_generator.

Logically, I have uploaded my programme for everyone that wants to use it:

Round_Robin_pairings_generator.rar (0.6 MB)

Have fun! Corrections are welcomed as usual.

Regards from Spain.

Ajedrecista.

[hgm]

In WinBoard I use the following code for calculating the pairing of a given game of a round-robin. The game sequence number is first converted to a round number and a 'pairing number' (the number of the game within the round) by a number of modulo operations, based on number of players and games per pairing (from which follows the number of games per round). Then the player numbers for the game are derived from this. Getting the entire tournament schedule would

Code: Select all

	roundsPerCycle = (nPlayers - 1) | 1;
	pairingsPerRound = nPlayers / 2;

    // calculate implied tourney parameters
    gamesPerRound = pairingsPerRound * gamesPerPairing;
    gamesPerCycle = gamesPerRound * roundsPerCycle;
    curCycle = nr / gamesPerCycle; nr %= gamesPerCycle;
    curRound = nr / gamesPerRound; nr %= gamesPerRound;
    curPairing = nr / gamesPerPairing; nr %= gamesPerPairing;
    matchGame = nr + curCycle * gamesPerPairing + 1; // fake game nr that loads correct game or opening position from file
    roundNr = (curCycle * roundsPerCycle + curRound) * gamesPerPairing + nr + 1;

	// make pairing
	if(curPairing == (nPlayers-1)/2 ) {
	    *whitePlayer = curRound;
	    *blackPlayer = nPlayers - 1; // this is the 'bye' when nPlayer is odd
	} else {
	    *whitePlayer = curRound - (nPlayers-1)/2 + curPairing;
	    if&#40;*whitePlayer < 0&#41; *whitePlayer += nPlayers-1+&#40;nPlayers&1&#41;;
	    *blackPlayer = curRound + &#40;nPlayers-1&#41;/2 - curPairing;
	    if&#40;*blackPlayer >= nPlayers-1+&#40;nPlayers&1&#41;) *blackPlayer -= nPlayers-1+&#40;nPlayers&1&#41;;
	&#125;

The algorithm used is circulating the players around a long table, where the last player (the BYE in case of an odd number of players) keeps its seat permanently.

[Daniel Shawul]

I have an 'awesome' round robin matches generator for _multiplayer_ games. It can generate exactly the ith match without generating previous matches which could be useful in parallel applications etc. The idea is based on computing factoradic of a number. Here is explanation. I use this in my multi-player GUI to produce matches. Utility java code for that

Code: Select all

package com.daniel.engines;

/** Utility class for combinatorics (permutations and combinations).
 */
public class Combinatorics {
	public static void Permutation(int n, int k, int[] data)  {
		for &#40;int j = 1; j <= n; ++j&#41; &#123;
			data&#91;n - j&#93; = k % j;
			k /= j;
		&#125;
		data&#91;n - 1&#93; = 0;
		for &#40;int i = n - 2; i >= 0; --i&#41; &#123;
			for &#40;int j = i + 1; j < n; ++j&#41; &#123;
				if &#40;data&#91;j&#93; >= data&#91;i&#93;)
					++data&#91;j&#93;;
			&#125;
		&#125;
	&#125;
	public static int nCombination&#40;int n,int k&#41; &#123;
		int product1 = n;
		int product2 = 1;
		for&#40;int j = 1;j < k;j++) &#123;
			product1 *= &#40;n - j&#41;;
			product2 *= &#40;j + 1&#41;;
		&#125;
		return &#40;product1 / product2&#41;;
	&#125;
	public static void Combination&#40;int k, int index, int&#91;&#93; data&#41; &#123;
		int comb;
		data&#91;0&#93; = index;
		for&#40;int i = k - 1;i >= 1;i--) &#123;
			data&#91;i&#93; = i;
			comb = 1;
			while&#40;data&#91;0&#93; >= comb&#41; &#123;
				data&#91;0&#93; -= comb;
				comb = nCombination&#40;++data&#91;i&#93;,i&#41;;
			&#125;
		&#125;
	&#125;
	public static void Combination&#40;int n,int k,int index,int&#91;&#93; data&#41; &#123;
		int a = n;
		int b = k;
		int nk = nCombination&#40;n,k&#41;;
		int x = &#40;nk - 1&#41; - &#40;index % nk&#41;;

		for &#40;int i = 0; i < k; ++i&#41; &#123;
			data&#91;i&#93; = LargestV&#40;a,b,x&#41;;
			x = x - nCombination&#40;data&#91;i&#93;,b&#41;;
			a = data&#91;i&#93;;
			b = b-1;
		&#125;

		for &#40;int i = 0; i < k; ++i&#41; &#123;
			data&#91;i&#93; = &#40;n-1&#41; - data&#91;i&#93;;
		&#125;
	&#125;
	private static int LargestV&#40;int a, int b, int x&#41; &#123;
		int v = a - 1;
		while &#40;nCombination&#40;v,b&#41; > x&#41;
			--v;
		return v;
	&#125;
&#125;

[Daniel Shawul]

For example when 3 players are in a pair, you would need 3!=6 permutations if order maters. Also if you just produce parings of index 0...i, it will produce matches in a 'boring' order where one player finishes all its matches (gauntlet), then the next and so on. To generate excitement, one may randomly shuffle indices 0 to i, and generate the matches in that order. After all randomness is source of excitement, no? I don't know what the burger tables do, and if there is a specific order matches need to be done depending on who beats who. Anyway I didn't have much options for multi player match makers at the time I used this.

[hgm]

It can generate exactly the ith match without generating previous matches which could be useful in parallel applications etc.

The WinBoard code I showed also works this was (number to pairing, without generating any other games), for exactly that reason (parallelism).

Note that I let it not only play the games round by round, but also go through the games in one round in such a way that there is an almost constant spacing between consecutive games of the same player. It always annoyed me that in the more common RR implementations (e.g. PSWBTM) this spacing varies wildly, to the point where the same engine has to play two games in a row. With parallelism this seemed undesirable, because the same engine could then easily have to play those games simultaneously, perhaps leading for competition for its book access, or garbling of its log file. In the WinBoard algorithm if there are N games in a round, the interval between successive games is always between N-1 and N+1 (inclusive).

[Daniel Shawul]

It can generate exactly the ith match without generating previous matches which could be useful in parallel applications etc.

The WinBoard code I showed also works this was (number to pairing, without generating any other games), for exactly that reason (parallelism).

Note that I let it not only play the games round by round, but also go through the games in one round in such a way that there is an almost constant spacing between consecutive games of the same player. It always annoyed me that in the more common RR implementations (e.g. PSWBTM) this spacing varies wildly, to the point where the same engine has to play two games in a row. With parallelism this seemed undesirable, because the same engine could then easily have to play those games simultaneously, perhaps leading for competition for its book access, or garbling of its log file. In the WinBoard algorithm if there are N games in a round, the interval between successive games is always between N-1 and N+1 (inclusive).

I see. I gues that this is a problem on SMP machines where resources are shared and number of processors is less than number of participants. While round robin and gauntlet is manageable even for multi player games, I am not sure how to do a RR that finishes prematurely (a swiz i think ?). That requires looking at the performance of the players and I am not sure if it can be parallelized. It also means it will need to be able to rank by itself and at the same time avoid duplicates. Does winboard have swiss capability ?

[hgm]

Yes, WinBoard can do Swiss, although I located the pairing code in a separate process, which is run as a 'pairing engine'. But obviously you have to wait pairing a new round until the previous round is completely finished. But WinBoard has that option anyway (-syncAfterRound true|false), because it can also be nicer for making intermediate standings.

[Ajedrecista]

Hello:

I realized that the source code with .txt extension that I uploaded is a little incomplete: it should be the same as the source code with .f95 extension, which is completely correct. The programme works flawless, but if someone compiles from the source code with .txt extension, then:

Code: Select all

An odd number of players means that player XY is fictional and it must be understood as a bye.

It will appear with any number of players instead with only an odd number of players. I forgot to add an if statement to the Notepad, but this if statement is included in the original source code in Fortran 95 extension. I have corrected it in the Notepad and I also added a little change: now the player which has a bye is not shown as paired with XY player but directly appears that this player has a bye. New outputs:

Code: Select all

Pairings in a Round Robin tournament with  5 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:   10 games.
b) Double Round Robin tournament:   20 games; the second half has the same pairings (colour reversed).
 
--------------------
 
ROUND  1:
 
Player  1 has a bye.
 2- 5
 3- 4
 
--------------------
 
ROUND  2:
 
Player  4 has a bye.
 5- 3
 1- 2
 
--------------------
 
ROUND  3:
 
Player  2 has a bye.
 3- 1
 4- 5
 
--------------------
 
ROUND  4:
 
Player  5 has a bye.
 1- 4
 2- 3
 
--------------------
 
ROUND  5:
 
Player  3 has a bye.
 4- 2
 5- 1
 
--------------------
 
End of the implementation of Schurig algorithm. Approximated elapsed time:   40 ms.
 
Thanks for using Round_Robin_pairings_generator.

Code: Select all

Pairings in a Round Robin tournament with  6 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:   15 games.
b) Double Round Robin tournament:   30 games; the second half has the same pairings (colour reversed).
 
---------
 
ROUND  1:
 
 1- 6
 2- 5
 3- 4
 
---------
 
ROUND  2:
 
 6- 4
 5- 3
 1- 2
 
---------
 
ROUND  3:
 
 2- 6
 3- 1
 4- 5
 
---------
 
ROUND  4:
 
 6- 5
 1- 4
 2- 3
 
---------
 
ROUND  5:
 
 3- 6
 4- 2
 5- 1
 
---------
 
End of the implementation of Schurig algorithm. Approximated elapsed time:   40 ms.
 
Thanks for using Round_Robin_pairings_generator.

Those little changes do not affect to the rightness of the pairings (the Schurig algorithm itself was not modified, only the output data) so I think that it is not necessary to re-upload my programme. The version that I uploaded yesterday already works perfectly.

-----------------------

@Muller: I also use a round number and a pairing number (I call them round and board); integers white(i,j) and black(i,j) are used, where i index stands for rounds and j index stands for boards.

I see that using the Schurig algorithm for an even number of players, one player (not the same player every time) will play the last game of a round and the first game of the following round... shuffling the order of the boards should solve this issue, although I was really interested on who encounters who in each round, and not in which board. Sometimes, some players play with the same colour in two consecutive rounds, but I think that it is a minor issue (and maybe compulsory?).

Congratulations for achieve to handle Swiss pairings in WB! Good work.

@Shawul: It looks interesting generating the pairings for the i-th round without generating previous pairings. But my objective was generating all the pairings. My programme is maybe a little more focused in human pairings when you do not know how to schedule pairings, this is why I made this simple tool. Of course, it can be used for engine pairings because 64 players (my maximum by default) in a RR tournament are factible for engines but not for humans, IMHO.

As far as I understood, Berger's tables are unique for a given number of players using the Schurig algorithm (you can take a look on the links of the first post of this thread to see how this algorithm works). If the number of players is odd, then one different player will have a bye each round: each player will not have two or more consecutive byes. When you refer to dependency of 'who beats who', it implies a Swiss system, which is not my aim. Sincerely, I would be unable of schedule pairings in a Swiss tournament... but at least I managed to schedule pairings in a RR tournament! Not bad at all, taking into account my very limited skills in programming (please remember that I am not a programmer).

Regards from Spain.

Ajedrecista.

[Ajedrecista]

Hello again:

I was puzzled that my simple programme spent around 0.6 seconds when doing all the pairings in a RR with 64 players... I was reporting milliseconds when in reality must be microseconds! So, the generation time is in reality around 0.6 ms in my computer and it makes more sense.

I consider quite important this change so I re-upload my RR pairings generator:

Round_Robin_pairings_generator.rar (0.6 MB)

Code: Select all

Round_Robin_pairings_generator, ® 2012.

Write down the number of players of the Round Robin tournament (up to 64):

64

Write down the clock rate of the CPU (in GHz), only for timing the elapsed time of the calculations:

3

End of the implementation of Schurig algorithm.

Approximated generation time:  605 microseconds.

The pairings (Berger's tables) have been saved in Pairings.txt file.

Thanks for using Round_Robin_pairings_generator. Press Enter to exit.

If someone who had downloaded the old version and still has a bit of interest on this programme, I recomend to replace that old version with this new one.

Output examples:

Code: Select all

Pairings (using the Schurig algorithm) in a Round Robin tournament with  3 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:    3 games.
b) Double Round Robin tournament:    6 games.
The second half has the same pairings as the first half, but with reversed colours.
 
--------------------
 
ROUND  1:
 
Player  1 has a bye.
 2- 3
 
--------------------
 
ROUND  2:
 
Player  3 has a bye.
 1- 2
 
--------------------
 
ROUND  3:
 
Player  2 has a bye.
 3- 1
 
--------------------
 
End of Berger's tables.
 
Approximated generation time:   34 microseconds.
 
Thanks for using Round_Robin_pairings_generator.

Code: Select all

Pairings (using the Schurig algorithm) in a Round Robin tournament with  4 different players.
 
Number of games in this tournament:
a) Single Round Robin tournament:    6 games.
b) Double Round Robin tournament:   12 games.
The second half has the same pairings as the first half, but with reversed colours.
 
---------
 
ROUND  1:
 
 1- 4
 2- 3
 
---------
 
ROUND  2:
 
 4- 3
 1- 2
 
---------
 
ROUND  3:
 
 2- 4
 3- 1
 
---------
 
End of Berger's tables.
 
Approximated generation time:   32 microseconds.
 
Thanks for using Round_Robin_pairings_generator.

Sorry for the inconvenience. My timing mistake was a big one! I hope that the rest is perfect (I am not thinking in optimization but in correctness of pairings), that is why I expect that it is the definitive version. Thanks for your patience.


Regards from Spain.

Ajedrecista.

[hgm]

@Muller: I also use a round number and a pairing number (I call them round and board); integers white(i,j) and black(i,j) are used, where i index stands for rounds and j index stands for boards.

I see that using the Schurig algorithm for an even number of players, one player (not the same player every time) will play the last game of a round and the first game of the following round... shuffling the order of the boards should solve this issue, although I was really interested on who encounters who in each round, and not in which board. Sometimes, some players play with the same colour in two consecutive rounds, but I think that it is a minor issue (and maybe compulsory?).

Probably reversing the board order of the odd-numbered rounds would solve that. I think the WinBoard algorithm solves it in a different way, by re-ordering the rounds.

Same color in two rounds cannot be avoided: otherwise the players would be subdivided into two groups depending on their color in the first round, and players within one group could never play each other, as they would always need to play the same color. In the table-circulation algorithm this only happens when the player 'swings around' the end of the table where the stationary player is, if you alternate the orientation of the boards along the table. Which in general happens once per tourney cycle, as swinging around the other end brings you to the opposite side of board 1, which does have the other color. So with 2N players, only when sitting on board N you will play the same color as the round before or after, as you sit only once on board N, and skip the chair on the opposite side of it. With fixed board orientation (which in a real OTB tourney is the most convenient), the 'stationary' player on board N would have to move to the opposite side of the table every round, to make sure also he alternates color.

With an odd number of player board N would be the 'bye', and the players change to the opposite phase of the white-black alternation not by playing the same color twice in a row, but by skipping a game.