PvP Matchmaking Algorithm

This page is currently under construction!

Примечание: This page is under construction and details the Matchmaking Algorithm used in Guild Wars 2 PvP..

Ratings

At the heart of PvP matchmaking algorithm is the Glicko2 matchmaking rating (MMR). This rating, which is an approximation of your skill level, helps match you with other players with similar skill level. In addition to two core ratings (one for unranked and ranked arena), a rating is also kept for each profession. More than one rating is used in order to encourage players to experiment with other professions they may not play regularly.

Glicko was chosen over its main alternative, Elo. Like Elo, Glicko tracks MMR for each player and updates that rating over time as you play the game. Glicko's main improvement over its predecessor is the inclusion of a ratings deviation (RD), which measures the reliability of the rating. By using RD, the matchmaking algorithm can compensate for players it has little or incomplete information about.

A volatility measurement is also included to indicate the degree of fluctuation in a player's rating. The higher the volatility, the more the rating fluctuates. Volatility changes over time in response to how you play the game. During periods of stability, your volatility should remain low, and reciprocally. The point of this is to allow the system to hone in on your appropriate rating as quickly as possible.

The system is also set up to increase your RD after periods of inactivity, just in case you're a little rusty. (See Ratings/@period and Ratings/@max-periods below.

Configuration

<Ratings period="3d" max-periods="20">
  <Rating default="1500" min="100" max="5000" max-change="300" profession-ratio="0"/>
  <Deviation default="350" min="30" max="350" />
  <Volatility default="0.06" min="0.04" max="0.08" system-constant="0.5" />
</Ratings>
<Ratings type="Unranked" reset="2014-02-01"/>
<Ratings type="Ranked"  reset="2014-02-01"/>

Element (XPath)	Description
Ratings/@type	If specified, indicates this element contains per-type overrides.
Ratings/@reset	Any ratings data with a timestamp before this date is reset to the default.
Ratings/@period	Length of inactivity for a single period.
Ratings/@max-periods	Number of periods of inactivity before a player's deviation to go from the minimum to the maximum amount.
Rating/@default	Default rating that is used when no data is available.
Rating/@min	Minimum rating allowed, anything below will be clamped to this value.
Rating/@max	Maximum rating allowed, anything above will be clamped to this value.
Rating/@max-change	The maximum, absolute amount a rating can change from a single game.
Rating/@profession-ratio	Controls the balance between profession rating and core rating. '0' means only the core rating is used, while '1' means only the profession rating is used.
Deviation/@default	Default ratings deviation that is used when no data is available.
Deviation/@min	Minimum deviation allowed, anything below will be clamped to this value.
Deviation/@max	Maximum deviation allowed, anything above will be clamped to this value.
Volatility/@default	Default ratings volatility that is used when no data is available.
Volatility/@min	Minimum volatility allowed, anything below will be clamped to this value.
Volatility/@max	Maximum volatility allowed, anything above will be clamped to this value.
Volatility/@system-constant	Glicko2 tuning parameter that constrains the change in volatility over time.

Matchmaking

Matchmaking is the process of organizing players in such a way as to encourage competitive and fun gameplay. The system uses a two-phase, score-based search method that takes into consideration several metrics. A score-based search method was used over other methods because it's a good compromise between the often competing goals of match quality and short wait times.

At the start of matchmaking, the system attempts to find a match customized for the first Filter/Iteration/@rosters rosters (party) in the queue. If no match can be created, these players will be put at the end of the queue to ensure other players have a chance at a match customized for them. While this may seem unfair at first, this has actually been shown to decrease wait times for all players.

The first phase, called filtering, gathers players based on their current MMR. The primary purpose of this phase is to both reduce the number of players being considered for a match, and to ensure that the match is appropriate given each player's skill level. Over time, padding is added to your player rating. While this may decrease match quality, it helps ensure that outliers still receive matches.

