Bayesian Reasoning for Game Development: Fair Match-Making for Multiplayer Games

In our first discussion, we explored that Bayes’ theorem offers a perspective on updating beliefs in light of new evidence: new data/evidence does not lead us to a definitive conclusion but updates our prior beliefs. We also introduced an intuitive and more concise expression of Bayes’s theorem;

Concise Expression of Bayes’ Formula.

Using this perspective, we aim to establish a robust framework that not only assigns accurate initial skill ratings to players but also refines these ratings over time, ensuring fair and balanced matchups.

The idea for this match-making system stemmed from our debates while playing Age of Empires 2 as a friend group. We regularly play this game for over 20 years, and we often find ourselves arguing over matchmaking. Everyone in our group claims to be weaker than they seem, and they try to take the stronger player to their side. I find this an excellent opportunity to both gather data and demonstrate the Bayes formula in action.

The heart of this match-making system consists of three main steps, the first one is the challenge of determining initial skill levels for new players, the second task of updating these skill levels using the principles of Bayesian inference, and finally creating a balanced match-up with up-to-date ratings.

Data and Database

We start by determining which data to track and deciding on the database where this data will be stored. For development, we will categorize the data into two types: player data for each user and game outcome data for each match.

It’s essential to track player names or IDs, along with their skill levels in the player data. Optionally, tracking win rates could provide additional insight, allowing us to compare the skill rating and win rate to identify and monitor any discrepancies. The structure of a player’s data could look like this:

using UnityEngine;

[CreateAssetMenu(fileName = "NewPlayer", menuName = "Player", order = 0)]
public class PlayerData : ScriptableObject
{
    public string playerName;
    public double skillLevel;

    public int wins;
    public int losses;
    public float winRate => (wins + losses > 0) ? (float)wins / (wins + losses) : 0;

    // Methods to update properties
}

Utilizing the PlayerData structure, we create organic data for each of our friends involved in the games.

A temporary database of organic players for development consists of our friend group playing AoE2.

While we don’t use a current database to fetch a pool of players, see how using scriptable objects allows us to individually tailor data storage for each player. Each of them encapsulates details such as skill level, preferences, and historical performance, making it easily accessible and modifiable throughout the development of our matchmaking system.

After creating a player database, we can now create a data structure for game outcomes. We use this data to store and process information about each match, thereby updating player statistics accordingly.

[CreateAssetMenu(fileName = "NewGameOutcome", menuName = "Game Outcome", order = 1)]
public class GameOutcome : ScriptableObject
{
    public PlayerData[] team1Players;
    public PlayerData[] team2Players;
    public int winningTeam;

    // Methods to update players properties on each team
}

In the future, we can improve collected game outcome data by adding more properties, such as game duration, resources collected, etc. which could offer insights into the status and dynamics of the game and enrich our understanding of each match.

Utilizing the GameOutcome structure, we create a database of games that have occurred among our friends in almost one month period.

An example of game outcome data. It is collected from organic matches among our friends.

You can see that, through these scriptable objects, referencing and data manipulation become more straightforward, perfectly serving our project’s needs.

Initial Skill Levels

As we complete the initial setup to keep records of each player and matchmaking, the first main task for this system is to establish initial skill levels. Remember that within the PlayerData class, the skillLevel attribute represents our prior belief about a player’s skill level. This is the value that is intended to be updated after each match, reflecting changes in player performance and skill as more data becomes available, thus yielding the most up-to-date indicator for a player’s performance.

If players make enough matches, after enough number of updates, their skill level should eventually converge to an interval that is close to the skill levels of each player. However, “enough number updates” should not always be as fast as we assume. Our goal is to achieve this convergence as swiftly as possible to avoid the cost of wasting time on poorly matched games so that the game should not lose retention due to a lack of fair match-making.

In the scenario where this system is deployed into a game already in production with a pool of players on its database, a possible approach should be starting with 0.5. This method is particularly suitable for a large pool of players whose initial skill levels are genuinely unknown. Another approach should be not rating a player for his first 10 or more matches, assigning his win ratio as the initial probability of skill.

Processing Game Data

After assigning initial skill levels to each player, the second main task is to update these skill levels after each match. We will process the data from each game and update each player’s statistics based on this information. To facilitate this, we need to incorporate a method into the GameOutcome structure that processes each match and updates the properties within PlayerData accordingly. Here is the general structure of a method to update player stats while processing each match:

    public void UpdatePlayerStats()
    {
        step 1.1: Calculate TEAM1 average skill
        step 1.2: Calculate TEAM2 average skill
        step 2: Calculate skill difference between the teams
        step 3: Update each players stats based on win/loose 
        and skill level difference using Bayes's formula
    }

