Matchmaking for computer games

Written by Anders Törlind - 2013 - All rights reserved.

Introduction

Wikipedia says: "Matchmaking is the process of matching two people together, usually for the purpose of marriage, but the word is also used in the context of sporting events, such as boxing, and in business."

Matchmaking is an old term with many uses. In the context discussed here, it originates from professional boxing, where the idea was to provide the audience with a match that was exciting and would return entertainment value for the admission fee. Today it is a term used, in the computer games industry, for automated algorithms for pitting players against each other for their own entertainment in various PvP formats. The rest of the text concerns itself exclusively with software and methods pertaining to computer gaming.

Purpose of the match maker

The very idea of the matchmaking software is, as mentioned above, to provide matches that are fun for the participating players. In a PvP setting, there is almost always a winner and a loser (or multiples of both in a team game) - Pleasing the winner is easy, pleasing the loser is harder. The matchmaking algorithm can be used to, so to speak, cushion the fall of losing too often.

A skilled player is subject to another hazard; boredom due to low challenge. Again, the matchmaker may come to our rescue. This will be discussed a greater length below.

Approaches to, and methods of matchmaking

Common modes of match making are easy to identify - I will list them here.

Manual

This is the "naive" approach. Put all players in a lounge and let them challenge each other. Eventually a pecking order will appear and the players will match themselves according to their tastes.

The manual method has many advantages, the obvious one being that "that which isn't there can't break". No player will complain about how they are matched if they do the matching themselves. Players may contact each other before commencing a match, thus furthering a feeling of community, and reducing the impact of a loss.

In a case where there are too many active players to get to know each other, various approaches may be employed:

Random

Mainly used for team games, where the manual approach would be untenable, random matchmaking may make sense. This means that you simply throw players together to form teams and then pit the teams against each other. It's less commonly seen for single player games, since manual matchmaking is so easily maintained, but will certainly work for that case as well.

The main appeal of this method is the speed of matching - It is easy to put together games of many players and have them playing each other without many minutes of preparation and team assembly. It has other interesting properties as well, the main one being that as the number of participating players per team increases, the skill levels of the teams tend to average out more and more. This means that matches tend to become more even as team sizes increase, meaning that even a weak player has a chance of winning matches now and then. If teams are sufficiently small, skilled players will be essential to team success, meaning that highly skilled individuals will win a clear majority of their matches.

Of course, there are also problems. The main one being that, given a bit of bad luck, a player may be matched with very bad team members or against very strong opposition many times in a row. Moreover, if the team size is large, the player may feel, or indeed be, powerless to affect the outcome of the match as an individual - The result is already determined by the large skill gap of the teams.

Schoolyard

This oddly named method is, of course, employed in schoolyard sports the world over. It consists of players being selected for their teams in order of play strength on a turn-by-turn basis. The "captain" of one team selects the best player form a pool of available players, after which the opposing captain gets his pick and so on, until the pool is exhausted or the teams are full.

The main purpose of this method is to ensure that the teams are fairly balanced, and that the ensuing match should offer a challenge for every participant of decent skill level. If the match is part of a series of matches, rebalancing often takes place between matches if the result of the match was too one sided. The method is usually quite successful in creating reasonably even matching.

If this method is to be used in an automated setting, there must be some kind of rating system in place for judging the skill levels of the players - This rating serves as the basis of team balancing. Also, in a computer game setting, more sophisticated algorithms than "captains choose" may be employed to balance the teams once the pool of players is known. The end result will be similar, if not identical.

Problems with this type of matching occur when players are highly competitive - The method works well in friendly environments. If the pool of players is a randomly selected set out of a larger population of players waiting to be matched, that set of players will tend to be fairly evenly distributed around average skill. Highly skilled players are unlikely to be matched together in the same team - Being consistently matched together with less skilled players may be frustrating. This is the old "...but why do I have to play with Sisyphus? He sucks!". Another problem is that the "skill floor" will remain at average - There is no reliable way for a skilled player in search of higher level play to get better than average teams for a match.

