Algorithme d'appariement JcJ

De Guild Wars 2 Wiki
Aller à : navigation, rechercher


Note :
Cette page est en cours de construction et détailera l'algorithme d'appariement utilisé pour le JcJ Guild Wars 2. Revenez ici-même bientôt !
ArenaNet.

L'algorithme d'appariement JcJ est une mécanique de jeu de JcJ.

Mécanique[modifier]

Au cœur de l'algorithme d'appariement JcJ se trouve la classification de matchmaking Glicko2 (CCM). Cette classification, qui correspond à une approximation de votre niveau de compétence, vous permet d'affronter des joueurs d'un niveau similaire au vôtre. En sus de deux classifications principales (l'une en arènes non classées, l'autre en arènes classées), une classification est aussi calculée pour chaque profession. L'utilisation de classifications séparées selon les professions a pour but d'encourager les joueurs à essayer des professions qu'ils n'ont pas l'habitude de jouer.

Nous avons préféré Glicko à son http://en.wikipedia.org/wiki/Elo_rating_system alternative principale, Elo]. Comme Elo, Glicko procède au suivi de la CMM pour chaque joueur et met à jour cette classification au fur et à mesure que vous jouez. La principale amélioration de Glicko par rapport à son prédécesseur est l'introduction d'un écart type des classifications (ETC), qui rend compte de la fiabilité de la classification. En utilisant l'ETC, l'algorithme de matchmaking est capable de compenser le manque ou le défaut de données relatives à un joueur.

De plus une mesure de la volatilité est incluse afin d'indiquer le degré de fluctuation de la classification d'un joueur. Plus cette volatilité est élevée, plus la classification fluctue. La volatilité change avec le temps en fonction de votre façon de jouer. Pendant les périodes de stabilité, votre volatilité restera basse, et inversement. L'intérêt de cette mesure est de permettre au système d'évaluer de façon appropriée votre classification et ce, le plus vite possible.

Le système est aussi programmé pour augmenter votre ETC après une période d'inactivité, au cas où vous seriez un peu rouillé. (Voir Ratings/@period and Ratings/@max-periods ci-dessous.)

Configuration[modifier]

<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"/>
Élément Description
Ratings/@type Si spécifié, indique que l'élément inclut des modificateurs « override » par type.
Ratings/@reset Toute donnée de classification horodatée antérieurement est réinitialisée à sa valeur par défaut.
Ratings/@period Durée d'inactivité sur une période unique.
Ratings/@max-periods Nombre de périodes d'inactivité avant que l'écart-type d'un joueur ne passe du minimum au maximum.
Rating/@default Classification par défaut utilisée lorsqu'aucune donnée n'est disponible.
Rating/@min Classification minimale autorisée, toute valeur inférieure sera restreinte à ce minimum.
Rating/@max Classification maximale autorisée, toute valeur supérieure sera restreinte à ce maximum.
Rating/@max-change Le maximum absolu de variation d'une classification après une seule partie.
Deviation/@default Écart type de classification par défaut utilisé lorsqu'aucune donnée n'est disponible.
Deviation/@min Écart type minimum autorisé, toute valeur inférieure sera restreinte à ce minimum.
Deviation/@max Écart type maximum autorisé, toute valeur supérieure sera restreinte à ce maximum.
Volatility/@default Volatilité de la classification par défaut utilisée lorsqu'aucune donnée n'est disponible.
Volatility/@min Volatilité minimale autorisée, toute valeur inférieure sera restreinte à ce minimum.
Volatility/@max Volatilité maximale autorisée, toute valeur supérieure sera restreinte à ce maximum.
Volatility/@system-constant Paramètre de réglage de Glicko2 qui limite la variation de volatilité sur la durée.

Appariement[modifier]

L'appariement ou matchmaking est le processus par lequel les joueurs sont organisés de façon à assurer une compétition toujours divertissante entre eux. Ce système utilise une méthode de recherche en deux phases, basée sur le score et prenant en compte différents facteurs. La méthode basée sur le score est préférable à d'autres car elle offre un bon compromis entre appariements de qualité et files d'attente réduites, deux objectifs souvent difficiles à concilier.

Au début du matchmaking, le système tente de trouver un appariement personnalisé pour la première Iteration/@rosters liste (groupe) dans la file d'attente. Si aucun appariement ne peut être créé, ces joueurs seront renvoyés à la fin de la file d'attente pour permettre aux autres joueurs de trouver un appariement approprié. Même si ce procédé peut sembler injuste de prime abord, il a en réalité été prouvé qu'il réduisait le temps d'attente de tous les joueurs.

La première phase, dite « de filtrage », réunit les joueurs selon leur MMR actuel. Le but premier de cette phase est à la fois de réduire le nombre de joueurs potentiels pour un appariement, et de veiller à ce que celui-ci soit adapté au niveau de compétence de chaque joueur. Graduellement, la recherche est élargie à partir de votre classification. Bien que ce procédé puisse faire baisser la qualité de l'appariement, il permet aux joueurs considérés comme des aberrantes de tout de même obtenir des appariements.

