mercredi 26 janvier 2011

[Focus] Comprendre le système de ligue de Battle.net sur Starcraft 2

Attention ! Cet article est très précis et donne pas mal d'informations sur les algorithmes utilisés par le Système de Battle.net, cachets d'aspirine à prévoir pour ceux qui auront le courage de le lire en entier.

INTRODUCTION

Cet article suit directement un post original sur l’analyse du “ladder” allant plus loin dans le détail à propos du système lui-même. Notons ici qu’une grande partie du contenu de cet article est de nature plus "spéculative", et si un détail s’avère erroné ça ne devrait pas se répercuter dans l’analyse d’origine. Nous fouillerons un peu plus profondément dans les fondamentaux des mathématiques pour comprendre le MMR, sans rendre ça trop complexe mais facile à suivre.

VUE D’ENSEMBLE

Pour commencer, on suppose que Blizzard utilise un système similaire au MMR de WoW Arena, malgré quelques distinctions. Le système de l’Arena utilise un modèle du théorème de Bayes pour créer son “ladder” et créer les matchs. Ce que ça signifie, c’est que le classement représentant le niveau du joueur est mis à jour après chaque match.

Suivant ça, le MMR (MatchMaking Rating) est en fait une partie des moyens de classement du niveau des joueurs. Blizzard utilise aussi un facteur « chance », d’incertitude (le sigma). Celui-ci influe beaucoup quand on débute. Plus on joue de matchs, plus ce facteur diminue et le système est plus “confiant” envers le classement qu’il vous a attribué. On se réfèrera à ce facteur d’incertitude comme le sigma. Ce facteur forme une courbe mathématique en forme de « cloche », aussi connue comme la loi de Gauss ou loi normale gaussienne. La courbe représente ceci : la zone probable (la ligue pourrait-on dire) dans laquelle votre niveau vous fait tomber et le fait que vous ne jouez pas exactement au même niveau à chaque match. Un joueur solide aura une courbe à la forme plus pointue par exemple. Car la surface est plus fine et la pointe plus haute, ce qui veut dire que le niveau« probable » du joueur est peu variable selon le match et que son niveau maximal « probable » est élevé.

Ce type de classement et de calcul du niveau des joueurs n’est pas nouveau. Le premier système utilisant cette méthode est le système Glicko, utilisé pour les joueurs d’échec, et il semblerait meilleur que le fameux système ELO lequel encourage de curieux comportements (il vaut mieux faire « égalité » dans le « ELO » que de risquer de perdre). Un autre système bien connu est le Microsoft TrueSkill, utilisé dans tous les classements et les distributions des matchs sur Xbox360 ou PC pour Dawn of War 2, par exemple.

Les données publiées sur le TrueSkill donnent une vision furtive des fondements d’un système moderne de classement de type Bayes (voir plus haut) mis au point pour les jeux vidéo. Les mises en application de Blizzard sont clairement différentes du TrueSkill, cependant on peut déduire beaucoup de choses de ce que nous apprend TrueSkill et de ce qu’on sait du ladder de Starcraft 2.


MATCHMAKING RATING

La version courte de ce qu’explique le lien au-dessus est qu’il est possible de prendre le MMR et le facteur d’incertitude (sigma) pour chacun des joueurs. Le MMR et le sigma forment une « cloche » pour chaque joueur. Il est possible de combiner la courbe en cloche sous un format de probabilité en 3D en combinant les données ainsi :
Figure 1 : représentation 3D du MMR

Ça peut aider d’imaginer ça en combinant 2 courbes en 2D perpendiculairement et formant une courbe 3D. Imaginons cette figure 3D vue du dessus et vue de profile.

Cette courbe est centrée dans un plan (x;y), où x est le niveau du joueur 1 et y le niveau du joueur 2. Par déduction, le « meilleur » match sera entre dans la zone où x=y. D’ailleurs, Blizzard tente de garder cette zone la plus fine possible.



Figure 2 : représentation 2D du MMR

Tracez une ligne le long de la zone x=y (vert), vous séparerez la courbe en 2. Si on compare la taille relative des surfaces de chaque côté de cette ligne, on obtient la probabilité de victoire d’un joueur. Si la courbe se trouve entièrement d’un seul côté du graphique alors un joueur est clairement avantagé par le système (courbe de droite). Attention ce n’est pas la détermination du statut « favori » lors de la page de chargement. Notez, dans la figure de gauche, que la zone du matchmaking peut ne pas être circulaire. Si le joueur possède des données de confiance différentes, la zone peut prendre la forme d’une ellipse.

