Round Robin Generator

[laserlight]

If you've ever been involved in chess tournaments, you would know they come in various formats, one of which is the round robin format.
In a round robin, each player plays every other player, and the difference in colours is kept to a minimum, with half the field having white for one more game than the other half.

I couldnt come up with a good enough algorithm myself, so I sent an email to the webmaster of CERN's chess club, where they had a round robin pairing calculator (http://chess.cern.ch/tournaments/robin.en.shtml) available.
The code was in pretty bad shape, but I managed to make out of the gist of the algorithm, and re-implemented it:
<?php
/************************************************
* Round Robin Pairing Generator
* Author: Eugene Wee
* Date: 23 May 2005
* Last updated: 23 May 2005
* Copyright (c) 2005 Eugene Wee
* Licensed under the Academic Free License 2.1
* Based on algorithm by Tibor Simko
************************************************/

function generateRoundRobinPairings($num_players) {
//do we have a positive number of players? otherwise default to 4
$num_players = ($num_players > 0) ? (int)$num_players : 4;
//set number of players to even number
$num_players = ($num_players % 2 == 0) ? $num_players : $num_players + 1;
//format for pretty alignment of pairings across rounds
$format = "%0" . ceil(log10($num_players)) . "d";
$pairing = "$format-$format ";
//set the return value
$ret = $num_players . " Player Round Robin:\n-----------------------";
//print the rounds
for ($round = 1; $round < $num_players; $round++) {
$ret .= sprintf("\nRound #$format : ", $round);
$players_done = array();
//print the pairings
for ($player = 1; $player < $num_players; $player++) {
if (!in_array($player, $players_done)) {
//select opponent
$opponent = $round - $player;
$opponent += ($opponent < 0) ? $num_players : 1;
//ensure opponent is not the current player
if ($opponent != $player) {
//choose colours
if ($player % 2 == $opponent % 2) {
if ($player < $opponent) {
//player plays black
$ret .= sprintf($pairing, $opponent, $player);
} else {
//player plays white
$ret .= sprintf($pairing, $player, $opponent);
}
} else {
if ($player < $opponent) {
//player plays white
$ret .= sprintf($pairing, $player, $opponent);
} else {
//player plays black
$ret .= sprintf($pairing, $opponent, $player);
}
}
//these players are done for this round
$players_done[] = $player;
$players_done[] = $opponent;
}
}
}
//print the last pairing (i.e. for the last player)
if ($round % 2 == 0) {
$opponent = ($round + $num_players) / 2;
//last player plays white
$ret .= sprintf($pairing, $num_players, $opponent);
} else {
$opponent = ($round + 1) / 2;
//last player plays black
$ret .= sprintf($pairing, $opponent, $num_players);
}
}
return $ret;
}
?>
In my case, I'm using it as:
$n = 4;
if (!empty($_GET['n']) && ctype_digit($_GET['n'])) {
$n = $_GET['n'];
}
echo '<pre>' . generateRoundRobinPairings($n) . '</pre>';
In "roundrobin.php", and so goto roundrobin.php?n=8 if I want 8 players.

[laserlight]

Wow, it has been nearly two years since I posted my code. At a whim, I decided to look again and see if I could make any improvements after two years, and I think I have. The function can be used in the same way as originally described:
/******************************************************************************
* Round Robin Pairing Generator
* Author: Eugene Wee
* Date: 23 May 2005
* Last updated: 13 May 2007
* Based on an algorithm by Tibor Simko.
*
* Copyright (c) 2005, 2007 Eugene Wee
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
******************************************************************************/

