<html>

<head></head>

<body>
    <div class="item">
        <div class="item-header">



        </div>

        <div class="item-body">

            <p>TLDR; Do you want to organize a tournament where the pairing system is round robin but some players need to play against other players at a specific time? This <a href="https://gist.github.com/e4c5/31e37c374df53fd68666">gist</a> is what you are looking for. If you want the full story, read on.</p>

            <h3>The Story</h3>

            <p>On friday evening, I got a call from the tournament director of <a href="http://scrabble.lk/" style="background-color: rgb(204, 222, 221);">Sri Lanka Scrabble</a>. he wanted to know if I could write a bit of code for him to change the pairing of the Premier Players Tournament - a round robin event. Now you might read Scrabble and Sri Lanka in the same sentence and decide to move on, but hold it right there, Sri Lanka is fast on it's way to being a global Scrabble power house. For example the young scrabblers won six prizes at the World Youth Scrabble Championship three months ago. But I digress.</p>

            <p>An odd number of players take part in this Premier Players Tournament and that means there is a bye. Another participant is <a href="https://people.csail.mit.edu/jasonkb/quackle/">Quackle</a>. Sometimes players ask to receive the bye in a certain round so that they can rush out and attend to pressing matters in the middle of the tournament. Or if they get the bye at the start or end of the day, they can then show up later or leave early. On this occaision five of the players had wanted the timing of the bye fixed and two others wanted to play against Quackle in a specific round.</p>

            <h3>The Berger Table</h3>

            <p>If only the bye needs to be accommodated, it can be done very easily just by changing the seeds. The algorithm to generate a Berger table is described on <a href="https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm">Wikiepdia</a>, thus it's easy to see that if someone wants to have the bye in the first round, he should be given the first seed and Bye the 10th seed (or vice verce).</p>

            <p>As pointed out by my friend Jayendra De Silva (former Tournament director for Sri Lanka Chess), you can fix the bye even for all eight players simply by changing the seeds and it can be done manually even with pen and paper</p>

            <p>If in addition to 'fixing the bye' one players wants to fix a time for the game against Quackle, that can be arranged by changing the seed for Quackle. Trouble arises when more than one player wants to player Quackle and Bye at certain times. Some combinations turn out to be impossible. In fact I spent quite a bit of time trying out various algorithms to try to 'flip pairings'. I soon reached the conclusion that the combination asked for was impossible but had not mathematical proof. So I ended up writing a brute force method to produce all possible combinations and to see if any one of them met the requirements.</p>

            <p><span style="color: inherit; font-family: inherit; font-size: 24px;">The Numbers</span></p>

            <p>For 9 or0 players, there are 3,628,800 possible pairings but it takes only a little more than half a minute to produced them all. However this is an O(n!) problem so it might well be impossible for twenty four players. Number of possible pairings is huge and bigger than even Avagadro's number. Trying out all combinations didn't produce a match, but the code can be used to generate customized round robin pairing schedules for many situations.</p>

            <p>Since many tournament directors probably will not be able to make much use of the code as it is, I will be releasing an online pairing generator real soon. There are quite a few of them already but none of them allow you to reschedule games as described above.</p>

            <p>&nbsp;</p>
            <style type="text/css">
                .gist-data {
                    max-height: 500px;
                }
            </style>


        </div>
    </div>


</body>

</html>

Monthly Archives for 2016 02

Modified round robin pairing.