Incorporating this structure, we can implement it as:

using UnityEngine;

[CreateAssetMenu(fileName = "NewGameOutcome", menuName = "Game Outcome", order = 1)]
public class GameOutcome : ScriptableObject
{
    public PlayerData[] team1Players;
    public PlayerData[] team2Players;
    public int winningTeam;
    public bool isProcessed = false;

    public void UpdatePlayerStats()
    {
        double team1AverageSkill = CalculateAverageSkill(team1Players);
        double team2AverageSkill = CalculateAverageSkill(team2Players);
        double skillDifference = team1AverageSkill - team2AverageSkill;

        UpdateTeamStats(team1Players, winningTeam == 1, skillDifference);
        UpdateTeamStats(team2Players, winningTeam == 2, -skillDifference);

        MarkAsProcessed(); // Assign the scriptable object is processed for training process.

    }

    private void UpdateTeamStats(PlayerData[] teamPlayers, bool wonGame, double skillDifference)
    {
        foreach (var player in teamPlayers)
        {
            player.UpdateStats(wonGame, skillDifference);
        }
    }

    private double CalculateAverageSkill(PlayerData[] players)
    {
        if (players.Length == 0) return 0;
        double totalSkill = 0;
        foreach (var player in players)
        {
            totalSkill += player.skillLevel;
        }
        return totalSkill / players.Length;
    }

    public void MarkAsProcessed()
    {
        isProcessed = true;
        PlayerPrefs.SetInt("Processed_" + name, isProcessed ? 1 : 0);
    }

    public void LoadProcessedState()
    {
        isProcessed = PlayerPrefs.GetInt("Processed_" + name, 0) == 1;
    }

}

While our scriptable objects can be modified during runtime, these changes will not persist. This shall be annoying considering the lengthy nature of the training process. To solve this, I introduced the isProcessed boolean flag to mark the processed data and save it to PlayerPrefs in development as an alternative to fetching from a database.

Now we can load and process all GameOutcome data. I do it before the first update at the Start lifecycle method.

public class GameOutcomeProcessor : MonoBehaviour
{
    private void Start()
    {
        ProcessAllGameOutcomes();
    }

    private void ProcessAllGameOutcomes()
    {
        GameOutcome[] allGameOutcomes = Resources.LoadAll<GameOutcome>("GameOutcomes");

        foreach (var gameOutcome in allGameOutcomes)
        {
            if (!gameOutcome.isProcessed)
            {
                gameOutcome.UpdatePlayerStats();
            }
        }

    }

}

Updating Player Stats

Up to this point, we have processed each match, invoking the update method of each player’s skill level, based on wins/losses and the difference in average team skill levels. The next step involves implementing the method to update those skill levels, i.e. UpdateStats(input1: the boolean of win or lost, input2: the numerical value of skill difference) method in PlayerData, which is almost the core aspect of our project.

Remember the concise formulation of Bayes’ Rule.

We already store the prior probability of a player’s skill level, we must now calculate the probability of likelihood and the probability of total evidence to derive a posterior probability after each processed match. So the general structure of the method looks like this:

    public void UpdateStats(bool wonGame, double teamSkillDifference)
    {
      Step 1: Update class properties related to win rate.
      Step 2: Calculate likelihood.
      Step 3: Calculate the total evidence.
      Step 4: Update players skill level based on the evidence
      i.e. each match.
    }

Step 1 of updating the class properties is straightforward. However, step 2 of calculating the likelihood presents a bit more of a challenge. This method should process the skill difference and return a probability value for the probability of likelihood, in other words:

private double CalculateLikelihood(double teamSkillDifference)    {

    return (a value between 0 and 1)
}

The sigmoid function;

The sigmoid function is a special case of the logistic function.

is widely used in statistics and machine learning to map the values into 0 and 1.

In machine learning, the sigmoid function is widely used to map values into probabilities i.e. [0,1] Reference: Researchgate

In the graph, clearly, for an input value of x, the sigmoid function returns a value between 0 and 1, so that we can incorporate it as probability values.

private double CalculateLikelihood(double skillDifference)
{
    return 1 / (1 + Mathf.Exp((float)-skillDifference));
}

Let's further investigate this method to see if it serves our expectations. Consider two different matches in which the average skill difference between two teams is -0.025 and 0.02.

While the average skill difference of teams may vary between -1 and 1, we obtain values between 0 and 1 using the sigmoid function. Now the outputs are more appropriate to use as a probability. You can also consider what alternatives can be used for the logistic function to map the skill difference values between 0 and 1.