function generateRoundRobinPairings($num_players) {
// Do we have a positive number of players? If not, default to 4.
$num_players = ($num_players > 0) ? (int)$num_players : 4;

// If necessary, round up number of players to nearest even number.
$num_players += $num_players % 2;

// Format for pretty alignment of pairings across rounds.
$format = "%0" . ceil(log10($num_players)) . "d";
$pairing = "$format-$format ";

// Set the return value
$ret = $num_players . " Player Round Robin:\n-----------------------";

// Generate the pairings for each round.
for ($round = 1; $round < $num_players; $round++) {
$ret .= sprintf("\nRound #$format : ", $round);
$players_done = array();

// Pair each player except the last.
for ($player = 1; $player < $num_players; $player++) {
if (!in_array($player, $players_done)) {
// Select opponent.
$opponent = $round - $player;
$opponent += ($opponent < 0) ? $num_players : 1;

// Ensure opponent is not the current player.
if ($opponent != $player) {
// Choose colours.
if (($player + $opponent) % 2 == 0 xor $player < $opponent) {
// Player plays white.
$ret .= sprintf($pairing, $player, $opponent);
} else {
// Player plays black.
$ret .= sprintf($pairing, $opponent, $player);
}

// This pair of players are done for this round.
$players_done[] = $player;
$players_done[] = $opponent;
}
}
}

// Pair the last player.
if ($round % 2 == 0) {
$opponent = ($round + $num_players) / 2;
// Last player plays white.
$ret .= sprintf($pairing, $num_players, $opponent);
} else {
$opponent = ($round + 1) / 2;
// Last player plays black.
$ret .= sprintf($pairing, $opponent, $num_players);
}
}

return $ret;
}
Aside from arithmetic simplifications and cosmetic changes to comments and spacing, the main change is the use of PHP's xor operator to simplify the colour selection code. Oh, and I decided to switch to the MIT/Expat license, which unfortunately increased the length of the code.

[halojoy]

:)

hi laser

you know i play chess .. good chess

if you remember i had a look at some FEN chess appication you had written
we had some contact via Instant Messenger
I know you write good scripts!

This tournament set up feature - make a round robin - in your latest post.

1. Does it work as standalone ? Or is it only API utility to include in other pages?
2. Can I just copy and RUN it at my server ( http://okay.mine.nu ) ? As it is?


thanks
mattafort
:)

[laserlight]

I would hardly call a single function an API. You can copy it along with the snippet of one way to use it that is in my first post.

[halojoy]

okay i will try
install it in my php development part of my server
and do some testruns



I will be back with Code Critique
because is the function of this phpbuilder board category

Sometimes critique in here is so heavy and upright
... without any due credits or compliments to balance critique
... that people only post code here ONCE
... never comes back again
... and most probably go elsewhere
If they can find any other PHP Scrits Website/Forum.
You think they can ??? :D
Are there any other sites for discussing php scripts and coding ...?


Be Back soon with comments to your script, within max 2-3 days
Regards
halojoy
:)

[halojoy]

hi

to be able to quickly and easy compare your 2005 function version
with the new 2007 version
I setup this roundrobin.php
It is for most PHP coders self-explaining, I hope :)<?php

$n = 4; // number of players in tournament
$functions = 2; // total number of versions of this function

if (isset($_GET['n']) && !empty($_GET['n']) && ctype_digit($_GET['n'])) {
$n = $_GET['n'];
}
if ( $n > 40 )
$n = 40;

$f = $functions;
if (isset($_GET['f']) && !empty($_GET['f']) && ctype_digit($_GET['f'])) {
$f = $_GET['f'];
}
if ( $f > $functions || $f < 1 )
$f = $functions;

// include and run function, using values of $f and $n
include "func.generate-rr$f.php";

echo "generateRoundRobinPairings($n);<br>\n";
echo "Version: $f<br>\n";
echo '<pre>' . generateRoundRobinPairings($n) . '</pre>';

?>


Files, all in same web folder:
func.generate-rr1.php ---- 2005 version include
func.generate-rr2.php ---- 2007 version include
roundrobin.php ------- main script

How to use:
URL/roundrobin.php?n=8&f=2
... where n= number of players ( max 40 players )
... if no value of n, 4 players ( like in original roundrobin.php, see Post #1 )
... and f= function version ( 1=2005, 2=2007 );
... if no value of f, the latest version will be used=highest number=total number of version



halojoy
:)