|
|
|
| Tuesday, March 07, 2017 |
Observing the Swiss
Posted: 2:29:00 PM
|
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
|
| Wednesday, May 17, 2006 |
Projects!
Posted: 1:59:00 AM
|
I decided to jump into Microsoft Project to organize my list of projects. My god, do I have a lot of projects. Not counting weekly tasks, I have 27 projects. Twenty-seven. When am I going to find time to do them all?
I suppose that's what Project is for, finding the time to do them all. It's not very encouraging at first glance, but when I glaze over the details, things do move along, if slowly. I doubt I'll ever complete all 27 projects, though, as certain projects, such as the D3TL 2003 upgrade (yes, I know it's 2006), D3DSN, and MediaSmarts probably isn't going to happen. They are the absolute lowest on my priority list right now, although I will at the very least review where these projects stand before June is out.
My goal is to get PwnedCars done before my vacation in June - by the way, I'm leaving for Melbourne, Australia on June 17th - and get some significant progress done on the new roncli Productions website. After that, I've got some long-term projects, including Cent, which I've mentioned here before. Since I've actually had to use C++ at work, I'm a bit more comfortable with the language, and hope that can help me get more done on Cent.
Here's a large (but incomplete, I must have some secrets!) selection of the 27 projects I have, for your interest:
modplug.roncli.com - Where ModPlug used to be hosted before the first crash, this box now holds some websites for MisterX (Kim), and its future is unknown at the moment. It probably will turn into a hosting box for the next modplug.com, but that's up to Kim & LPChip. (By the way, modplug.roncli.com technically isn't an address, it's just my designation for the computer itself.)
reborn.roncli.com - Reborn is my router, running FreeBSD 6.1 just like the ModPlug box. It's also my network's backup server with 300 GB of storage space. It backs up everything, including my MAME collection, OSMusic.Net, and all of the photo's Kathy's got stored on her computer.
successor.roncli.com - This is my main computer, and the reason it's a project is because I want to reinstall Windows. Yeah. That's going to be a fun day or three.
www.roncli.com - This is the Windows server where all my ASP websites live. The only thing I need to do is figure out how to backup the databases so that Backup can pick them up and put them onto Reborn.
Outpost Music - My music group that I haven't really done much with in a year and a half. Well, it's high time I got the forums working. I'll likely work on that after vacation.
The Nightstalker - Not to be confused with http://www.roncli.com, http://tns.roncli.com is solely devoted to my music. However, there's only 2 songs listed there right now. Considering I've released over 50, that's got to change.
Chess - Not sure what to call this yet, but I'm really interested in making a site with Java that will allow people to solve chess puzzles, play games, chat, and more. Definitely a long termer.
Cent - I really haven't come out and said what this is, but it's my dabbling into CrystalSpace to see if I can write a legitimate 3D first person shooter. It uses Crystal Space as its rendering engine, so once I understand it - and I understand a lot of it right now - writing the necessary code should just be a matter of time. How far I go with it depends on how well it runs.
Solar - Solar is a TCP/IP Text Processing Engine. I can hear it now. Huh? Basically, it is a telnet server that allows multiple connections, allowing them to interact. It would be great groundwork for a MUD-type application, but I really haven't had any plans to do anything with it. Putting it in as a project at least gives me an opportunity to improve it.
ChessCli - This is definitely being called ChessCli, and is my attempt at creating a WinBoard chess engine.
Outpost IRC Bot - Not sure if I even want to continue this project, but it was designed to be a cutthroat one hour compo manager. I had a lot of ideas for this about 4 years ago. Whether I can recall them, well, who knows.
roncli.com Logs - I'd really like to expand http://logs.roncli.com, as I'm recording a lot more information than I'm displaying. I'd also like to work on the performance and get this thing smoking along.
Torrent Keeper - Frustrated with the lack of true multithreading BitTorrent applications, I started Torrent Keeper about a year ago. It hasn't gone anywhere, but I figure this will likely follow Backup and Due Process as one of the first few roncli Productions offerings.
Word Field - A silly idea of mine that I'd like to follow through on eventually. Combine word scramble, mine sweeper, and some aspects of Press Your Luck, and you've got a good idea what this game will be like.
D3TL 2003 - As mentioned above, I started to do an upgrade of D3TL in 2003. The database was really badly designed, even though it was much better than just updating a Flash file every now and again. Problem is, I don't play Descent anymore, and given that there hasn't been a real game played in months, I might be better off saving an idea like this for Cent if I ever finish it.
D3DSN - This is the Descent 3 Dedicated Server Network. Yes, it's still up. No one uses it though, because the software's buggy. When I went from Visual Basic 6.0 to .NET, I really messed up with some timing issues. What I really need to do is add true threading to that application, but the last time I tried to test it with Esa, I ended up giving up because he wasn't seeing the new web services for some reason or another. Again, if I ever pick this up, it will probably be for Cent instead.
IsItUp - Recall September of last year when I high-tailed up to Lubbock, TX, to escape Hurrican Rita. While I was up there, I was interested in whether or not my servers were up. So, I wrote IsItUp, an insanely simple app. I might expand it a bit, but probably will end up being released as freeware.
Numbers - Some people write "Hello World". I write Numbers. I've written this game in many languages, including TI99-4 Basic, Macintosh QuickBasic (OS 7.0 days!), C128 Basic (dual screen!), and finally Visual Basic 6.0. It's a rather addicting game, and over the years I've added some features to it that make it even more challenging. I want to do something with it, I just don't know what yet.
roncli.com Blog - Yes, the very same one you are reading! I'd like to add some things to the blog, maybe my BOINC stats, maybe my Google Calendar agenda, perhaps some other widgets that will make the site more interactive.Labels: Blog, Cent, Chess, ChessCli, Coding, D3DSN, D3TL, Descent 3, IRC, IsItUp, Logs, ModPlug, Numbers, Outpost Music, Projects, roncli.com, Solar, The Nightstalker, Torrent Keeper, Word Field
|
| Wednesday, November 23, 2005 |
0-0-0+
Posted: 12:36:00 AM
|
I just think it's a cool move. Meant for defense, you can really demoralize your opponent by castling queen-side while at the same time putting them in check with your rook.
After playing a few games at work, I may actually be getting back into chess again.Labels: Chess, Games
|
|