Step 3 of calculating total evidence is indeed another task that requires attention. It represents the total probability of observing the evidence under all possible scenarios. Four our match-making system, we can formulate;

Hypothesis (H): A player’s or team’s skill level.

Evidence (E): The outcome of a match (victory or defeat).

In situations where specific information about the teams or players involved in a match is lacking, the system should assume an equal chance of victory or defeat, by default. If this is the case, assigning a value of 0.5 would be reasonable, just like flipping a coin to predict the outcome, signifying an equal likelihood of winning or losing.

If we assume it is a perfectly matched game, again assigning the probability of evidence as 0.5 would be reasonable, since the winner will be determined based on the random factors in a procedurally generated map, such as resource positions, map structure, etc.

For our development process, it is also a pragmatic approach for practical considerations of computational efficiency and simplicity. However, developing a more robust method to calculate the probability of total evidence is important, and should be covered in a future study.

Based on these assumptions, let’s see how it goes:

If we have a Team 1 of 4 players with skill levels 0.6, 0.4, 0.3, and 0.7

And a Team 2 of 4 players with skill levels 0.5, 0.4, 0.6, and 0.65

It yields a team 1 average of 0.5 and a team 2 average of 0.5375.

We obtain a team skill level difference of 0.0375. Let’s now calculate the updated skill levels of the two cases of victory or defeat.

Updated score of the player with 0.6 in case of victory(top) and defeat(bottom).

It seems to be working well so far. Using this structure, one implementation of PlayerData should be:

[CreateAssetMenu(fileName = "NewPlayer", menuName = "Player", order = 0)]
public class PlayerData : ScriptableObject
{
    public string playerName;
    public double skillLevel;

    public int wins;
    public int losses;
    public float winRate => (wins + losses > 0) ? (float)wins / (wins + losses) : 0;

    public void UpdateStats(bool wonGame, double skillDifference)
    {
        wins += wonGame ? 1 : 0;
        losses += wonGame ? 0 : 1;

        double adjustedSkillDifference = skillDifference;
        if (wonGame)
        {
            if (skillDifference < 0)
            {
                adjustedSkillDifference = -skillDifference;
            }
        }

        if (!wonGame)
        {
            if (skillDifference > 0)
            {
                adjustedSkillDifference = -skillDifference;
            }
        }

        double likelihood = CalculateLikelihood(adjustedSkillDifference);

        skillLevel = BayesCalculator.CalculatePosterior(skillLevel, likelihood, totalEvidence);
    }

    private double CalculateLikelihood(double skillDifference)
    {
        return 1 / (1 + Mathf.Exp((float)-skillDifference));
    }
}

Separating the Bayes formula into a different class should be nice for modularity and readability.

public class BayesCalculator
{
    public static double CalculatePosterior(double prior, double likelihood, double totalEvidence)
    {
        double posterior = (likelihood * prior) / totalEvidence;
        return posterior;
    }

Match Making Based On Up To Date Probabilities

At this point, we can assume that we have the most up-to-date probability of skill levels of each player. What is left is the third main task: to make a proper matchup.

Match-Making Type 1 — Pool of Players In A Queue

One scenario should be creating match-making between all players in a queue for defined team sizes. In Age Of Empires 2 and many online games, users request to join the matchmaking queue with random players with preferred team sizes.

Match-making Scenario 1 in Multiplayer Games

For this type of match-making, the structure of the implementation should look like this;

public class Matchmaker : MonoBehaviour
{
    public int team1Size;
    public int team2Size;

    public void CreateAndDisplayTeams(int team1Size, int team2Size)
    {
      step 1: Load the data of all the players in the match-making queue
      step 2: Sort them by skill level
      step 3: Create two empty lists for each team
      step 4: Traverse each player in sorted list and assign them to each team
    }
}

We can implement this scheme as follows:

public class Matchmaker : MonoBehaviour
{
    [SerializeField] public int team1Size;
    [SerializeField] public int team2Size;

