Machine Learning for Optimal Matchmaking

[Music] hi I'm Josh Menke welcome to my talk on machine learning for optimal matchmaking now I've been working in matchmaking for over 16 years at this point and I actually do have a background in machine learning but I've never actually seen the two combined I've used machine learning to figure out player skills but that's just a number that goes into matchmaking I've never actually used machine learning to do the matchmaking itself and in this case I'm not actually the creator of what I'll be talking about today I'm a consumer of it a client the person who actually did all the work in the research and came up with this really nice method his name is Tom Minka and he is a researcher at Microsoft Research I work for 343 industries on Halo and this I was one of the and one of the clients of this work along with Ryan clevon who is works worked on gears of war at the coalition we both had interest in improving

matchmaking through machine learning and I will say in my sixth in my over 16 years of matchmaking this is probably the biggest leap forward I've seen in terms of how you do match me so I hope you enjoy it I think it's great and let's get on with the talk so let's first explain what type of matchmaking were actually talking about matchmaking is the way that players in competitive multiplayer games find other players to compete against and play with and so the way this works is you have a group of players who wants to play a match or and these players could be submitting a request to matchmake from all over the world not necessarily together but they want to match and so they send some information to a matchmaker something about their skill their location other information that could be useful don't worry too much about that yet and then that information is then used by the matchmaker to place these players into matches and into teams to play against each other that's the type of matchmaking that we'll be working with today and talking about how to improve and since we're

talking about using machine learning we should probably define that as well so for this talk a simple definition we can use of machine learning is an algorithm that Tunes itself using data rather than being tuned by hand now we may be asking how do we put these together well match making algorithms are traditionally tuned by hand and what we're going to suggest is we can use machine learning to tune our match making algorithms automatically instead from the data so let's talk first about how matchmaking is done today so the state-of-the-art matchmaking today is pretty much like this you hope you put the players go in the matchmaker kind of hopes that it can make the best possible match out of the players and then it waits eventually it settles for something worse and that goes across whatever your matchmaking on but for example for skill the matchmaker sees a player and it hopes to find the same size same skilled player for that player to magic to match with and if it can't it'll wait and eventually it

settles for an imbalance matched and that's basically how matchmaking is worked for a pretty long time when we're talking about automated matchmaking and this is kind of how it goes again just interview how it works over time you have our matchmaker and a player comes and says hey I'd like to play and then he waits because there's no one else to match me equipment with him yet then another player comes along then the matchmaker says well these two aren't quite a good match I'll wait a little bit longer because there could be something better come along player three comes along and it says well player three still not great but player one's been waiting for a while and it's better than matching against player two so I guess we'll create that match at player one and three they'll play the other and then player four comes along and it's like Oh player four would have been the perfect match with player one oh well too late now I guess four will get to go play with player two and we'll just settle for it now you've noticed what I mentioned that it it could say to itself

Oh player four would have been perfect and that's because if the matchmaker knew what was coming it could create optimal matches they could have waited for player four it would have known oh wait player four is gonna come I know it's gonna I know player four is coming and so I'll wait and then when player 4 comes like if player one a better match than I have been giving him and so if matchmakers knew the whole future then you could solve matchmaking just with combinatorial optimization over the known future so the idea here the key point for this presentation for how this method works is we'll use machine learning to predict what's coming and then because we know what's coming we can just use optimization methods to create these massive these matches but before we get to anything too fancy let's start with how conventional matchmakers work today and then use that as a jumping off point to see how it can improve them and where the machine learning comes in so when we first create a matchmaker today we

generally start by setting up a set of rules for the matchmaker to use to create matches and here I've given the example of the types of rules that we need first we definitely need to define what a match looks like so in this case we need to let the matchmaker know that hey we need eight players and we need them as two teams of four and then often you have some kind of expansion over latency where you say hey we really want the latency between our between the players and the server's are playing on to be no more than 50 milliseconds but as the players weight will excrete increase that tolerance to allow to up to 200 milliseconds you also tend to do a similar thing with the skill gap it starts small and grows over time you also have some bookkeeping type of awk of variables to match on like the build versions need to match the players need to be playing the same game there the game needs to be able to talk to the server and playlists must must match which in Halo we use playlists identify what players are asking to play we can players can only play with each other on

