Wednesday, February 19, 2014

Tournament Seeding: A basic look at how player positions change tournament results.



I have not updated this blog in a long time and I decided it’s been too long.  So time to finally put another entry in!  Last time I took a look at the simplest double elimination bracket you could come up with and how the bracket was affected by uniformly changing player 1’s chance of winning a single game.  You can see the results from that study at this link

http://loyalsol.blogspot.com/2013/04/winning-major-just-how-good-do-you-have.html

It took me a while to get back to this both because I’m still working on my PHD time is precious and also that I wanted to update and optimize the code some more before proceeding to make larger studies easier to do.  The previous version of the code required me to recompile every time I wanted to change the bracket size which made large scale studies tedious. So I took the time to generalize the code into a version where I could control all the parameters from a simple control file at run time.  To do so, I had to essentially gut a good portion of the code and then go through the debugging process to ensure the result I was getting was accurate.   Took some time, but finally got back to where it should be.   At any rate hope you guys like this. 

Set up:

This time I want to up the level of complexity a little.  So this time we are going to examine another common topic that comes up and that is seeding.   If you go to a local tournament you might have a situation come up once in a while where two of the better players have to play each other fairly early in the bracket or you might have the person who has to face the top player in the first round go “Ah man! Do I have to play him in the first round?!!”   But this leads to a question how much does playing the top player early affect the outcome of the tournament?  So to begin to look at this I set up a tournament bracket with two unique players which will be the top players and the remaining slots were filled by “field” players.   This is the simplest “seeding” scenario you can have.   Player 1 and Player 2 were set to have a 90% chance to beat any of the field players while Player 1 had a 40% chance to win over Player 2 head to head.  So basically in this scenario Players 1 and 2 are well above the rest of the players in terms of skill, but Player 1 has a slight disadvantage against Player 2.   In this scenario the focus of the study is how the chances of winning the tournament varies with how far apart the two players are positioned.


Fig 1.  Illustration of how distance is defined. Since the first round the two players can fight each other in winners bracket is in round 2, this would be defined as a starting distance of 2.  In a 32 man bracket 5 is the maximum distance the two players can be separated by.
The starting distance is defined as the round the two players will meet in winner's bracket assuming both players win all of the matches up to this point.  This provides a nice clean way to turn 32 possible starting positions into simply 5.

Results:

When I first started these calculations I had a couple initial ideas what I might expect, but when I actually performed the calculations I found some very interesting results.  


Fig 2.  The probability plots for Player 1 and Player 2's chance of winning the 32 man bracket as a function of the starting distance. 


This first result I noticed was the overall win rate of Player 1 in general shoots down heavily just by having Player 2 in the Bracket.  To compare Player 1’s chance of winning a tournament with a 90% win rate against the field in the absence of a tough matchup is between 70% and 93%, but the addition of a single disadvantaged match up was enough to drop the overall win rate well below 30%.  In this case the match up isn’t even that horrible, but because of the way the double elimination format works player 1 will have to beat player 2 twice and more than likely one of those times will be in grand finals. 

While the first result was interesting (but not completely shocking) the most interesting result was tied to the seeding.  The graph is shown in terms of the first round the two players could meet in assuming both players won all their matches in winners prior to that.   So for instance if Player 1 was in the 1st slot and Player 2 was in the 3rd slot, the first round the two could possibly meet in is the 2nd round.   The graph shows two very interesting trends.   For player 2 intuitively his chances of winning the tournament progressively go up as the two players are placed further and further apart, but for Player 1 it is the exact opposite!  Player 1 has the highest chance of winning the tournament by facing Player 2 early in the tournament.  Player 1’s worst chance is if he is on the opposite side of the bracket from Player 2.  

So how can we explain these results? Well it’s actually not that difficult.  The best chance for Player 1 to win the tournament is to knock Player 2 into losers early so he has to run the whole losers bracket which gives Player 2 the highest chance of being knocked out of the tournament.   If the two players are on opposite sides of the bracket so that they can only meet in winners finals or in the losers bracket, this causes Player 1’s chances to drop more because now if he meets Player 2 in winner’s bracket Player 1 will have to play a 3 out of 5 set instead of a 2 out of 3 which extends Player 2’s advantage.  