    // You can invoke this method at any life cycle method like start
    // or in any specific input.
    public void CreateAndDisplayTeams(int team1Size, int team2Size)
    {
        PlayerData[] allPlayers = Resources.LoadAll<PlayerData>("PlayerData");

        var sortedPlayers = allPlayers.OrderBy(p => p.skillLevel).ToList();

        List<PlayerData> team1 = new List<PlayerData>();
        List<PlayerData> team2 = new List<PlayerData>();

        double team1TotalSkill = 0, team2TotalSkill = 0;

        foreach (var player in sortedPlayers)
        {
            bool canAddToTeam1 = team1.Count < team1Size;
            bool canAddToTeam2 = team2.Count < team2Size;

            if (canAddToTeam1 && (team1TotalSkill <= team2TotalSkill || !canAddToTeam2))
            {
                team1.Add(player);
                team1TotalSkill += player.skillLevel;
            }
            else if (canAddToTeam2)
            {
                team2.Add(player);
                team2TotalSkill += player.skillLevel;
            }
        }
        //Display the teams
    }
}

Here are some results for 4vs4 and 3vs3 matchmaking for the players in our database, assuming they are all in the queue.

4 vs 4 match-makings of the queue with up-to-date probabilities.

3 vs 3 match-makings of the queue with up-to-date probabilities.

Match-Making Type 2 — Random Teams In A Lobby

Another scenario for matchmaking should be matching players in a lobby. In Age of Empires 2, and many other games, people join the lobby and select random teams.

Match-making Scenario 2 in Multiplayer Games

In lobby matches, players are usually unable to make a proper matchup among themselves and are often anxious about unbalanced teams. If we are to create match-making for this case, the structure of the implementation should look like this;

public class FairMatchmaker : MonoBehaviour
{
    public List<PlayerData> availablePlayers = new List<PlayerData>();

    public void CreateAndDisplayFairTeams()
    {
      step 1: Sort availaible players by skill level
      step 2: Create two empty lists for each team
      step 3: Traverse each player in sorted list and assign them to each team
    }
}

We can implement it as,

public class FairMatchmaker : MonoBehaviour
{
    public List<PlayerData> availablePlayers = new List<PlayerData>();

    public void CreateAndDisplayFairTeams()
    {
        var sortedPlayers = availablePlayers.OrderBy(p => p.skillLevel).ToList();

        List<PlayerData> team1 = new List<PlayerData>();
        List<PlayerData> team2 = new List<PlayerData>();

        double team1TotalSkill = 0, team2TotalSkill = 0;

        foreach (var player in sortedPlayers)
        {
            if (team1TotalSkill <= team2TotalSkill)
            {
                team1.Add(player);
                team1TotalSkill += player.skillLevel;
            }
            else
            {
                team2.Add(player);
                team2TotalSkill += player.skillLevel;
            }
        }
    }
}

An example lobby using our development database.

Match-making of the lobby in the previous image based on up-to-date probabilities.

How can you use it for a game or app that is currently in production?

If you intend to implement this framework in your game or application, you shall start by assigning initial skill levels for each player. If the skill level of the players is genuinely unknown, you can simply assign it 0.5. Or you can allow the user to play several games. After a predetermined number of games, for example, 10, assign the skill level based on the player’s win ratio. If a player wins 3 out of 10 matches, start their skill level at 0.3. You can show it to the users by multiplying it by 2000 as a rating, which resembles an ELO rating. Obviously, 600 is easier to track than 0.3, as 1340 is much easier to track than 0.67, and nowadays users are more acquainted with it.

If you are not eager to invest much in a database, consider saving the player’s skill level to PlayerPrefs. When a user wants to enter a queue, send this information to the server with the request object.

If a user requests to join the queue for a 3vs3 match, you should adjust the following method accordingly;

public class Matchmaker : MonoBehaviour
{
    [SerializeField] public int team1Size;
    [SerializeField] public int team2Size;

