Weekly WaveShine #5

Bracket Analysis and Unreal Project Update

Hello, and thanks for stopping by for the this week’s entry in my Weekly WaveShine series! In this week’s entry you can look forward to:

  1. A rather extensive look at the mathematical fairness between bracket seeding schemes [Go To]
  2. An update on my Unreal side project [Go To]
Want more or to check out the architecture for my Unreal side project? Check out last week’s blog entry or my most recent entry!

Game Design Exercise Tournament Bracket Analysis

As I’ve mentioned in previous posts, I’m working through Game Balance by Brenda Romero and Ian Schreiber. I’ve finished reading the chapter on ranking, rating, and tournament systems, and I’ve started working through some of the exercises. The following is an analysis of a tournament bracket system and the fairness of expected outcomes.

The Problem

Consider a 1v1 single-elimination bracket made up of 8 players. Assume that all players have some absolute, fixed representation of their individual skill throughout the tournament such that:

  1.  The 8 players can be ordinally ranked 1-8 with 1 being the most skillful and 8 being the least.
  2. The best player (1) has a 55% chance to beat the next best player (2), a 60% chance to beat the third best player (3), and so on.
  3. Similarly, the second best player (2), has a 55% chance to beat the third best player (3), and so on for all players.
Consider the two bracket seedings to the right and calculate the probabilities for each player to win the tournament and assess which bracket is more fair.

Bracket A – Ordered Seeding

Players are seeded in direct order of their rank.

Bracket B – Traditional Seeding

Players are seeded such that the most skillful player plays the least skillful player and so on.

The Solution

In order to make it easier to calculate all of these probabilities, I decided define the problem mathematically. I could have written a program to actually just brute force the values out for me, but I figured this would be quicker given the limited nature of the problem. If I needed to consider larger or a greater number of examples, I might have done this.

The first thing I did was mathematically represent the probability of each player beating another player such that the probability of Player A (A) beating Player B (B) can be represented as:

P(A, B) = .5 + .05(B – A)

Relationship # 1: Probability of Player A Winning Over Player B

A mathematical representation of the probability of Player A (A) beating Player B (B) given the above properties.

Additionally, given the 1 v 1 property of the game, the following is also true:

\begin{array}{ll} P(A, B) + P(B,A) &= 1\\ P(A, B)& = 1 – P(B,A) \end{array}

Relationship # 2: Identity Between Probabilities

This follows from the fact that only one player can win. Therefore, the probabilities of a player winning or losing to another player should be equal to one.

This is a supporting relationship to help with simplifying the math for the following relationship:

\begin{array}{ll} P(A, C) – P(A, D) & = (.5 + .05(C-A)) – (.5 + .05(D-A))\\ P(A, C) – P(A, D) & = .05(C-A) – .05(D-A))\\ P(A, C) – P(A, D) & = (.5 + .05(C-D)) – .5\\ P(A, C) – P(A, D) & = P(D,C) – .5\\ \end{array}

Supporting Relationship # 1: Simplification of Difference in Outcome Probabilities

This helps to remove player A from the considerations of this relationship.

Next, assuming that Player A beats Player B, then the odds of Player A defeating the winner of the match between Player C and Player D can be expressed as:

\begin{array}{ll} P(A, C, D) & = P(A,C) \times P(C,D) + P(A,D) \times P(D, C)\\ P(A, C, D) & = P(A,C) \times P(C,D) + (P(A,D) \times (1 – P(C, D))\\ P(A, C, D) & = P(A,C) \times P(C,D) + P(A,D) – P(A,D) \times P(C, D)\\ P(A, C, D) & = P(A,C) \times P(C,D) – P(A,D) \times P(C, D) + P(A,D)\\ P(A, C, D) & = P(C,D) \times (P(A,C) – P(A,D)) + P(A,D)\\ P(A, C, D) & = P(C,D) \times (P(D,C) – .5) + P(A,D)\\ P(A, C, D) & = P(C,D) \times (1 – P(C,D) – .5) + P(A,D)\\ P(A, C, D) & = P(C,D) \times (.5 – P(C,D)) + P(A,D)\\ \end{array}

Relationship # 3: Probability of Player A Beating Winner Between Player C and Player D

The end result of all of this simplification makes it so that we actually only need to know two outcome probabilities to calculate the original probability which saves a bit of math.

Thus, the probability of Player A winning their half of the bracket can be expressed as:

\begin{array}{ll} P(A, B, C, D) & = P(A,B) \times P(A, C, D)\\ P(A, B, C, D) & = P(A,B) \times (P(C,D) \times (.5 – P(C,D)) + P(A,D))\\ \end{array}

Relationship # 4: Probability of Player A Winning A Four Player Bracket Over Players B, C, and D

I don’t think there’s a clean way to further simplify this statement, but as you’ll see, we won’t need to calculate this value too many times.

Finally, the probability of Player A winning the entire 8 player elimination bracket can be expressed as:

\begin{array}{llll} P_{W}(A) = P(A,B,C,D) \times ( & P(E,F,G,H) \times P(A, E) +\\ \, & P(F,E,G,H) \times P(A, F) +\\ \, & P(G,H,E,F) \times P(A, G) +\\ \, & P(H,G,E,F) \times P(A, H))\\ \end{array}

Relationship # 5: Probability of Player A Winning Full Bracket

Sorry if the formatting is a little unusual. I wanted to keep the width down so that it’d still look half decent on mobile.

The way this can be read is the probability of Player A winning their half of the bracket before calculating the sum of their odds of beating the other finalist times the odds of that player making it to the finals at all.

One last relationship, I promise! While I was working the probabilities for Bracket A, I realized that all of these relationships have an interesting property where N is just some random integer:

\begin{array}{ll} P(A, B) & = P(A-N,B-N) \\ P(A, C, D) & = P(A-N, C-N, D-N)\\ P(A,B,C,D) & = P(A-N, B-N, C-N, D-N)\\ \end{array}

Supporting Relationship # 2: Probability of Player A Winning Full Bracket

This means that P(1,2,3,4) is equivalent to P(5,6,7,8) and P(1,2) is equivalent to P(5,6). As a result, almost all of the probabilities for Bracket A can be written in terms of P(1,2,3,4) and its relevant combinations as well as P(1,N) where N is any number between 2 and 8, inclusive.

Let’s start calculating the values for each player winning Bracket A. Relationship 5 is going to require each player’s probability of winning their half of the bracket for the first term. Thanks to supporting relationship #2, we can see that the probabilities for Players 5 and above winning their half of the bracket are actually equivalent to Player X-4’s probabilities where X is any number between 5 and 8, inclusive. Thus:

PlayerExpressionValue
1P(1,2,3,4)0.342375
2P(2,1,3,4)0.257625
3P(3,4,1,2)0.232375
4P(4,3,1,2)0.167625
5P(5,6,7,8) = P(1,2,3,4)0.342375
6P(6,5,7,8) = P(2,1,3,4)0.257625
7P(7,8,5,6) = P(3,4,1,2)0.232375
8P(8,7,5,6) = P(4,3,1,2)0.167625

Table #1: Probability for Each Player Winning their Half of Bracket A

I just wrote a quick calculator in Google Sheets to calculate these values. There’s probably a more elegant solution. The probabilities for each half of the bracket add up to 1 as expected.

PlayerPlayer 1 Wins = P(1,N)Player 1 Loses = P(N,1)
2.55.45
3.6.4
4.65.35
5.7.3
6.75.25
7.8.2
8.85.15

Table #2: Outcome Probabilities for Player 1

These values will be used to help compute the final win probabilities for each player in Bracket A.

Finally, we’ll use these values to compute the final win probabilities for each player in Bracket A.

PlayerExpressionValue
1P(1,2,3,4) * [P(1,2,3,4) * P(1,5) + P(2,1,3,4) * P(1,6) + P(3,4,1,2) * P(1,7) + P(4,3,1,2) * P(1,8)]0.2606372484
2P(2,1,3,4) * [P(1,2,3,4) * P(1,4) + P(2,1,3,4) * P(1,5) + P(3,4,1,2) * P(1,6) + P(4,3,1,2) * P(1,7)]0.1832390016
3P(3,4,1,2) * [P(1,2,3,4) * P(1,3) + P(2,1,3,4) * P(1,4) + P(3,4,1,2) * P(1,5) + P(4,3,1,2) * P(1,6)]0.1536608734
4P(4,3,1,2) * [P(1,2,3,4) * P(1,2) + P(2,1,3,4) * P(1,3) + P(3,4,1,2) * P(1,4) + P(4,3,1,2) * P(1,5)]0.1024628766
5P(1,2,3,4) * [P(1,2,3,4) * P(5,1) + P(2,1,3,4) * P(4,1) + P(3,4,1,2) * P(3,1) + P(4,3,1,2) * P(2,1)]0.1236872484
6P(2,1,3,4) * [P(1,2,3,4) * P(6,1) + P(2,1,3,4) * P(5,1) + P(3,4,1,2) * P(4,1) + P(4,3,1,2) * P(3,1)]0.08018900156
7P(3,4,1,2) * [P(1,2,3,4) * P(7,1) + P(2,1,3,4) * P(6,1) + P(3,4,1,2) * P(5,1) + P(4,3,1,2) * P(4,1)]0.06071087344
8P(4,3,1,2) * [P(1,2,3,4) * P(8,1) + P(2,1,3,4) * P(7,1) + P(3,4,1,2) * P(6,1) + P(4,3,1,2) * P(5,1)]0.03541287656

Table #3: Overall Outcome Probabilities for Bracket A

These are the expressions for the probabilities for each respective player to win Bracket A.

Now we’ll move on to Bracket B and start by computing the half-bracket probabilities. Unfortunately, we won’t be able to take advantage of Supporting Relationship #2 to meaningfully reduce the number of probabilities we’ll need to compute. The table and values for the half-bracket probabilities are below:

PlayerExpressionValue
1P(1,8,4,5)0.571625
2P(2,7,3,6)0.451875
3P(3,6,2,7)0.333125
4P(4,5,1,8)0.221375
5P(5,4,1,8)0.158625
6P(6,3,2,7)0.126875
7P(7,2,3,6)0.088125
8P(8,1,4,5)0.048375

Table #4: Probability for Each Player Winning their Half of Bracket B

Calculated the exact same way. Honestly in retrospect I could have done this way faster just using Google Sheets/Excel.

Finally, we’ll use these values to compute the final win probabilities for each player in Bracket B:

PlayerExpressionValue
1P(1,8,4,5) * ([P(2,7,3,6) * P(1,2) + P(3,6,2,7) * P(1,3) + P(6,3,2,7) * P(1,6) + P(7,2,3,6) * P(1,7)])0.3510134766
2P(2,7,3,6) * [P(1,8,4,5) * P(2,1) + P(4,5,1,8) * P(1,3) + P(5,4,1,8) * P(1,4) + P(8,1,4,5) * P(1,7)]0.2403353672
3P(3,6,2,7) * [P(1,8,4,5) * P(3,1) + P(4,5,1,8) * P(1,2) + P(5,4,1,8) * P(1,3) + P(8,1,4,5) * P(1,6)]0.1605204453
4P(4,5,1,8) * ([P(2,7,3,6) * P(3,1) + P(3,6,2,7) * P(2,1) + P(6,3,2,7) * P(1,3) + P(7,2,3,6) * P(1,4)])0.1027318359
5P(5,4,1,8) * ([P(2,7,3,6) * P(4,1) + P(3,6,2,7) * P(3,1) + P(6,3,2,7) * P(1,2) + P(7,2,3,6) * P(1,3)])0.06568066406
6P(6,3,2,7) * [P(1,8,4,5) * P(6,1) + P(4,5,1,8) * P(3,1) + P(5,4,1,8) * P(2,1) + P(8,1,4,5) * P(1,3)]0.04210505469
7P(7,2,3,6) * [P(1,8,4,5) * P(7,1) + P(4,5,1,8) * P(4,1) + P(5,4,1,8) * P(3,1) + P(8,1,4,5) * P(1,2)]0.02483913281
8P(8,1,4,5) * ([P(2,7,3,6) * P(7,1) + P(3,6,2,7) * P(6,1) + P(6,3,2,7) * P(3,1) + P(7,2,3,6) * P(2,1)])0.01277402344

Table #5: Overall Outcome Probabilities for Bracket B

These are the expressions for the probabilities for each respective player to win Bracket B.

Analysis: What's Fair?

So to summarize, I’ve gone ahead and aggregated the key data points from our prior calculations:

PlayerReaching Finals (Bracket A)Reaching Finals (Bracket B)Winning (Bracket A)Winning (Bracket B)
134.24%57.16%26.06%35.10%
225.76%45.19%18.32%24.03%
323.24%33.31%15.37%16.05%
416.76%22.14%10.25%10.27%
534.24%15.86%12.37%6.57%
625.76%12.69%8.02%4.21%
723.24%8.81%6.07%2.48%
816.76%4.84%3.54%1.28%

Table #6: Outcome Probability Summary

This is to make it easier to read and compare the probabilities we calculated above. Each cell represents the probability for the player on that row to achieve the outcome listed in the column above.

Based on the graph to the right, we can make a few observations:

  1. We can see that the curve representing winning in Bracket A (yellow) is not monotonic (strictly decreasing). In fact, Player 5 has a greater probability of winning than Player 4 in spite of the fact that Player 4 is technically more skillful.
  2. The curve representing reaching the finals in Bracket A (blue) is also not monotonic, and is in fact even more exaggerated than winning in Bracket A (yellow).
  3. Players 1, 2, 3, and 4 in Bracket A are just as likely to reach the finals as Players 5, 6, 7, and 8, respectively. This means that Player 5 is in third quartile (top 25%) in probability to reach the finals while being below the median in skill. Likewise, Player 6 is above the median in probability to reach the finals while being below the median in skill.
  4. The probabilities for reaching the finals and winning in Bracket B (red and green, respectively) are monotonically decreasing. In Bracket B, if you are more skillful, you are always more likely to have a positive outcome.
  5. For Bracket B, the correlation between skill and probability of reaching the finals is stronger than the correlation between skill and probability of winning. This means that skill matters more when determining whether you’ll make it to the finals vs. whether you’ll win.

Figure #1: Graphical Representation of Summary

This is a graphical representation of Table #6, color coded based on the legend above. Player is the horizontal axis, and percentage outcome is along the vertical axis.

I think ultimately, what’s fair will come down to down to what your definition of fairness is and the intention of the overall tournament. For most people, Bracket B will probably seem more fair. Top players can expect to be more likely win than any player that is worse than them. Furthermore, top players can expect their skill to have even greater influence when it comes to reaching the finals and ultimately earning 2nd place. This is especially important at top levels of professional play, where economic outcomes are directly tied to winning or losing. For professional players, placing lower than a less skilled opponent and ultimately being compensated less would definitely seem unfair. Since most tournaments seek to determine the top player as consistently as possible, it makes sense that Bracket B’s seeding is considered “traditional seeding”.

I do think, however, than an argument can be made for Bracket A to be considered more fair. Under such a format, on average, top players still generally can expect to win more often, but lesser players have better odds. Furthermore, below average players have significantly improved chances of reaching the finals and placing second as compared to Bracket B. For some players, they might have better odds of making it to finals than a better player. Under such a seeding system, skill would be a lesser determinant of average result and the choice to participate at all would carry greater weight. These properties probably make Bracket A pretty undesirable to professionals and spectators compared to Bracket B.

The context where Bracket A’s seeding system would potentially be desirable would be in “arcadian” or amateur tournaments. I actually have personally played in arcadian tournaments before while playing Super Smash Bros. Melee competitively. These tournaments specifically denied entry to top level players both regionally and globally so that average level players would have a greater chance to win. These tournaments were somewhat infrequent, but especially popular with attendances often rivaling those of local major tournaments. From a tournament organizer’s perspective, these tournaments set out to better engage the average player who made up the majority of the tournament attendee population.

Because of the number of players and overall low amount of time and exposure within the scene, most players didn’t actually know how good they were relative to each other. This would make it difficult for them to tell what kind of seeding scheme had been employed. Thus, if one employed Bracket A’s seeding, then there was a high chance that the median player would place second and could potentially even win the tournament. Either outcome would be high visibility and would cause that player to be regarded as having high potential within the area among other players. Players that are actually more skillful than the high-placing median player would then play them either casually or in traditionally seeded tournaments, likely beating them and feeling like they’d improved since the arcadian tournament, giving a sense of progression to above average players that they might not normally get. So if this seeding scheme were employed but not discovered, it would actually serve as a source of motivation for increased participation in subsequent tournaments, regardless of whether they followed an arcadian ruleset or not.

Thus, in similar settings where the aim of the tournament is to drive player engagement over skill-accurate outcomes and where this seeding system would be difficult to detect, then Bracket A’s seeding could actually be more desirable. To this day, I’ve never asked the tournament organizer that ran the Michigan arcadian tournaments, but I wouldn’t be surprised if this was at least part of the conversation when seeding the bracket.

So to conclude, we can see that mathematically, Bracket B is more “fair” in terms of what people generally expect from tournaments, with better players placing higher and winning overall more often. Bracket A is more “fair” in absolute terms, in that the average result between players is more equal on average and is less heavily influenced by skill. Depending on context, either bracket could be desirable, and it comes down to the designer to decide on the desired tournament experience and then select the appropriate tools to achieve that.

Unreal Project Update

I’m currently working on bringing cursor control to the MOBA-style free camera I’m working on. I’m also taking a second look at the architecture I have in place and am experimenting with improving the way I’m using the Gameplay Ability System (GAS) so that I can use tasks more flexibly. I’ve been out of town this weekend, so I haven’t been able to reach a “done” state with things, but once I have, I’ll be sure to make a post about the changes I’ve made.