Dependencies

• A basic understanding of matchmaking and the async matchmaker - This deep dive doc is intended to be read after the basic introduction and integration guides. If you haven't done so, check out Integrating the Async Matchmaker guide first.

Key Concepts

• MMR, or Matchmaking Rating, is an estimate of a player's progression, power level, or skill rating in the game. It is used in the matchmaking algorithm to find players that match the attacking player's power level.
• A Bucket is a section of the matchmaking cache that groups similar players based on their qualities, like their MMR. Buckets provide fast access to defenders with power levels close to the attacking player.
• Hashing is the act of transforming data into an identifier or a key via a one-way mathematical operation. In the matchmaker's case, the player's EntityId is hashed into a key in the matchmaking Bucket.

Overview

The matchmaker is designed to keep all the data it needs in memory to make querying lightning-fast. But when there are a ton of players in memory, the matchmaker can't loop over all of them for every query that comes in. For that reason, it divides the players into Buckets based on their approximated power level, or MMR. The MMR can be in any range and is highly game-specific. When matching players together, the matchmaker only considers a portion of the players from around the attacking player's MMR. This limitation keeps the matchmaking very fast while still giving good results.

The basic operating principle of the asynchronous matchmaker is as follows:

• Database scan - The matchmaker periodically performs a database scan operation to find a batch of players from the database. This can be turned off and only rely on player state update messages.
• Convert model & calculate MMR - All eligible players are converted into matchmaker player models and sorted into matchmaking Buckets based on the player's calculated defense MMR.
• Find possible candidates - When a matchmaking query comes in, the matchmaker starts iterating through players from the Bucket closest to the given attack MMR and checks the eligibility and quality of the match for each considered candidate.
• Find the best candidate - After the matchmaker finds a small list of eligible candidates, the best match is returned based on the earlier quality value.
• Evict from cache - If the target's Bucket population was above a defined threshold, the matchmaker evicts the target from the matchmaking Buckets to prevent the same players from being attacked repeatedly.
• Confirm with target - The initiator of the battle should still confirm with the target that the battle is possible since the matchmaking model stored in the Buckets might be hours or even days old.
• Retry if needed - If the initiator of the battle fails to or chooses not to attack the given target, it can re-query the matchmaker to find a new candidate.
• Manual updates - A player actor can also manually inform the matchmaker that they are available for matchmaking, for example, when going offline after a play session. Informing the matchmaker can reduce the need to perform expensive database scan operations constantly. In addition, the player can use the same update message to notify the matchmaker that they are no longer available, for example, when activating a shield or coming online.
• Automatic Bucket resizing - The matchmaker will periodically resize its Buckets to allocate more cache space to the high-traffic Buckets.

Quick Guide

Interfacing with the Matchmaker

The base matchmaker actor uses the following MetaMessages to communicate with the user code:

• AsyncMatchmakingRequest - Request a match from the matchmaker.
• AsyncMatchmakingResponse - The matchmaker responds with a match.
• AsyncMatchmakingPlayerStateUpdate - Update matchmaker with new player state.

Matchmaking Request & Response

The matchmaking request-response pair of messages is the primary way to interface with the matchmaker. The matchmaking request contains the matchmaking query, a number of retries, and a set of excluded PlayerIds. The matchmaker can consider the number of retries in the matchmaking logic to find players outside the normal MMR range if the matchmaker doesn't see any players in the expected range. The set of excluded PlayerIds can be used when we've tried to establish a match with some player but were unable to do so, and we want to tell the matchmaker not to offer that player again.

The response contains a MatchmakingResponseType enum and a single EntityId of the best match. The response type can be either Success (found a good match), NoneFound (could not find anyone eligible) or FakeOpponent if a fake opponent was returned. If ReturnModelInQueryResponse is set to true, the response will also contain the matchmaking model of the best match.

After a player is suggested as a match, the matchmaker will, by default, try to remove the player from the matchmaking cache to prevent the same players from being attacked over and over. You can configure this setting by overriding the PlayerRemoveAfterCandidateOfferThreshold property in your derived matchmaker.

MatchmakingPlayerStateUpdate

You can use the player state update message to inform the matchmaker that a player is or is no longer available for matchmaking. Sending these messages is left up to the implementation, and the matchmaking system will function without them.