Now the thing to note here; however, is that advantage is very small.   The best chance of winning and worst chance in a 32 man bracket only differ by about 2% with the largest drop being from the winner’s finals drop. In terms of who wins the tournament seeding makes a very small difference for player 1.  For player 2 the difference increases by about 2.3% from worst seeding to best seeding. Overall seeding has an effect on who wins the tournament, but the effect is very minimal.   

The seeding makes very little difference toward who will win the tournament.  So the question becomes   “Does seeding make any difference at all?” Well in, it actually does.  Because in a standard 32 man tournament the top 3 positions are usually paid out, so while Player 1 has the best chance of winning it all by playing Player 2 early does he have the best chance of actually getting top 3 consistently by playing player 2 early? 


Fig 3.  The chance of Player 1 placing in the Top X or higher.  For the X-axis a value of X=4,means Top4 or higher. 

Table 1.  Tabulated probabilities of getting TopX or higher for all starting distances.

Well the answer to this is that playing Player 2 early hurts Players 1’s overall chances of getting into the money positions.  The same effect that helps Player 1 “win it all” is the same effect that lowers his chances of placing in the Top spots.  Losing to Player 2 early forces you to run through all of loser’s bracket which increases your chances of getting “scrubbed out”.   As a result player 1 won’t place in 2nd as consistently as when the bracket has the players seeded as close as possible.  Player 1’s chance of placing in the money goes down from 98% to 83% from the furthest possible seeding to the closest.   This is also demonstrated by the chance of player one entering grand finals from the winner’s side of the bracket. 


Table 2.  Player 1 and Player 2's chance of making it to grand finals as a function of starting distance. Listed as the chances of making it from Winner's Bracket, Loser's Bracket, and the sum of those two giving the total chance of making it.

 Now of course we also need to take into account the fact that you get far more money for 1st than you do for 2nd or 3rd so we also want to take a look at the average and not just the overall placing percentage. Fortunately this is actually very easy to estimate.  Let's assume we have a normal 70/20/10 tournament split which is standard for a lot of tournaments. For a 32 man/$5 entry tournament the total pot will be $160. As shown by the graph, seeding player 1 further away from player 2 will result in a much more consistent amount of cash even when you consider player 1 has a higher chance of getting 1st by playing Player 2 sooner. And actually when you adjust for the average income you realize that once again the best position for Player 1 is either opposite side of the bracket from Player 2 or where the two players will meet in the round right before winner’s finals.   While the latter position has a slightly higher average, the opposite position has the most consistent chance of getting some money even if it means less of a chance of getting 1st.

Fig 4. On the left Player 1's average expected winning based on starting position and on the right Player 1's chance of finishing in any of the three money positions.


Conclusion:

The first message to take away from this was that the overall win rate dropped significantly for Player 1 by simply introducing a player who has a small advantage over Player 1.  This once again shows that the double elimination bracket coupled with 2 out of 3 and 3 out of 5 sets tends to exaggerate advantages players have over each other.  In this case you can see that a 6-4 advantage is enough to shift the chance of winning a tournament into a 75%-24% split between Player 1 and Player 2. (Note: 75% and 24% don’t add up to 100% because the field consumes a small percentage).  It goes to show that a single disadvantaged match up in the tournament can bite you big time if you are forced to play it. 

The results from this simulation paint a very interesting picture.  On one hand by seeding the two players as far away as possible both players have a much higher chance of placing either 1st or 2nd and it also ensures that the better player will have the best chance at winning.   If you are the underdog you will get paid more consistently by being seeded as far away as possible, but you also have the worst chance of getting 1st place by being seeded that far.    If your goal is a consistent placing then being seeded far away is what you want, but if your goal is to get first place (say to win a large prize that goes with it) you actually want to face the top player before you get to winner’s finals where you have a better chance of winning a 2 out of 3 set instead of a 3 out of 5 in addition to the other player having to play more loser’s bracket matches.  In terms of funding using a standard 70/20/10 tournament split, the highest average is also to play the top player right before winner’s finals.    The top player overall benefits the most from seeding as his odds of winning and odds of placing high only go up with being put further and further apart. 

In my next article I will add some more details to this study such as bracket size effects,  how things change upon the addition of a third player, etc.  I plan on getting this next one out much faster. Fortunately the bulk of the coding is done so all I need to do is small tweeks here and there. 



 

Sunday, April 21, 2013

Winning a Major: Just how good do you have to be? (Part 1)

