Matchmaking Overview #

The goal of matchmaking is to determine what parties should be sent to a single game instance together. To support matching players together into high-quality games quickly and at scale, Pragma has created a matchmaking service that implements a streaming-based algorithm for creating matches. The Matchmaking service handles queue configuration and uses matchmaking logic to compare parties to form appropriate matches to send to the game server.

The Matchmaking service is structured to work at scale to support the world’s largest games. All matchmaking state is held in-memory upon entry from the Party service to improve performance by avoiding extraneous network hits. This allows the Matchmaking service to remain CPU-dependent and tailored to prioritize for match speed or quality; when more comparison data is used, the matchmaking is slower but the quality of the match is higher.

Matchmaking process #

Matchmaking flow diagram

At a basic level, the Matchmaking process works as follows:

  1. Parties enter the Matchmaking service on a new Matchable object. You can think of a Matchable object as a container for parties in matchmaking.
  2. Matchmaking is initialized and the Matchable object is placed into a queue.
  3. Matchables are compared to each other using custom logic defined in the Matchmaking Plugin matchParties method, taking or giving parties as needed.
  4. Once an appropriate match is found (two Matchables contain parties that are suitable to be in a game instance together), the Matchmaking service can send the parties in the Matchables to the game instance. New game instances that have been created can remain in matchmaking or reenter it at any time to accept more players.

Continue reading for more information about matchmaking queues, the matchmaking loop, and different approaches to matchmaking.

Matchmaking service implementation #

Developers can use the Pragma SDK to communicate matchmaking tasks such as leaving matchmaking or getting matchmaking information. You define custom matchmaking logic using the Matchmaking Plugin. By default, this plugin provides the most basic skeleton of a matchmaking flow, with the initialize, matchParties, matchPartiesWithGame, and endOfLoop function.

The Matchmaking Tasks topic explains how to use the SDK methods and plugin functions to implement and customize the Matchmaking service features.

Matchmaking queues #

At the heart of the Pragma matchmaking service are a set of queues. Queues allow you to separate Matchables into different matchmaking loops to ensure only parties within the same queue can be matched together. Parties in different queues will never be compared, and thus will never enter a game instance together.

You have full control over how many queues there are, and which specific queue a party will enter. This allows you to set matchmaking logic that applies only to one specific group.

Each queue is defined by its unique Matchmaking queue key. A matchmaking queue key contains two pieces of information, both of which are set in the Party service: a GameServerVersion that splits queues by the version of the game server, and a custom ExtMatchmakingKey that provides a location for developers to define variables they want to use to split queues. Having a blank ExtMatchmakingKey and GameServerVersion causes all players to enter one global queue.

For example, consider a game that has multiple game modes: 3v3 Ranked, 3v3 Casual, and Co-op Adventure. In this case, we configure the ExtMatchmakingKey proto to consider the game mode.

message ExtMatchmakingKey {
    GameMode game_mode = 1;
}

enum GameMode {
    Unspecified = 0;
    ThreeVsThreeRanked = 1;
    ThreeVsThreeCasual = 2;
    CoopAdventure = 3;
}

Matchable comparison #

The Pragma matchmaking service works in loops to compare Matchables (which contain parties) within the same queue and send viable matches to the same game instance. Pragma supports matching parties with each other, as well as adding parties to existing game instances. When making comparisons, you have access to each queue member’s data, all stored in-memory, allowing the matchmaker to make thousands of comparisons per second.

If the matchmaking queue only contains one Matchable, the matchParties/matchPartiesWithGame method is skipped and endOfLoop is called.

Matching parties #

When the matchmaking process begins, the Matchmaking service selects the oldest member of the queue as the anchor Matchable. This Matchable is compared with every other Matchable in the queue, starting with the next oldest member (relative to the current anchor), to check viability of combining parties into one Matchable. The Matchable being compared to the anchor Matchable is called the other Matchable.

Matchmaking loop overview

During each of these local comparisons, the matchmaking engine invokes the Matchmaking Plugin’s matchParties method, which includes custom logic to determine whether to produce any of the following changes to the Matchables:

  • Produce a new game instance: If there’s a good enough match for players to begin playing a game, send them to the game via a NewGameInstance object.
  • Take parties from the other Matchable queue member: If adding some parties from the other Matchable to the anchor Matchable would improve the quality of the possible ensuing match, move those parties into your anchor Matchable.
  • Take parties from the anchor Matchable queue member: If removing some parties from the anchor Matchable would improve match quality, move the party to the other Matchable. This is usually performed in combination with taking some parties from the other Matchable, making an exchange of parties.
  • Continue matchmaking with new anchor: If, after comparing the anchor Matchable with all other Matchables in the queue, no NewGameInstance has been generated, the anchor position is moved to the next oldest Matchable in the queue. To add custom behavior at this stage, implement endOfLoop as described in Add custom behavior after a matchmaking loop.