A few game-specific examples when you might want to send a player state update to the matchmaker are when

• An attacking player has tried to target a defender, but the defender was not available due to a shield being active. The defender player actor can inform the matchmaker of this.
• A player has gone offline in a game where only offline players are valid targets, and is now available for matchmaking.
• A player has come online and is no longer available for matchmaking.

The payload of the state update is the updated MatchmakingPlayerModel of the player. The conversion of the PlayerModel to the MatchmakingPlayerModel is left up to the sender of the message. In the case where the message is used to inform the matchmaker of a player's ineligibility, the payload can be left as null.

The matchmaker can choose to ignore the state update in cases where it would result in adding a new player to an already well-populated Bucket. You can configure this setting by overriding the PlayerIgnoreUpdateInsertThreshold property in your derived matchmaker.

Advanced Usage

Buckets

The matchmaking Buckets are implemented as replace-on-insert fixed-size dictionaries, which means that inserting an item to a full dictionary slot will always replace the old item. This allows the data to be easily accessed, but also prevents the memory usage from growing out of control. The dictionary has an internal fixed-size array, where the inserted players are hashed into based on their PlayerId.

Additional Bucketing Strategies

Bucketing players based solely on their MMR might be fine for most games, but when introducing additional requirements or rules, MMR alone might not be enough. Therefore, the matchmaker allows for defining additional bucketing conditions to help optimize the finding of players based on these rules.

When the matchmaker wants to decide which Bucket a player belongs to, it will ask each bucketing strategy for a label for the player. For example, the MMR bucketing strategy will label the player an index out of the MmrBucketCount value depending on where the player lands within the minimum and maximum MMR range. A player with an MMR equal to or close to the minimum will get an index of 0, while a player with an MMR equal to or close to the maximum will get an index of MmrBucketCount - 1. Another strategy might decide to use another type of label, like a StringId. Once the matchmaker has given a player a label from each bucketing strategy, the matchmaker will try to find a Bucket that matches these labels. If it finds a matching Bucket, it will add the player to it. In the case where it doesn't find a Bucket that matches the labels, it will create a new Bucket for the player.

This behavior means that the maximum amount of Buckets is calculated by multiplying the number of labels of each bucketing strategy together, which can easily lead to a large number of Buckets. If the number of Buckets grows too large, it is recommended to use a smaller number of MMR Bucket labels by changing the MmrBucketCount value.

Adding a new bucketing strategy to the matchmaker requires you to create a new class deriving from AsyncMatchmakerBucketingStrategyBase class. Which takes in a TLabel type parameter and an optional TStrategyState parameter. The TLabel has to be a class implementing either IDistinctBucketLabel<T> or IRangedBucketLabel<T> where T is the type itself. The TStrategyState parameter is an optional parameter that can be used to store the state for the bucketing strategy.

A label implementing the IDistinctBucketLabel<T> interface means that the label is a distinct value that is not sortable in any specific order. Distinct labels are treated as being equally wrong if they do not match the desired label. If a label implements the IRangedBucketLabel<T> interface, however, it means the label is sortable into an order of some sort, and close-by labels are viewed more favorably when trying to find a match for a player. For example, the MMR strategy labels are ranged labels because close-by Buckets are always a better option than far-away ones.

The TStrategyState is an optional state object which can be used to persist any data used by the strategy into the database. The state type should be unique for each strategy, even if two strategies could technically share the same state. This is because the matchmaker will restore the state to the correct strategy based on its type.

One important point about creating a bucketing strategy label is that the label should be equatable by value, and not by reference. The GetHashCode method should also be value-based and ideally not change between server restarts and different environments (like string.GetHashCode()).

public class MyMatchmakingBucketingStrategy : AsyncMatchmakerBucketingStrategyBase<
        MyMatchmakingBucketingStrategy.Label,
        MyMatchmakerPlayerModel,
        MyMatchmakerQuery>
{
    [MetaSerializableDerived(1)]
    public class Label : IDistinctBucketLabel<Label>
    {
        [MetaMember(1)] public ArenaId Arena { get; private set; } // A label based on the arena the player has chosen

        public string DashboardLabel => Arena.ToString();

        Label() { }

        public Label(ArenaId arena)
        {
            Arena = arena;
        }

        public bool Equals(Label other)
        {
            ... // // Value-based equality
        }

        public override bool Equals(object obj)
        {
            ... // Value-based equality
        }

        public override int Label()
        {
            return Arena.GetHashCode();
        }
    }

    public override bool IsHardRequirement => true; // Only same-arena players can be matched together

    public override Label GetBucketLabel(MyMatchmakerPlayerModel model)
    {
        return new Label(model.Arena);
    }

    public override Label GetBucketLabel(MyMatchmakerQuery query)
    {
        return new Label(query.Arena);
    }
}

