Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: [1] 2  All

Author Topic: Swiss tournament pairing script  (Read 14990 times)

0 Members and 1 Guest are viewing this topic.

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Swiss tournament pairing script
« on: September 09, 2015, 10:56:53 am »
+2

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! ;D
« Last Edit: February 04, 2016, 03:36:09 pm by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Drab Emordnilap

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1832
  • Shuffle iT Username: Drab Emordnilap
  • Luther Bell Hendricks V
  • Respect: +1886
    • View Profile
Re: Swiss tournament pairing script
« Reply #1 on: September 09, 2015, 01:02:17 pm »
+3

I know nothing about python, but some about tournament structure, so bear with me:

When you say you're matching players with similar score, you mean "tournament standing", not "game VP score", right?

I agree with "no player plays the same table twice" being a hard constraint. I feel like "no player plays the same opponent twice" should also be a hard constraint. Is that not possible to guarantee?


I'm certain there's a reason for it, but can you explain to me why this wouldn't work as a method for creating match pairs? For this example, let's say we have 14 players total.

First round, random pairs. Easy.
Subsequent round, sort players by W/L records. So round 2 you would have

a 1-0
b 1-0
c 1-0
d 1-0
e 1-0
f 1-0
g 1-0
h 0-1
i 0-1
j 0-1
k 0-1
l 0-1
m 0-1
n 0-1

Randomize the order of people with identical records,

c 1-0
e 1-0
d 1-0
a 1-0
b 1-0
f 1-0
g 1-0
n 0-1
l 0-1
k 0-1
i 0-1
m 0-1
h 0-1
j 0-1

Group into pairs,

c 1-0
e 1-0

d 1-0
a 1-0

b 1-0
f 1-0

g 1-0
n 0-1

l 0-1
k 0-1

i 0-1
m 0-1

h 0-1
j 0-1

Check each pair to see if it matches a "used pair", starting from the top. If a pair matches a "used pair" (we're looking at c-e right now), swap the bottom member of the pair (e) with the next member of the list (d). Check the new pair (c-d). If it's also "used", swap the new bottom member (d) with the member 2 down (a). Repeat this until the pair is un"used". (If this fails, that means c has played every other player already. Unlikely, but error catch here for that.) If the pair isn't "used", move to the next pair in the list. If the last pair in the list is used, do the same thing, except move upward -- swap the top member with the one above it, and so on, until you make a valid pair. Now you need to recheck upwards the pairs you modified this way.

This should result in all players paired as closely as possible with someone close to them in tournament record, but never against someone they've already played.

Once all pairs are valid, add those pairs to the "used pairs" list for future rounds to check against.

Each player needs a list of tables they've been at associated with them. Each table gets dealt a pair that doesn't match the table. If this isn't possible (a pair has played between them every table) then add that pair to the "used pairs list" (since they now can't be a valid match), and redeal the pairs with the updated list.

So after writing all that out, I think I basically wrote the same thing you did, except not letting a player play the same player twice. Personally I'm on the side of "make a top player play a lower record rather than the same person they've already played", but I can see both arguments.
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #2 on: September 09, 2015, 02:59:09 pm »
+1

When you say you're matching players with similar score, you mean "tournament standing", not "game VP score", right?

Of course. The tournament format for points is 4 for a 2P win, 2 for a 2P loss, 3 for a 2P tie, then 5-3-1 for 3P games with ties splitting all points evenly between tied positions. If someone leaves early or joins late then they get zero points for rounds they didn't play in; I would deal with "virtual opponents" since I use Solkoff score to differentiate between tied players for ranking purposes, but I'll be having a playoff game to determine who makes it to the next round after the Swiss so it shouldn't ever affect things.


I agree with "no player plays the same table twice" being a hard constraint. I feel like "no player plays the same opponent twice" should also be a hard constraint. Is that not possible to guarantee?

I remember coming up with a situaton where the guy at the top had played everybody within 2 points of him, and I decided I'd rather have him replay one of those people than match him up with someone 3 or more points behind (so more than a whole game of Dominion). This is somewhat arbitrary, and it rarely actually comes up, as it turns out. Most of the test sets of data I came up with ended up matching people 3 or more points apart and didn't end up matching people who had already played each other (and all of these came up with either n<12 or when I had a lot more rounds than Swiss is comfortable handling, so more than log(2)n).

I'm making these rules up; is there a good reason why I should match people 3 or more points apart before rematching people who have already played? I didn't do it this way for implementation purposes


I'm certain there's a reason for it, but can you explain to me why this wouldn't work as a method for creating match pairs?

So after writing all that out, I think I basically wrote the same thing you did, except not letting a player play the same player twice.