La seconde phase de l'algorithme est la phase d'attribution des scores. Lors de cette phase, chaque joueur se voit attribuer un score par rapport aux autres joueurs susceptibles de l'affronter. Les variables utilisées pendant cette phase incluent la classification, le rang, la taille du groupe, la profession, la position dans l'indexation, et le débuff « Sans honneur ». Pour chaque variable, le système recherche les joueurs qui se rapprochent le plus de la moyenne de ceux déjà sélectionnés. Le système tente également de garder la redondance de professions au minimum.

Configuration[modifier]

<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>
Configuration
Filter/Iteration/@rosters Le nombre de listes pour lesquelles la phase de filtrage tentera de créer un appariement personnalisé.
Filter/Iteration/@limit La durée maximale par itération que peut passer le serveur à tenter de créer des appariements. Cette mesure de sécurité garantit la performance et la stabilité du serveur.
Filter/Potentials/@min Le nombre minimum de listes devant réussir la phase de filtrage avant une première tentative de création d'appariement.
Filter/Potentials/@max Le nombre maximum de listes que la phase de filtrage doit réunir. Cette mesure de sécurité garantit la performance et la stabilité du serveur.
Filter/Rating/@padding La recherche est élargie à chaque seconde que vous passez dans la file d'attente après Filter/Rating/@start. Cette mesure de sécurité garantit qu'aucune donnée aberrante ne se retrouve sans appariement.
Filter/Rating/@start Aucun élargissement de recherche n'a lieu sur l'étendue de la classification d'une liste avant ce délai.
Filter/Rating/@end Aucun élargissement supplémentaire de recherche n'aura lieu après ce délai. Cette mesure de sécurité garantit un degré minimum de qualité des matchs.
Scoring/@type L'algorithme d'attribution des scores à utiliser. Team notera les listes selon les équipes : le système ne vérifiera la redondance des professions qu'au sein d'une même équipe, au lieu de tout l'appariement.
Scoring/Age/@seconds Score ajouté ou déduit à chaque seconde d'attente d'une liste. Cette mesure de sécurité garantit des temps d'attente acceptables pour tout le monde.
Scoring/RosterSize/@distance Score ajouté ou déduit en fonction de l'écart entre la taille de la liste potentielle et la taille maximale de toutes les listes sélectionnées, y compris les deux équipes.
Scoring/RosterSize/@perfect-fit Score ajouté ou déduit si la taille de la liste potentielle correspond au nombre exact de joueurs requis pour remplir toutes les places libres dans l'équipe.
Scoring/Rank/@distance Score ajouté ou déduit en fonction de l'écart entre le rang moyen de la liste potentielle et le rang moyen de toutes les listes sélectionnées, y compris les deux équipes.
Scoring/Rating/@distance Score ajouté ou déduit en fonction de l'écart entre la classification moyenne effective (classification - écart type) de la liste potentielle et de celle de toutes les listes sélectionnées, y compris les deux équipes.
Scoring/Ladder/@distance Score ajouté ou déduit en fonction de l'écart entre les points d'indexation moyens de la liste potentielle et ceux de toutes les listes sélectionnées, y compris les deux équipes. En arène classée uniquement.
Scoring/Profession/@max Nombre maximum de professions qu'il devrait y avoir dans une équipe.
Scoring/Profession/@unique Score ajouté ou déduit pour chaque profession unique, inférieur à Scoring/Profession/@max, que la liste potentielle ajouterait à l'équipe.
Scoring/Profession/@common Score ajouté ou déduit pour chaque profession en double, supérieur ou égal à Scoring/Profession/@max, que la liste potentielle ajouterait à l'équipe.
Scoring/Dishonor/@distance Score ajouté ou déduit en fonction de l'écart entre le total de « Sans honneur » de la liste potentielle et le total de « Sans honneur » de toutes les listes sélectionnées, y compris les deux équipes.
Scoring/Dishonor/@stack Score ajouté ou déduit par nombre de débuffs « Sans honneur » cumulés par les membres de la liste potentielle.

Pseudo-code[modifier]

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)

Indexation[modifier]

L'indexation est une liste des joueurs qui participent au jeu compétitif. Votre position dans l'indexation est déterminée par le nombre de points que vous obtenez pendant une saison.

Vous gagnez des points en jouant bien, et parfois même en cas de défaite. Par exemple, en continuant à donner votre maximum même lorsque l'issue du match semble déjà décidée. Si vous vous retrouvez dans un match déséquilibré, pas de panique : vous perdrez moins de points en cas de défaite et en gagnerez plus si vous réalisez une bonne performance. De même, si vous participez à un match facile, ne pensez pas pouvoir vous la couler douce. Une bonne performance vous rapportera toujours quelques points, mais une piètre performance vous coûtera cher.

