Algorithme d'appariement JcJ
Des éléments clés de cet article sont incomplets. Vous pouvez aider le wiki en y contribuant.
|
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)