MUC game modes that they both want to play together so you have some simple values like that so this set of rules that tells the matchmaker these things need to match up for our players for fun here's sort of an example of what that looks like in like JSON the highlighted area show kind of how we would set up an expansion rule where we're saying hey you know we want them to have start off at a difference of point two and skill in this in this case but you can increase that over time by a certain amount up to a certain point don't get too hung up on that but that's kind of how that works this is how we're setting up rules the key thing to notice here is that a rule is generally a set of numbers and that's where later on had to give a little bit of a hint we're optimizing over a set of numbers which there's a lot of pretty straightforward ways to optimize over numbers if you know what to look for so again the matchmaker has this set of rules and over time players are coming in and it's looking at those rules and using them to set up those matches and we're an actual request from

a player will look something like this the players sending over a creation time because the matchmaker needs to keep track of how long is the player waited it's sending over an ID of the player so it knows who is who it tells us how good the player is something about their location in maybe in the form of a latency table I give the example here that if a player's favorite data center is east us then you could also just say that they are in East us player rather than keeping all of the ping information it just depends on what your goals are and like I said again the player is going to indicate their playlist ID what they actually want to play and they're gonna have some information about their build version other more bookkeeping type items and so the matchmaker compares for quests of this nature between different players it checks each rule that it has and decides whether or not Bob can match Alice so for example it checks hey is the skill gap between these two less than ten in this case it's five for Alice's 32 Bob is 27 so

they can match that's okay and if all the rules pass then then two players two teams whatever have you are able to match and play together now there's some issues with this approach though as you'll notice first these rules apply globally to all players in the world that are matchmaking which means the same threshold the same gaps that are allowed are the same everywhere and this can be an issue because it may be that if I'm in the UK and I have to play against a u.s. player I may want a tighter skill gap in that situation then I would be willing to accept if I were to play locally I might be okay sacrificing a bit of fairness if my latency at my connection to the server is better so that creates a bit of an issue already and also these rules tend to be static they tend to be the same whether you are in a time of high-population traffic or low population traffic and what that means is during off-peak hours the players will always wait for your rules to

expand if you're using rules of that type that expand if your rules are saying look for a good match but then wait for a while and accept a bad match then you are building in a wait time that is unnecessary in your off-peak hours because those better matches they're just not ever going to happen so why are you making your players wait for them and that's a general point of this talk is if your matchmaker was a bit smarter it would never make your players wait for matches that it knew we're not going to happen so if your only takeaway that you take back to your game is hey let's measure some real-time statistics on our population and on our ticket rates and then don't expand and so just change our rules real time so that when the pop goes down they are immediately start off pre expanded you will already have a nice improvement for your players in terms of wait time at least so static rules are inflexible causes some problems and there's some consequences that all of these kind of come together to cause in terms of both your making players wait yeah you're not dealing

with the regional versus global differences between them and here's kind of what happens when you do that so before I get into that let me define a term I'm going to show to show you what happens because of this and that term is predictability predictability is a measure we use to tell us how often the better team wins and so it's sort of a measure of unfairness so if it was 50 percent that would mean that this match is unpredictable between the two teams and so because it's a perfectly fair match it's close to a draw but if it's like 90 percent that means the better team is winning nine out of ten times and it's just not as fair so I will be referencing predictability as a measure of fairness as it throughout the talk and that's what that means can can the can can the worst team have a shot at winning that match so let's look at some graphs again to show the consequences of using these conventional matchmaking so on the Left what I'm showing here and the first graph is how

many players are looking for a match and you'll notice there's a pretty wide swing between bottom in the top here and that wide swing is what leads to some of these problems that we've talked about and that first one is here is the wait time that during high population times players are waiting for about 20 seconds for match but that goes up to close to 60 70 80 seconds a mat of wait time so their wait time is increasing a lot because of that shift in population in addition you see the same type of effect on other metrics that may be important to you like on the left here there's that predictability metric I mentioned player fairness is going from being somewhat fair at at about 70 percent chance for the best team to win all the way up to like near a hundred percent chance they will win every time this is a pretty big change over time in consistency of the match fairness and you see a similar issue with latency that players during the good population times of the day high traffic they're having very very good latency this is

access latency meaning over what you would get on compared to what your best you could have in which case players are an average going from around 1012 latency all the way up to close to 100 milliseconds of latency as the day changes now with this graph I'm trying to illustrate an even worse aspect of having these static rules for matchmaking what this graph shows is the trade-off between wait time which is on the x-axis and predictability on the y-axis you want that predictability to be close to 50% you want it to be as low as you can go the optimal point of this graph would be the bottom left corner and along this curve you will see what your options are for that trade-off how long do you want to make your players wait to get what predictability you want now in static rule matchmaking though you usually pick a predictability and you just deal with whatever the wait time is but this graph shows us that there's sort of an optimal point at that knee of the curve depending on what's important to you as a designer but

