A new matchmaking format for solo queue players in team games | Deephaven

Many of today’s most popular online games are team-based. A large percentage of their core player base are those who “solo queue”: people who play by themselves. They rely on online matchmaking to find random teammates and opponents to play with. This large portion doesn’t have access to tournament-style play unless they take the initiative to join a clan, or have friends with similar playing schedules.

Let’s consider a few currently trending examples and their match sizes:

I could list a whole lot more. Team-based games thrive in online gaming just the same (if not better) as 1v1 games do. Team-based games in an online setting, however, lack a tournament mode for solo queue players. Players who play team based games by themselves miss out on competitive tournament play commonly available to 1v1 games and pre-made teams. In this blog, I present a solution in the form of a new tournament style matchmaking mode for solo queue players in team-based games.

Online matchmaking in gaming has evolved in the same way games have themselves. The systems employed are designed to maximize the player’s experience when playing. These matchmaking systems assign a point score, usually known as a matchmaking rating (MMR), to every player who plays the game online against others. When a player enters a matchmaking queue, the system waits until other players of a similar caliber (MMR) enter the queue. Once enough players accrue, the system places the players into a match, and off they go.

These MMR systems are designed using the fundamental principles set forth by the Elo rating system. Player MMR is typically defined by the following:

• Wins
• Losses
• Performance
• MMR relative to other players

Most games use their own ranking systems that differ slightly from Elo, but the principle remains the same. An effective MMR system takes an online gaming experience to the next level.

Tournaments for team based games require the teams to be set when queuing up. For a 5v5 game such as League of Legends (or any Multiplayer Online Battle Arena for that matter), players will enter a tournament in groups of five. The event organizers will rank teams based on the ratings, and seed them accordingly. These tournaments exist for all different ratings from the lower levels to the absolute top professionals. Creating seeds is easy when the teams are pre-made.

Tournament modes, however, are not widely available for solo players of team based games. This leads a large part of the player base for a team based game to miss out on a tournament format. Standard online matchmaking only creates a single game at a time. While this has proven to be sufficient to keep players coming back, it doesn’t capture the same excitement that comes with a competitive tournament bracket.

I propose a new matchmaking system designed entirely for solo queue players of team-based games. This matchmaking system will collect a sufficient number of players in a queue, create a set of teams from those players, seed the teams, and place each team into a standard tournament bracket. The special part of this system is that it will create teams that are evenly matched based on the game’s MMR system. Additionally, the results of this endeavor are teams that are mathematically evenly matched, which allows matchmaking systems to widen MMR pools it uses to collect players in queues.

Combinations​

Given $n$ players, how many unique teams of $r$ players each can be created?

The answer is called a combination. The formula is as follows:

$_{n}C_{r} = frac{n!}{r!(n – r)!}$

To perform this calculation in Python, run:

from math import factorial

def num_combinations(n, r):
    return int(factorial(n) / (factorial(r) * factorial(n - r)))

print(num_combinations(64, 4))

In Python, the itertools package has a combinations method that will return all possible groups of a given size from a pool of unique objects.

Combinations of combinations​

How many ways can $n$ players be split up into $m$ teams of $r$ players each?

The answer is a combination of combinations. The formula is as follows:

$_{n}CC_{r} = frac{prod_{k=1}^{n/r} frac{(kr)!}{r!(kr – r)!}}{(lfloor n/r rfloor)!}$

Perform this calculation in Python:

from math import factorial, floor

def num_combinations(n, r):
    return int(factorial(n) / (factorial(r) * factorial(n - r)))

def num_combinations_of_combinations(n, r):
    m = floor(n / r)
    k = r
    product = 1
    while k <= n:
        product *= num_combinations(k, r)
        k += r
    return int(product / factorial(m))

print(num_combinations_of_combinations(32, 8))

There is no method provided by a Python package to return an object containing all combinations of combinations of a given size for a set of unique objects. This method, however, will do the trick:

import itertools

def combinations_of_combinations(lst, n):
    if not lst:
        yield []
    else:
        for item in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n - 1)):
            for items in combinations_of_combinations([x for x in lst if x not in item], n):
                yield [item] + items

print(combinations_of_combinations(range(6), 3))
print(list(combinations_of_combinations(range(6), 3)))

Be careful when using this method, though. The number of combinations of combinations increases exponentially with $n$. If you give a first argument that is sufficiently large, you’ll be waiting millennia for it to finish.

Exponentially increasing ways to split players up​

Splitting players into even teams based on MMR is simple in theory. Group players such that the average MMR on a team is near the overall average of everyone in the pool. The difficulty in doing this stems from the total possible number of ways players can be split into teams. Even if a few even teams are created, there’s no guarantee that the remaining players can be teamed up in a way that’s evenly matched.

With 16 players and teams of 4, there are 1,820 ways to create a single team, and 2,627,625 ways to create 4 teams of 4.

With 64 players and teams of 4, there are 635,376 ways to create a single team, and over 5 * 10^53 (500 sexdecillion) ways to create 16 teams of 4.

The estimated total number of atoms in the universe isn’t too many orders of magnitude greater than the number of ways to split up 64 people into 16 teams of 4.

The code​

Creating even teams from a sufficiently large player pool requires some efficient processing. A brute force approach will work for small $n$, but will take an inconceivable amount of time should $n$ get large enough.

The solutions can be found over at the solo queue tournament bracket creator. There are a number of docs, the brute force solution, and a smarter solution.

16 people, 4 teams​

Let’s use results from a seeding match in a Halo LAN tournament.

from deephaven import read_csv

seeding_results = read_csv("https://raw.githubusercontent.com/deephaven-examples/solo-que-tournament-bracket-creator/main/data/csv/halo_seeding_match.csv")

Here’s a screenshot of the output of the smarter team combinations maker. It gives 5 possible combinations of 4 teams of 4 that are evenly matched:

Do it better​

The “smarter” isn’t necessarily the “smartest” solution. It still requires calculating ratings for every possible team. Think you can improve upon it? Give it a shot!

For more details about my matchmaker, check out my Learning Session:

Combinatorics play an important role in a large number of cutting edge STEM research. This is just one way to use it.