Observing the Swiss

Posted
Chess Coding Descent Swiss The Observatory
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!

Comments

Add Your Comments

roncli.com Blog
This is my blog where I give my thoughts and opinions on various topics and share my creative endeavors with the world. I run two personal blogs, but combine them here for ease of access.

Blogger - My oldest blog using the Blogger platform contains posts full of opinions, gaming, and code.

Tumblr - Tumblr posts are all about my creative side, containing music, videos, writings, and updates on my web creations.

You can select a category below to view the latest post, or browse thorugh the posts using the navigation found at the top and bottom of each post.
Categories
Coding (167)
Life (138)
Gaming (117)
Music (64)
World of Warcraft (48)
roncli.com (42)
Software (36)
Servers (29)
Hurricane Rita (27)
Six Minutes To Release (27)
Screenshot (25)
Hurricane Ike (24)
Projects (24)
Silliness (21)
Trax in Space (21)
Cent (19)
Crystal Space (15)
OSMusic.Net (14)
Blog (13)
Editorials (13)
LibWowArmory (13)
Lyrics (13)
roncli Productions (12)
VB.NET (12)
Descent (11)
LibWowAPI (10)
Descent 3 (9)
Due Process (9)
Backup (8)
CTG Music (8)
Node (8)
Overload Teams League (8)
Six Gaming Podcast (8)
ASP.Net (7)
Azure (7)
Buffalo (7)
League of Legends (7)
NWS (7)
Rendr (7)
SETI@Home (7)
The Nightstalker (7)
Video (7)
Diablo III (6)
Hard Drives (6)
Logs (6)
Windows (6)
BOINC (5)
Cent Credits (5)
Cent Main Theme (5)
D3DSN (5)
Descent: Underground (5)
FreeBSD (5)
Google Desktop (5)
Google Earth (5)
Outpost Music (5)
Overload (5)
Ron's Bronze Plays (5)
Sports (5)
UPS (5)
Birthday (4)
Buffalo Sabres (4)
Constellation (4)
Everytime (4)
JavaScript (4)
Preview (4)
Pwned Print (4)
roncli's Dumbass Award (4)
San Antonio (4)
Sigh of Excitement (4)
Six Gaming (4)
Steam (4)
Stripped Down (4)
The Observatory (4)
trac (4)
Twitch (4)
Visual Studio (4)
Winamp (4)
AJAX (3)
All In My Head (3)
Blackjack (3)
Chess (3)
Crypt of the NecroDancer (3)
D3TL (3)
DCL (3)
Gate (3)
Given Up (3)
Guitar (3)
Inspiration Edit (3)
jQuery Default Button (3)
MAME (3)
MediaTagConverter (3)
ModPlug (3)
NeonXSZ (3)
NetHack (3)
Numbers (3)
Paper (3)
PHP (3)
Rawr (3)
Sift (3)
SQL Server (3)
Tumblr (3)
Vision (3)
Year in Review (3)
AM Browser (2)
Asana (2)
ASP.Net RSS Toolkit (2)
Bicycle (2)
BlizzCon (2)
Cheevos FTW! (2)
Crazy Browser (2)
Descent Champions Ladder (2)
DMTB (2)
Docker (2)
Elbow (2)
Eternally (2)
Evans Blue (2)
Fire In My Heart (2)
Games (2)
GitHub (2)
GTR (2)
Houston Astros (2)
How To Play (2)
Hurricane Katrina (2)
iPhone (2)
IRC (2)
IsItUp (2)
Las Vegas (2)
Legs (2)
LibBeImba (2)
Minnesota Wild (2)
Miss Driller (2)
Module Sixteen (2)
Monitor Resolution (2)
NeKo (2)
New Zepsi Industries (2)
Niagara Falls (2)
Novus Compo (2)
Pittsburgh Penguins (2)
Poker (2)
Pwned Cars (2)
Reinstall (2)
Remake (2)
Retro (2)
roncli Productions Intro (2)
San Francisco (2)
San Francisco Rush 2049 (2)
slammy (2)
Sleep (2)
Solar (2)
SoundCloud (2)
Stress (2)
Strings (2)
Tempurpedic (2)
The Editor (2)
TNS Raw (2)
TopCoder (2)
Troupe (2)
w.bloggar (2)
Wedding (2)
XAML (2)
You (2)
Zepsi (2)
#modarchive Story 2 (1)
#occupygregstreet (1)
Absolute C++ (1)
Achaea (1)
Acronyms (1)
AdAware SW (1)
Adobe Acrobat (1)
AdventureQuest (1)
Alaska (1)
allen one (1)
AMD Settings (1)
Analyze (1)
APIs (1)
app.config (1)
Art (1)
ASSP (1)
Audiosurf (1)
Aveyond (1)
Awakening (1)
Bellaire (1)
BitTorrent (1)
Black Ox II (1)
Blackberry (1)
Blender (1)
Blogger (1)
BOINC Synergy (1)
BoincView (1)
Boom Bitches! (1)
Browserify (1)
Bullseye (1)
Byline (1)
CAD-KAS PDF Reader 2.4 (1)
CAPTCHA (1)
CDBurnerXP Pro (1)
CherryOS (1)
ChessCli (1)
Chick-Fil-A (1)
Child Controls (1)
clones (1)
ColdFusion (1)
Come Back To Me (1)
Compo (1)
Constellation Main Theme (1)
Cooking Lili (1)
Core Decision (1)
Crystal (1)
Databinding (1)
DataGrid (1)
DataGridView (1)
Deadly Drums (1)
Decade (1)
Dell (1)
Demogorgon (1)
Descent Rangers (1)
Diabetes (1)
Diamond Problem (1)
Doge2048 (1)
Doom's Day (1)
Double Buffer (1)
Dr. Jeffrey Masters (1)
Drama (1)
Dreamweaver (1)
Dudley's Dungeon (1)
Einstein@Home (1)
Ellon in the Dark (1)
Elon Musk (1)
EveryDNS (1)
Evolution (1)
Eyes (1)
Fedora Core 6 (1)
FeedPage (1)
Fiddler (1)
FlowDocument (1)
Foobar 2000 (1)
Foxit Reader (1)
Galveston (1)
Geocore (1)
GMail (1)
Google Calendar (1)
Google Chrome (1)
Google Pages (1)
Google Wave (1)
Grid (1)
grl (1)
Grooveshark (1)
Grunt (1)
GTR2 (1)
Guitar Solo (1)
Hackers (1)
HCC (1)
Hearthstone (1)
Heroes of the Storm (1)
HomesickAlien (1)
Houston Aeros (1)
ICallbackEventHandler (1)
If Paige Wins (1)
IIS (1)
Inno (1)
Internet Explorer (1)
Interview (1)
iPad (1)
Iron Chouquette (1)
Irrlicht (1)
Jaded (1)
jQuery UI (1)
jQuery UI Scroll Menu (1)
JW Player (1)
Kado Kado (1)
Kaspersky (1)
KFOS Inner Space Radio (1)
Know What (1)
Kromaia (1)
Let It Ride (1)
Let's Encrypt (1)
Let's Play (1)
LibWowHeroes (1)
LifeCast (1)
LINQ to Entities (1)
Linux (1)
Liquid Wars (1)
ListView (1)
Loading (1)
Lukan Schwigtenberg (1)
Mac (1)
MadTracker (1)
Mastodon (1)
Melbourne (1)
Melt (1)
Message From Beyond (1)
Micro Center (1)
Mistakes (1)
Monitor (1)
Mouse (1)
Moving (1)
Mr. Driller (1)
MSDN (1)
NASCAR SimRacing (1)
Network (1)
New Year (1)
olmod (1)
On Fire Series (1)
Opalus Factory (1)
Open Labs (1)
Open Source (1)
Operation Payback (1)
Overwatch (1)
PearPC (1)
Phony (1)
Piano (1)
Pingle (1)
pogo.com (1)
PowerStrip (1)
Programming (1)
PSP (1)
PXO (1)
Quadra (1)
Radeon (1)
Radio Shack (1)
Rant (1)
RedHeat (1)
Reject (1)
Release (1)
Religion (1)
Rendr Template (1)
Renegade (1)
Retrovirus (1)
RIP (1)
RockMelt (1)
Scott Hanselman (1)
Self-Destruct Sequence Podcast (1)
Showsan (1)
Silverlight (1)
Sitemap Generator (1)
Smoke (1)
Sol Contingency (1)
Sound Blaster Audigy (1)
Speedrun (1)
Spelling (1)
SQL Reporting Services (1)
SSL Certificates (1)
Stanley Jakubowitz (1)
Starbase Arcade (1)
Starcraft II (1)
Starting All Over (1)
Story (1)
Sublevel Zero (1)
Swiss (1)
Tetris (1)
Thanksgiving (1)
The Crossroads (1)
The Time Now (1)
The Wight to Remain (1)
Time and Date (1)
Toronto (1)
Torrent Keeper (1)
Total Bollocks (1)
Trans-Siberian Orchestra (1)
TraxSurf (1)
Trillian (1)
Twitter (1)
Typing (1)
Ultimate Boot CD (1)
UpdatePanel (1)
US Interactive (1)
Video Bob (1)
ViewState (1)
Vince Young (1)
Vincent Lau (1)
Vocals (1)
Voyage (1)
Walter Savitch (1)
Warlords of Draenor (1)
Weather (1)
Westward (1)
What Do I Know (1)
WikiLeaks (1)
Windows Defender (1)
winLAME (1)
Winter Classic (1)
Word Field (1)
World Record (1)
Worst Things in the World (1)
WPF (1)
Xamarian (1)
XBox (1)
XM Radio (1)
XML Web Services (1)
Yahoo! Pipes (1)
Yes (1)
You Are Not Alone (1)
Share This Page
Social Media
Ronald M. Clifford
@roncli @mastodon.social