ideally you're not going to want to make a player wait as if you look at this graph and you're making them wait 134 seconds for a match that is 52 percent predictability and that's pretty good that means your your worst players are having a forty eight percent chance to win you could but if you were going for 51 percent you have to more than double their wait time it looks like here so at that point is it really reasonable to keep increasing the fairness where the amount of fairness you're going to get out of a long wait time isn't worth it anymore it's just going up too high now that's and that tends to be a problem with the static rule it's never going to capture what this graph looks like because this graph changes throughout the day and there are going to be a different good point to pick depending on what time of day it is if it's a low traffic part of the day you're going to want to wait at much less of waiting a long time it's going to get not going to buy you very much in terms of how good your matches so this just shows another kind of trade-off between just fairness and wait time that's important to matchmaking so again let's review the consequences of

choosing the current conventional way that we match me so conventional matchmaking what we have there is uh we ignore the real timing incoming request rate at a given time of day we don't take into account that there's a lot more people looking for matches right now than usual or vice-versa we also were to ignore the skilled distribution at that time of day like we don't look at are there good players around right now and we don't look at regional distribution in folks maybe the population traffic is low globally but it's high and say the EU at which point we would want you players to be able to have a different matchmaking preference and this results in either long wait times as players wait for rules to expand and firt to learn that as the system tries to account for the fact that population traffic has changed or we have to deal with it and accept matches that we know are bad in order to have faster wait times neither of which are really that great so and and why would we give players an extra long match an extra long wait time followed

by just as bad a match it's like the worst of both worlds they're getting both long waits and bad matches so we need a more optimal approach to do this and this is where we come into the approach that we decided to look at and before we talk about optimal we have to define what is optimal and for us in order to define that we came up with a utility function so we can actually put a number on optimal so our matchmaker could optimize over that value in addition this approach uses real time statistics we look at both the arrival rate of players and their skill distribution and we take into account that by region so we know how many players in each region are coming in for matches and we know what their skill distribution is at any time of the day then we use machine learning in order to predict what's going to happen in the future so that we can you then use an optimizer to optimize over those future matches that we predict will happen and so let's define again what optimal is

because we have a utility function that gives us a number that we put on optimal and to do this we just wait a number of metrics we feel are important or we let our designers weight them and the metrics we chose for our approach for weight time we assume that players don't want to wait forever we assume skill gap is important and we represent that as predictability as I explained earlier we also have something called equal run win rate which is basically do bad players win just as much as good players and is that important to you or can you have decent skill gaps but it's always in the favor of the of the good players is that important or not and of course latency how important is it that players have good ping on the servers that they play on and so what what this method does which we call true match is it adapts in real-time to optimize those metrics and matches so again it is using real-time statistics predicting what's coming and

then just optimizing over our utility function to give the type of matches that our designers have told us are important so before going into any more details let's look at a high level comparison between our proposed changes and conventional matchmaking so here's some of the important aspects we wanted we want to call out first tuning rather than tuning the values of your match maker by hand true match will do for you real time throughout the day and automatically you don't have to do those hand to knee and this means that instead of being able to only tune once a month or whenever players complained you just let true master the tuning for you all the time and in addition an important aspect of what you can do with true match is that instead of your rules applying only globally to everybody true match can can customize those rules to apply to players and regions specifically so every region and every skill bucket has its own set of rules to help it optimize its own matchmaking and in addition this allows us to do

predictions at our region and a skill level so we can tell a player how long they will wait and that wait time is customized by that players region where they're at and with their skill level lists which is a great which is great for players it also means that because we have these predictions if a prediction doesn't look like what actually happens and this happens consistently that can we can do some form of automatic alerting we can have the system let us know hey there's something wrong going on traumatic isn't able to predict correctly that something's going on that's unexpected right now those types of things are a lot more difficult to catch in standard conventional matchmaking when matchmaking is not working out the way you think it should you often don't find out about it until players start complaining so it gives us some nice automated monitoring and alerting so in addition right now the system which we call true match is has launched with Gears of War 5 and in Halo 5 we've switched over to it and there's some potential here to make it a standard service that third-party folks can use

as well so let's get back to talking about our utility function and we review that so we have this we call a unified objective function every match is going to have a wait time it's going to have a skill gap it's going to have a player all the players Layton sees from within the match and we can measure wind rates over our sections of our population that can all go into a single value that represents the utility of our system of a match of a certain amount of time of day of a region whatever we would like that utility to be and those like equations versus looking at graphs this is kind of what our utility equation looks like it's a weighted sum over these items that we think are important now something that we tend to do to make it easy for designers to use then we set the weight weight on wait time to be just 1 what and what that means is that all of the other weights how long you would wait to have one more

