I Need Help! - Special Round Robin Tournament Algorithm

[Charles de Gaulle]

While hosting small tournaments, I’ve come across an issue in creating the actual match-ups. Here are the stats and requirements that I’m working with:

1. It’s a five player game in which turn order matters!!!

2. Every person plays five games, one as player 1, 2, 3, 4, and 5 (you can think of this as playing 5 Pacific 1940 games, one as China, one as Japan, USA, UK, and ANZAC…)

3. It’s supposed to be a round robin tournament, so each person plays against every other player; however, as an extra stipulation, each player will only see every other player once.

Now according to what I just mentioned, there will have to be 21 people total (because if every player plays five games and there are four opponents in each game and every opponent will only be seen once, there will have to be 20 other people to fill those spots; this also means 21 games total will be played).

If you’re not confused already, also remember, one of the other stipulations is that of the 5 games that everybody plays, each one has to be a different position in the turn order (in A&A terms, think of it as a different country). So there cannot be someone who plays as player #2 in more than one game, because he has to have a game as each different player position.

-*-
To make this a little clearer, here’s a much simpler breakdown I created for hosting a 3 player game with the same rules:

There are 7 players and 7 games being played. The players are listed as “1,” “2,” “3,” etc. The player listed at the top of the list goes first (he is the nation that moves first) the player at the bottom of the list goes last (he is the nation that moves last).

Game 1. Game 2. Game 3. Game 4. Game 5. Game 6 Game 7.
----1---------4---------6---------2----------7----------3---------5
----2---------1---------7---------5----------4----------6---------3
----3---------5---------1---------6----------2----------4---------7

At first glance, this just looks like a bunch of numbers. But it’s actually a carefully constructed round robin tournament. Notice how it meets all the requirements I mentioned earlier:

1. Each player only sees every other player only once.
2. Each player gets to play only once in first, second, and last positions in the turn order.
3. There are only three people in each game.

Now, if you are making any sense of what I’m saying, perhaps you can help me. I have successfully created a tourney bracket like this for 4 player games, and there is actually more than one way to “solve” the match-ups so that everything is just as I said. But I’m making these through trial and error, and I’ll spare you from the headache of seeing the actual 4-player-games bracket.

But what I really need right now is a bracket for 5 player games (the twenty-one-participant model I spoke of earlier). But with 21 different games to set up and all the stipulations I mentioned about turn order and only seeing every opponent once, I haven’t been able to manually figure out the bracket.

Is there some sort of algorithm, formula, or something I can use other than the excruciating task off trial and error to create a list like the one I showed for the 3 player game? And yes, I am aware that many round-robin generators exist, but I’ve never found one that has support for games that have multiple players and takes into account the importance of turn order (in a game like Axis and Allies where you’re not just “white” or “the player who moves first,” where you are in the turn order makes a huge difference, as that is the nation you are playing.)

If any of you intellectuals understand what I’m talking about, please let me know if you have a solution. My simple model for the 3 player game version is a good start, but I’m wondering if it’s even possible for the 5 player version I’m talking about? Maybe the math just doesn’t cooperate.

PLEASE HELP!

[CWO Marc]

@charles-de-gaulle
I don’t have an answer to your actual question, and I have no idea whether what you have in mind is mathematically possible, but here’s the angle which really puzzles me. You mentioned that this issue arose out of hosting small tournaments, but you also mentioned that the concept involve 21 people playing 21 games, which doesn’t sound like a small event to me. From a practical point of view, there are two questions which come to mind. First, what is the rationale for having all the stipulations you mention? If I’m understanding your post correctly, you’re saying that what makes the problem so difficult is satisfying all the stipulations – but this begs the question of why you have so many of them in the first place. Second, your post presumably works from the assumption that you actually have 21 players on hand who’ve indicated that they’re willing to play under this round-robin system…but is that actually the case? In other words, are you trying to work out the mechanics of something to which they’ve already agreed, or are you developing a concept that you want to pitch to them as a cool idea once you’ve worked out the details? If it’s the latter, you may end up investing a great deal of work in a concept that might not actually fly with your intended audience.

[barnee]

@charles-de-gaulle ask @redrum he’s smart

[redrum]

I think you could solve it as a sort of “bin packing” problem where you have 21 “bins” and you have to put each player into 5 of those bins while enforcing both that they need to be in each position of the bin once and can only be in the same bin as each other player once.

[Charles de Gaulle]

@cwo-marc Thanks for the excellent thoughts. You always give good insight.

Something I should have mentioned that might make this sound a bit more reasonable is that this tournament bracket isn’t being made for Axis and Allies. It’s just a five player game in which turn order plays a big role (going first vs going last is drastically different, almost like playing a different nation in A&A). Also, the game is “free-for-all,” meaning players can legitimately team up and matches can be easily lost because an amateur “threw” the game—this is why it’s so important that participants only face each other once.

The “21” model was created simply because it’s the smallest possible bracket for a five-player game that could offer a player a chance to go first, second, third, fourth, and last–AND only see each opponent once.

You might be wondering why “only seeing an opponent once” is so important to me. In this game, there are five competing players that strive to eliminate opponent’s pieces. It is very well possible for someone to be eliminated entirely in the first few rounds of the game. As you gentleman might remember, I entertain a bunch of goofy kids and am practically still one myself. It’s not uncommon for an experienced veteran to get “bullied” by even just 1 silly opponent who goes out of his way to destroy the threat of a skilled player early on by focusing only on him (much to the harm of both players).