Rappelons que ce schéma est emprunté à une présentation du TrueSkill, et est propriété de Microsoft. TrueSkill intègre la possibilité du match nul. Plus intuitivement, on peut imaginer ça comme la «zone du matchmaking idéal», quelque chose de similaire est plus ou moins adapté sur le ladder Starcraft 2 pour accorder au système du matchmaking une certaine marge de manœuvre (le MMR ne vous donne pas forcément un adversaire d’exactement votre niveau).

Après qu’un math ce soit terminé, le système a besoin de mettre à jour le MMR et le sigma pour les 2 joueurs. Dès que le match est terminé le MMR du gagnant augmente et celui du perdant diminue. Le plus intéressant reste ce qui de passe avec le sigma. Si le match se termine comme prévu, avec la victoire du joueur favori, selon le système (pas le statut « favori » de l’écran de chargement), alors le sigma des 2 joueurs va diminuer (l’incertitude du résultat diminue). Ceci car le système fait confiance au classement effectué en amont et le répercute sur les joueurs. Si le match se termine contre la logique du classement et que le sigma des 2 joueurs est faible, alors le sigma des 2 joueurs va augmenter car le système estime qu’il y aurait eu un mauvais classement alloué à chaque joueur (l’incertitude du résultat augmente).
Si le sigma d’un joueur est surestimé (qu’il soit vainqueur ou perdant) il peut diminuer (rendant l’issue des matchs suivants moins incertaine) car, selon le bon MMR et la valeur du sigma, il est théoriquement possible pour le système de prendre en compte le niveau du joueur et le classer avec plus de précision. Si le sigma du joueur est faible, quoi qu’il arrive, il peut augmenter après un résultat « surprise » si cette « surprise » est vraiment inattendue (car le sigma est faible, l’adversaire aurait été choisi pour garantir le résultat, bon ou mauvais).

En résumé, en combinant le MMR et le facteur d’incertitude (sigma) d’un joueur, on créé une courbe. Prenez cette courbe et formez une figure en 3D. Cette figure montre la probabilité de victoire quand on sépare le schéma en 2 le long de la ligne x=y (zone d’égalité du niveau des joueurs). Le matchmaking essaie de trouver la zone x=y, mais il étend la recherche si aucun match n’est rapidement trouvé.


PROMOTION RELEGATION

Comme théoriquement présentée, la promotion de ligue requière un MMR supérieur au seuil d’une certaine ligue. Quoiqu’il arrive, le système réclame un degré particulier de confiance (envers le classement alloué) avant d’autoriser une montée, une promotion car le MMR évolue fortement après chaque match et la diversité des adversaires est très grande, souvent venant de différentes ligues. La théorie initiale suppose que le sigma nécessite juste d’être suffisamment bas pour permettre une promotion, mais il a été confirmé que le sigma ne devient jamais suffisamment bas (pour permettre la promotion à lui seul). A la place, la promotion devient possible grâce à une « moyenne glissante» (du MMR). Voici une illustration :

Figure 3 : éligibilité à la promotion en fonction de la moyenne glissante

Le MMR est imprévisible. La moyenne glissante cherche à lisser le rapide changement des données dans le temps en évaluant vos progrès sur X parties. Comme nous l’avons estimé au préalable, le système n’utilise pas TOUT l’historique des matchs car s’il le faisait, vous seriez bloqué dans une ligue (le système lisserait votre progression depuis les premiers matchs). Une fois que votre moyenne glissante passe le seuil d’une ligue en particulier, c’est le moment où vous obtiendrez la promotion.

Des joueurs comme CauthonLuck et Ret, qui ont des ratios W/L au plafond, avait leur données MMR au plafond aussi. Mais qu’importe, leur moyenne glissante était à la traîne (si vous gagnez tout le temps, il n’y a pas de courbe de progression, vous stagnez au top :p). Dans le cas de ces joueurs, ça prendra plus longtemps à la moyenne pour atteindre le seuil demandé. C’est la raison pour laquelle des joueurs comme Idra, qui ont été affectés par ce problème ont décidé de perdre volontairement des matchs pour être promu, car ça permet à la moyenne d’augmenter plus vite.