I had originally started this project to put numbers to what we see in fighting game tournaments.  Sure we know top players are really good,  sure we know advantages matter, but the question is "How much do they matter?" or "Just how good are the top players?"

If you read my previous blog post you saw I looked at how advantages effect 2 out of 3 sets as well as 3 out 5 since these were related to tournament success; however, I quickly found the math behind the problem grew too large too fast. So in order to actually get a result I wrote a computer code to simulate multiple tournaments and collect statistics.   The math behind it is a little bulky, but the general idea is straight forward.  Set up a bracket (size chosen by user), run each match, and record the results. Just like a real tournament except this one is controlled through probability.  As I also stated in the last article, I don't want to get too technical because this is meant for a general audience. More technical explanations can be given upon demand (It includes words like Monte Carlo).  I am also planning on releasing the code at a later date, but as of right now it is not the most user friendly.

With this code we can simulate a wide variety of tournaments by adjusting the individual match ups.  By averaging over different tournament brackets it is possible to obtain the probability of winning for a scenario.

Introductory Data



So one of the first cases we can study is a very simple example.  Let's say we have a tournament where every player has the same chance of beating any other player with one exception: You are the one player whose has different odds of beating the other players.  This is actually a rather simple set up, but it gives a great deal of information.

For this data, I took player 1's match up probabilities against everyone else in the tournament and scaled them up incrementally from 5% up to 95%.  Obvious at 0% the result is easy to predict since if you have no chance of winning a match you have no chance of winning a tournament and likewise at 100% if you always win every match up you will never lose a tournament.

I also changed the number of players to look at the effect of the bracket size.  The numbers you see are in powers of 2 since new player slots are introduced when the bracket doubles in size.    The size of a typical major is above 128 while local tournaments are around 8-32.

The data is presented in two ways.  The table contains the raw data and the plot shows a color plot of the same data. The bracket size is on the top.  The bolded percentages is player 1's win rate against the other tournament players (IE for 60% if I played 10 games against any other player I would expect to win 6 out of 10).   The percentages listed are the number of first place finishes out of 100,000 samples.

The contour plot shows the lowest win tournament percentages in blue while the highest are displayed in yellow.  The x axis is the number of players in the bracket and the y axis is the match upwin percentage. 