(Voir Match Prediction pour savoir comment le système calcule vos chances de victoire.)

Configuration[modifier]

Configuration
Ladder/@type Si spécifié, indique que l'élément inclut des modificateurs « override » par type.
Ladder/@start Tous les résultats obtenus avant cette date ne sont pas pris en compte dans l'indexation.
Ladder/@end Tous les résultats obtenus à ou après cette date ne sont pas pris en compte dans l'indexation.
Ladder/@default Nombre de points pas défaut à utiliser si aucune autre donnée n'est disponible.
Ladder/@min Nombre minimum de points d'indexation possible.
Ladder/@max Nombre maximum de points d'indexation possible.
Ladder/@leaderboard Le classement associé à cette indexation.
Ladder/@leaderboard-points Nombre minimum de points requis pour que les données du joueur soient prises en compte dans le classement.
Matrix/@odds Seuil minimum de chances de victoire. Couplé avec Matrix/Score/@min pour déterminer le nombre de points d'indexation à attribuer.
Score/@min Score minimum requis pour gagner Score/@points points d'indexation.
Score/@points Nombre de points à attribuer si les seuils Matrix/@odds et Score/@min sont atteints. Seul le seuil le plus élevé est pris en compte.

Pseudo-Code[modifier]

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)

Chances de victoire[modifier]

Le système tente de prédire l'issue d'un match avec les mêmes données que celles utilisées pour le matchmaking. Parmi celles-ci, les deux facteurs principaux qui décident de l'issue d'un match semblent être la différence de ratings entre les deux équipes et la différence de taille maximum entre les deux équipes.

Le rang est également pris en compte à titre expérimental, mais pourrait être supprimé ultérieurement.

Configuration[modifier]

<Prediction>
  <Rank  method="Spread" spread="40" weight="1"/>
  <Rating method="Spread" spread="200" weight="5"/>
  <Roster method="Spread" spread="4"  weight="2"/>
</Prediction>
Prediction/*/@method Détermine quelle méthode de calcul utiliser.
Prediction/*/@spread Amplitude maximale à calculer.
Prediction/*/@weight L'impact qu'a ce calcul sur la prédiction finale (plus le nombre est élevé, plus l'impact est important).
Prediction/Rank S'il est disponible, le rang moyen de chaque équipe est pris en compte dans le calcul.
Prediction/Rating Si elle est disponible, la classification effective moyenne (classification - écart type) de chaque équipe est prise en compte dans le calcul.
Prediction/Roster Si elle est disponible, la taille maximum de la liste de chaque équipe est prise en compte dans le calcul.

Pseudo-Code[modifier]

// 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 + 1;
  if team == 'red':
    return 1 - normalized
  else:
    return normalized

Débuff « Sans honneur »[modifier]

Le débuff « Sans honneur » est l'un des moyens utilisés pour encourager le fair-play. Un comportement irrespectueux sera sanctionné à moyen et à long terme par des cumuls. Chaque cumul représente une durée qui diminue avec le temps. Chaque fois que vous recevez un débuff « Sans honneur », vous recevez également un temps mort. La durée du temps mort augmente de manière exponentielle en fonction du nombre de cumuls. En d'autres termes, votre première infraction n'entraînera qu'un court temps mort, mais votre 20e infraction vous empêchera de jouer pendant un long moment.

Pendant un temps mort, vous ne pouvez pas participer à des matchs en arène classée ou non classée, mais vous pouvez jouer dans des arènes personnalisées.

Les débuffs « Sans honneur » affectent aussi le matchmaking en vous opposant à des joueurs qui en ont reçu également. Ce n'est pas une file d'attente différente, mais simplement une suggestion dans le système de matchmaking.

Il est possible d'avoir des cumuls de débuffs « Sans honneur » sans pour autant avoir de temps mort actif car les débuffs diminuent beaucoup plus lentement que les temps morts.

Configuration[modifier]

Dishonor/@stack-duration Durée d'un seul cumul de débuff « Sans honneur ».
Dishonor/@timeout-duration Durée, par cumul de débuff puissance @timeout-exponent, à ajouter au temps mort du joueur.
Dishonor/@timeout-exponent Exposant utilisé pour multiplier les cumuls de débuffs par Dishonor/@timeout.
Dishonor/@timeout-rounding Le temps mort additionnel est arrondi à l'intervalle @timeout-rounding le plus proche avant d'être ajouté au temps mort total du joueur. Cela représente également le temps mort minimum qui puisse être attribué.
Penalty/@reason Raison pour laquelle le débuff est attribué. Abandon : si vous quittez un match avant la fin. QueueDodge : si vous quittez ou ne confirmez pas que vous êtes prêt. Banned : si un MJ décide que vous ne pouvez plus participer à des matchs en arène classée ou non classée.
Penalty/@stacks Nombre de cumuls de débuff « Sans honneur » à ajouter au joueur.

Pseudo-Code[modifier]

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)