The second phase of the algorithm is the scoring phase. During this phase each player is scored against every other player being considered for matchmaking. The metrics used during this phase include: rating, rank, party size, profession, ladder position, and dishonor. With each metric the system is looking for players that are as close as possible to the average of those already selected. The system also attempts to keep the number of duplicate professions to a minimum.

Configuration

<Filter>
  <Iteration rosters="50" limit="50ms"/>
  <Potentials min="20" max="500"/>
  <Rating padding="10" start="30s" end="4m"/>
</Filter>
<Scoring type="Team">
  <Age seconds="15"/>
  <RosterSize distance="-500" perfect-fit="200"/>
  <Rank distance="-10"/>
  <Rating distance="-5"/>
  <Profession max="2" common="-500" unique="500"/>
  <Dishonor distance="-100" stack="-50"/>
</Scoring>

Element (XPath)	Description
Filter/Iteration/@rosters	The number of rosters the filtering phase will try to form custom matches for.
Filter/Iteration/@limit	The maximum amount of time the server should spend trying to create matches per iteration. This is a performance fail-safe to keep the server responsive.
Filter/Potentials/@min	The minimum number of rosters that must pass the filter phase before attempting to create a match.
Filter/Potentials/@max	The maximum number of rosters the filter phase should gather. This is a performance fail-safe to keep the server responsive.
Filter/Rating/@padding	Padding is added every second you wait in the queue after Filter/Rating/@start has passed. This is an outlier fail-safe to ensure everyone gets a match.
Filter/Rating/@start	No padding is added to a roster's ratings range until this length of time has passed.
Filter/Rating/@end	No additional padding will be added after this length of time has passed. This is a fail-safe to prevent match quality from degrading futher than prefered.
Scoring/@type	The type of scoring algorithm to use. Team will score rosters on a per-team basis, i.e. will only check for duplicate profession on the team, not the entire match.
Scoring/Age/@seconds	Score added or removed for every second a roster has been waiting. Outlier fail-safe to ensure no one waits too long.
Scoring/RosterSize/@distance	Score added or removed based on the distance between the potential roster's size and the max roster size of all selected rosters, including both teams.
Scoring/RosterSize/@perfect-fit	Score added or removed if the potential roster's size matches the exact number of players needed to fill empty spots on the team.
Scoring/Rank/@distance	Score added or removed based on the distance between the potential roster's average rank and the average rank of all selected rosters, including both teams.
Scoring/Rating/@distance	Score added or removed based on the distance between the potential roster's average effective rating (i.e. rating - deviation) and the average effective rating of all selected rosters, including both teams.
Scoring/Ladder/@distance	Score added or removed based on the distance between the potential roster's average ladder points and the average ladder points of all selected rosters, including both teams. For Rated Arena only.
Scoring/Profession/@max	Target maximum number of professions that should exist on a team.
Scoring/Profession/@unique	Score added or removed for each unique profession, under Scoring/Profession/@max, the potential roster would add to the team.
Scoring/Profession/@common	Score added or removed for each duplicate profession, at or above Scoring/Profession/@max, the potential roster would add to the team.
Scoring/Dishonor/@distance	Score added or removed based on the distance between the potential roster's total dishonor and the total dishonor of all selected rosters, including both teams.
Scoring/Dishonor/@stack	Score added or removed per stack of dishonor the potential roster has on any of its members.

Pseudo-Code

def gatherPotentials(queue, target, config):
  potentials = []
  for roster in queue:
    if roster.ratingLow > target.ratingHigh:
       continue
    if roster.ratingHigh < target.ratingLow:
      continue
    potentials.append(roster)
    if len(potentials) >= config.filter.potentials.max:
      break
  return potentials

def shouldPopulateRed(red, blue, config):
  if red.players >= config.teamSize:
    return False
  if blue.players >= config.teamSize:
    return True
  return red.ratingLow < blue.ratingLow