Rated

In rated matchmaking, player strength forms the basis of team selection from the very beginning. As opposed to the schoolyard method, where an essentially random set of players is assigned to teams, rated matchmaking begins with selection by player strength. Players may be selected to a pool by rating and teams then created to be of equal strength from the pool or players may be selected directly from a queue of waiting players by filtering on the fly. The player selection method is not really very important, but the end result is two teams of homogenized and balanced skill facing each other. Win chances should approach 50/50 in every match.

Obviously, a rating system for player strength is needed for this to be even remotely feasible. I will touch on the desired properties of such a rating system in another text, but suffice to say that it has to rate players reliably across a large skill span and must not exhibit skew under the influence of the matchmakers decision.

Rated matchmaking is used to ensure that matches are challenging for all participants equally. It normalises win ratio towards 50% for all but the most extremely skilled players, meaning an equal dosage of frustration and elation for all players.

Drawbacks of rated matchmaking are complex. Some players simply do not desire tightly fought matches, and instead prefer dominance of less skilled opponents. Some think the tension inherent in defending your rating, and consequently matching, is too stressful. Some players oppose perceived elitism inherent in rated systems, feeling that play strength in a computer game correlates to self value - Or that they expect bad treatment from those who do.

League

Leagues are a tried and tested method of matchmaking in team sports. The idea is that a league provide a framework of advancement for a player or (persistent) team. They generally form a hierarchy of separate leagues, often a tree structure, where each lower level feeds winners to the level above and losers to the level below. Often, leagues run for a set time, after which over performers are moved up, under performers are moved down, scores reset and the league restarted with a new set of teams.

In a computer game context, leagues are often used in organised play, where some arbiter runs tournaments etc. It is also possible to implement in a fully automated way. A league system requires no rating system as such - It is a rating system in itself, as well as being the match making mechanism.

Automated leagues may be implemented in different ways. The obvious example is the "cup" - Pre-planned matches pit all league members against each other once or twice (to compensate for home advantage). An example more applicable to popular online games may be that players are selected randomly to a match from a pool formed by a single league - Though this requires very large leagues for quick matching. The latter method will give a rough normalisation of player strength in any given match.

There are several nice features about leagues. They serve as bragging rights, much as levels do in RPGs, yet maintain a less abrasive air around them than rating systems. Sufficiently small leagues will yield interesting matches for the most part, as the skill span between the top player/team in a league and the bottom one should not be completely insurmountable.

Less flattering features include the fact that even a very good player or team may end up on the bottom of an even more skilled league, meaning a sudden rash of losses upon promotion. This is expected and natural (though often difficult) in the sporting world, but harder to accept in a computer gaming context. In set-time leagues this situation might persist an entire cycle, or even longer if the player manages to cling to a league that he just barely qualifies for.

Ladder

A ladder is a one-dimensional ordering of players after who beat whom. This is employed for example in title boxing and MMA, where the only thing needed to be crowned as champion is to beat the current champion once.

This method is often a support structure for manual matching, but may work as an automated matchmaker as well. Usually, a player lower on the ladder will issue a challenge to a player higher on the ladder. If the challenger wins, he takes the spot of the defender, pushing the defender down one rung. If the defender wins, the status quo remains. Defenders declining a challenge default to a loss.

The ladder is not very sophisticated, and hard to make workable in a multi-player environment. On the plus side, it gives rise to "linear champions", something that gives some story to your matchmaking.

Conclusion

The matchmaker is an important part of a PvP game. It forms the basis of a large part of the player experience: The opposition. As such, it is very much the subject of player opinion and feedback. Heated debates will arise about its supposed fairness or unfairness. A matchmaker that serves unsatisfying matches (as judged by the playing community, not by some universal metric) will cause much lamentation and may in fact turn people off the game completely. As such, the matchmaker should be scrutinized and under watchful eyes for unwanted behaviour. Exactly what behaviour is unwanted or desired is, as always, in the eyes of the beholder!