Probablement pour les mêmes raisons, des joueurs ne sont pas promus ou relégués correctement malgré la forte probabilité que leur moyenne ait franchi le seuil de confiance. Blizzard a confirmé qu’il s’agissait d’un bug qui doit être réglé en faisant changer les joueurs de ligue (par eux-mêmes ??).


LE CLASSEMENT VISIBLE (Battle.net)

Voyons, comment tout ça amène au classement battle.net et trucs du genre statut “favori” ? On se rappelle que dans WoW, les changements de classements sont basés sur la comparaison directe de votre classement battle.net à celui du MMR adverse. Donc si votre niveau actuel est de 500 et que vous jouez des gens avec un MMR de 2000, votre classement grimperait fortement après chaque victoire grâce à la différence de niveau. Maintenant, on a pu voir à l’écran de chargement, que des joueurs voient leur adversaire « favori » et que de son côté l’adversaire voit aussi l’autre « favori ». Comment ça se fait ? La théorie dit que le système compare encore votre classement à celui (caché) de votre adversaire. La raison de tout ça est que le système vous amène à votre propre MMR le plus vite possible :

8 Août 2010, kzn explique :
« Voilà comment ça marche. Disons que vous avez un MMR de 2500, vous démarrez un nouveau placement. Ça commence avec un classement à 0, mais le système vous mettra en en face de joueurs au MMR de 2500. Si vous perdez le match, votre classement ne changera pas du tout. Si vous gagnez, il augmentera de beaucoup de points. Ceci s’explique par le fait que le système tente de vous allouer un classement proche de votre MMR le plus vite possible.
Par conséquent, on peut déduire que quand le classement augmente, la valeur cachée du seuil de la ligue visée est additionnée à votre classement battle.net et comparée au MMR de votre adversaire, afin de calculer le gain/la perte de votre classement battle.net.

Exemple :

ExcaliburZ et moi faisons une game. Son MMR est de 2600, son sigma de 100, son classement de 300 (pts). Mon MMR : 2500, sigma : 50, classement : 150 (pt). Le seuil MMR du Diamant est de 2300. ExcaliburZ gagne parce qu’il déchire. Qu’est-ce qu’il se passe ?
_son MMR augmente
_mon MMR diminue
_nos deux sigmas diminuent
_son classement va s’améliorer. Comment? En comparant mon MMR (2500) avec son classement + le seuil MMR Diamant => 2300 + 300 = 2600, son gain est ainsi de 2600 par rapport à mes 2500.
_mon classement va diminuer. De la même manière, son MMR (2600) par rapport à mon classement + le seuil MMR Diamant => 150+2300 = 2450. Donc je perds des points en proportion (2450vs2600).»


CONCLUSION

SC2 utilise un modèle du théorème de Bayes pour sa capacité à déterminer le MMR et le niveau de confiance de chaque joueur. Ils forment un schéma du type Gauss (loi Normale) qui sert à déterminer la probabilité de victoire. La promotion/relégation intervient quand un joueur dépasse/passe sous le seuil de confiance suffisant. Le classement battle.net (visible) évolue en comparant le classement lui-même avec le MMR (caché) et le seuil de la ligue.

Plus de précision avec Vanick :

8 août 2010, Vanick :
« Pour être clair, le niveau du joueur n’est jamais définitif, constant. Le sigma n’est jamais égal à 0. Tous les joueurs réalisent des performances variables de match en match et au fur et à mesure leur niveau augmente (ou diminue).
[…] le ladder SC2 possède un facteur basé, indépendamment du temps, sur votre dernier match qui augmente la valeur sigma du joueur d’un montant directement lié au fait que le niveau de jeu varie. Même si vous jouez des parties les unes derrière les autres, ce facteur gardera une valeur minimum qui fera augmenter le sigma. Ceci permet au système de s’adapter au niveau du joueur en permanence (forme d’élasticité pour adapté au plus juste le MMR malgré les variations du niveau de jeu). »


Traduit de l’article d’Excalibur_Z sur TeamLiquid.net.
http://www.teamliquid.net/forum/viewmessage.php?topic_id=142211
Merci à la team fureur pour les illustrations.

Nous recherchons activement la personne qui à réalisé cette traduction afin de l'a citer comme source.




Aucun commentaire:

Enregistrer un commentaire