def scoreRoster(roster, team, maxLadder, maxRosterSize, config):
  score = 0
  # adjust score by time queued
  score += roster.age * config.age.seconds
  # adjust score by lower-bound rating distance
  distance = abs(team.ratingLow - roster.ratingLow)
  score += distance * config.rating.distance
  # adjust score by rank distance
  distance = abs(team.rank - roster.rank)
  score += distance * config.rank.distance
  # adjust score by ladder distance
  distance = abs(maxLadder - roster.ladder)
  score += distance * config.ladder.distance
  # adjust score by roster size
  distance = abs(maxRosterSize - roster.players)
  score += distance * config.rosterSize.distance
  if roster.players == maxRosterSize:
    score += config.rosterSize.perfectFit
  # adjust score by dishonor
  distance = abs(team.dishonor - roster.dishonor)
  score += distance * config.dishonor.distance
  score += roster.dishonor * config.dishonor.stack
  # adjust score by profession count
  for profession in list_of_all_professions:
    count = roster.countProfessions(profession)
    if count == 0:
      continue
    count += team.countProfessions(professions)
    if count >= config.professions.max:
      count -= config.professions.max - 1;
      score += count * config.professions.common
    else:
      count = config.professions.max - count
      score += count * config.professions.unique
  return score

def pickRoster(team, maxLadder, maxRosterSize, potentials, config):
  best = None
  playersNeeded = config.teamSize - team.players
  for roster in potentials:
    if roster.players > playersNeeded:
      continue
    roster.score = scoreRoster(roster, team, maxLadder, maxRosterSize, config.scoring)
    if best is None or best.score < roster.score:
      best = roster
  return best

def populateMatch(target, potentials, config):
  red = []
  blue = []
  # add target roster to red team
  red.append(target)
  maxRosterSize = target.players
  maxLadder = target.ladder
  while red.players < config.teamSize or blue.players < config.teamSize:
    chosen = None
    if shouldPopulateRed(red, blue, config):
      chosen = pickRoster(red, maxLadder, maxRosterSize, potentials, config)
    else:
      chosen = pickRoster(blue, maxLadder, maxRosterSize, potentials, config)
    if chosen is None:
      break
    maxLadder = max(maxLadder, chosen.ladder)
    maxRosterSize = max(maxRosterSize, chosen.players)
  selected = []
  for roster in red:
    roster.team = 'red'
    selected.append(roster)
  for roster in blue:
    roster.team = 'blue'
    selected.append(roster)
  return selected

def withdrawRosters(queue, target, config):
  # gather rosters that could be potentially matched
  potentials = gatherPotentials(queue, target, config)
  if len(potentials) < config.potentials.min:
    return None
  return populateMatch(target, potentials, config)

def rollbackRosters(queue, rosters):
  for roster in rosters:
    roster.team = None
    queue.append(roster)

def gatherRostersForCustomMatch(queue, config):
  rosters = []
  for roster in queue:
    rosters.append(roster)
    if len(rosters) >= config.filter.rosters:
      break
  return rosters

def createMatches(queue, config):
  rosters = gatherRostersForCustomMatch(queue, config)
  failed = []
  while len(rosters) > 0:
    roster = rosters.pop()
    queue.remove(roster)
    selected = withdrawRosters(queue, roster, config)
    if selected is None or selected.players != config.teamSize * 2:
      failed.append(roster)
      selected.remove(roster)
      rollbackRosters(queue, selected)
    else:
      sendCreateMatch(selected)
  # move rosters we couldn't find match for to the end of the queue
  for roster in failed:
     queue.append(roster)

Ladder

The ladder is a list of all players currently participating in competitive play. Your ladder ranking is determined by how may points you are awarded throughout a season.

You are awarded points for playing well, and often, and sometimes even if you lose a game. Even if a comeback may not seem possible, you can still be rewarded for continuing to try your very best. If you find yourself in an uneven match, fear not, you will risk fewer points for losing, and have more points to gain for doing well. Likewise, if you participate in an easy match, don't think you're home free. Performing well might award you points, but performing poorly will take even more away.

(See Match Prediction for more information on how the system determines your odds of victory.)

Configuration