The “21” model is the smallest logical number (for a 5-player game) that is “fair” in my group. The extra stipulations are there to give everyone an even chance without too much luck being involved.

[Charles de Gaulle]

@redrum Now that I think about it, that’s actually very close to what I’ve tried doing in MS Excel. The 3 and 4 player versions were easy enough, but 5 is giving me a hard time.

Just for some interest, here’s a snapshot of part of the “solved” bracket for the 4 player, 13 participant version.

[redrum]

@charles-de-gaulle Yeah, I think you’ve been manually doing it which for small problem sets like 3-4 players which is probably not too difficult. Once you get to 5+, its very difficult and time consuming to do manually and you may need a programmatic approach.

You can try to do it manually but it may get to the point where you end up having to try to swap around a bunch of game assignments to avoid breaking your conditions which is where a human starts to struggle but where computers and optimization algorithms shine.

[CWO Marc]

Thanks for the additional information. It helps to know that this isn’t for A&A because a single A&A game can take an awfully long time to play, never mind 21 of them. I have some follow-up questions.

1. You say that each game involves five players (that’s clear enough) and you say that “every opponent will only be seen once” over the course of the multiple games. What I’m wondering is whether “every opponent” refers to specifc individuals or whether it refers to a unique combination of individuals. To explain myself, let’s take five people and designate them as A, B, C, D and E, and let’s use person A as our reference point. In the first game, person A will face B, C, D and E. So far so good. In the second game, will person A need to face four entirely different individuals (say F, G, H, I and J)? Or does it suffice to face a different combination of individuals which can include some of the members of the previous group but not all of them – for example, B, C, D, E and F? If it’s absolutely prohibited for any of the players to ever face any of the same individuals in any of the games, regardless of what combinations they’re in, this implies a rather large number of people.

2. Is a “different opponent” defined by who the physical persons are, or is it defined by the position in which they’re playing? In other words, if person B is playing the #1 position (which I assume means the person who plays first in the turn order) in one game, and if person B is playing the #2 position in another game, is person B considered to be a different oppenent, even though it’s the same individual?

3. When you say “turn order matters”, do you mean that players are defined (within your system) in terms of what – in an A&A context – is the prescribed order in which the nations on the board get to take their turns? Or do you mean something else?

4. How many game rounds are there? (I define a round as each player in the turn order playing one turn.) Are people allowed to play multiple rounds until a game is finished?

5. Is the “you’ll never play the same opponent twice” concept an end in itself? Or does it relate to a larger concept for winning the tournament itself? To use an imperfect analogy: in the NHL playoffs, most teams never get to play against each other; they play in pairs, and each pairing eventually results in one team eliminating the other. Each winning team then meets another team which similarly eliminated another team in the first round, and so forth, with the number of teams surviving each round dropping by 50% at each round, until ultimately only two teams face off in the finals. There’s a clear goal and a clear progression. Is there some sort of similar goal in your rotational system? You seemed to indicate that one of your aims is to compensate for the fact that some players are strong and experienced, and thus can potentially bully weaker ones. Fair enough, but does this mean that the objective is simply to allow everyone to experience one game against every possible level of opponent, but that there’s no specific overall outcome regardless of who wins which games?

[CWO Marc]

I think I’ve found a way for you to work out your five-player matrix without too much trouble. I tried to see if there was a reasonably systematic / programmatic way to work out the answer for the simpler case of a three-player matrix; there is, and you should be able to scale it up. It’s a manual process that involves checking things – but it uses a process of elimination, so some parts of the process get shorter as you progress, which makes it manageable.

It also breaks the problem down into stages, so that you don’t have to try to figure out all the variables at once by an excruciating process of trial and error. Crucially, it first determines only the issue of “who plays with whom in each game”, and it leaves until a second stage the issue of who plays which turn order position.

Here’s the approach I took, after studying the photo you posted (which answered a lot of my earlier questions).

For clarity, I designated the players with numbers (1, 2, 3, etc.), and I designated the turn order positions with capital letters (A, B and C). You might want to give Roman numerals to the games.

I started with Player 1 (hereafter just 1). The game has three turn order positions, and therefore also has three players per game. 1 has to play once in each turn order position, which means three games. There are three players per game, so at each game 1 plays against two opponents. The opponents are required to all be different at every game, so this means that 1 will play against six other people, numbered from 2 to 7. Thus:

1 plays against 2, 3, 4, 5, 6, and 7

Since it’s a three-person game, this translates into:

1 plays against (2 & 3) and (4 & 5) and (6 and 7)

All three of 1’s match-us are now spoken for (though note that we haven’t yet nailed down which turn order position he plays in each pairing; that will come later), so we can turn to the next player to consider. Here’s where the process of elimination comes in. The next player to consider is 2. If we were replicating the pattern of this line…

1 plays against 2, 3, 4, 5, 6, and 7

…you’d think this that corresponding “2” line would look like this…

2 plays against 1, 3, 4, 5, 6, and 7…

but in actuality it looks like this…

2 plays against 4, 5, 6, and 7

…with two numbers (1 and 3) eliminated because 2 has already played against both of them. (The systematic check to apply at every step of this procedure is the question, “has this been used before?”)