better of each of those so for example if you set w3 for latency if you set that to ten you're willing to wait ten more seconds for one millisecond better of latency and that makes it easier for our designers to trade off how important each of these items are they can trade them off directly on time 1% more predictability is one second more of wait time that's what we tell that's what we can put into our utility which is very nice and there's some nice ways we can use these utility functions we don't have to use them at the global level we could actually put a utility function on every game title and even drill down to every player they can have each have their own utility function to tell the matchmaker what's important to them they also are really nice to use to evaluate any change you make to matchmaking because if you already know what is important to you then changing other aspects outside of that will change the utility and you can then see

if that utility is still what you wanted it to be if you're still meeting the goals now if you have some already existing thresholds and gaps that you're using in your matchmaker we've had we have a few ways we've used that I won't go too much into detail on right now for time but it's not difficult to reverse-engineer those values to what weights they would want to be in your utility function and so now it's the step back at a high level again and look at how the true match algorithm actually works what it's what it's sort of path is that it takes but it's act the actual steps it goes through so first it's going to count the requests it's seeing by type so that's regular intervals true match measure measures how many players are we seeing in each region in every different skill bucket that's important to us and that lets true match have a good idea of what type of players are coming in what does the population look like right now that lets us predict what is going to come soon and so then we

have as an optimizer which then chooses the best rules given what we expect from that population count to create the best matches to create the best utility because it now know what's coming and after we've chosen those rules it dead match makes and players play matches and they see what happens and then after that we measure the results true match we'll look at okay I made these types of matches did they match what I'd hoped would happen with these players did they get the matches I wanted them to have and did the population behave how I expected and using those measurements true match then updates itself it updates the way that it understands how to connect those counts that's getting with what action is going to happen when we match make and after it's updated itself to be more accurate for that time of day it then goes back and recounts again to see what population looks like and we keep going on this cycle yeah a typical cycle time could be about 15 minutes where it is

constantly measuring the population changing the matchmaking rules themselves and also improving its own ability to do the matchmaking to do those estimates to create those rules so let's we'll take some time and go into these these sections a little more in detail so let's talk about the components of true match I talked about counting so the first component we have here is the population tracker that's kind of where discounting happens the player request for matchmaking go into the population tracker and it tracks how many players are coming in of each different type it then creates a population model which is just a simpler version of all the requests that are coming in to explain to the true match system what it expects to happen what what what what the population currently looks like sorry not as much what's going to happen but what the population looks like right now then we have a little system called the metric predictor it's job is to take the current model of the population and use

that to predict what would happen given the matchmaking rules so there's already some rules set up there's some default rules that are made at initialization that exist the metric predictor will take the rules state as it is right now and take the population model and then it will predict this is where some of that machine learning comes in it'll predict okay if this is the population and if these are your current matchmaking rules this is what I expect to happen if you match make that way so it then tells the optimizer this is the expected utility of the matches that will be made because of the rules that you gave me this lets the optimizer decide whether it likes that expected utility and if not it can change itself before any matches actually have been made it can change itself based on the predicted utility and create better rules for the Matt for the better rules for matchmaking before the players use them and it could go through a few cycles of this improving the rules before they're actually applied so again we've modeled the population we predict based on the rules

and that model what's going to happen with those rules and then we tell them optimizer to do a better job in a conic so you can do that so let's dig in a little bit onto how that population tracking actually works just a little bit the population tracker needs to take a stream of requests coming in from the players and create a population model to inform our metric predictor and the way we do that is we assume that the population isn't changing too fast that the population rate isn't going to change too much right now and that actually tends to be reasonable and then we need to be able to return to the metric predictor what we can about what the population looks like right now and there's a few ways to do that a simple way would just be to use a circular buffer where you just hold on to the last say thousand requests and then you use those thousand requests to calculate on-the-fly the statistics of the players that have come in and handoff just basically to

say okay in the last thousand matches this percent came from EU and this is what the skill distribution of those players were that's kind of what the Metra predictor needs to know about maybe a more compact way would it be to be something more like a histogram or you're tracking the counts of the number of players you've seen within a certain bucket of skill and within the different buckets of Regents and that's more in practice what we do so that we can in theory have millions of players being represented in just a compact histogram and be going a little more detail onto what this ends up giving us is we stored those request rates and given a request type we can then return the rates of that type at any given time and by type I mean I'm combining what skill bucket were you in and what region bucket you were you in and so the example here at the bottom is what it might look like I'm a Brazilian player for in Brazil we are seeing 0.01 requests per second for example for players between skills 0.3

