roncli.com blog
The blog of roncli
roncli.com blog
roncli.com
blog
Profile
roncli
Houston, Texas, United States
Labels
Coding
CTG Music
Editorials
Games
Miscellaneous
Music
Servers
Silliness
Software
Sports
Trax in Space Beta
Weather
Recent Posts
Observing the Swiss
BlizzCon franchise roundup
Attention - Gullibility
AMD 16.5.2 error "Qt5Core.dll is missing from your...
The Observatory
Six Degrees of Confusion
Report Card: 2015
Crypt of the NecroDancer Bard Deathless record
Windows 10 public "beta"
Descent's Potential Ascent
Archives
February 2005
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
June 2008
July 2008
September 2008
December 2008
February 2009
July 2009
August 2009
September 2009
October 2009
November 2009
February 2010
March 2010
April 2010
June 2010
July 2010
August 2010
September 2010
October 2010
November 2010
December 2010
March 2011
June 2011
July 2011
August 2011
September 2011
October 2011
December 2011
January 2012
February 2012
April 2012
July 2012
November 2012
July 2013
April 2014
July 2014
August 2014
November 2014
December 2014
March 2015
April 2015
May 2015
June 2015
July 2015
September 2015
January 2016
February 2016
May 2016
July 2016
November 2016
March 2017
Current Posts
Tuesday, March 07, 2017
Observing the Swiss
Posted: 2:29:00 PM 0 comments
Running The Observatory is super fun. Being a self-proclaimed 6 degrees of freedom junkie, watching pilots pull off incredible moves just to avoid taking an extra 10 points of damage here or there is fascinating.

The format of The Observatory is largely inspired by CoNDOR, the racing league for the game Crypt of the NecroDancer. Over there, they have their main commentator and several referees who work in the background to ensure that everything goes smoothly. However, on The Observatory, I am afforded no such luxury.

Therefore, I've tried to automate as much as I can to ensure that I can spend time focusing on the action rather than on administering of the tournament. To this end, drawing on my experience from making SixBotGG for Six Gaming, I created FusionBot for The Observatory.

This bot takes care of a number of fun (and not so fun) admin tasks, but the one thing I wanted to highlight was the algorithm I created to create a Swiss pairing system for the qualifier tournaments. In a Swiss tournament, everyone plays a round every game, with the idea being that as the tournament progresses you will play opponents who are closer and closer to your skill range.

A manually-ran Swiss tournament often will have the tournament director throwing players who have the same number of wins in a pile, and randomly determining from that pile who plays who. There are ways to ensure people don't play each other twice, and even ways to govern who gets a bye round.

For The Observatory, I had added constraints that required some custom programming. For instance, players can't play each other if neither of them can host a multiplayer game. But as a general algorithm, here's how I managed to get a working Swiss algorithm in node.js.

1) Get a sorted list of players


This part's pretty easy. You want a list of players sorted by their performance.

var eventPlayers = Object.getOwnPropertyNames(event.players).filter((id) => !event.players[id].withdrawn).map((id) => {
    return {
        id: id,
        eventPlayer: event.players[id],
        ratedPlayer: ratedPlayers.find((p) => p.DiscordID === id) || {
            Name: obsDiscord.members.get(id).displayName,
            DiscordID: id,
            Rating: 1500,
            RatingDeviation: 200,
            Volatility: 0.06
        },
        points: event.matches.filter((m) => !m.cancelled && m.winner === id).length,
        matches: event.matches.filter((m) => !m.cancelled && m.players.indexOf(id) !== -1).length
    };
}).sort((a, b) => b.points - a.points || b.ratedPlayer.Rating - a.ratedPlayer.Rating || b.matches - a.matches || (Math.random() < 0.5 ? 1 : -1));

Here, I get all of the players in the tournament that haven't withdrawn and return an array that includes the player's ID (which for a Discord bot is simply their Discord ID), their player information for the tournament, their ELO, the number of wins they have in the match, and the number of matches they play. We then sort this so that the people with the most points are on top, and break ties on ELO, least number of matches played, and in the case that everything is even we just flip a coin.