At first glance, if we follow what we did with 1, this…

2 plays against 4, 5, 6, and 7

…translates into…

2 plays against (4 & 5) and (6 and 7)

…but if we apply the “has this been used before?” test we see that (4 & 5) and (6 and 7) were both used with 1, so we can’t use them with 2. Switching two of the digits, however, gives this…

2 plays against (4 & 6) and (5 and 7)

…which works because 4 hasn’t previously played against 6, and 5 hasn’t previously played against 7.

At this point I put together a little table to see if anything was missing. The results I have so far are:

The “1” match-ups

1 2 3

1 4 5

1 6 7

The “2” match-ups:

2 4 6

2 5 7

This leaves the “3” match-ups to work out. 3 has already been used with 1 and 2, but has not been used with 4, so I wrote the partial line:

3 4

We need another number to complete the line. 5 comes after 4, but it’s been used with 4 previously. Next comes 6, but that’s also been used with 4 previously. Next is 7, which has no previous use with 4, so the line becomes:

3 4 7

I then went back over all the previous lines to check whether there are any remaining numbers with which 3 had not yet been used. Yes indeed: 5 and 6. This generated the following line:

3 5 6

I don’t know if the forum has a posting length limit, so I’m going to break off here and continue in a second post in a few moments.

[CWO Marc]

Now to resume. By now we’ve generated a tentative table of three-number match-up lines which looks like this:

1 2 3
1 4 5
1 6 7
2 4 6
2 5 7
3 4 7
3 5 6

As a check, I then mentally went through the following two-number combination: one-two, one-three, one-four, etc., all the way up to three-seven, to see if each pair of numbers in the combination can be found on one and only one line of the table. Answer: yes. So – unless I’ve overlooked something, which I hope I haven’t – we now have a complete list of who gets matched with whom, which meets the required “play with everyone but only once” condition.

Now to figure of the turn order. Each player gets to play in each position (A, B and C) once. The first cluster of unedited lines is:

1 2 3
1 4 5
1 6 7

If we move the 1 by one and two spaces respectively, we get:

1 2 3
4 1 5
6 7 1

Now for these unedited lines:

2 4 6
2 5 7

The first line already has the 2 in the A position, and the 4 and the 6 don’t conflict with anything above, so it’s tentatively fine as is (more on this later). The second line needs to have the 2 in the C position. Putting the 7 in the B position would conflict with an earlier line, so our only choice is to put it in the A positition:

7 5 2

Our table thus far is:

1 2 3
4 1 5
6 7 1
2 4 6
7 5 2

We’re now left with these two unedited lines:

3 4 7
3 5 6

Here we run into a problem: the lines can’t be arranged to avoid conflicts. I therefore had a second look at that “tentatively fine” earlier line and tried switching it around. That fixed the problem, with the rest of the table fell into place. The full final result is…

1 2 3
4 1 5
6 7 1
2 6 4
7 5 2
3 4 7
5 3 6

…which can be verified by noting that each number appears once in each column:

A B C
1 2 3
4 1 5
6 7 1
2 6 4
7 5 2
3 4 7
5 3 6

[CWO Marc]

Incidentally, I’ve just checked my table against yours (which is oriented horizontally rather than vertically)…

Game 1. Game 2. Game 3. Game 4. Game 5. Game 6 Game 7.
----1---------4---------6---------2----------7----------3---------5
----2---------1---------7---------5----------4----------6---------3
----3---------5---------1---------6----------2----------4---------7

…and I see that we got the same results in three of the cases and similar but different ones in the remaining four, so it looks as if the problem has at least two valid answers. This is is good news because this suggests that even your five-player matrix should be workable in at least one way.

[Charles de Gaulle]

@cwo-marc I believe you’ve already solved your questions, but just to be sure, I’ll briefly answer them for clarity to everyone.

1. The answer is yes. Player A is only allowed to see Player B once. “Once” refers to certain individuals rather than combinations of individuals.
2. A different opponent is defined by who is playing. Player B is still Player B regardless of his position in the turn order.
3. Yes. Turn order is similar to Axis & Allies in which it defines a person’s place and affiliation on the board.
4. For this answer, I’d first like to say that it does NOT affect anything else. So don’t consider these numbers in calculations. However, to answer the question, there are typically 11 rounds (it can change because players can get skipped if they have no valid moves). There are almost always 54 moves (turns) total (unless the last move is an invalid one for everybody). By nature of the game, the fifth player typically only gets 10 moves while everyone else gets 11. (11*4 + 10 = 54)
5. This concept was created for overall fun (in a relatively small group of 21 people, it’s fun to get to “fight” against everybody) but more importantly, to ensure overall fairness. Since it’s a 5 player game rather than a 1vs1, luck plays a huge factor, as there is much that goes on out of your control while the 4 other players take their turns. Also, this isn’t just about winners and losers. Players will strive to “win second place” or do their best regardless, because after the 21 games are played, each participant receives points for where they placed in each game (4 points for a win, 3 for 2nd, 2 for 3rd, 1 for 4th, and 0 for fifth).

[Charles de Gaulle]

@cwo-marc Now then, to address this beautiful system you’ve written, this is indeed the correct way to go about making the bracket. I would have never been able to explain it so informatively as you just did, but yes, this is what I’ve tried to do to create the 5-player, 21-participant version.