Adding the new strategy is done by overriding the InitializeAdditionalBucketingStrategies method in your matchmaker, as shown below.

protected override IEnumerable<IMatchmakerBucketingStrategy<MyMatchmakerPlayerModel, MyMatchmakerQuery>> InitializeAdditionalBucketingStrategies()
{
    yield return new MyMatchmakingingStrategy();
}

Automatic Bucket Rebalancing

The matchmaker will gather statistics about the distribution of players found from the database and dynamically size the matchmaking Buckets accordingly. The range of MMR covered by a single Bucket is divided equally between Buckets, but the number of players that can fit in a Bucket is based on the collected samples. A Bucket has a defined minimum size to avoid cases where none of the collected samples happen to hit the Bucket's MMR range. The maximum total amount of players stored in the Buckets can be specified in MatchmakerOptions.PlayerCacheSize.

When a Bucket is created, its initial size is set to the value defined in MatchmakerOptions.BucketInitialSize, which can be higher than the minimum size, but not lower. A Bucket has an implicit maximum size of the total cache size in the case where the game only has a single active Bucket.

The rebalancing system works by collecting a sample of the labels of every player added to the matchmaking cache, and then calculating the ratio of players that have been put into each Bucket. When the rebalancing operation happens, this data is turned into a DynamicBucketSizingModel and all existing Buckets are resized to fit it. The collected data is only persisted in-memory, so when the matchmaker restarts it will start the collection process again. The model, however, is persisted in the database and will be used in sizing Buckets after a matchmaker restart.

Matching

A matchmaking algorithm can be as simple as just looking at the difference in MMR, or a very complex design taking almost everything into account. It can try to be as fair as possible, or have hidden mechanics to help players on losing streaks or favor matches against rival guilds.

A good matchmaking algorithm should look into making the player's experience as fun and engaging as possible, without having the opponents be too hard or too easy. If the defending player is penalized for successful attacks against them, it's important to consider their perceived experience as well.

protected override bool CheckPossibleMatchForQuery(TMmQuery query, in TMmPlayerModel player, int numRetries, out float quality)
{
        quality = 300 - MathF.Abs(query.AttackMmr - player.DefenseMmr);

        // Disallow attacking own guild members
        if(query.AttackingGuildId == player.GuildId)
                return false;

        // Prefer targeting members of rival guilds
        if(query.RivalGuilds.Contains(player.GuildId))
                quality += 100;

        // Penalize mirror matches
        if(query.AttackingHeroId == player.DefenseHeroId)
                quality -= 20;

        // Try to attack weaker opponent if losing
        if(query.LoseStreak >= 3 && query.AttackMmr > player.DefenseMmr)
                quality += 30;

        return true; // Match is possible
}

To make the matching algorithm as fair as possible, the matchmaker is designed to offer a fairly wide range of _MMR_s and player choices to the game-specific matching method. To prevent the opponents offered being too easy or too hard when the attacking MMR is close to a Bucket boundary, the matchmaker will alternate between two adjacent Buckets while iterating for players. In addition, the Buckets are iterated in a random order to consider all candidates equally regardless of their hash key.

Scaling

The matchmaker can be scaled up by adding new instances. Each instance scans, and stores data separately from the others, so scaling up is fairly linear. When running multiple instances, the game code can use a round-robin algorithm to query the different matchmakers one after another or just pick one at random.

If filling up the Buckets seems too slow, it's also possible to tweak the matchmaker options to scan through the database faster. Changing the options below should help.

• DatabaseScanTick - The amount of time between each database scan operation.
• DatabaseScanMinimumFetch - The minimum amount of players fetched in a single database scan tick. This value is used when all the Buckets are well populated.
• DatabaseScanMaximumFetch - The maximum amount of players fetched in a single database scan tick. This value is used when the Buckets are empty or low population.

