Meeting Your Match
The Xbox Live® online gaming service is used by tens of millions of players around the world to play against each other in a wide variety of games. Such a system must be able to match players with other players of comparable skill level in order that they have an enjoyable gaming experience. So how can we create an automated system to match players of similar ability at a particular type of game?
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, and so the system must have a way of estimating the skills of players. This presents some significant challenges, however. In particular, a game is not always won by the stronger player. For example, a game may involve an element of chance, and in a particular game this might happen to 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 clearly gives us some information about the players’ relative skills.
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.
So 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.