As you found, there are actually several ways to solve the 3-player, 7-participant version. I can attest that there are also at least 3 ways to solve the 4-player, 13 participant version as well.

I’ve tried methods very similar to what you just wrote out, and it does work. But as redrum pointed out, it becomes increasingly hard for a simple human like me to work out, because the possibilities explode greatly at 5 players and above to the point of madness.

I’ll continue diligently working on at least finding ways that DON’T work for the 5-player, 21-participant bracket. So far, by process of elimination, just like the beautiful model you wrote out here, I’ve tried many,many matchups, but they all have thus far failed. Your supposition that there probably IS at least one “solve” does give me hope, as I believe all these failures I’ve faced are purely a result of the enormous possibilities 21 players give.

Again, I’d like to thank you Marc and everyone else for giving me these ideas to consider, as I now have many good tools for working on this further.

…I just hope many crazy comrades don’t ever think of a 6-player version of our game, because I’ll probably end up losing my wits trying to solve it.

[aardvarkpepper]

@charles-de-gaulle said in I Need Help! - Special Round Robin Tournament Algorithm:

It’s not uncommon for an experienced veteran to get “bullied” by even just 1 silly opponent who goes out of his way to destroy the threat of a skilled player early on by focusing only on him (much to the harm of both players).

I’ll tell you a hypothetical story, just sit back and relax for a bit.

Let’s say Player 7 is a nice person by some estimations, they like spending time with their friends, many of whom like playing this board “game” (note the quotation marks). Now let’s say that Player 7 feels that they’re mostly wasting their time with this “game” that they’re not very good at, and doesn’t feel that they are being respected. So to make a lasting impression on others, Player 7 decides to “take down” whoever is thought as the “strongest” player in whatever “game” they play in. That way player 7 earns respect, maybe even admiration on some level. Some others might call this “bullying” but really, Player 7 is just playing their own game, which isn’t necessarily “the game” with all these nice pat rules that the others think they’re playing. Understand the distinction between game (life goals) and “game” (board game), this distinction comes up later.

Let’s say every player in the group is more skilled at the game the lower their number is, and that this is generally recognized by the group. So 6 can expect to beat 7, all other things being equal, 2 can expect to beat 5 handily, etc.

Let’s say Player 1, instead of just being skilled at the “game” with all the formal rules, also is good at the GAME and by that I mean player psychology, making friends, just those sorts of things. And they understand of course players 6 and 7 are going to feel marginalized and disrespected, that there’s a pecking order. See?

So now we get some very interesting results.

In Game One with players 1, 2, and 3, in Game Two with players 1, 4, and 5, and Game Three with players 1, 6, and 7, the same thing happens. When appropriate, 1 treats opponents with respect and consideration, so conspiring against 1 is reduced. After all, if other players immediately conspire against 1, it’s basically admitting they’re not on 1’s level, so 1 wins anyways in a sense. And if it sometimes suits 1 to be dominant to players that like to be dominated (oh my), then let’s say that happens too.

But that isn’t the interesting part, we’re assuming that all things being equal 1 was favored to win anyways, so if 1 wins, no big deal right?

But that’s not the end of it. Though player 1 wins all their games, what of the other games that other players play? If 1 wants to destroy their competition in the game sense (not the “game” by its nice clean rules, but the GAME, like life shenanigans), then what?

We know that player 2 already lost the game in which 2 matched against 1. But player 2 is also playing with 5 and 6 in game four, and with 4 and 7 in game five. And because 1 is masterful at the game, 1 says “well, you know, I like 2, but really, 2 needs to be taken down a notch”. So player 5 and 6 conspire so player 5 wins against player 2 in game four, and players 4 and 7 conspire so player 4 wins against player 2 in game five.

But wait, you say, that’s crazy? Of course it’s crazy. But because 2 is losing all their games, 2 becomes the new 7. That’s just how it works, even though it’s not how it’s SUPPOSED to work, we KNOW that 2 is better at the “game”, but that certainly isn’t what the game results will show. But the outcome, as weird as it is, still suits everyone except number 2, so you can easily see how it happens with a little encouragement.

But it’s all more or less okay because the best player is still the best, and if one player’s not where they ought to be in the ranking that’s just how it goes, oh well? But that’s not even the twist ending. The twist in our little story is NOBODY is where they ought to be, actually the SEVENTH best at the “game” is player 1, it’s only that the seventh player is actually a master of the GAME OF LIFE (not the “board game”). And all the little complications in the OP were entirely besides the point to someone that understood how to work the system.

Instead of meekly playing along and accepting the rules of the board “game” and the supposed rating system, the least skilled at the “game”, the REAL player 7, has such a strong grip on the GAME (in terms of getting people do what one wants them to do in real life) that they are, without dispute so far as the other players are concerned, player 1! Is that really what was desired?

I’m not saying it plays out dramatically like in a movie. You can do a lot with a slight wrinkle in the nose, some subtle hand gestures, and a friendly smile, maybe a little shrug to help things along. It doesn’t even have to be conscious manipulation, it’s really just a very natural part of social interaction that one influences others in these subtle ways.

So the real question is not whether it happens, it’s how much it happens, and whether the OP system counters it, (which it doesn’t, right?)