Using the Async Matchmaker in message-update-only mode

You can configure the matchmaker only to use player state update messages to update the matchmaking cache. This can be useful in games where the database scanning doesn't make sense. For example, if matchmaking entries are generated during gameplay and it doesn't make sense to keep them stored in the player state. An example could be a game where the player battles against other players' team compositions, and after each battle, the team the player used is sent to the matchmaker for other players to match against. The downside of this approach is that the matchmaking cache will be empty until the first player update message is received.

To enable this mode, you need to override the EnableDatabaseScan property in your matchmaker and set it to false.

// MyAsyncMatchmakerActor.cs

...

protected override bool EnableDatabaseScan => false;

...

When using this mode, it's recommended to also override the PlayerIgnoreUpdateInsertThreshold property to Never to ensure that all player update messages are processed. If the game's ratio of taking entries from the matchmaker versus adding them to the matchmaker is about 1:1 or higher, the PlayerRemoveAfterCandidateOfferThreshold should also be set to Never to allow the buckets to fill up.

// MyAsyncMatchmakerActor.cs

...

protected override bool EnableDatabaseScan => false;

protected override BucketFillLevelThreshold PlayerIgnoreUpdateInsertThreshold        => BucketFillLevelThreshold.Never;
protected override BucketFillLevelThreshold PlayerRemoveAfterCandidateOfferThreshold => BucketFillLevelThreshold.Never;

...

Check out Sending Player Updates to the Matchmaker for information on how to send player update messages to the matchmaker.

Multiple Matchmaker Entries Per Player

The matchmaker stores a single entry per player by default, but it's possible to configure the matchmaker to allow multiple entries per player. This can be useful in games where the player can have multiple parties or teams that can be matched against or games where multiple matchmaking entries are generated during gameplay. Players are still limited to a single entry per Bucket, and the matchmaker will replace the old entry with the new one if the player already exists.

To enable this feature, override the AllowMultipleEntriesPerPlayer property in your matchmaker and set it to true. The ReturnModelInQueryResponse property should also be set to true to allow the game code to differentiate between the different entries.

// MyAsyncMatchmakerActor.cs

...

protected override bool AllowMultipleEntriesPerPlayer => true;

protected override bool ReturnModelInQueryResponse    => true;

...

When this feature is enabled, the matchmaker will use the TryCreateModels instead of TryCreateModel method to create the matchmaking models from the player. The TryCreateModels method can return an array of matchmaking models instead of a single one. If not using the database scanning feature, the method can return null. In this case, the game has to send manual player update messages to the matchmaker to add states to the matchmaking cache.

// MyAsyncMatchmakerActor.cs

...

protected override MyMatchmakerPlayerModel[] TryCreateModels(TPlayerModel model)
{
    // Create and return an array of matchmaking models.
    return new MyMatchmakerPlayerModel[] { ... };
}

...

If the AllowMultipleEntriesPerPlayer feature is enabled, the AsyncMatchmakingPlayerStateUpdate message can no longer be used to delete entries from the matchmaking cache. Any null payloads will be ignored instead.

Returning Fake Results

The matchmaker can be configured to return fake results when no suitable match is found. This can be useful in games where interaction with the other player is not required and a fake result can be used instead.

To enable this, override the EnableFakeOpponents property in your matchmaker and set it to true. The CreateFakeOpponent method should also be implemented.

// MyAsyncMatchmakerActor.cs

...

protected override bool EnableFakeOpponents => true;

...

protected override MyMatchmakerPlayerModel? CreateFakeOpponent(MyMatchmakerQuery query)
{
    // Create and return a fake opponent for the given query.
    return null;
}

...

Current Limitations

The Metaplay async matchmaker is great for some use cases, but not so great for others. Here are some common gotchas that you might want to know:

• Data in the matchmaking cache can be old - The data of a player in the matchmaking cache is only refreshed when it is rescanned from the database or an update message is sent with new data.
• Players get cleared from the matchmaker as new ones enter - The matchmaker will regularily remove players from the matchmaking cache as new players are found. It is not possible to guarantee that a player is targeted before they are removed.
• The matchmaker only offers a single result - If a list of results is required, a new query should be made for each result.