and point 4 we've got a skill bucket and we have a region and for all the regions and all the skill buckets the population model can tell the Metra predictor what those rates look like so it knows what the population looks like real time and again customized by skill and region and so with the Metra predictor can do with that is if it knows the population model and it also knows the rules that the matchmaker is currently using it can predict using those rules what kind of matchmaking is going to happen it'll predict for every region and for every skill bucket the wait time for those players what their pings are going to be how fair the matches is are going to be and it makes those predictions for every single match and then eventually it gets back what actually happened it finds out per ticket how long did this player actually wait what was his real latency what was

the fairness of that match and because it gets those actual metrics back the metric predictor can then use machine learning to update its own internal model of how the population and the rules connects to those predicted metrics and because it becomes more accurate it's feeding that information later into the optimizer which can then optimize more accurately and we'll go a little bit more into more details about that because that metric predictor has what are called free parameters inside of it that are tuned with that feedback so let's go a little bit more in so so yeah let's go more into that how that Metra predictor works so for each of those metrics for latency for fairness for wait time each of those has its own formula you can think of that formula as a mini little machine learning model each of those formulas because it's like a little machine learning model has some parameters inside that are updated and adapted over time given the real given the reality of what happened so there can be more and more accurate about its predictions and

that's important and so women will step into a little bit of a quick example of how one of our formulas work and that is the wait time formula this is pretty important because this is how the model knows what the wait time is going to be it's going to predict on average how long players are going to wait and that prediction is important to the optimizer because it's going to update the rules based on the predictions about the wait time and so the optimizer can look at this prediction and say oh if I make the rules this way players are going to wait too long so let me adjust the rules and then I will ask the Metra predictor again okay what about these this set of rules how long will they wait with this set and the vector predictor can then give back a prediction in the optimizer can then say okay that's fine I don't need to change any more so let's talk about what just one of those formulas look like that I call sort of a mini machine learning model so this version on this slide is not the adaptable

adaptive sort of machine learning version this is just a static approximation to what the wait time will be given what it knows about how many requests are likely to be able to match with player T so I got this beaten for every player whose player T there's some set of matches that he can match with given that this formula don't worry too much about the details of this formula it's not as important just to know that there is one it says this you could reverse-engineer this if you want don't do in your head right now but this will return a wait time for 1v1 matches now so that's the first problem right our matches are often for before so in order to make this better without having to manually figure out all the different aspects of matchmaking and population dynamics that will modify this equation we just add some parameters we add a scale which is the C and we add a shift which is B and both of these values are just learned from the data so it just learns based on the type of data it's

getting back what it should actually how it should modify slightly this formula to be more accurate in its predictions and so for a little bit of intuition here that C value goes up depending on how many players are in each match so if it was just one V one then the value is one but as we add more players we are now calculating how long do I need to wait for one more player and then another player so that just scales up correctly in addition the buffering time that gets more to the point that most conventional matchmakers and we we did build this on top of a conventional matchmaker will allow some men a time to gather the tickets together and that is a sort of a buffer fluff time that needs to be worked in to the formula to account for and so that it will learn how long that amount of time is for your particular matchmaking population and matchmaker so this is just an example of the fact that it will improve and adapt the way it even just

predicts wait time all throughout the day appropriately and without having to be manually tuned and again there's a formula just like this for every other aspect of the metric predictor and we don't have time to go into each of them but there's a similar one so that it is even it's able to refine and become more and more accurate on how it predicts what's gonna happen to fairness when we tweak a rule what's going to happen to latency when the rules changed so that is an extra beaut valuable input for our optimizer which we will get to so the optimizer so I keep talking about this optimizer that makes rules somehow now if you remember if you think back I showed you sort of an example what our rules look like at the very beginning and there are a bunch of numbers right it's it's a usually some variable like skill gap some attribute like the skill gap and a value that says the skill gap can't be more than some number so the rules in our matchmaker we don't

actually have the matchmaker write out a bunch of random rules that comes up with we actually pick the form of the rules we still have some attribute and a number that it's worked on by that attribute the difference here is that instead of us manually choosing what that number should be we let the optimizer figure out what that number it picks that number value so in other words the optimizer is just searching over this vector of numbers or each number is just a number that goes into one of our rules and there's a lot of very straightforward off-the-shelf ways to do that you could use gradient descent you can use branch and bound but the end of the day at this point you just have a vector of numbers that you can tweak with your algorithm you can tweak and move them up and down and you have a utility function which is coming now from your metric predictor you're trusting that your metric predictor is telling you what what how those rules are going to affect the matches you're trusting that it is accurate about simulating in a matter of sense what type of matchmaking happens given your rules so now you just use