What is the “mathematical solution”? If you have a nice clean simple answer, there’s going to be factors you’re not accounting for mathematically, and that means the system will be subject to manipulation via manipulation of the variables that ought to be accounted for but aren’t. It is not required that someone understand or even have intent to manipulate a system, people naturally puzzle out what works, just like you don’t need real intent or understanding of calculus to near-automatically catch a ball when it’s thrown to you.

I’d imagine if you wanted a real mathematical address to player skill in the “game”, the mathematical solution would have to be very dirty indeed. Like you’d have to use a modified Glicko with additional multipliers based on turn order, and accounting for multiple players with rating having different motivations for game outcomes. I’m not even sure you could call such a system Elo / Glicko any more; if Glicko is really “different” enough to Elo that it deserves a name change, surely a system with so many added variables and considerations would have its own name.

But as I see it, CWO Marc’s first post in the thread - it really returns to, what is the purpose of the system? If you want a mathematical answer you need to define the mathematical question. So what is it that’s wanted, exactly?

1. A system to accurately assess player strength (which would require a load of data crunching, there’s just no other way to get the corrective numbers for a particular population)

2. A system to not-so accurately assess player strength, but which requires less work

3. A system that doesn’t even pretend to try to assess player strength at all, but could still be of interest to players.

https://www.youtube.com/watch?v=THUGHEJjjGc

Is Bill Murray REALLY assessing mathematically a horse-sized duck versus a hundred duck-sized horses? Clearly not. It’s schmoozing, but 800,000+ views; apparently some people found it interesting.

4. A device to get players interested in playing more games

5. A device to convince players of the legitimacy of game outcomes. I’ll point out again the OP system just doesn’t mathematically account for “bullying”.

Or something else, what? Once you can clearly define the issue, and I mean clearly and honestly and openly in all ways, even if those end up maybe looking a little shameful, only then can you really define mathematical solutions.

@charles-de-gaulle said in I Need Help! - Special Round Robin Tournament Algorithm:

The “21” model is the smallest logical number (for a 5-player game) that is “fair” in my group. The extra stipulations are there to give everyone an even chance without too much luck being involved.

What are the specific criteria for “fair”? Consider, why does the one designing the model not account for and predict a lower ranked player hitting a higher ranked player, offplaying it as “bullying”, even though apparently this is enough of a trend to be noticeable? Could it be that the predictive model need be re-examined and reconsidered from the ground up?

If you’re looking for a mathematical solution, you need to not look at how you want things to be, but how things really are.

But the OP is about a “special round robin tournament algorithm”? All right, then, cautions given so let’s look at that then.

1. “It’s a five player game in which turn order matters” / 2) Every person plays five games. This is really just one thing mathematically. Or procedurally. Whatever. An n-player game in which every player plays n games, isn’t that the parameter?

2. “Each player will only see every other player once” which is another thing,

3. 21 players = 21 games. Well, we’ll look at this. I don’t think this should be taken for granted.

Okay, so let’s look at the 3 player game (abbreviated hereafter as 3PG). What if have only 3 players? Fine, that works out, just one game. But what if we have 4 players? Well then there’s a problem. You can have a 3PG game with players 1, 2, and 3, but for there to be a game with player 4, then you need either 1 and 2, or 1 and 3, or 2 and 3 to play a game together again. There’s no way around it, you simply can’t have a round-robin for 3PG with 4 players with the specified conditions.

But you define the parameters by specifying the player count and the value for n in nPG? All right, if you say so, but you do see where that’s a bit odd. Rather than saying here are the number of players you have and let’s figure out a system, you stick on so many parameters and requirements it’s quite the pincushion. I really think if you’re designing a system you would do best to consider a system that doesn’t have so many requirements for participants. Of course I’m not familiar with your situation, for all I know you have total control over the number of participants, so eh.

Apparently it works for 7 players for 3PG, or 13 players for 4PG, but what is that says 21 will be the magic number for 5PG? Really, you just take n-PG, then take (n(n-1))+1? If it were that simple, then shouldn’t it be easy to figure out your brackets?

Let’s take a cute little example. Let’s say that we use nCr mathematics to resolve 7 players in 3PG. First let’s say that we’re using nCr instead of nPr in the first place because numbers can just switch name tags; it doesn’t REALLY matter if you’re doing 1,2,3 vs 1,3,2 if “2” and "3’ can just switch name tags. Then we say how do we figure out how many games a player plays? 6C2 = 15, 5C1 = 5, divide to get 3. Wow, what a great answer, so simple, and completely wrong for all I know, but eh.

If this combination thing is so great then what happens if you go from 7C3 = 35 to 6C2 = 15? Oh, let’s not worry about THAT, it looks weird but TRUST me (wink wink). 6C2 = 15, 5C1 = 5, divide to get 3, it’s magic! don’t think about anything else! frantic hand gestures!

12C3 = 220, 11C2 = 55, amazing! Divide and you get 4! Magic!

20C4 = 4845, 19C3 = 969, divide and you get 5!

Hey well (shrug) it’s not like I’m really thinking things out, just kinda throwing some nCr stuff at the wall and seeing what sticks, you know? But if that IS actually all you have to do, then you just set up a program to generate the nCrs and to handle the “division” part so you get a nice clean output. I mean, how hard could THAT possibly be?

Look yeah, let’s just take the 7 player 3PG. Here, you have 6C2.

