roncli.com blog: March 2017

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: Chess, Coding, Descent, Swiss, The Observatory