"I'm Sorry, What?!" The biggest bailout in the history of Descent II! youtube.com/watch?v=GLlTk7wa59

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

“BART anime merch" are three words that I would not have expected to go together, but here we are. railgoods.com/bart/anime/

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Does anyone else sing the chorus to "Cherish" by Kool & The Gang to themselves whenever they play or watch streams of Balatro? Or is that just me?

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

I'm fact that's what Lingo needs: a "phone" block. The clue is an incorrect autocorrected form of the answer. 🙃

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

It's like my phone knows I've been playing Lingo. I typed in "exited" and my phone was all:

⬜️ EXCITED ------
▪️
▪️

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

@arborelia Bag-les.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

A comparison of the classic Tetris and Descent communities. Not a post I write lightly, either.

roncli.com/blogger/37031578090

Reply Boost Favorite
martin
@luftlesen @mstdn.jp

Aptiz played #Pentis again. In the beginning you can see roncli asking in the chat for the right version. About an hour later, he broke the #PentisRankings record with 60K ! Congratulations roncli 🏆 🎉
twitch.tv/videos/2052528360?sr

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Yeah, it's season 11. But the OTL Season 6 highlight reel is up, this time Fireball has taken the reins! Check out this video jam packed full of kills, deaths, silliness, and Sirius puns. youtube.com/watch?v=SXstLVjnaG

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Over on , someone retweeted sympathy for the people being laid off today...

