Most matchmakers use linear solvers.
You List variables, You put in a bunch of constraints, you set a cost function, and tell it to solve for minimum “cost”
Lets build a version of Overwatches matchmaker on paper.
We have a bunch of players, they have MMR (one value) and SR (another) for each role.
So, you build a list. Which player ID, Time they have been queueing (the pity timer), their MMR, their SR, and a bit set for Tank, DPS, or Support.
If they queue for two roles, they are added to the list twice.
so you get something which looks like…
id, sr, mmr, tank, support, dps, pitytimer, selected
1, 2200, 0.2564324, 1, 0, 0, 25, 0
...
This is a person, who has been queued for 25 seconds, for tank, with an SR of 2200, who is not selected for a game.
So you set up a dataset for all of them, and you tell it that you are going to have “selected” as your variable.
Then you add constraints.
// when you multiply if they are selected, and if they are
// DPS for all of the dataset, and sum them up, the number has to be 2.
sum(selected .* dps) == 2
sum(selected .* tank) == 2
sum(selected .* support) == 2
// you can't have SR for any one player too far from the average of the ones selected
avgNon0(sr .* selected) - sr > 1000
avgNon0(sr .* selected) + sr < 1000 // ditto but in the other direction.
You put in a constraint, where they ID’s can’t show up more than once. (so someone doesn’t end up as Tank AND support in the same match).
Now you have possible games. So, you want it to pick the best of them.
// lower score = MMR being closest.
MMRCost = sqrt((avg(mmr)^2) * 6 - ( sum(mmr .* selected)^2))
// take pity on people who have been waiting longer, so make it so it "wants" to match them more.
TotalCost = -MMRCost -sum(pitytimer.* pittytimeScale)
Min(totalcost) //tell it to minimise total cost.
and then it should have the selected players set… so filter for them, and you have a match IF the cost isn’t too awful.
And that is how matchmakers are typically written… You play around with the formula so they are either conics or linear lines. Sometimes you rerun it with more constrains if it pops a bad result to force it down another path (like for the ID constraint, you don’t try to set them up right away, you just ban a particular player from showing up twice and rerun, because speed).
That gives you MOST of what Blizzards matchmaker actually does right there.
If you want to play around with something like that, and you can code, then May I suggest you do it in Julia, and use their EXTREMELY good JuMP
library for it. (https://jump.dev/
)
I believe Blizzard wrote their own solver (which is REALLY insane), but that is Blizzard for you. Typically you just use Cbc (https://projects.coin-or.org/Cbc
) or GLPK (https://www.gnu.org/software/glpk/
)
I’ve written so many, I can basically rattle them off now :), but my first few took literally 8 months or so. They are a pretty specialist area of maths, as solvers tend to be.
I could throw an actual matchmaker together in Julia, if you want to play with one. They are not USUALLY written in Julia, but damn in Julia doesn’t make them easy to read and maintain (even if it gets unstable for “odd” reasons).