optimization you give it a set of numbers and you tweak those numbers and then you ask your Metra predictor what the utility was and then you can keep going and refining those different numbers in your rules until you have what you hope is an optimal set of rules so again our rules let's talk again about what these rules look like so here's a fairly classic rulership starting point so skill gap this is a rule that says hey you know what the skill gap between any two players can't has to be less than some parameter that's our number that's what that red parameter that's what's going to be optimized now the question is is this a good rule to use is this the type of rule we should be using this is a very conventional classical way to do this that most of you out there are probably using and when you do this you end up with that graph that we talked about again this graph is what is going to be optimized over this is the predictability represents the skill gap and then you have the wait time on the bottom so you want to pick what the

optimizer is going to do is pick the point on this blue line that gives the best utility now if you decide that both predictability and wait time are equally important that will result in you picking something on the knee of this curve and that's the line you're optimizing over so an important thing to think about is that the form of rule you choose decides what this line looks like and so you can ask ourselves are we picking the best form of the rule is there a better line we could actually get and lines different again every time a day this line changes so every two different times of day you're going to reoptimize but even still at a given time of day is this rule creating a good line or could I create an even better line if I change what the rule looked like and that's the question Microsoft Research asked of course because they're brilliant they wanted to ask and make sure they're picking the right line and to do that they had to change the form of the curve of the form of that formula first to an equivalent form it's the

same it's just as equipmen you can still do a raw skill gap like you were before but the putting in a form that allows them to search conveniently over all possible curves to optimize on so we're not just optimizing on a curve first we're gonna optimize over what's the best curve to pick to optimize on so what they did was they did a bunch of math they wrote a proof I'll spare you for now on but they proved you can rewrite this type of rule differently instead of being just give me the skill gap needs to be less than some number you can instead say no some function of the skills the difference in a function of each skill can just always be less than the number one so you don't need to change it can always just be one your your rule doesn't need to actually change what the skill gap is you just change that function and I give a little example here don't get too caught up in it if you don't want to but basically if you want if the rule if you wanted the rule to be the skill gap can't be more

than 0.5 between two players then you basically make that F function just be two times the skill and that'll get you right back it by using that form to the skill gap can't be more than 0.5 now this is already I want to point out as a nice improvement because now what this is telling you is you don't actually have to change the rule in your matchmaker the matchmaker itself could have the exact same rule which is just a minus B has to be always less than 1 what you're changing is what you're putting in for a and B you're changing you're making up changing the players skill that you put in rather than actually changing the matchmaker and so if you can't again if you don't have time to fully implement true match implementing this aspect is very key because it makes it easier for you to real-time tune potentially what the gap is so he instead of actually changing the skill gap that you allow you just change the skills as they go in and I think that's that's a pretty cool way to do it so they use this form that I spoke

about they use that form of rule to search over all possible rules to find the best rule they should be using so that you can search along the best curve and they did it they found the best curve but we don't actually use the one they found in practice because they found one that's almost as good but really simple to use well relatively simple let's go over what they found that is easy to use and again what I mean here is well I'll show in a second what will review the curves again but first let me tell you what we found we found that instead of saying hey the skill gap can't be any more than some number we've mapped the skills first and this case the mapping we use is we take the players skill and we find what percentile is that skilling is this player at 97% a player or is a an eighty percentile what is the percentile so we're no longer using the raw skill but we're using a percentile of the skill and then we scale that percentile that scaling value that is the parameter that

actually gets changed that actually gets optimized over by true match and what that does is whatever scale you put in there it represents how wide of a percentile you're willing to matchmake over instead of matchmaking on the raw gap you're saying instead of saying this player could match between 1.5 and 2.5 you're saying no this player can match between the 80th percentile and the 82nd percentile so the gap is always a percent of the population which means that the gap is the same for everybody all players get access to all the same amount of other players and because every player sees the same number of players they can match with wait time is constant across everyone and that's why I have the slide I save map the skills so the wait time is constant and everyone has the same way time and so let me go through an example to illustrate it because it's a little tricky of a concept so let's go through this this this

