Matchmaking Key Concepts #

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. In this topic, we’ll take a look at the key concepts employed within our matchmaker and explain how you can create quality matches quickly for your players.

Matchmaking Overview #

Matchmaking process overview

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

  1. Parties enter the Matchmaking service from the Party service.
  2. The party is added to a new Matchable object, which is placed into a queue. You can thing of a Matchable object as a container for parties in matchmaking.
  3. The Matchmaking service works through the matchmaking loop, using custom logic defined in the Matchmaking Plugin matchParties method to compare Matchables and determine if two Matchables are appropriate matches for a game instance.
  4. The Matchmaking service can move parties between Matchables to make higher quality matches.
  5. Once an appropriate match is found, the Matchmaking service can send the parties in the Matchables to the game instance. New game instances that have been created can remain within the matchmaking flow 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 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;
}

The Matchmaking Loop #

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.

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.

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.

Errors #

If the matchParties method throws an exception, the Matchmaking service logs an error and removes both the anchor Matchable and the other Matchable from the queue to allow for debugging. Players are notified via a SessionChangedV1Notification. The anchor position is then reset to the oldest Matchable in the queue.


Matchmaking
Matchmaking Components