This is my attempt at replicating how the Counter-Strike: Global Offensive MatchMaking works in queueing players at similar ranks in a reasonable amount of time.
The Problem Statement
Suppose we have many players around the globe searching for a game. Each player can be represented by a tuple
(player_id, rank_score, timestamp).
player_idis the unique identifier for that player.
rank_scoreis the score for that player. It may use any rating system such as Elo or Glicko-2.
timestampis the time at which the player started searching for a match.
Our job is to group 10 players (or some other number) that are similarly ranked to give the most competitive experience to the players. In an ideal case scenario, we'll do our best to sort players into like-ranked matches. But to avoid extended waiting times, players might be placed into matches of higher or lower ranks.
Here we are not accounting for the network latency of players to find matches in the closer geographical regions, and we are also not accounting the case when few players form a lobby to play a match together. These can be easily accomplished by making only a few modifications.
Step 1: Comparing some sigmoid functions
A sigmoid function is a bounded differentiable real function that is defined for all real input values and has a non-negative derivative at each point.
But why all this maths?
Remember, we want to match players with similar ranks. But what if the player ranks are very far apart and they have been queueing for a very long time? We have to use the factor of time to reduce the separation of ranks among these players so that they eventually find a match.
For now, our choice of the sigmoid function will be the logistic function defined as -
Step 2: Modifying logistic function to decay rank difference proportional to the elapsed time
Imagine our player ranks are normalised within the range
[-1, 1]. At time
t = 0, our range is bounded between the boundary of the two curves
[-1, 1]. Assume that we have many players looking for a match but their ranks are too far apart to meet a certain threshold.
After some time has passed by, say ~330 seconds, our range is squashed to
[-0.5, 0.5] pushing every point (rank) closer to each other. This rank decay allows us to queue players even when their rank difference is too large at the start, but they have been waiting for a long time to play.
Note: A very important observation here is that if a player A is ranked above a player B in the range
[-1, 1], he/she will still be ranked higher in some other range, say
[-0.5, 0.5]. The points only move closer but never cross each other.
Visualising how the rank decay will eventually find a match
It can be seen that at time
t = 0, player ranks are too far apart. At time
t = 150 the ranks move closer to each other. Around time
t = 330, the ranks move close enough to each other that a match can be found.
But there's a potential flaw when a new player joins
There might be a scenario when few players have been waiting for a long time finding a match. Their ranks have been shifted towards the mean (zero in our case). When a new players joins with rank too high or too low, ideally he/she shall be matched with players of similar ranks. But ranks of other players might have shifted away from the rank of the new player.
One solution to the problem is to shift the rank of the new player by some amount right at the start. But by how much amount? We can use the average waiting time before a match is found. This will allow us to shift the rank of the new player by just the right amount!
Step 3: Grouping players with similar ranks
Now that we have adjusted player ranks by introducing the factor of time, we can now perform grouping of players that are withing a certain threshold.
How should we go ahead? Can we use clustering algorithm here?
K-means clustering allows us to form k-clusters but it doesn't control the number of elements in each cluter. Rather, we want our clusters to have exactly 10 players (or some other fixed number). It's not relevant how many clusters we form.
Modifying clustering algorithm to form clusters of fixed size
Our strategy is quite simple. Assume that each cluster contains at most 10 players (or some other fixed number). Whenever a cluster is full, the players in that cluster are paired together for a match. Each cluster is represented by its centroid which is the average rank of players in that cluster.
For each player, we perform the following:
- Find the closest cluster for this player.
- If the distance between the closest cluster and player is less than some threshold then add this player to this cluster, otherwise create a new cluster for this player.
- Recalculate the centroid (average rank) for the modified / newly created cluster.
- If the cluster is full, then create a match for these players and remove them from the queue.
Note that the correct order to iterate over the players is in the ascending order of their timestamp so that players waiting for longer are queued earlier if they can be matched.