EDIT: I'm keeping the most recent versions of all relevant files attached to this OP.I can't decide whether this belongs in the Tournaments subforum or here. I guess I'll put it here. Maybe it will tickle the brains of other software folks out there. Maybe someone organizing their own IRL tournament will find it useful.
So I'm organizing an IRL tournament. The first few rounds will be Swiss rounds and I wanted to write a script to automate the process of making pairings for these rounds. I did a little bit of research but there doesn't seem to be much out there in terms of algorithms or existing software for this, and even if there was, Dominion has some extra constraints that would probably complicate things. I wrote a script (which I'm attaching to this post, for the curious -- if anyone would like to play around with it and try to find bugs I certainly won't complain
there are some things that are kind of hackish, though, sorry about that.)
Unique Constraints:
- My biggest constraint is sets of base cards. As it turns out, for a 2P tournament I can accommodate up to 2x+1 players given x sets of base cards -- I can have a three-player game if necessary for an odd number of players. It gets a little hairier if there are 12 or less people in some cases, but the goal is to create livable matchups without adding in any extra tables for number of players > 12. I really want to have tables set up with kingdoms that don't change throughout this process. Having the 3P game switch between tables is probably just fine but otherwise I don't want to be messing with the tables. This adds the constraint that a player can't sit at the same table twice. In fact, while most Swiss tournament constraints are pretty flexible, this one is a dealbreaker.
Regular Swiss constraints:
- Try to minimize pairing players with very different scores.
- Try to minimize pairing players who have already played each other (less important than having similar scores).
So the way I've ended up implementing the interesting part of this is like so:
- Before giving up and saying we need to add more tables to make matchups possible, we have to brute-force through every possible combination. I don't know of an elegant way to get around this, but luckily the only way this will happen for large tournament sizes is if you play more rounds than Swiss tournaments really want to play, so this shouldn't come up in practice.
- Once a pairing is generated, we check to see if it's possible to assign each pairing to a table that none of them have already played at. If we can, then we're done; if not, then keep going and try the next pairing. I'm not positive that my algorithm for pairing people together is perfect but it seems OK.
- I have two recursion functions that I use called SmartRecurse and DumbRecurse. DumbRecurse just pairs all remaining people left together just going down the list sorted by their scores. It tries that and if it doesn't work out, it gives up.
- SmartRecurse will try looking through all ways to pair the top remaining player with someone within 2 points of their score that they haven't played (first calling DumbRecurse to fill out the rest of the matchups, then SmartRecurse if none of the DumbRecurses work out). If that fails, we widen the search to include people that have already been played, DumbRecurse first then SmartRecurse like before. If that fails, we try including everyone else, Dumb then Smart. If all of this fails, it can only be because we need more tables, so it will prompt the user to add another table and try again.
- DumbRecurse isn't technically necessary, but I think it improves the performance and it pushes the priority toward having people at the top play opponents who are close to them in the score. I've tweaked this algorithm several times and this has given me results that look the most pleasing to me in all cases, so that's why I've ended up on this.
If there are any thoughts or criticisms on this, I'd certainly like to hear them. I'm not convinced that any of the parts of my algorithm are optimal. It's also pretty specific to this tournament format and the UI is something I just threw together and is probably far from perfect -- if there are ways to make this extensible I'm interested in that too. It may not actually be that difficult to make this work for a tournament that prefers 3P games as opposed to 2P games, though the assumption that you should be able to play enough rounds without adding tables and while having good matchups will probably change, so the priorities may be different, which could affect implementation significantly, so maybe not.
But one day, the dream is to have someone else moderate the tournament with the help of this script, so all they would need is to be able to resolve rules issues and make those calls, and then I can play in the tournaments!