Meeting Your Match

Every day, millions of players around the world log in to Xbox Live® to play against each other in hundreds of different games. Their enjoyment depends on being matched to other players of comparable skill, so that they get a good gaming experience. So how can we use model-based machine learning to automatically match players of similar ability?

One of the great advantages of the online world for gaming is the ready availability of opponents at any time of day or night. An important requirement for Xbox Live is the capability to find opponents with comparable skill levels, in order that players have an enjoyable gaming experience. This requirement means the system must have a way of estimating the skills of players. However, achieving this presents some significant challenges – in particular, a game is not always won by the stronger player. Many games involve an element of chance, and in a particular game luck may favour the weaker player. More generally, a player’s performance can vary from one game to the next, due to factors such as tiredness or fluctuating enthusiasm. We therefore cannot assume that the winner of a particular game has a higher skill level than the loser. On the other hand we do expect a stronger player to win against a weaker player more often than they lose, so the game outcome does give us useful information about the players’ relative skills.

Figure 3.1Xbox Live® provides a real-time matchmaking service for online gaming.

Another challenge concerns new players to the game. We have little idea of their ability until we see the outcomes of some games. New players are not always poor players – they may have played under different identities or have experience of other similar games. Either way, it is essential to have reasonably reliable assessments of their skills after only a few games so that they can be matched against players of comparable skill. This ensures that new players have a good gaming experience and so are more likely to continue to subscribe to Xbox Live. Rapid assessment of skills is therefore important to the commercial success of the service.

A final challenge arises when we have games played by teams of players. We observe that one team wins and the other loses, and we must use this information to learn about the skills of the individual players. At first it might seem impossible to solve this ‘credit assignment’ problem. But we can make use of the fact that, particularly in online games, the composition of teams changes frequently and so over the course of multiple games we can disambiguate the contributions of individual players to the successes and failures of the teams in which they play.

We will need to work with the data available in Xbox Live, when doing match-making amongst the players. Table 3.1 shows a sample of the kind of data that we need to work with, in this case from the Xbox game Halo 2.

Excel

CSV

Table 3.1Sample of the available data, showing ten games in the ‘Head to Head’ variant of Halo2. The columns give the anonymized player ids, their scores, the game outcome, the game id and the variant of the game that was played.

In summary, our goal is to use data of the above form to infer the skills of individual players, in order to match players against others of a similar skill level in future games. A secondary goal is to use the inferred skill levels in order to create ‘leader boards’ showing the ranking of players within a tournament or league. The system must also allow for the fact that players may play one-on-one or may work together in teams. Furthermore, we must solve this problem in a way that makes efficient use of the game outcome results so that we can arrive at an accurate assessment of a player’s skill after observing a relatively small number of games involving that player.

The models developed in this chapter are based on the Trueskill model from Herbrich et al. [2007]. You can recreate all results in this chapter using the companion source code [Diethe et al., 2019].