This way ends up being a lot like what I did, mostly because my way searches for these things first anyways (that's why DumbRecurse exists, it just blindly matches people up with the next guy down the list and sees if it works, must like your "group into pairs" step).

Your algorithm handles simple cases pretty well, and your "used pairs" thing gives me an idea for a check I can do in SmartRecurse to improve performance -- if the people I'm about to pair together have already played at all tables between the two of them, then just skip it. Extending it can get a little hairy, though.

How do you assign the 3P game if you need one? Swapping and checking gets a little more complicated than that. I ended up having the 3P game towards the bottom of the rankings if possible, mostly for ease of implementation since I couldn't think of any reason to do one way or the other (and I wanted this algorithm to be deterministic).

I wanted to have the option to add a table if matchups were going to be ugly or impossible, so you'd want to have two "used pair" lists -- one for people who have already played each other and another for pairs who have played all tables together, which can be cleared if a table is added.

But these are minor fixes, and implementation of your idea would probably look a lot of like my implementation anyways. In many cases it will end up the same or very similar.


Personally I'm on the side of "make a top player play a lower record rather than the same person they've already played", but I can see both arguments.

I was a little shocked to find so little guidance on Swiss tournament structure. I found myself just making up rules for how to handle it when matchups weren't going to be perfect, which never feels good.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Drab Emordnilap

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1832
  • Shuffle iT Username: Drab Emordnilap
  • Luther Bell Hendricks V
  • Respect: +1886
    • View Profile
Re: Swiss tournament pairing script
« Reply #3 on: September 09, 2015, 03:18:48 pm »
+1

Most of my experience comes from strictly 2 player games (tournament fighters and CCGs), so my go-to answer for odd player counts is adding a bye. In Dominion you can have a 3 player game, but your tournament scoring can be simpler if you limit to only 2 player tables... but people come to tournaments to play, not to win bye rounds. I agree that you want the 3 player table as close to the bottom of the standings as possible.

The main reason to favor "different opponent" over "closer score" is a player experience one, I think. Part of the reason to go to a tournament is to play with different people, and "I already played with this guy -- what gives?" You're right that it won't come up too often, since two players playing each other will tend to push their standings apart on average, so ultimately it's not a big deal either way. MTG goes with "always new opponent", so sometimes you'll be playing someone of a different standing rather than someone your own standing, but balances it out with how tiebreakers work (to determine who makes the cut to the single-elimination top 8 between players of tied win-loss records, they look at the records of each player's previous opponents. The player(s) who played against better placing opponents have better "tiebreakers".)

I know there's software that Wizards of the Coast distributes for swiss pairings for their events for Magic: the Gathering. Here's a link

https://mtgarena.appspot.com/#t6269712744841216

to an online script someone wrote with similar functionality. It generates random pairings, you enter game results, and it pairs up the next round's pairings based on standings, but never then same opponent. Don't know that you could just use this necessarily (can't do 3 player games, for one), but maybe it's useful for something. (That link goes to an example tournament I made up information for.)
Logged

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Swiss tournament pairing script
« Reply #4 on: September 10, 2015, 05:58:39 am »
+1

Funny, I happened to write a swiss pairing generator a few days ago. In that case I didn't have the table constraint that you have and simply needed to pair players, so I could use a polynomial-time minimum-cost general matching algorithm on the backend, for which I used Blossom V. I set up the graph so that players who had already played didn't have edges between them (making rematches impossible), and the cost of each edge would be higher the greater the difference in points between the players, which causes the algorithm to prefer to match players with equal or similar point values. Then the script would randomly select one of the optimal matchings (just by randomly picking one pairing at a time, so it's not necessarily uniformly random w.r.t. all optimal solutions).

In your case, because you're doing three-way matching, solving optimally is probably NP-hard. I think I'd try formulating it as an integer program and feed into an IP solver like SCIP. I think that would be quicker to get going and more flexible than coding the brute force by hand.

One thing worth thinking about is that with a small number of tables available, you may want to be planning ahead for future rounds. For example, suppose you're pairing A-B and C-D this round, and you think next round you might pair off A-C. Also suppose that the only tables A hasn't played are X,Y and the only tables C hasn't played are Y,Z. If this round you put pair A-B on table X and C-D on table Y, then next round you can't pair A-C as there isn't any table they both haven't played. But if you put C-D on table Z instead, then next round A-C can play on table Y. This starts to get into combinatorial design theory if you want to make most efficient possible use of tables, but some heuristics might help without needing to get too fancy, like preferring to place players on tables that their likely future opponents have already played.

Check each pair to see if it matches a "used pair", starting from the top. If a pair matches a "used pair" (we're looking at c-e right now), swap the bottom member of the pair (e) with the next member of the list (d). Check the new pair (c-d). If it's also "used", swap the new bottom member (d) with the member 2 down (a). Repeat this until the pair is un"used". (If this fails, that means c has played every other player already. Unlikely, but error catch here for that.) If the pair isn't "used", move to the next pair in the list. If the last pair in the list is used, do the same thing, except move upward -- swap the top member with the one above it, and so on, until you make a valid pair. Now you need to recheck upwards the pairs you modified this way.
If I understand correctly, this algorithm can fail to terminate on some inputs that have a valid pairing available.

Here's a simple case to demonstrate, although it's artificial in that not every player has played the same number of matches. I haven't checked to see whether it can be extended to a larger case that is more realistic.

Suppose there are four players a,b,c,d. a has played b and b has played d. The unique valid pairing is a-d b-c. But if we begin with standings a,b,c,d, first the algorithm will fix the top pair by swapping b with c, to get a,c,b,d. Then the algorithm will fix the bottom pair by swapping b with c again, to go back to a,b,c,d. Having broken the top pair, it then attempts to fix the top pair again, entering an infinite loop.
Logged

UmbrageOfSnow

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 167
  • Shuffle iT Username: Umbrageofsnow
  • Respect: +301
    • View Profile
Re: Swiss tournament pairing script
« Reply #5 on: September 10, 2015, 02:50:25 pm »
0

I can't talk about the coding, but I agree with Adam's position of preferring repeat opponents over large point disparity.

When I've played games in tournaments I've always been annoyed by decisions the tournament organizers make that bias things away from the most skilled player winning.  Obviously tournaments are too small a sample size anyway, but it just feels bad.  Preferring a much lower ranked player can give one medium-high ranking player a boost over the other guy he's tied with, essentially at random.  That would really piss off the guy tied in points who already played the guy who gets to go up against the bad player.

If it were a ton of rematches every tournament, the rematch thing would be a problem, but happening very rarely, the more fair thing is Adam's original plan.

And when you get the one rematch in the whole swiss-portion of the tournament, that can be kind of neat, like a rivalry.
Logged

Drab Emordnilap

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1832
  • Shuffle iT Username: Drab Emordnilap
  • Luther Bell Hendricks V
  • Respect: +1886
    • View Profile
Re: Swiss tournament pairing script
« Reply #6 on: September 10, 2015, 03:02:41 pm »
0

I can't talk about the coding, but I agree with Adam's position of preferring repeat opponents over large point disparity.

When I've played games in tournaments I've always been annoyed by decisions the tournament organizers make that bias things away from the most skilled player winning.  Obviously tournaments are too small a sample size anyway, but it just feels bad.  Preferring a much lower ranked player can give one medium-high ranking player a boost over the other guy he's tied with, essentially at random.  That would really piss off the guy tied in points who already played the guy who gets to go up against the bad player.

If it were a ton of rematches every tournament, the rematch thing would be a problem, but happening very rarely, the more fair thing is Adam's original plan.

And when you get the one rematch in the whole swiss-portion of the tournament, that can be kind of neat, like a rivalry.

I guess the difference is, are you just doing Swiss, or is the Swiss an elimination procedure to cut to the finals/semifinals/etc? If the Swiss is the whole thing, then yeah, the one of the top two players who gets paired down and wins an extra round because of it is a big deal. But if you're taking the top 4 to elimination rounds anyways, I think it matters less -- The players at the elimination cusp have worse records, and so are less likely to not have a new opponent to play at their current record.
Logged

UmbrageOfSnow

  • Moneylender
  • ****
  • Offline Offline
  • Posts: 167
  • Shuffle iT Username: Umbrageofsnow
  • Respect: +301
    • View Profile
Re: Swiss tournament pairing script
« Reply #7 on: September 10, 2015, 03:04:14 pm »
0

Even if it matters less, it still matters.

Also, Adam's script could be used for either Swiss-only or Swiss-then-elimination tournaments.
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #8 on: September 10, 2015, 03:31:05 pm »
0

The particular tournament(s) I'm doing are Swiss-then-elimination tournaments. In fact, here's a link to the format doc.

Also, most of the time in a 2P tournament you can have all of the cake and eat it too -- you can play people you haven't played at your same score pretty much all of the time. Usually you round the number of players up to the next power of two and play log(2)(that many) rounds, but sometimes in that last round things are a little bit imperfect if you had to round up a lot. And I also wanted to be able to handle playing one or two more rounds after that if necessary, mostly so it could be extensible to 3P tournaments and still make sense (RGG-sanctioned tournaments require as many 3P games as possible and I do want to still have those occasionally).

As I mentioned before, even the way it is with preferring rematches to point disparity, I rarely see rematches actually happen, partially because when two people play each other, it often results in a point disparity anyways so it's easy to find people you haven't played with similar scores.

It looks like there are arguments for doing either way, and I haven't found some "official" or "conventional" way to do it anywhere.


Blueblimp -- your idea for looking ahead might enter into play if you had some way of predicting peoples' skill before the tournament starts, like a seeding. Of course, if you expected to pair A and C next round, then why aren't they playing each other this round? I'm having trouble seeing how you can fit that into pairings reliably -- and of course in the worst case there's nothing you can do if the match doesn't go the way you thought it would. It seems like a slight optimization.

I tried reading about Blossom algorithms and my brain started hurting. I'm not convinced that some variant wouldn't work at all for a 3P game mixed in, but I can't quite wrap my head around that enough to say for sure yet. Do you really think it would be impossible? In any case, the worst-case performance isn't my main concern, most of the time with reasonable sample sizes the script will terminate pretty quickly because it looks for the good things first and you can usually find them, but it would be nice to have it perform well in all cases :)
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Jack Rudd

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1323
  • Shuffle iT Username: Jack Rudd
  • Respect: +1379
    • View Profile
Re: Swiss tournament pairing script
« Reply #9 on: September 10, 2015, 08:00:39 pm »
+1

There's plenty of software for creating Swiss pairings for strictly two-player games. It becomes harder to find it if 3-player games can be added in to the mix.
Logged
Centuries later, archaeologists discover the remains of your ancient civilization.

Evidence of thriving towns, Pottery, roads, and a centralized government amaze the startled scientists.

Finally, they come upon a stone tablet, which contains but one mysterious phrase!

'ISOTROPIC WILL RETURN!'

blueblimp

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2849
  • Respect: +1559
    • View Profile
Re: Swiss tournament pairing script
« Reply #10 on: September 10, 2015, 08:07:07 pm »
+1

I like strongly avoiding rematches in Swiss tournaments, but actually if I were running a tournament then here's something I'd give a try instead of Swiss. The thing I don't like about Swiss is that either you need horribly mismatched "slaughter" rounds/games, OR you need to unfairly hand out starter points to players you think are especially strong (McMahon system).

Instead I'd try using a batch-computed Elo tool such as Bayeselo to compute player Elos after each round, using the games played in the tournament. Then for each round, match players of similar strength according to a mixture of Elo and initial seeding info, and when entering the final elimination bracket, select and seed players according to their Elos only (ignoring the initial seeding). The reason to compute Elos in batch instead of with an incremental algorithm (which is normally what's used for Elo) is that a batch algorithm converges better with a small amount of data, and in a tournament there aren't many games so that's very important.

The advantage of batch Elo over Swiss is that you aren't punished for playing strong players if you're a strong player too, because winning against them helps your Elo more than winning against weak players. That way the tournament organizer is incentivized to make matches as close as possible, as that provides more information to the Elo computation to help its accuracy, unlike Swiss where the tournament organizer is incentivized to make matches _not_ close so that strong players get the points that they need to rise to the top of the standings. With batch Elo, unlike incremental Elo, it's OK for two strong players to play first round, because later results will show that they are both strong, so that the loser of that match doesn't get punished in the standings.

I tried reading about Blossom algorithms and my brain started hurting. I'm not convinced that some variant wouldn't work at all for a 3P game mixed in, but I can't quite wrap my head around that enough to say for sure yet. Do you really think it would be impossible? In any case, the worst-case performance isn't my main concern, most of the time with reasonable sample sizes the script will terminate pretty quickly because it looks for the good things first and you can usually find them, but it would be nice to have it perform well in all cases :)
The Blossom algorithm is complicated (which is why I use somebody else's implementation instead of writing my own) but the problem it solves is simple. You have a graph with n vertices (the players) and m edges (each corresponding to a pair of players who are allowed to pair this round). A perfect matching is a set of n/2 edges such that no two edges have a vertex in common (in other words, the matches for one round). You can also assign costs to the edges (higher cost represents a pairing you'd rather not make, like when two players have different points), and the algorithm can find a minimum-cost perfect matching, which is a perfect matching that minimizes the sum of the costs of the edges it chose. The wikipedia page isn't the greatest but just linking it here anyway: https://en.wikipedia.org/wiki/Matching_(graph_theory).

That only works as a model for selecting pairs of players though. If you want to select triples of (table, player 1, player 2), then it becomes a 3-dimensional matching problem, which is NP-hard. For NP-hard problems, good performance can't be guaranteed on large data sets, but integer programming is a good bet when trying to solve practical examples of NP-hard combinatorial optimization problems. Writing a brute force solver by hand can also work sometimes but with IP you get to use an existing IP solver instead of having to do everything from scratch. That makes it easier to try different things because you don't need to rewrite your solver code, and if you're looking for approximate solutions, the IP solver might do a better job than an ad-hoc approach.
Logged

pst

  • Minion
  • *****
  • Offline Offline
  • Posts: 584
  • Respect: +906
    • View Profile
Re: Swiss tournament pairing script
« Reply #11 on: September 10, 2015, 09:20:20 pm »
0

If rematches is suitable depends on the number of rounds. If the number of rounds is the binary logarithm for the number of players plus maybe two then it works fine without, but the more rounds you have the more you will finish the tournament with uninteresting matchings, and it would be better to have the top players meet each other again instead.

I haven't looked around for software for this for many years, so I'm out of touch, but then for example in US Scrabble you'd usually use n Swiss rounds followed by one or a few "king of the hill" ronds where just #1 met #2, #3 met #4, etc. (with an exception if there already is a clear winner).

When I was into Othello I liked the principles of  the pairing program PAPP which was used there. It simply optimized the pairing for each round where you had a rules file with penalties for lots of stuff, some of which many pairing systems would just forbid. There were penalties for meeting someone with n more wins than you, for playing the same opponent twice, three times, etc., for being the start player k times more than half of the rounds, etc. This worked fine both for a smaller number of rounds and for a large number of rounds.
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #12 on: December 06, 2015, 10:34:13 am »
+1

Update:

I used the 2P script for the tournament I held in October and it went really well. There were no problems and my life was really easy -- I could just focus on answering rules questions and I even had time to talk to people.

The next tournament I'm going to host is an RGG-sanctioned one, which means that as many 3P games as possible should be played, and if the number of people there is not a multiple of 3, then 4P games should be played (and not 2P) games so that no byes are given. I knew I'd have to make some modifications to the script to handle this, but I didn't think it would be as easy as it was. I'm pretty proud of how extensible I made this thing, I really only had to make a couple of small changes and rewrite SmartRecurse and DumbRecurse and everything just worked really well without much fixing at all.

During the process I found a small, basically meaningless bug in the 2P script and so I went back and made a couple of tweaks. I'll attach the source of both of these files to this post.

I've done much more testing on the 2P script than the 3P one, but I want to use it for my tournament on January 30th so by then I will definitely have something that works. If you're interested in using either of these or testing either of these, feel free to do so -- I have some useful little bits for testing.

When you're entering results, if you want to make this part much quicker, you can put in -1 for the table number and it will fill all the tables with a result (first player in the list wins, second player comes in second, etc.) and just move on. If you put in -2 for the table number it will randomly assign a valid game result to each table and move on -- this makes testing much quicker, I've found.

EDIT: a more recent version of this script has been made, it's attached to the OP
« Last Edit: February 04, 2016, 03:36:59 pm by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Elestan

  • Witch
  • *****
  • Offline Offline
  • Posts: 472
  • Respect: +428
    • View Profile
Re: Swiss tournament pairing script
« Reply #13 on: December 06, 2015, 01:03:12 pm »
+1

The next tournament I'm going to host is an RGG-sanctioned one, which means that as many 3P games as possible should be played, and if the number of people there is not a multiple of 3, then 4P games should be played (and not 2P) games so that no byes are given. I knew I'd have to make some modifications to the script to handle this, but I didn't think it would be as easy as it was. I'm pretty proud of how extensible I made this thing, I really only had to make a couple of small changes and rewrite SmartRecurse and DumbRecurse and everything just worked really well without much fixing at all.

I haven't gotten too deep into the code yet, but let me bounce my biggest fear off of you and see whether you think it's handled:

The worst-case scenario is that I get to the final round (#4) of the prelims, and discover that there are only two players left who haven't played table #3, and five players who are forced onto table #4 because they've played every other table.  This problem comes up a lot when trying to seat for the last round of a 4-round prelim with 13 or 14 players (so, 2-3 3P and 1-2 4P games).

Does your matching algorithm head off such possibilities?
« Last Edit: December 06, 2015, 03:24:44 pm by Elestan »
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #14 on: December 06, 2015, 03:55:41 pm »
+1

Without thinking too much about this, I don't know of an algorithm that can prevent that kind of thing by taking match results into account -- if you're that constrained on tables then it seems you want everybody to have a pre-set order of tables that they play on regardless of match results.

Swiss structure, as it's supposed to be based on match results, starts to break down a bit if you play too many games -- it also has a little more trouble with smaller numbers, meaning sometimes you need to have more tables than the minimum required for everyone to have a place to sit. My script accounts for this by forcing a minimum of 5 tables for any number of entrants in a 3P tournament -- I'd recommend having some spare sets ready in case you need to switch out (this is what I do for my tournament). The more tables you have (and I'm not talking physical tables, but kingdoms to play), the more flexibility you get and the more you can accommodate having people play each other based on their score instead of which table they need to sit at.

I will think about this more and I will also research making python code that is agnostic to Python 3+ vs. earlier versions of Python.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #15 on: December 07, 2015, 02:26:10 pm »
0

I've made changes to these scripts so that they should work on both python 2 and python 3. I haven't done rigorous testing to verify it yet, so if any problems come up please let me know. I've attached the updated scripts.

After thinking more about the algorithm, I don't have that much more to add; does it at least make sense what I said?

EDIT: A more recent version of these scripts has been made, they're attached to the OP
« Last Edit: February 04, 2016, 03:37:30 pm by AdamH »
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

Elestan

  • Witch
  • *****
  • Offline Offline
  • Posts: 472
  • Respect: +428
    • View Profile
Re: Swiss tournament pairing script
« Reply #16 on: December 07, 2015, 10:28:02 pm »
+1

After thinking more about the algorithm, I don't have that much more to add; does it at least make sense what I said?

Sure.  The tricky part about using extra sets with a limited supply of physical cards is that making good sets gets progressively harder as you go because you use up your available cards.  I think I'll want to play around with the matchup tool, and see just how many sets it generally wants in order to get through the prelims.

My gut is telling me that perfectly shuffling the players so they have no table replays and minimal player replays actually maps to a cryptography problem relating to hashing algorithms, so I'm going to run it by a friend of mine with a PhD.
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #17 on: February 03, 2016, 07:56:39 am »
+5

I've gotten some feedback about the last tournament I ran related to tournament format. While a lot of what goes on in RGG-sanctioned tournaments in terms of format is determined by RGG (and more is "recommended") I went and re-read the guidance I got and tried to incorporate it with the feedback I received. Here's what I'm working with.
 
My current format (let's assume 18 or more people, the final rounds get shorter and/or don't happen with less people):
- 4 games in the preliminary round. All 3-player if possible, 4-player games if necessary so everybody plays (no 2-player games allowed -- my 2P tournaments end in an elimination bracket that I'm happy with, and RGG says they "do not support or want to see 2P tournaments for Dominion ever" because they "have determined [3P] is the best format for Dominion tournament play". All of this applies to these 3P sanctioned tournaments).
- For a 3P game, you get 5 points for a win, 3 points for second, 1 point for third
- For a 4P game, it's 6-4-2-0
- If players tie, they split the combined points for the positions they tied for (two-way tie for first in a 3P game gives each player 4 points).
- The script I use will pair people with similar scores together and will never allow a person to play the same kingdom twice under any circumstances. Past that, it will try to pair people who haven't played together.
- After 4 games, the nine players with the highest scores advance to the semifinals. If there is a tie, a tiebreaker game is played.
 
- In the semifinals, each player plays three games on the same three boards. Scoring is the same, but all points from the preliminary round are erased and only used for seeding.
- Each player has a predetermined path through the boards. Variety of opponents is attempted but with only three boards, a good job is not done of this.
- If we're out of time, the final standings after three games will be the standings of the tournament, with a tiebreaker game only being played to determine a champion.
- If time permits, the top three scores in the semifinals will advance to a one-game championship. A tiebreaker game will be played if necessary to determine the top three scores. The outcome of this game determines the placement of the top three players in the tournament.
 
 
RGG guidance:
"all players play several rounds with different opponents and then the best players advance to final rounds or a final round, depending on the total number of players"
 
"break ties, when necessary (to advance someone) with a coin flip"
 
"As for the final rounds, we prefer you not have a final round. Let those who advance [play] a few more rounds and then the player with the highest points (4 for 1st, 2 for second, 1 for third) is the winner."

 
It really isn't more specific than this (turns out they don't mention "Swiss" but technically "Swiss" only applies to tournaments where only 2P games are allowed. It extends nicely to this, though). Here are the main differences between what I have and what is recommended:
 
- Coin flip vs. tiebreaker game. Yeah I feel like I made a pretty good improvement here.
- Scoring: it seems RGG likes to give you a little bonus for placing first in a game. I don't have guidance on 4P game scoring. Interesting. I like the idea but I'm not sure how it could extend to 4P games.
- Final round: for some reason I thought having one game to decide everything was preferred by RGG but it turns out to be the opposite.
 
One complaint I got was about the semifinals, with the lack of variety you get with opponents. I also haven't felt super-great about having one final round and it seems RGG doesn't like that either. It seems like I could just make the semifinals a little bit bigger, not have a final round, and just have that be it. This would end up being a big improvement on the format, I think.
 
 
How to improve the semifinals/finals:
With a large player pool, like I have for the preliminaries, I get a lot of flexibility with the way I put players together into games. I prepare 12 different kingdoms, so I just tell my script that's what it has to work with and it does a good job of making sure pairings are made that accomplish all of my goals. Sometimes I have to switch out a kingdom between rounds, but I have these handy trays that make this extremely easy to do. I'm really happy with the way that works.
 
Unfortunately, as the field gets smaller, this gets more difficult to do. It has a lot to do with the fact that I want there to be 4 games played in the prelims and I'd like for players to be able to lose a game and not be out of the tournament (to account for the variance in Dominion) -- but 4 3P games wants to accommodate 81 people and when you get much less than that number (namely, below 15 or so) a better solution if you're limited on number of tables is to just have everyone play a pre-set path through the tables in the preliminary rounds -- as you try and have people play opponents with a similar score you end up not being able to re-use your kingdoms.
 
So there are two things directly at odds here: wanting to minimize the number of kingdoms you have to prepare and wanting to not have the same people playing each other the whole time. Having a pre-set path through the kingdoms helps out with this (since your format is closer to a round-robin than a true Swiss at this point) but these two things are still at odds. If you want to have a true round-robin, you'll need a unique board for every single game that's played (or close to it, depending on the numbers).
 
For small numbers of players, well if it's the prelim rounds you can just prepare like 8 boards and be fine. For the semifinals, you have 9 players and you don't want to have to prepare 9 boards for that. I'd sort of like to have a 4-game semifinal and have that be it, but to make everybody play each opponent exactly once I have to make 12 different boards. Gross. That's actually really hard to do. So I want to find some pre-set path for 9 players to play 4 games each where there's this nice middle ground between people getting to play a variety of opponents and me not having to make a million different boards for it.
 
I think I've found a nice middle ground: I can make six boards, and have each player play four of them. No player will play the same opponent more than twice, and each player will play either five or six of the available eight unique opponents over the course of their four games. I've done some tweaking and put in what I think is a reasonable seeding, so here it goes.
 
Players are A through I, with A being the top seed and I being the bottom seed. I'm not positive this is the best seeding but most of the seedings seem pretty much the same to me TBH. Of note is the fact that three people get to play 6 different opponents and I chose to make those three the bottom seeded people.
 
Round 1:
Table 1 AFG
Table 2 BEH
Table 3 CDI
 
Round 2:
Table 1 CDH
Table 2 AFI
Table 3 BEG
 
Round 3:
Table 4 ADH
Table 5 BFI
Table 6 CEG
 
Round 4:
Table 4 CEI
Table 5 ADG
Table 6 BFH
 
Perhaps it's useful to come up with paths like this for different numbers of players, I'm not sure. This seems particularly useful for semifinal play when you know you'll have an exact number of people and that number is small.
 
 
Also, I've made a couple of modifications to my pairing scripts based on a bug I encountered at the tournament. I'll upload recent versions of those scripts soon (I need to make sure they're python 2/3 agnostic and I haven't done that since making some big changes). I also wrote a script that will input all of the kingdom cards/components you have available and randomly generate kingdoms from the components you have left -- you tell it what you like and it sets those components aside and doesn't give you kingdoms with those cards/tokens/mats/whatever if you've run out. I'll upload that once I check it for Python happiness as well.
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

shark_bait

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1103
  • Shuffle iT Username: shark_bait
  • Luckyfin and Land of Hinter for iso aliases
  • Respect: +1868
    • View Profile
Re: Swiss tournament pairing script
« Reply #18 on: February 03, 2016, 08:40:44 am »
+2

I'm sure you've probably thought of these already, but I'll throw these out for discussion.

Remove 1 prelim game and add it to the semifinals.  Then take a few more players into the semifinal round.  I think this would work best if you could take half of the players and advance them.  So 24 players with 12 making the SFs.  Then in a 3 game prelim you would be able to advance with a 1st, 2nd and 3rd place finish.  The challenge here is that you could get unlucky in one game and matched up against the champ in another and then you're done.

Get rid of the prelim/semifinal distinction and play 6-7 swiss style games then take the top 3 for a 1-2 game final between the top 3 players.  The advantage is that you have many games to establish yourself at the top and a single bad game won't eliminate you.  The downside is that towards the end you would have a lot of games with people who are statistically eliminated and potentially 1 or 2 kingmaking games with all players statistically out except for 1 player.

Another suggestion would be to not make the kingdoms ahead of time (or at least the 12 unique SF kingdoms).  Get out the randomizers and deal out 10 cards, maybe an event or two.  Have yourself and another tourney helper veto maybe one or two cards on an initial glance or cherry pick a specific type of card into the mix.
Logged
Hello.  Name's Bruce.  It's all right.  I understand.  Why trust a shark, right?

Is quite curious - Who is the mystical "Celestial Chameleon"?

Infthitbox

  • Explorer
  • *****
  • Offline Offline
  • Posts: 317
  • Respect: +440
    • View Profile
Re: Swiss tournament pairing script
« Reply #19 on: February 03, 2016, 09:38:00 am »
0

I'll reply in-depth when I have the time necessary (currently at work), but I appreciate you looking into this. There is a piece of paper on my desk at home with A-I in various arrangements and tons of crossed-out (failed) semifinal structures that I was toying with right after I got back home.
Logged

Limetime

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1237
  • Shuffle iT Username: limetime
  • Respect: +1179
    • View Profile
Re: Swiss tournament pairing script
« Reply #20 on: February 03, 2016, 09:43:41 am »
0

I've gotten some feedback about the last tournament I ran related to tournament format. While a lot of what goes on in RGG-sanctioned tournaments in terms of format is determined by RGG (and more is "recommended") I went and re-read the guidance I got and tried to incorporate it with the feedback I received. Here's what I'm working with.
 
If you don't want 3p games why don't you ask someone with power(DX) to straighten them out?
Logged

Voltaire

  • Jester
  • *****
  • Offline Offline
  • Posts: 957
  • flavor text
  • Respect: +1097
    • View Profile
Re: Swiss tournament pairing script
« Reply #21 on: February 03, 2016, 10:11:51 am »
+2

I've gotten some feedback about the last tournament I ran related to tournament format. While a lot of what goes on in RGG-sanctioned tournaments in terms of format is determined by RGG (and more is "recommended") I went and re-read the guidance I got and tried to incorporate it with the feedback I received. Here's what I'm working with.
 
If you don't want 3p games why don't you ask someone with power(DX) to straighten them out?

Because 3-player is better for the vast majority of in-person tournaments.
Logged

Voltaire

  • Jester
  • *****
  • Offline Offline
  • Posts: 957
  • flavor text
  • Respect: +1097
    • View Profile
Re: Swiss tournament pairing script
« Reply #22 on: February 03, 2016, 10:13:29 am »
0

Remove 1 prelim game and add it to the semifinals.  Then take a few more players into the semifinal round.  I think this would work best if you could take half of the players and advance them.  So 24 players with 12 making the SFs.

Is the issue here not then that half your entrants only get to play 3 games? That's not much.
Logged

AdamH

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2833
  • Shuffle iT Username: Adam Horton
  • You make your own shuffle luck
  • Respect: +3879
    • View Profile
    • My Dominion Videos
Re: Swiss tournament pairing script
« Reply #23 on: February 03, 2016, 10:18:21 am »
+2

Hitbox:

I have many similar pieces of paper :P I've convinced myself that I can't do any better than this with just six tables. I tried real hard to have everyone play 6 unique opponents our of 8 but I couldn't do it and I don't think it's possible. I actually couldn't do all that much better with 9 tables, I needed all 12 to get the "perfect round robin."

Shark bait's ideas:

There is a trade-off between having the tournament be just one big Swiss round and having it be as Un-Swiss as possible by introducing these different rounds. The benefits and drawbacks of pure Swiss are that people drop out when they aren't doing well, sometimes matches are irrelevant if one player has a big lead, etc. But it's the purest form of the tournament, meaning it should be best at finding the best players and it accommodates 3P games, 4P games, whatever, and deals gracefully with ties.

By cutting off halfway through the tournament or so and resetting the scores, I try to minimize the number of irrelevant games over the course of the tournament: the players at the bottom aren't completely out of it until after their third game (OK sometimes they can be but this will only be one, maybe two people and dropouts can be handled nicely if they really don't want their four guaranteed games) so there's only one irrelevant game at most for those people. The people on the top would like to seed well in the semifinals so in theory all of those games are relevant.

In fact eliminating the bottom half of players and just keeping scores intact doesn't seem like the worst thing ever -- it's very close to just pure Swiss at that point anyways. You could attenuate the scores at that point to try and decrease the probability of irrelevant matches while still preserving some advantage for players who have done well in the prelims beyond just seeing. Maybe like 0-1.5 tournament points to start things off? This is something I haven't really thought about. I want to think about this some more and maybe there are some suggestions?

As for making sets on the spot -- I really don't know about that. I would like to do as much work in advance as possible and automate the work that needs to be done day-of as much as possible (in fact for my next 2P tournament, I'm going to try having someone else moderate the tournament so I can play -- it should only require moving cards around the way the computer tells you to and answering rules questions/disputes). Making 12 sets on the spot seems much more difficult to me than preparing 12 sets ahead of time. There are issues with sleeves and making sure I have all available components, and the kingdoms are higher quality when I spend some time with them (and people I trust) looking them over before hand. I'm still trying to find ways to make my life easier in this regard (eliminating Mayday sleeves from my life entirely is probably my next step). But I know many people who organize IRL Dominion tournaments will want to cut down on the number of different boards they use (and make sure they're all "good" boards with at least some skill component).
Logged
Visit my blog for links to a whole bunch of Dominion content I've made.

popsofctown

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 5477
  • Respect: +2860
    • View Profile
Re: Swiss tournament pairing script
« Reply #24 on: February 03, 2016, 10:22:01 am »
+2

Remove 1 prelim game and add it to the semifinals.  Then take a few more players into the semifinal round.  I think this would work best if you could take half of the players and advance them.  So 24 players with 12 making the SFs.

Is the issue here not then that half your entrants only get to play 3 games? That's not much.

You should try driving across state to a double elimination fighting game tournament.  It's the thrillz man!
Logged
Pages: [1] 2  All
 

Page created in 0.324 seconds with 21 queries.