...and then said that Amazon Games was hiring. You know, the one that just had layoffs in NOVEMBER.

Honestly? Tech sucks right now.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Seriously. Why is it called Sagittarius, A Star? Clearly, it's Sagittarius, A Black Hole. Silly astronomers.

Reply Boost Favorite
Cultural Historian: Dr. RGST
@DrRGST @mastodon.social
Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

This eslint/stylistic breakup is going to give me a headache. Don't developers have something better to do than give other developers busywork?

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Bing is so bad. otl.gg is being blocked in their search results, and Bing webmaster tools are absolutely useless, not telling me why it's being blocked.

Does anyone know of some way to get a human to look at this and see what's wrong with it?

Reply Boost Favorite
Olivia W'
@WLivi @retro.pizza

it's not actually common for real hackers to use two keyboards at once; that's just a stereo type.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

I got my wish. 🤒

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Me and my wife, despite buying a house of nice size, always seem to get in each other's way, be it in the kitchen, on the stairs, it doesn't matter. She's all up in my two square feet.

I often joke that all I want for Christmas is my two square feet.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Update 2: The record that beat Blue Scuti stood for one day. Blue Scuti got it back.

Reply Boost Favorite
🌪 MikeMathia.com 📡
@mikemathia @ioc.exchange

#C++

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Update: This record stood for 1 day.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