2,3
2,4
2,5
2,6
2,7
3,4
3,5
3,6
3,7
4,5
4,6
4,7
5,6
5,7
6.7

Then you have 5C1

3
4
5
6
7

And how do you get from there to 1,2,3 / 4,1,5 / 6,7,1?

First, you define the ordered permutations by defining the place of “1” then fill in the rest. So we’re arbitrarily taking 1,2,3, what next? Well the thing about 5C1 is it doesn’t actually represent 3, 4, 5, 6, and 7, does it? Of course not, because there 3, 4, 5, 6, and 7 are abstractions that can “name tag switch” with 2.

So actually what you’re doing procedurally is you defined the location of 1, then you took the first sequence in 6C2 which is “2,3”, defining the permutation “1,2,3”. Then since you want to eliminate any repetition, you’re *eliminating all remaining elements in 6C2 that have the “2” or “3” elements (“1” is already eliminated).

So from 6C2, you’re selecting “2,3” and eliminating “2,4”, “2,5”, “2,6”, “2,7”, “3,4”, “3,5”, 3,6", and “3,7”. But then why do you divide 15 by 5 to get 3?

Hm, how to explain it. It just works out that way mathematically. There’s fifteen elements in 6C2, five elements in 5C1. The elements in 5C1 are mutable until they’re defined by their selection in 6C2. Every element in 5C1 recurs in 6C2 five times; once defined the element is removed from both lists.