<Ladder default="0" min="0" max="1000000" leaderboard-points="1">
  <Matrix odds="0.0">
    <Score min="0"  points="-1"/>
    <Score min="200" points="0"/>
    <Score min="300" points="1"/>
    <Score min="400" points="2"/>
    <Score min="500" points="3"/>
  </Matrix>
  <Matrix odds="0.2">
    <Score min="0"  points="-1"/>
    <Score min="300" points="0"/>
    <Score min="400" points="1"/>
    <Score min="500" points="2"/>
  </Matrix>
  <Matrix odds="0.4">
    <Score min="0"  points="-1"/>
    <Score min="400" points="0"/>
    <Score min="500" points="1"/>
  </Matrix>
  <Matrix odds="0.6">
    <Score min="0"  points="-2"/>
    <Score min="300" points="-1"/>
    <Score min="400" points="0"/>
    <Score min="500" points="1"/>
  </Matrix>
  <Matrix odds="0.8">
    <Score min="0"  points="-3"/>
    <Score min="200" points="-2"/>
    <Score min="300" points="-1"/>
    <Score min="400" points="0"/>
    <Score min="500" points="1"/>
  </Matrix>
</Ladder>
<Ladder type="Competitive" start="2014-11-12" end="2014-11-30" leaderboard="PvPLadder"/>

Element (XPath)	Description
Ladder/@type	If specified, indicates this element contains per-type overrides.
Ladder/@start	Any game results that occur before this date are not included on the ladder.
Ladder/@end	Any game results that occur on or after this date are not included on the ladder.
Ladder/@default	Default number of points to use if no other data is available.
Ladder/@min	Minimum number of ladder points possible.
Ladder/@max	Maximum number of ladder points possible.
Ladder/@leaderboard	The Leaderboard associated with this ladder.
Ladder/@leaderboard-points	Minimum number of points required before the player's data will be submitted to the Leaderboard.
Matrix/@odds	Minimum odds threshold. Paired with Matrix/Score/@min to determine the number of ladder points to award.
Score/@min	Minimum score threshold required to earn Score/@points ladder points.
Score/@points	Number of points to award if both Matrix/@odds and Score/@min thresholds are met. Only the highest thresholds count.

Pseudo-Code

def getPoints(oddsOfVictory, finalScore, config):
  currentDate = Time.now()
  if currentDate < config.startDate or currentDate >= config.endDate:
    return 0
  bestMatrix = null
  for matrix in config.ladderMatrix:
    if matrix.odds > oddsOfVictory:
      continue
    if bestMatrix is null or matrix.odds > bestMatrix.odds:
      bestMatrix = matrix
  bestScore = null
  for score in bestMatrix.scores:
    if score.min > finalScore:
      continue
    if bestScore is null or score.min > bestScore.min
      bestScore = score
  return bestScore.points

def processGame(player, game, config):
  oddsOfVictory = predictionToOddsOfVictory(game.prediction, player.team)
  finalScore = game.score[player.team]
  if game.result == 'desertion':
    finalScore = 0
  prevPoints = player.ladderPoints
  pointsAwarded = getPoints(oddsOfVictory, finalScore, config)
  if game.result == 'victory':
    pointsAwarded = max(1, pointsAwarded)
  player.ladderPoints += pointsAwarded
  if player.ladderPoints >= config.leaderboardPoints:
    sendLeaderboardUpdate(config.leaderboard, player.id, player.ladderPoints)
  else if prevPoints >= config.leaderboardPoints:
    sendLeaderboardRemove(config.leaderboard, player.id)

Match Prediction

The system attempts to predict the outcome of a match with the same metrics used in matchmaking. Of these, the two biggest factors in deciding the outcome seem to be the difference between each team's ratings, as well as the size of their largest party.

Currently rank is also being used on an experimental basis, but may be removed.

Configuration

<Prediction>
  <Rank  method="Spread" spread="40" weight="1"/>
  <Rating method="Spread" spread="200" weight="5"/>
  <Roster method="Spread" spread="4"  weight="2"/>