example and remember a gap of one is okay because we don't actually change the gap that's required so our rule will always allow if the gap is 1 and we're gonna pick a scale of 10 which should mean that players can match between 10 percent of the of the population give her a plus or minus so let's let's kind of look at this so we have some players a B and C now their skills are as written point 5 1.0 and 1.5 these are above average players that's assume that the middle is about zero now if we just stopped here and used our rule did no other transformation well remember skill gap of 1 is okay so player a and C okay maybe they're right on the border they could match but a can match B and B cannot see that's the kind of skill gap approach but now let's map them onto percentiles these are the percentiles that would be associated with these players if those skills values were from a normal distribution a standard normal so here's those percentiles a would be

in the 69 percentile C's good player in the top 90 third he's a 93rd percentile so top seven percent player now again if we're allowing a gap of one and we do nothing else but just map them to percentiles these players could all match each other because they're all within one but remember the scale is 10 so we would multiply each of these by 10 to get what is actually the final scaled skill used for comparison and again we've said that a distance of 1 is okay so in this case a cannot match B because they are not within one of each other however B can match C so unlike our raw skill approach this is changed thing we're change things at a who is closer to the middle of the distribution a is going to be a little more finicky in who they will match skill wise because the population is denser there whereas B and especially C as they move out farther on the population density they have a wider skill raw skill gap but they still see the same amount of population just over

a wider gap and again this allows us to ensure that the wait time is the same for all of our players now you may ask okay so you've told me what like why are we doing all this so let's get back to the we did this because we're trying to ask ourselves what type of rules should true match be optimizing over and we wanted to search the space of all possible rules which Microsoft Research did for us because they're very smart and find what rules should we use and I submitted that we use a rule that does this type of transformation and the question is is it really that good and here is a simulation we did to show how good it is so given the same type of data the yellow line is our original classic standard skill gap type curve so if we were to use the original curve we pick the original rule of just has to be smaller than some skill gap we're stuck with that yellow curve that's the best we can do is to search along that curve

and find the optimal point for our utility but like I said earlier you want to be in the bottom left corner that's the best you can be that blue curve that's what you get if you choose that other form of rule that constant wait time that scaled percentile type of rule so we have found a more optimal rule space to search this way as well so not only do we optimize over the best set of rules to pick weight to talk we're not only we optimizing each rules setting we are optimizing the form of the rule itself and so this is a great type of rule to use so another takeaway you could pull from this even if you can't implement full true match is instead of matchmaking on the skill gap matchmake on the percentile gap matchmake so that players can match makes a within 1 or 2 percentile of where they are at on on on the skill curve so again at the end of

the day this is what we ended up with for our rules they compared skill percentiles instead of skills and everyone sees the same size pool of players to match with and we can scale those percentiles as the population changes during our high traffic times we can say you match within 1% of the population during low traffic that can be dialed down to within 10% and again it's like doubly optimal right we've got optimal curve and we find the optimal point on the optimal curve now what about regions how does this work because we've talked a little bit about regions well basically the way we implement this is that every pair of regions hasn't has their own optimized rule so when I am comparing a u.s. player to an EU player there's a rule just for that comparison which makes it so that we can optimize over what that gap should be between those players and let me do a little example to walk through what that effectively does so

here we go we have an EU player she is waiting for matchmaking right now if this was conventional matchmaking she would say timeout after waiting for five minutes because I've just not enough fish in the pool she's fishing she's waited five minutes she was not able to find a full match that way and so she's done and so in the conventional approach when this would happen she would say well I cannot find a match in the EU so I will manually choose to allow matching in the US which she's not as happy about because US matches have worst latency but she'll deal with it just so she can find a match now this is somewhat suboptimal because she just wasted five minutes finding this out now here's the true match approach instead of first trying in one pool and then trying in another pool she will search both pools at the same time but with slightly different sized Nets her net for the EU

pool will be larger meaning that she is willing to accept a larger skill gap than she would accept in the u.s. just so she can get more play more players from the EU to play with so she's fishing with a larger net in in the EU and in the u.s. she will cast a net at the same time that will be smaller so it's less likely to catch fish from the u.s. pool so basically what she's able to do is represent her personal preferences for where she wants to search by the size of the nets now the match will be made as soon as there are a total of say seven fish in both nets so she could catch some from the US and from some from the EU but in theory shall still see the same slice of the population as everybody else available to matchmake in a reasonable amount of time with a good trade-off in her preferences so let's look at what happens when you apply true match to a real-life situation the

example we are taking here came from halo 5 in 6 player free-for-all which is 6 players who are all playing against each other to see who can win this is a good choice for us for true match because this is a playlist that has a very wide request rate over the course of a day the amount of tickets that are coming in at a trough time can be a tenth of what we'll see at our peak times it is not a crazy popular playlist first one of our not as popular ones so it actually makes it a good example for what happens when you apply true match and so let's see what happens at when we use it so what I want to show here I need to be able to compare it to something so you have some sort of idea of whether it's working right or not but here here we're looking at the actual utility over the course of time that we ran this the utility from using true match is that yellow line and you'll notice that over the course of a day it is relatively flat meaning that yes it