So when “2,3” is defined, then 5+4 elements are removed (one of those being the permuatation “1,2,3”). When “4,5” is defined, 3+2 elements are removed (one of those elements being the permutation “4,1,5”). When “6,7” is defined, 1+0 elements are removed (the permutation “6,7,1”, for a total of 15 removed elements.

It’s less about “dividing” and more about that’s just how it works out, just like how you get the sum of the integers 1 through n by (n(n+1))/2.

I could be totally wrong about how it all works, but that’s how it seems to me.

(Edit - when I write, for example, “divide and you get 4!”, I mean divide and you get four, exclamation mark for emphasis. Not 4! in the mathematical sense (=24))

[CWO Marc]

Here are a few additional thoughts, based on your “I’ve tried many, many matchups, but they all have thus far failed” comment and on aardvarkpepper’s analysis, which among other things raises the question of whether the kind of matrix you’re contemplating actually achieves the fairness it’s supposed to deliver.

To illustrate the argument I’m about to make, I’ll use the relatively simple case of the three-player matrix, which has already been solved, my version of it being:

A B C
1 2 3
4 1 5
6 7 1
2 6 4
7 5 2
3 4 7
5 3 6

The first point to consider is this. You’ll note that every player does indeed play in each position (A, B and C) exactly once, and that every player plays against every other player exactly once, as required. At first glance, everything looks perfectly symmetrical, and therefore perfectly “fair”, because the assumption being made is that “symmetry equals fairness.” It turns out, however, that there are two problems here. Problem one has already been pointed out by Aardvarkpepper: the concept that “symmetry equals fairness” is questionable. Problem two is that the matrix is only symmetrical when you view it it terms of every player playing against every other INDIVIDUAL player. It stops being symmetrical when you view it it terms of every player playing against every possible COMBINATION of players. In the above example, for instance, 1 gets to play against three combinations of players; 2&3, 4&5, and 6&7, but never gets to play against all the other possible combinations of players (such as 2&6). If you work from the assumption that “symmetry equals fairness”, the logical conclusion would be that your players would all have to play a game against all the other possible combinations of players, not just against every individual player. This would not only increase the number of games to be played, it also require you to drop the requirement that each play play each position only once.

The second point to consider is this. As noted, the above matrix does not include all the possible three-player combinations. Some of the possible combinations are “valid”, in the sense that they work within the matrix, while others are “invalid”, in the sense that they wreck the matrix. This may explain the “I’ve tried many, many matchups, but they all have thus far failed” problem you’ve been running into. Your five-player matrix experiments presumably all use the following match-ups as their starting points, since those match-ups are quick and easy to identify…

1 2 3 4 5
1 6 7 8 9
1 10 11 12 13
1 14 15 16 17
1 18 19 20 21

2 6 10 14 18
2 7 11 15 19
2 8 12 16 20
2 9 13 17 21

…but I’m wondering if those match-ups include “invalid” ones that make the rest of the matrix impossible to complete? I’m not saying that your contemplated 5-player matrix is impossible; I’m saying that working it out may require a good deal of mathematical knowledge (which I certainly don’t have). If you look at the Wikipedia articles on round-robin tournaments…

https://en.wikipedia.org/wiki/Round-robin_tournament
https://en.wikipedia.org/wiki/Tournament_(graph_theory)

…you’ll note that the scheduling algorithms for even the relatively simple case of rotating two-player match-ups are quite complicated, or at least (to borrow a phrase from Calvin and Hobbes) look complicated “to the untutored eye of the ignorant layman.” This doesn’t appear to be a problem you’ll be able to solve by continuing to “diligently working on at least finding ways that DON’T work for the 5-player, 21-participant bracket.”

Which brings me to a practical suggestion. The problem you’re working on is extremely difficult to solve if the only solution that’s acceptable to you is one that meets your requirements perfectly. If you settle for “almost perfectly,” however, it immediately becomes quite manageable. I assume from your remark “I’ve tried many, many matchups, but they all have thus far failed” that every time you try to set up a matrix, there are always one or two match-ups that don’t fit. How about simply living with them? As has ben discussed above, the premise that “symmetry equals fairness” has got a couple of conceptual problems with it, so it seems to me that having a couple of non-fitting outliers in your matrix is hardly going to be a fatal flaw. And you’ll note that the Wikipedia articles mention the concept “dummy competitors”, whose function seems to be make scheduling algorithms work. If the professionals need to use loopholes of this type, there’s no dishonour in your doing likewise.

[Charles de Gaulle]

@aardvarkpepper Dang. To be frank, your story is a lot more philosophical in nature than I actually feel is necessary to worry about. But that’s because I should have explained something:

—This whole tournament idea is actually for a playtest. Aside from having a fun, quick-moving tournament, I’m trying to gather statistics from a large pool of players to see if there is any bias involved. The “bias” I’m talking about relates to my earlier vague reference that “turn order is important.”

In each five player game, there are five “colors,” each with their own situation on the board. My hope is that any innate advantages or disadvantages of being one color vs another color are outweighed by the much larger influence of the players themselves. After the tournament is over, my idea is to scramble the players and start over, as many times as possible to weed out any issues with the game’s balance. If there is any position in the turn order which is noticeably doing worse or better, it should eventually become evident.

The reason I’ve been putting “fair” in quotes is largely due to how ambiguous being “fair” is, given so many variables and human choices, strategies, and real-life motives. However, my objective is to make a balanced game rather than an objectively “fair” tourney. In order to gather at least somewhat accurate data, I am trying to lesson individual player influence to help make the bracket “fair,” at least on paper.

This whole “21 participant, 5-player” model that I’m so stubbornly adhering to was created by asking myself, “What’s the smallest number of games a participant could play and still get a chance at being each color (position in the turn order) and also facing every other participant?” Well, the answer is that each participant would have to play at least 5 games obviously, and since there would have to be 4 opponents in each of those games, there would be 20 opponents total plus the first guy (= 21).

So 21 is the smallest magic number for 5 player games. And it offers the unique distinction of only requiring opponents to see each other once (which, in my opinion, helps to lesson individual player influence over the data I desire). The next magic number for 5 player games is 42. Likewise, 7 is the first magic number for 3 player games, and 14, 21, etc. are the next ones.

The only reason to use larger “magic numbers” is to compensate for what @CWO-Marc has noted: even with all these stipulations, there are still many inconsistencies, as a 3 or 4 or 5 player game has groups of players than could potentially be switched around and manipulated to change results. But…as we’ve all come to conclude, it is also easy to just swap one player with another to get another valid matchup. So if I scramble the players after each tourney, I’ll get closer and closer to an accurate answer.

My hope is that the game is already “fair enough” to the point that skill level, luck, and matchups play a much larger role than the color (or rather, the place in the turn order) that each participant plays. As I’m sure some of you are probably thinking, there are easier ways to playtest with acceptable accuracy than to go to all this trouble building something around a “magic” number that was created through preset rules. But being the curious, stubborn person that I am, I want to solve it this way; it’s fascinating; it’s unique; and although it’s imperfect, it will work for me if it’s indeed possible.

The 3 player variant that you did some awesome number crunching with @aardvarkpepper is a very good frame with which to build an intense 7 player tournament with perhaps 21, or even 105 games if desired. The 4 player variant, which I’ve found several solutions for, was so enjoyable in playtesting, that we’ve already reused it several times. I must take the time to examine more in detail, aardvark, the way you solved the 3P version, as it might work better than everything I’ve tried so far.

[CWO Marc]

Your response to aardvarkpepper provides some interesting insights into why you’re developing this matrix, and it also raises some new questions. I’m not sure I’ve fully grasped what you’re getting at, but it sounds as if you’re trying to generate a massive amount of evidence in order to make a point by the sheer brute force of quantity. What I’m most unclear about is the nature of the point you’re trying to make by doing this. To put it as a question: are you trying to test your game’s level of balance for your own benefit (possibly because its balance can’t be proved from theoretical considerations alone) or are you trying to prove its balance to someone else who needs to be convinced? If it’s the latter, I doubt that a bunch of statistical data is going to overcome their scepticism. I don’t know if you’ve ever seen the original pilot movie for the eventual TV series Voyage to the Bottom of The Sea, but there’s a scene depicting an argument at the U.N. between two scientists, each of whom thinks the other is an idiot. Scientist B produces a stack of calculations which he says proves that he’s correct, puts them on Scientist A’s desk and says he’s welcome to check the figures for himself. Scientist A mumbles for a few seconds, looking at random through the stack of papers, then puts them down in disgust and declares that there’s no point in checking these figures because “I cannot be wrong!” So much for the scientific method.

When I talk about proving fairness (or lack thereof) from theoretical considerations, I’m referring to this sort of thing, quoted from something I remembered from Wikipedia: “Robert Feinerman has shown that the game of dreidel is “unfair”, in that the first player to spin has a better expected outcome than the second player, and the second better than the third, and so on. Feinerman, Robert (1976). “An ancient unfair game”. The American Mathematical Monthly. 83 (8): 623–625.” Or to use a different model, consider the buttered toast phenomenon. If a slice of toast, buttered on one side, were flung energetically into the air a hundred times under perfectly random conditions, it would land buttered-side-down exactly (or almost exactly) 50% of the time. Then why is it that, in real life, buttered toast sliding off a plate tends to land buttered-side-down significantly more often than 50% of the time? Because in real life it involves conditions which are relatively standardized rather than random. The slice of toast typically starts out sitting on plate buttered-side-up being held somewhere between waist height and chest height by a human being roughly five to six feet tall. If the plate is accidentally tilted, the toast slides off and falls with an acceleration of 1G (9.8 m/s squared). Over the distance at which it was dropped, this typically gives the slice of toast enough time to turn over once but not twice – so it hits the floor buttered-side-down. I don’t know if all this has ever been proved empirically, by running hundreds of toast experiments (half of them randomized and half of them standardized), but even if it’s been done the numbers wouldn’t change my mind; the theoretical argument I’ve mentioned sounds convincing in and of itself. In fact, I’d find it much more interesting to read additional theoretical arguments demonstrating that the above model is wrong than to read masses of numerical data demonstrating that the above model is right.

But anyway, I agree that the matrix is, if nothing else, an interesting theoretical exercise in its own right – kind of like solving a “Seven Bridges of Konigsberg” type of problem. I don’t have the mathematical background to crack it, so unfortunately I can’t be of any help with it.

[Charles de Gaulle]

@cwo-marc You hit the nail right on the head. Fairness is definitely a quality that is largely based on opinion and perspective. Luckily, I don’t have anyone actually complaining to me that the game is unfair—I think most of the players are much more focused on tricking and influencing each other enough to claim a win—which is exactly what I’d expect (and maybe even encourage) in a free-for-all with 3, 4, or 5 people.

The main complaints I’ve gotten are more like, “Bob kept screwing me up because he moves right before I do.” That’s where the idea of only having to play against every opponent once came to mind, in an attempt to lessen some of the luck of the draw that’s involved.

As you may have noticed, I’ve been almost maintaining a bit of secrecy about what this game is, and that’s because it’s actually something unique we came up with. This is just me being hopeful and daydreaming, but I think the game may have market value, even if only in a digital format. There have been flaws, and we’ve been tweaking the setup try to fix that. I think the setup is at a decent standard now, but hosting these tournaments will give me a good idea of whether or not it needs more work.

I must say, I’m amazed at the depth of thought you and aardvark have explained in relation to what actually goes on in the minds of players in large competitions. I have been focusing so much on the math and given little thought to the amount of psychology involved in tactics and motivations. It’s something I’ll definitely try to consider more in any future tournaments where outside factors and real-life pressure can play a heavy role.

[CWO Marc]

The fact that you haven’t said anything specific about how your game works actually makes it easier to discuss it from a broad theoretical perspective. The theoretical issue I’m wondering about at this point relates to what you mentioned here: “The main complaints I’ve gotten are more like, “Bob kept screwing me up because he moves right before I do.” That’s where the idea of only having to play against every opponent once came to mind, in an attempt to lessen some of the luck of the draw that’s involved.”

What I’m wondering is: to what degree are you trying to eliminate (or compensate for) factors which give one player a potential advantage over another? And with all those factors eliminated, what does the game outcome actually end up hinging on? There has to be some way for Player X to gain advantage over Player Y, because otherwise there would be no mechanism for winning the game. I’m not expecting any answers, since your game is confidential; I’m just framing these as questions for you to think about.

Even though nobody wants to play a game that’s unfair, the flip side is that wants to play a game which is so perfectly balanced and utterly fair that it’s dull and pointless. Games are inherently conflictual. Okay, an exception can be made for certain Euro-style games in which the focus is on teamwork rather than winning and losing, and perhaps that’s what you’re designing, but I’m going to assume that we’re talking about conventional adversarial games. Let’s take A&A, and the conflict which inspired it, WWII. In simplistic terms, the Axis powers start out in a position of military strength and economic weakness, while the Allies start out in a position of military weakness and economic strength. Is this situation balanced? Arguably yes, since each side has both strengths and weaknesses. Is the situation symmetrical? Definitely not, because the strengths and weaknesses are different on the two sides. Is it fair? That’s a matter of opinion. Does it make for an interesting game and an interesting historical event? Absolutely yes.

One final observation about turn order, by the way. The quintessential no-luck-involved game, chess, has a turn order: White plays first. Does this mean that chess has a deep structural flaw and is inherently unfair? I don’t think so. There was a Soviet chess grandmaster (I can’t remember his name, so I’ll call him So-and-so) who was once asked if he preferred playing White or Black. He answered, “It doesn’t matter to me. If I play White, I win because I play first. If I play Black, I win because I am So-and-so.” Blaming one’s defeat on turn order alone is simplistic, unless the game is so badly designed that turn order inherently gives one side such a clear advantage. In such a case, the bias will be obvious without having to play dozens of game to verify its existence.

[Charles de Gaulle]

Success!

I hope I’m not crying wolf (I will double check later), but I believe I found a solve!

Thanks so much for your help gentlemen! Your ideas gave me an idea for a fun way to do this:

A more generic table can be created by making the top row “player 1 through player 21” and substituting likewise wherever the roundel or chip repeats. Each column represents a game, with position in the column determining turn order.