2) For each player, match them to a potential opponent


Here, we create a recursive function that attempts to match players based on a set of criteria. In that function, we get the players that have yet to be matched up, and find potential opponents for the first player in that list.

var remainingPlayers = eventPlayers.filter((p) => matches.filter((m) => m.indexOf(p.id) !== -1).length === 0),
    firstPlayer = remainingPlayers[0],
    potentialOpponents = remainingPlayers.filter(
        (p) =>
            p.id !== firstPlayer.id &&
            event.matches.filter((m) => !m.cancelled && m.players.indexOf(p.id) !== -1 && m.players.indexOf(firstPlayer.id) !== -1).length === 0 &&
            (firstPlayer.eventPlayer.canHost || p.eventPlayer.canHost)
    );

You see here that the list of remaining players can't exist in my "matches" array. We get the first player and a list of potential opponents. Opponents cannot be yourself, cannot have been already played, and as is a special case either you or your opponent must be able to host a game. Inside the recursive function, if there is only one player in "remainingPlayers", we check to make sure that the player hasn't had a bye before. That is, if they've played as many matches as there have been rounds in the tournament, the bye is okay. If not, we fail attempt at making a matchup. Failed attempts get interesting, and we'll get to that in a moment.

if (remainingPlayers.length === 1) {
    if (firstPlayer.matches >= event.round) {
        return true;
    } else {
        return false;
    }
}

Now we start a loop through potential opponents. As long as there is a potential opponent available, we will try to assign them the match until we run out of opponents. How we determine who to match an opponent up is where the fun math comes in:

let index = Math.floor(potentialOpponents.length / Math.pow(2, event.round + 1));

With this formula, in an 8-person tournament, the top player will play the 5th seed in round 1, the 3rd seed in round 2, and the 2nd seed every round thereafter (assuming all other conditions for being a potential opponent have been met). This is far better than throwing names into a pile and drawing randomly. Since it uses math, it makes later round matches more meaningful, and allows for earlier matches to be scheduled fairly. Here's the loop in its entirety:

while (potentialOpponents.length > 0) {
    let index = Math.floor(potentialOpponents.length / Math.pow(2, event.round + 1));
    matches.push([firstPlayer.id, potentialOpponents[index].id]);
    if (remainingPlayers.length <= 2) {
        return true;
    }
    if (matchPlayers()) {
        return true;
    }

    matches.pop();
    potentialOpponents.splice(index, 1);
}
return false;

We push the match onto the matches array, but if we don't ever return true because we run out of remaining players or we can't match future players, we basically back the match out of the matches array and try again until we run out of matches to try. The "matchPlayers" function is our recursive function this resides in.

3) Determine who's home


In chess, there's a concept of determining who gets the white pieces. In Descent, it's about whose home level you're playing in. Here in The Observatory, we don't want people playing home or away too many times in a row, so we have a way to make sure that happens as infrequently as possible:

match.sort((a, b) => (
    (event.matches.filter((m) => !m.cancelled && m.home === a).length - event.matches.filter((m) => !m.cancelled && m.home === b).length) ||
    (event.matches.filter((m) => !m.cancelled && m.players.indexOf(b) !== -1 && m.home !== b).length - event.matches.filter((m) => !m.cancelled && m.players.indexOf(a) !== -1 && m.home !== a).length) ||
    (Math.random() < 0.5 ? 1 : -1)
));
eventMatch.home = match[0];

The "match" is the array of players, and we sort the array in a way that makes it so that the player who has played home the least gets it next. In the case they've both played home and away identically, we flip a coin.

Summary


Putting together a Swiss algorithm for pairings wasn't too hard, and in fact was more about getting all of the nuances of a Swiss tournament just right. A lot of trial and error was had, and the first two seasons of the Observatory resulted in some pretty spectacular failures. But the code is pretty solid now, and you can find the whole function under "generateround" in fusion.js. I would like to break this algorithm out of the bot and into its own NPM module at some point, perhaps that's something for a future CodeShare episode!

Labels: , , , ,