One of the first ways we can check the data for accuracy is to look for values which we can easily calculate own our own.  The easiest case is when the match win rate is set to 50%.  With the way the bracket was designed,  if player 1 has a 50% win rate then every player has the same chance of winning.   Thus the expected win rate is equal to 1/(# of players).  If you calculate this for each bracket you see the simulation data matches this. So the simulation matches perfectly with the expected value for the easily calculable case.

The first trend of interest is that for any given win rate, as the bracket increases in size the win rate also declines.  This is actually to be expected.  If you have more players you would expect there to be more chances to for you to lose.  While this is obvious, one of the things that was not entirely obvious was large this effect was.   For values less than 50% the result does not change much (Obviously since you lose most of your matches), but for values above 50% there is a very interesting trend.  Smaller win rates drop off much much faster than larger win rates!   

 If you notice at 60% for a small local you have a very reasonable chance of winning, but by the time you scale it up to the size of a major a 60% match win rate you will win roughly 1 out of every 20.  This means that even if you are the best player if you are only slightly better you will still lose more majors than you win.  A 60% advantage is not nearly enough to be a consistent winner because odds are you will get randomed out in a bracket that size.   In fact only match win rates of 85% or higher actually translate to winning over half of your tournaments consistently. It actually speaks to the skill level of many of the top players when they are able to consistently win or place at majors. They aren't just slightly better,  they have an enormous edge.

This brief examination actually shows us quite a bit of insight.  In order to be a consistent winner you not only need to be just better, you need to be much better than your opponents.   In addition you can actually see for a given bracket size that every little bit helps.  Every advantage you gain over your opponents gives you a much greater chance of coming out in first place and it becomes really pronounced for large brackets.  I graphed the data for the 512 man bracket so it is easy to see.  After 50% the probability of winning a tournament beings to rise a little, but after about 65% it shoots up fast and at that point every additional percentage dramatically increases the chance of winning a major. 


  
I will be going into much more detail in my upcoming posts.  I will be going over probability of placing in the top 8,  how first round byes effect your chances of winning,  what happens when a top player is in your bracket,  and other related topics.  Hope to see you guys again.


 

 Q&A



Q: But what if (Insert Player Here) has a bad day and gets knocked out early?

A:  This method actually takes that into account.  When we talk about win rates that includes fluke losses.  I mean if a player like Daigo had a 96% win rate against other players that 4% are the rounds where Daigo had an off game and there is a small chance that he could have two bad games in a set resulting in getting knocked into losers early.    This is all accounted for by the numbers.

Q:  Well in a real bracket I'm going to have a lot of varying win rates.  So why is this any good?

A: Yes in a real bracket you do, but the thing is the tournament win rate is still related to what you see.  For instance if half your match win rates are 60% and the other half are 50% then your tournament rate is in between 50% and 60%, but you would expect a higher deviation.  In other words it becomes bracket dependent.   You could have all your advantaged match ups on your side of the bracket and like wise you can have all your even match ups.   But at worst you will have the 50% probability and at best you will have the 60%.

More detailed situational data will be presented in the later additions.  Right now this is still very general.  

Q: But what about character advantages?  How does that factor into this

A:  That is also taken care of by the numbers.   If I am equal skill to my opponent and we are playing a match up that is bad for his character it will be reflected by my win rate vs his win rate.






Sunday, February 5, 2012

Theory Fighter meets Theory: How do matchup numbers affect sets and tournaments?

 Preface:

This article can get a little lengthy and also makes some math references, but in general I tried to keep the math language down to make it more readable for a general audience.  If you are the kind of guy who likes math then I can write a more detailed description how I got these results. 

I will also note this is my first time trying to type on this website so some of the formatting may be screwed up because it didn't copy perfectly from MS Word.

P.S.  If you are lazy and don't care about how I got this, skip to the results

Introduction:

Tier lists and match up charts…We all know of them and we all know how much trouble they can cause. They are often our way of ranking against all the other characters in the game. In an ideal world there would be no problem with match up charts, but of course we know quite well that our world is far from ideal. A single trip to any major message board will show you this fact.  You end up with arguments that are a combination of egos, inexperienced players, over-exaggerations, under-exaggerations, trolls, random posters who add nothing to the debate, and then the occasional knowledgeable poster who finally adds to the discussion. So I decided to do a mathematical analysis that would (hopefully) be much less controversial and also provide some useful information at the same time. Now before we get to the meat of this I just wanted to state my credentials.  I graduated from Washington State University (GO COUGS)  with a degree in both Chemistry and Mathematics.  I am currently doing my PHD in Chemistry at Louisiana State University (GO TIGERS!) specializing in Physical Chemistry which is a probability heavy field.

So one of the common tools we use in rating characters are match ups.   We usually define this as the chance of winning a match up given two players of equal skill.  This is usually a measure of how balanced or unbalanced a matchup is.   Although everyone should know, we say a 5-5 is a balanced match up or that it is a coin flip who will win.   A match up that is say 8-2 is a match up where one character’s tools overpowers the other’s to the point that the matchup is very one sided.   Now I am going to keep this general to keep the arguments to a minimal so I won’t use any game specific examples. 

You might say this next part is obvious for 95% of the population of the world.  If I wanted to know my chance of winning a 6-4 match up in my favor it is simply I have a 60% chance. That is rather obvious, but just saying the chance of winning a tournament match of this type is simply 60% is terribly wrong!  In actual application we never play just a single game, we always play sets!  In a set we play till one person hits the critical number.  In a 2 out of 3 set we stop if a player wins 2 games because the third one is irrelevent.   

So the question becomes: "What is the probability of winning a set?" The approach we can take is to treat this in the same manner in the same way someone would treat a simple coin flip. Fortunately this math is well explored.  Let’s say we have a fair coin where the chance of getting heads or tails is equal, basically a 50/50 chance.  We want to know the chance of getting 2 heads out of 3 flips (which translates to winning a best 2 out of 3 set).  According to a normal coin flip there are 8 possible outcomes which you can write out to prove it to yourself.  Out of those 8 possibilities here are the orders that would qualify as getting two heads

HHT, HTH, and THH

So there are 3 possibilities and so the chance of getting two heads is 37.5% or 3/8.  Now at the same time we would also say that getting 3 heads is just as good because in a tournament if I win the first two matches we don't even play the third one. So we add the 1/8 chance of getting 3 heads and we find our chance is 50% which is what we would expect. Both players have an equal chance of winning the set given an equal match up.  Now you might ask,  what happens if the chances of getting heads and tails are not equal (For example: Chance of getting heads is 60% and Tails is 40%).   Fortunately for us this math has already been worked out and is ready for us to use. The name in math for this distribution is called the binomial distribution. If you really want to look this up go for it, it is very easy to find and use. If you wish to replicate my results for a set of any size all you need to do is add up the terms that are equal to or greater than the number of wins required to take the set.  So for a FT5 (or best 5 out of 9) all you need to do is add up the probability you will win 5, 6, 7, 8, or 9 times.

The results for individual matches:
So what does this break down to?  Well for starters let’s just examine how good/bad match ups can affect a simple tournament match.
   This table contains the calculated results of common sets that occur within a standard tournament.  The way to read this should be straight forward,  just find what the match up of interest is (For example if your character has a 4-6 match up against your opponents) and this will tell you the chance of winning each set type.  

As you can see the probability of winning a 2 out of 3 set quickly differs from the individual chances of winning a single game.  Each time you add an additional round the chance of overcoming a bad match up goes down and the chance of winning a good match up goes up. You can also see that in grand finals the match is inherently slanted toward the winner side because the loser must win twice while the winner only needs a single win.  

So this gives us the chance for each individual match inside of a tournament so our next question is how can we use this information to calculate the chance of winning a tournament which is a combination of several of these matches? In order to extrapolate this into a full sized tournament there are a couple issues to deal with. The tournament size will determine the probability because the more matches you play the more chances for something to go wrong.  For simplicity I am going to use a 4 man double elimination bracket as an example since it is the simplest case and actually shows some rather interesting information.  All the probabilities will drop as the tournament size increases so these in a sense are the "best case" odds.  

The second issue is that every tournament is a different combination of match ups and the probability will reflect that. Sometimes you might get unlucky and get a bad match up out of the gate or you might never run into one. So to get around this complication I suggest using an average match up instead of an absolute match ups. There are two ways to do this.   

The most accurate way is to average the match ups for a specific tournament bracket.  For instance let’s say my characters match ups with the other 3 characters are 3-7, 5-5, and 5-5. So my average match up for the tournament will be about 4.3-5.7 or slightly better than 4-6. You can also find the error associated this rather easily. For this example the standard deviation is about 1. So we would expect this characters chance for any given tournament set up is between the chance of 5-5 or 3-7 which.  The problem with this method is if you extend it to large tournaments it becomes a nightmare to calculate. 

Now the second way is to create an average match up for my character’s match up as a whole.  Or in other words average your match up chart and figure out your character’s average match up.   The problem with this approach is the fact that some characters are more likely to be in a tournament than others.You would have to work out some system to make sure it is weight properly, but I am not going to get into that right now. For my small example the first method will work just fine.  

When all is said and done: 

When you finally finish with the math (It took me two days to finally work it all out), YOU FINALLY get to the Results!  Here they are boys. 


 You can also display this information as a graph for easy visualization:


These results shows that based on shear probability that the chance of winning even with a small tournament bracket rapidly changes with the average matchup.  Just having a slight edge can almost double your chances to win while having a slight disadvantage can drop you by a large amount.   The 5-5 probability makes sense since if everyone has the same chance out of 4 players then each player has a ¼ chance. For my example of a character who’s average match up in the tournament is 4-6 with an error of 1. The most likely value is around 8-9%, but depending on luck you can be between 1-25% if you get a favorable bracket.  If I get screwed and have to play the 3-7 more than once or early on then my chances go down, while if I never play the 3-7 match up then my chances go up to 25%. 

What to take home from this:

So you might be asking the question, ok why should I care? What these results tell us is that bad and good match ups have a massive effect on the ability of a character to make it through a tournament and win it. Now you might be thinking “Oh so that means I have to play top tier in order to win.”, but there is another side of this.   

Let’s say you have a match up that is really a problem for you even if it isn’t supposed to be bad. Having this one match up that gives you difficulty can provide your own personal barrier to winning and drop your chances. It is an encouragement to get better in those match ups because as you see above just increasing your odds of winning a single match up greatly increases your odds of winning the whole thing! Just giving yourself even a slight edge over everyone else massively improves your odds of winning. It isn’t about necessarily what we traditionally think about match up numbers, but rather you can also view this as your own personal match up chart and how it effects you!

I may release a more detailed version if people wish to see it, but for now that is all.

-LoyalSol