    public void CreateAndDisplayTeams(int team1Size, int team2Size)
    {
        PlayerData[] allPlayers = all players in queue
        .....

    }
}

or If a user requests to join a lobby with random teams and you need to make fair matchmaking, modify the FairMatchmaker class accordingly.

After the match ends, it’s crucial to update each player’s stats and skill level, which lies at the heart of Bayesian inference. Ensure that these updates are written to your database or PlayerPrefs, depending on where you store the data.

Assignment: On the Verge Of Fail or Fair Match-Making

Let’s investigate some different cases of the method that updates the skill level of each player. Compare two cases, one player wins and is on the weaker team, and another player also wins and is on the stronger team.

(Top) An update on a player’s score from a match where a much stronger team faced off against a weaker team. (Bottom) An update on a player’s score from teams of nearly equal strength.

When playing against stronger opponents, I anticipate a more substantial score adjustment, and the reverse should hold for weaker opponents. In our example, in the match where the skill difference is 0.0375, a score of 0.6 is updated to 0.6112. However, in a less fair match, a player from a stronger team with a skill difference of 0.375 is updated from 0.6 to 0.7111, which appears to be quite unfair. How can we solve this problem? What are other edge cases to cover?

Hint:

In the GameOutcome class, we update players in each team by UpdateTeamStats(PlayerData[] teamPlayers, bool wonGame, double skillDifference)

The third argument skillDifference of UpdateTeamStats contains information on who was in the stronger team.

// Belongs to GameOutcome class
public void UpdatePlayerStats()
    {
        double team1AverageSkill = CalculateAverageSkill(team1Players);
        double team2AverageSkill = CalculateAverageSkill(team2Players);
        double skillDifference = team1AverageSkill - team2AverageSkill;
        // Stronger team is updated with positive skillDifference.
        // If team 1 is stronger, skillDifference is positive
        // UpdateTeamStats(team1Players, winningTeam == 1, positive);
        // UpdateTeamStats(team2Players, winningTeam == 2, negative);
        // If team 2 is stronger, skillDifference is negative.
        // UpdateTeamStats(team1Players, winningTeam == 1, negative);
        // UpdateTeamStats(team2Players, winningTeam == 2, positive);

        UpdateTeamStats(team1Players, winningTeam == 1, skillDifference);
        UpdateTeamStats(team2Players, winningTeam == 2, -skillDifference);

        ...
    }

In the UpdateStats method of the PlayerData class,

// Belongs to UpdateStats method of PlayerData class.
...
double adjustedSkillDifference = skillDifference;
if (wonGame)
{
    if (skillDifference < 0)
    {
        adjustedSkillDifference = -skillDifference;
    }
}

if (!wonGame)
{
    if (skillDifference > 0)
    {
        adjustedSkillDifference = -skillDifference;
    }
}
// This approach makes implementation simpler but causes a loss of some 
// information, such as, who is in the stronger team.
...

This approach makes implementation simpler but causes a loss of some information.

Now get rid of this part and rewrite the CalculateLikelihood method. Make sure that it covers the four following cases. Optionally you shall accept victory/defeat status as input;

private double CalculateLikelihood(bool winStatus, double skillDifference)
{
    Modify this method and return a value between 0 and 1 such that;
    Case 1: Player wins and is in the weaker team (increase skill significantly).
    Case 2: Player wins and is in the stronger team (increase skill slightly).
    Case 3: Player loses and is in the weaker team (decrease skill slightly).
    Case 4: Player loses and is in the stronger team (decrease skill significantly).
}

While a bad response should be as follows, it covers the essence of what we are trying to achieve.

    private double CalculateLikelihood(bool winStatus, double skillDifference)
    {
        const double significantChange = 0.01; // a low value 
        const double slightChange = 0.005; // a relatively lower value

        if (winStatus)
        {
            if (skillDifference < 0)
            {
                // Case 1: Player wins and is in the weaker team (increase score significantly)
                return 0.5 + significantChange;
            }
            else
            {
                // Case 2: Player wins and is in the stronger team (increase score slightly)
                return 0.5 + slightChange;
            }
        }
        else
        {
            if (skillDifference < 0)
            {
                // Case 3: Player loses and is in the weaker team (decrease score slightly)
                return 0.5 - slightChange;
            }
            else
            {
                // Case 4: Player loses and is in the stronger team (decrease score significantly)
                return 0.5 - significantChange;
            }
        }
    }

A solid, robust solution should look like this;

    private double CalculateLikelihood(bool winStatus, double skillDifference)
    {
        double adjustedSkillDifference = .....

        double extraProperty = ....

        // should return a value around the total evidence that we can update prior belief properly
        return 1 / (1 + Math.Exp(-extraProperty * adjustedSkillDifference));
    }

or maybe a combination of the two cases should yield a good solution.

private double CalculateLikelihood(bool winStatus, double skillDifference)
    {
        double adjustedSkillDifference = .....

        if(winStatus){
          adjustedSkillDifference = ...
        } 
        else
        {
          adjustedSkillDifference = ...
        }

        // should return a value around the total evidence that we can update prior belief properly
        return 1 / (1 + Math.Exp(-adjustedSkillDifference));
    }

If you devote yourself, please also consider punishing a win against weak opponents, instead of increasing the probability of skill slightly (case 2). Would it make sense? And would it be practically feasible?

On the verge of fail and fair match-making | Cover Image Credited: Sora Shimazaki on Pexels |(Creative Commons Zero License (CC0))

I hope this article has provided a foundational understanding of the Bayesian perspective on matchmaking applications. While this approach offers a solid starting point, there is definitely room for improvement and further refinement to enhance its effectiveness and precision in creating balanced matches.