</Prediction>

Element (XPath)	Description
Prediction/*/@method	Specifies which calculation method to use.
Prediction/*/@spread	Maximum spread to calculate.
Prediction/*/@weight	The impact, with higher numbers indicating more impact, this calculation has on the final prediction.
Prediction/Rank	If present, each team's average rank is used for the calculation.
Prediction/Rating	If present, each team's average effective rating (i.e. rating - deviation) is used for the calculation.
Prediction/Roster	If present, each team's maximum roster size is used for the calculation.

Pseudo-Code

// Return the spread between two values normalized to -1..1.
def calculateSpread (red, blue, maxSpread):
  spread = (blue - red) / maxSpread
  return clamp(spread, -1, +1);

// Returns a prediction value between -1 and 1, where -1 means red dominate,
// and +1 means blue dominate.
def predict(red, blue, config):
  rank = calculateSpread(red.averageRank, blue.averageRank, config.rankSpread) * config.rankWeight
  rating = calculateSpread(red.averageRatingLow, blue.averageRatingLow, config.ratingSpread) * config.ratingWeight
  roster = calculateSpread(red.maxRosterSize, blue.maxRosterSize, config.rosterSpread) * config.rosterWeight
  totalScore = rank + rating + roster
  totalWeight = config.rankWeight + config.ratingWeight + config.rosterWeight
  return clamp(totalScore / totalWeight, -1, +1)

// Returns the team's odds of victory as a ratio of 0..1, where 0 means
// minimal chance of victory and 1 means minimal chance of defeat.
def predictionToOddsOfVictory (prediction, team):
  normalized = prediction / 2 + 0.5;
  if team == 'red':
    return 1 - normalized
  else:
    return normalized

Dishonor

Dishonor is one of the methods used to encourage good sportsmanship. Behavior is tracked in the medium to long range through stacks. Each stack represents a duration that decays over time. Every time you receive dishonor you also receive a timeout. The length of a timeout increases exponentially based on how many stacks you currently have. In other words, your first offense may yield a short timeout, while your 20th may keep you from playing for a much longer amount of time.

While in timeout, you may not participate in ranked or unranked arena, but you can still play in custom arenas.

Dishonor also impacts matchmaking by preferring to place you with other players that also have dishonor. This isn't a separate queue, but merely a suggestion to the matchmaking system.

It's possible to have stacks of dishonor without having an active timeout because dishonor decays at a much slower rate.

Configuration

<Dishonor stack-duration="15m" timeout-duration="30s" timeout-exponent="1.5" timeout-rounding="1m">
  <Penalty reason="Abandon"  stacks="10"/>
  <Penalty reason="QueueDodge" stacks="4"/>
  <Penalty reason="Banned"   stacks="1000000"/>
</Dishonor>

Element (XPath)	Description
Dishonor/@stack-duration	Length of time a single stack of dishonor will last before expiring.
Dishonor/@timeout-duration	Length of time, per stack of dishonor to the power of @timeout-exponent, to add to the player's timeout.
Dishonor/@timeout-exponent	Exponent used when multiplying dishonor stacks by Dishonor/@timeout.
Dishonor/@timeout-rounding	Additional timeout is rounded to the nearest @timeout-rounding interval before being added to the player's timeout. Also acts as the minimum length of timeout that can be earned.
Penalty/@reason	Reason the dishonor is being awarded. Abandon: leaving a match before the end. QueueDodge: leaving or failing to confirm you're ready for a match. Banned: When a GM determines you may no longer participate in ranked or unranked arena.
Penalty/@stacks	Number of stacks of dishonor to add to the player.

Pseudo-Code

def roundInterval(value, interval):
  return max(interval, round(value / interval) * interval)

def applyDishonor(player, penalty, config):
  player.stacks += penalty.stacks
  newTimeout   = pow(player.stacks, config.timeoutExponent) * config.timeoutDuration
  player.timeout += roundInterval(newTimeout, config.timeoutRounding)

References

{{#Widget:prettyprint}}