I got the honor and privilege of calling the NES Tetris NTSC world record today while running Classic Tetris Wars on my Twitch channel for the very first time. It was thrilling. Congratulations to Blue Scuti for his 6,609,220 level 153 performance. clips.twitch.tv/DiligentDeadGo

Reply Boost Favorite
Yogthos
@yogthos @mas.to
Reply Boost Favorite
TwistBit
@TwistBit @musicians.today

like, you used to use a phone line to access the internet

now the internet is accessible on your phone

nothing has changed actually

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Six Degrees of Sunday returns Sunday, January 7th, at twitch.tv/roncli. Cya there!

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Are you ready to get Six'd Off?

Six Degrees of Sunday, my 6DoF long play Twitch series, is getting revived for 2024. Plus, I will be producing Six'd Off, a companion YouTube series showcasing each game.

Check out the announcement for the game list and more! youtube.com/watch?v=yeRbjjpQVZ

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

So I started a fresh YouTube channel some time ago, and yesterday I released the first real video to it.

Check out highlights from Argus Industrial Moons' run to the OTL Season 10 Best of the Rest title! youtube.com/watch?v=Z2x-GGW9FY

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

I guess that qualifies as a "log"...

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

People at work are calling Kubernetes K8, and I hate it. It's not "Kubernete"!

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Want a preview of what CTWC will be like next weekend from a gameplay perspective? CTL Season 22 finals starting now.

twitch.tv/classictetrisleague

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

No airport hell this morning, but you know that lady that talks about security at literally every airport? I just realized, she sounds old AF.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

If this security line posted signs "5 minutes from this point", "10 minutes...", etc., They'd have to post them every foot.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

I'm sorry, what?

Reply Boost Favorite
Robin Ward
@eviltrout @carpdiem.online
Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Did I miss Elon making another purchase? twitter.com/unity/status/17016

Reply Boost Favorite
Konstantinos Dimopoulos
@konstantinosd @mastodon.gamedev.place

That's a lovely free bundle of books for people interested in getting into games programming: fanatical.com/en/bundle/intern

#gamedev #book #free #programming

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

Use TypeScript they said. It'll be better they said.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

If you know, you know.

Reply Boost Favorite
Ronald M. Clifford
@roncli @mastodon.social

@shanselman Speaking of Overload, here's something you may be interested in... recently, some community members released "Overload First Strike", a single player Overload campaign that is a complete remake of the original Descent First Strike campaign.

overloadmaps.com/overload-firs

It can work with just the original game, but it works best with "olmod" as it takes advantage of some of the features it provides: olmod.overloadmaps.com

Reply Boost Favorite
Scott Hanselman 👸🏽🐝🌮
@shanselman @hachyderm.io

@PossiblyMax @deepthaw ya and there are new remakes of Descent like Overload that are enhanced and there’s even hardware that Vic Putz made to make the Space Orb look like a controller with NO drivers. Works on all operating systems hanselman.com/blog/bringing-th

Reply Boost Favorite
Join roncli on Discord!
Join the roncli Gaming Discord server for discussion about gaming, development, and more!
roncli.com Media Player