Making and Delivering Matches – part one

This blog is part of our ongoing Essential Guide to Game Servers series. This is part one on matchmaking – part two is here.

Matchmaking can be a complicated, often magical black box that steals your players’ first couple of minutes spent inside the game. It’s regularly blamed for marred launches, long wait-times, unreasonable lag, and degraded match quality.

However, it’s also at the core of many games’ online communities, the manager driving your content’s “seasons,” the lifeblood of any competitive Player Vs Player (PVP) title, and an important tool in an experience designer’s tool chest. When it works well, it hums.

The teams at Unity and Multiplay are working hard on an awesome new solution for matchmaking, which will be fully integrated with Multiplay’s scaling technology and dashboard. Built on the Open Match framework, this new matchmaker will work with Unity, Unreal and the other main engines. This is something we’ll blog about more in the future, so stay tuned!

For now, let’s tackle and demystify some of the complexity around matchmaking. Read on to learn more about designing an online matchmaking system for a connected, engaging game experience. Caleb Atwood, Software Engineer for Connected Games at Unity, who has been working with Multiplay on the new matchmaker, tells us more.

What is Matchmaking?

For the purposes of this piece, we’ll primarily be talking about a matchmaking service, one that is hosted online and provides consolidated logic for putting players together. There are other approaches that involve game clients broadcasting to discovery systems (like classifieds), or server lists from which a player can browse and choose servers.

While the implementations vary, many of those systems share components with the approaches described here. There are many advantages in unifying your matchmaking logic into a scalable, online piece of infrastructure… including reliability, configurability, and a generally simpler management story for your connected games business.

It’s also worth noting that there are several common multiplayer architectures for online games; namely P2P (Peer-2-Peer), and DGS (Dedicated Game Server). The matchmaking approaches here work for both, however the latter sections of this post will spend more time diving into implications born out of dedicated server architectures. With that out of the way, what is the matchmaking part of a matchmaking service?

Matchmaking is the ingress point for connecting your players to your online game servers. It typically consists of:

       1) A population of players that want to play

       2) A collection of algorithms for putting players together

       3) Online infrastructure for running the algorithms at scale

       4) A system for orchestrating the lifecycle of your dedicated game servers

       5) Delivery of updates and the game server information back to the waiting players

       6) (Bonus) Other ancillary services for doing features like game sessions, stats, backfill, and join-in-progress

Separating concerns

If we squint, there’s really only 2 parts: One that puts players together into matches, and one that takes those matches and puts them on game servers. Let’s talk about making matches first…

Making matches

From a 10,000 foot view, the goal for this part of the system is simple: Players/parties go in one side, and ready-to-play groups of players come out the other. Sometimes the outcomes are free-for-all, sometimes they’re highly configured team structures. Of course, the story gets less and less straightforward the more game design considerations you want to drive into your online match-made experience.

Usually, this starts with the addition of one or two very common constraints:  

  1. You want to group players so that they have similar gameplay goals. E.g. competing, exploring, socializing, etc.
  2. For real-time games, the players will need fast round-trip connections to their online experience to mitigate lag.

Ideally, you want to actually be able to design the way players come together in your online experience, create and measure signals in order to describe the quality of those games, and use that data to drive decision-making back into your design.

QoS

Let’s start with the usual suspects: QoS, or Quality of Service, is a term used to describe how “good” a player’s connection is to any given game server region. This might be something simple, like the average of several round-trip pings to a few regions where your dedicated game servers are configured. You may have more stringent requirements that necessitate the streaming of several large chunks of data between the game client and server to better measure for packet-loss.

Regardless, for matchmaking we’ll want to use this data to put players together whose pings are compatible with a nearby, common server location. E.g. players in Asia shouldn’t get stuck on South American servers, especially if the game is susceptible to issues caused by slow round-trip times.

If the game in question is a turn-based or asynchronous experience, QoS will likely be a less critical measure to focus on.

Skill and Other Attributes

Next comes the rest of the player-data waterfall: Skill, XP, coins, gear, roles, game modes, history, win-streaks, rank, planned-progression, etc. These will be data points that describe a combination of the player’s intention to play with additional statistical information you may have about the player.

Some portion of the data comes from the game client, while some will come from other backend databases, trusted to provide untampered metrics for skill, inventory, and progression.

Skill population distribution

Ping East US Game Server Distribution

For skill specifically, there are whole books on creating skill algorithms and why skill is (or is not) useful in matchmaking design. For this post, skill is just another attribute that you may want to have available to your matchmaking algorithm when building matches. For more information about skill, check out some of these common skill algorithms: Glicko 2, Elo.

The key takeaway is that skill in the context of matchmaking is a couple of numbers you can use as a basis for predicting how a game might play out as part of your decision making logic.

Algorithms

So we have a population of players with data, but how do we actually do the player selections? Without getting into the full complexity of graph-theory clustering algorithms (of which I am no expert), there are several common, easy-to-follow patterns (like generational, searcher/advertiser) to use when first getting started. What you select will likely follow a similar flow:

1. Query the population on hard filters (criteria that must be met) based on some initial criteria (gamemode, QoS targets based on server capacity available in a region, skill banding, XP minimums)

2. Loop over players or select some players to start doing localized optimistic selections

2.1. If necessary, proceed to do more direct comparisons (fitness weights, player intent, predicted outcome, quality assessment)

3. If you did some parallel work, make sure players don’t appear in multiple matches

For example, a greedy team-based matchmaking algorithm might:

1. Analyze the distributions of data from the population and generate skill and QoS bands.

SELECT players WHERE skill between 650-750 AND East US Ping < 120ms.

SELECT players WHERE skill between 750-800 AND East US Ping < 120ms.

Skill population distribution 2

Ping East US Game Server Distribution 2

2. Query for all parties with those bands wanting to play the “capture-the-flag” gamemode

3. Fan-out loops over the parties based on where they fall in the bands

3.1. If there’s room on an existing team, put the party in

3.2. If not, make a new team and move to the next party

3.3. Combine the teams in the same bands into matches and check the match meets the game mode requirements (e.g. 10 teams of 2-3 players)

3.4. Any parties that don’t fit are passed over for the next matchmaking loop

4. If there were purposefully overlapping bands, look for and resolve any player collisions

But, what if players have been waiting a long time? Does optimistically assuming they’ll eventually get selected in 3.1, despite being passed over in 3.4 several times, create the guarantees your game experience needs? This is where concepts like generations and fall-backs in matchmaking become important.

You’ll want some part of your algorithm to consider players that have been waiting and try to prioritize making matches for those players, even if the match quality won’t be as high. If this causes another potential match that overlaps in players to become invalidated, then there’s a trade-off to be made.

Typically at this point, an appended third requirement to the original constraints becomes painfully important:

           3. Matchmaking has to be fast, robust, and reliable.

More on this last point in part two (the Infrastructure section) – read it now! This is part of our Essential Guide to Game Servers series.

To stay in the loop, follow Multiplay on our social channels: LinkedIn, Twitter and Facebook. The project is still in alpha, but you can read more about the Connected Games roadmap in our blog and on this webpage.

2019-04-07T18:16:50+01:00March 27th, 2019|Essential Guide to Game Servers|