was impacted by the lower population but it did okay now what the blue line is is something we call an Oracle because this is what would happen if I did have to choose conventional static rules but I knew the future so I could pick the very best static rule for the whole day for just that one day and that's what you see here you'll see that it was not able to maintain as high of a utility despite perfect knowledge during the lower pop times a day and that's going to translate to some interesting artifacts in our other metrics that we care about so let's go look and see where these true match made these trade-offs so here's the skill gap as represented by predictability you can see here that what happened was that true match decided to raise the predictability which is equivalent to raising the allowed skill gap he matches that are not as fair and so it decided to maintain the utility that it was asked for it would create matches that are less fare so they could still

be somewhat timely whereas the static rule decided or would basically what doesn't really have as much of a choice because it's more static but the best static rule we could pick did not do that and for the most part kept that predictability the same so the matches were more fair on the Oracle during those off hours but we'll see that the trade-off may not have been worth it as we switch to look at what the wait times did so we see here with the wait time true max kept the wait times down to still under five minutes whereas the Oracle if we just pick the best static possible rule known ahead of time is taking players up well past the 10-minute mark into even 15-minute wait times just to keep a difference of about what 10 percent or so in fairness which perhaps does not seem to line up with what our utility so again we see the nice benefit of using true match is that despite wide variances in the amount of players who are available to play we can keep those metrics more flat so the

takeaway from this experiment is we are able to get the same utility as the Oracle during our normal population hours but cut in half relative to the Oracle during the off hours we're this allows us to drop the wait time by 72% compared to using static rules even if we knew the perfect static rule and yes we are trading 13% predictability fairness for those we're trading that off instead of waiting an extra 600 seconds or an extra 10 minutes of wait time which seems fine from the design intent we generally don't ask our players to wait three times as long in order for just 13% more fairness so the takeaway there is true match is doing what we expected as we asked it for from the design intent so let's go into what didn't some nice takeaways overall from true match are first of all because we have a utility function that trades off wait time this allows our designers to wait the importance of different

characteristics of matchmaking directly against how long players will to improve each of those different metrics you want a better latency well how much how long are you willing to wait for one millisecond better of pain you want it to be more fair okay how long are you willing to wait for 1% 3% or 5% improvement in fairness we can do all of those directly through the utility function another really cool aspect of true match is that because we have that metric predictor predicting all those all your metrics we can tell players individually customized to that player how long they are likely to wait for a match we can give nice customized personalized predicted wait times this is something that's sort of a been a holy grail for me in my career in matchmaking to set player expectations on how long they're going to wait and how those be accurate by not only taking into account how much traffic we're seeing right now but how many people are coming through from your region and how many players are coming through at your

skill level so we can set those expectations and we're using real-time statistics in true match and real-time feedback so that we can create optimal rules and optimize how well we're predicting the effects of those rules all throughout the day in ways that you just can't practically do manually so the machine learning is helping us tune real-time and this results in some nice real-time optimized matches for our players which we're trading off the wait time the skill gaps of latency although things are important to us real-time based on the time of day now I wanted to go through some simple improvements that I've covered somewhat of in this talk just remind you of things you can do even if you can't implement all of true match today and one of them is what I talked about with using percentiles for matchmaking instead of matchmaking directly on the raw skill gap and to do this one way to do it is to just as often as you can per hour say three or four times an hour update your own model of the population have some way maybe

you're just tracking simply the quantiles of cross your skill distribution during every time of day just have an idea what those are and then and how what the amount of population you have and then you have to have some kind of mapping that map's player skills to percentiles if a player skills 5.2 what percentile is that if that's the 87th percentile or whatever it may be and then once you have a way of mapping players onto their percentiles you match make on percentile instead of matchmaking on the raw gap and you use your real-time statistics to change the scale based on how much population you have at every given time of day that alone is definitely not as good as full true match but it will let your players feel like they don't have to wait an extra long time during low traffic times of the day to get what's going to be a bad match anyways so just something to think about if you can't take away everything from true match today take away some of these points to use and that's all I have thanks for coming if

you have some questions you can tweet them at me you could try to contact me in my discord you can use the comments section I really I'm enjoying using true match myself in Halo 5 it solved a lot of the sort of issues I've had over time at matchmaking and I hope this has been useful to you as well thank you for coming