Example

In the following image, Matchable 1 (M1), which consists of Party 1 (P1), starts as the anchor:

Match Parties Logic

  • a: M1 is compared to M2. Based on custom logic, M1 takes P2 from M2. M2 is removed from the queue because it no longer contains any parties.
  • b: M1 is compared to M3. Custom logic determines no party swapping is needed.
  • c: M1 is compared to M4. Based on custom logic, M4 takes P2 from M1. M1 has not exhausted the queue and the anchor advances to M3 (M2 was removed).
  • d: As anchor, M3 is compared to M1. Custom logic determines no party swapping is needed.
  • e: M3 is compared to M4. Custom logic determines a match has been found and the two Matchables are sent to the game service in a NewGameInstance object.
If a new party joins the queue, its Matchable is added to the end of the queue. The new Matchable will be compared to others in the queue the next time the anchor position advances.

Matching parties with active game instances #

When an active game instance enters matching from the Game Instance service, the Matchmaking service creates a Matchmaking.GameInstance object with game information required to make an appropriate match. A Matchmaking.GameInstance instance is similar to a Matchable in that it contains parties for comparison. Unlike a Matchable, a Matchmaking.GameInstance cannot have parties taken from it.

To make comparisons, the matchmaking engine invokes the Matchmaking Plugin’s matchPartiesWithGame method. In this method the Matchmaking.GameInstance is the game and the Matchable in the queue that’s being compared to the game is the anchor.

The matchPartiesWithGame method includes custom logic to determine whether parties from the anchor Matchable should be added to the active game instance. If adding some parties from the queue would improve the quality of the match in the current game instance, add those parties to the game Matchmaking.GameInstance and return a GameInstanceUpdate object.

If no suitable match is found after comparing the game instance with all Matchables in the queue, matchPartiesWithGame can return null.

You cannot remove parties from a Matchmaking.GameInstance.

Matchmaking approaches #

The above operations enable you to produce appropriate matches. When matchmaking, one must always consider a trade-off between matchmaking speed and match quality.

Matchmaking services tend to use either a streaming method or batching method when matchmaking. In general, streaming and batching methods differ in the way they apply party comparison logic. While both streaming and batching methods are valid and have been proven to work at-scale, Pragma implements a streaming approach to support matching players together into high-quality games quickly and at scale. The Pragma streaming-based matchmaking process focuses on developing a clear set of match criteria and tuning time-based envelopes.

Streaming-based matchmaking #

Streaming-based matchmaking involves selecting a single Matchable (a grouping of one or more parties) to compare, one-by-one, to each other Matchables in the queue.

As the anchor Matchable steps through the queue, logic defined in the Matchmaking Plugin determines if the Matchables should be merged or if individual parties should be moved between the Matchables. After iterating through the queue, the anchor position moves to the next Matchable in the queue.

This process happens in memory and thus is extremely fast. You can expect that each party will have its chance as an anchor hundreds or thousands of times per second. If at any point of time that grouping of parties forms a valid match, it should immediately be sent to start that match.

Envelopes #

To ensure high quality matches, we recommend using time-based envelope expansion to balance the competing concerns of producing matches as quickly as possible while also making the highest quality matches. In an envelope expansion approach, an envelope represents qualities of an ideal match at a point in time. Using time-based envelopes, you can modify the strictness of your acceptable match criteria as time progresses. That is to say, you can continue to broaden the criteria of what makes an ideal match the longer a party is in matchmaking. Early comparisons can restrict acceptable matches to only those considered ideal.

Given that envelopes are expanded in human time (for example every 10 seconds), while the loop itself is giving every matchable a chance to be an anchor hundreds or thousands of times per second, the ‘greedy’ nature of the architecture is able to produce extremely high quality matches.

Batching-based matchmaking #

The batching style of matchmaking is defined by viewing the entire set of parties in a queue at a single point in time. This application requires you to consider the number of comparisons necessary to produce high quality matches without introducing scaling issues. The potentially large number of required comparisons could make the process difficult to optimize, and often requires extensive modeling and testing.

While resulting matches may prove ideal, developing logic to compare the entire set of parties in a queue at a single point in time tends to be more difficult than comparing one Matchable to another, which happens in streaming-based matchmaking. Pragma recommends implementing a streaming approach to support matching players together into high-quality games quickly and at scale.

Testing #

Pragma Engine provides the MatchmakingTestFactory to test custom implementations of the MatchmakingPlugin. The test factory has methods to easily create a Matchable or MatchmakingGameInstance in various different states to test specific matchmaking scenarios.


Matchmaking
Matchmaking Tasks