Fixing MM (also,why it may never be perfect).

Comment below rating threshold, click here to show it.

Syrail

Senior Member

12-15-2010

This is meant as an informative post. I'll be linking to various references, so if you don't understand something, read through them and hopefully you can learn something new.

Matchmaking looks like a pretty simple problem. We all know what we want in a game, and a good basic start is this:

-Everyone's Elo is close to mine
-Everyone's Summoner Level is close to mine
-I did not have to wait a long time for a match.

The fact is, a perfect solution does exist to this problem. However, it's not feasible to find that solution. I'll explain enough to demonstrate why this is the case.

(I'm going to start flinging around capital letters soon, and this is just related to Set notation. Basically it's shorthand for sticking stuff in groups and comparing them to each other.)

Let's just start with the simple case, and ONLY consider Elo and summoner level. We can define the simple problem like this:

-Let's call a "player" P, where each player in P has an Elo rating and a Summoner Level.
-Now for groups, which are just a set of players, from 1 to 5. We'll call them Gn, with the n just being a number showing how many players are in the group.
So... G1 = {P1}, G5 = {P1,P2,P3,P4,P5}.

-Now let's call a "match" M a set of 10 different players {P1...P10};

-Finally, let's call the queue Q, where Q contains all players and groups waiting to be placed in a match. Q = {P1..Pn, Q1...Qn}

Our first problem, then, is to find a set of M's given a Q, with each P in exactly one M. Alternatively, we can say that for all P in Q, there is only one M where P is in M.

We can simply just drop every 10 players into a match, and BOOM, instant matchmaking! Right? .....right?

Of course not! Some players are in groups, so we have to keep them together! We'll just start by combining our groups first (gotta be fair, we don't want any premades going up against full pubs!), and then fill the gaps with solo players. For example, we might make M = {G2, G2, G1}, or M = {G2,G3}, or the dreaded M = {G4,G1} , with just one pug and a premade.

Now we're done, right? Nope. This is still wrong. We have groups, but they could be any rating at all, and that's just no fun for anyone.

So now this turns from a simple grouping problem into an Optimization Problem

The most important part to notice is this:

Quote:
an optimization problem is the problem of finding the best solution from all feasible solutions.
Let's talk about these "feasible Solutions". In solving the previous problem, we found exactly one (A set of groups of 10 players)

To find the truly "best" solution, we first need to find every possible solution of the problem. This takes a while, and is related to the problem called Set Packing, or, more specifically, maximum set packing. This problem is "NP-Complete", meaning in part that no one has yet found a way for it to be solved in polynomial time . In plain English: THIS WOULD BE VERY SLOW. And that's just to find the POSSIBLE groupings, not to figure out which one's the best!

In the real world, solving the problem that way is all kinds of impractical, and it's usually easier to just make an educated guess. For example, you could sort all your people by their Elo, and then pick some nearby folks, sticking them in a group. This is actually realistic, but isn't perfect, since you don't always have 10 people at exactly 1337 Elo to group together. This means that often you will be paired with the people who are near but not exactly at your rating.

There are many other things to consider too. What do you rate a group on? Their average Elo? Some adjusted value? Just how long should a player have to wait without anyone else in their Elo range logging in before they should be moved up or down a bracket for matching?

All of these things boil down to fancy guesswork. This guesswork WILL get better with time, and not because "your Elo will get to where it is supposed to be" (Even though it might), but because I can guarantee you Riot is gathering data on matches, and closely watching this data to tweak and improve matchmaking. The thing is, this information can't catch everything. You can't just say "twitch was drunk this match", "Shaco spent all game berating his team".. As far as info you can analyze goes you just have kills, deaths, assists, and win/loss information. Numbers.

"Get to the point, Syrail! How do we fix it?
You'll hate me for this, but the answer is easy: Follow the Summoner's Code. Play your games, and play them as well as you can. Be a good teammate, even if others aren't, and do your best to pull a win out. The more players do this, instead of leaving or AFKing, the more good data is available for Riot to look at when they tweak the rules of MM, and the better the guesses become. Every game you AFK, leave, or undermine your team in provides either no information at all, or even worse, bad information, which doesn't make it better for anybody.

it's important to notice that these things would apply to even a system that did not use Elo, so arguing that chess scores do not work in a team game is pretty much moot. If you insist on continuing to make that argument, then feel free to prove me wrong by designing a system that is provably better. I'll readily admit being put in my place, and you'll probably be very rich, or at least get a good job.

..Alternatively you can prove that P=NP, find a fast solution to the full problem, and pretty much be immortalized in the world of computer science forever. Your choice.

TL;DR: Summoner's code is for more than the warm fuzzies. Yordles in Piltover are crying because you didn't read the whole thing, and you should feel terrible about it.


Comment below rating threshold, click here to show it.

gun fu panda

Senior Member

12-16-2010

+1 and bump because computer science problems are fun.


Comment below rating threshold, click here to show it.

AbsoluteFILTH

Member

12-16-2010

This.


Comment below rating threshold, click here to show it.

tehm

Junior Member

12-19-2010

I absolutely agree that this is basically optimization problem; just a quick blurb on quick, good, approximations to NP hard problems...

Let R_m be the average rating of all players in Q... The problem then becomes one of "filling two sacks" M with five elements each such that the weight of each sack is within a set tolerance E of 5*R_m with standard deviation S below some specific number CAP or whatever.

From memory this is basically how matchmaking worked back when I still played though this may very well have changed since then. I believe, as designed, this is basically a special case of the knapsack problem which has a very quick solution. (If you're wandering how you handle the standard deviation. You simply throw all elements in Q who are too far from the mean into one of two special Qs (Q_high, Q_low for example) which follow the exact same rules but which by virtue of how they are created will have quite different means. Recurse as necessary to handle special cases but 95% of a population is within two standard deviations of mean so you don't have to recurse far...) The larger the E the faster the expected solution, the smaller the E the "better" the expected solution.

Iff I'm right about this then I believe that the quickest way to get "good" answers fast is to simply have a Q with a large number of unique elements basically normally distributed.

Obviously having misweighted elements in Q (read as not following the "Summoner's Code") is going to skew results and make a lot of this moot... But If we can trust the weight assignments of the elements in Q then (at least per the old matchmaking that I described) the more people in the queue the better AND faster the matchmaking process.

(i.e. The problem when simplified like this becomes convergent rather than divergant in time as size grows and thus "really fast".)

Tehm

TL;DR
Carry on.. nothing to see in this post. It's all nerdy stuff.