Fonctionnement de l'équilibreur d'équipe dans World of Tanks Blitz

WoT Blitz est un tireur de chars mobile dans lequel les joueurs se battent dans un format 7 contre 7.
Un entremetteur, ou équilibreur, est un mécanisme qui, basé sur la composition des joueurs souhaitant entrer dans la bataille, forme la composition des équipes.

Les réservoirs ont les paramètres suivants importants pour le matchmaking:

• Niveau. Selon le niveau, différentes caractéristiques des chars changent (par exemple, la vitesse, la pénétration de l'armure). Au 1er niveau - les chars les plus faibles, au 10e - les plus forts.
  
• Tapez Il existe 4 types de chars dans WoT Blitz: des destroyers légers, moyens, lourds et des chars (artillerie automotrice antichar)
  

La mise en œuvre la plus simple d'un entremetteur consiste à jeter des joueurs au hasard dans des équipes. Mais dans ce cas, les joueurs de bas niveaux n'auront aucune chance de causer au moins quelques dégâts, et cela deviendra inintéressant de jouer.

Prérequis

La liste des exigences pour l'équilibreur a été établie sur la base des commentaires de la communauté des joueurs et est régulièrement mise à jour à ce jour.

Au moment de la rédaction de l'article pour les batailles régulières, la liste comprenait les éléments suivants:


Développer un entremetteur, en particulier compte tenu d'un tel nombre de restrictions, est une tâche très intéressante. Et les approches de sa solution peuvent être très nombreuses.

Balancer formant une paire de joueurs

Initialement, dans les chars mobiles, un équilibreur a été utilisé, qu'il a hérité de son grand frère - les chars de bureau. En général, il a plutôt bien fonctionné, mais il a eu plusieurs problèmes: premièrement, il n'a pas donné de garanties claires pour satisfaire aux exigences; deuxièmement, l'ajout de nouvelles exigences s'est révélé assez difficile.


Début de bataille

Par conséquent, un autre équilibreur a été écrit, qui a fonctionné selon l'algorithme suivant:

• Nous répartissons les joueurs en groupes selon le niveau et le type d'équipement;
• À partir des joueurs résultants, nous formons des paires;
• Nous dispersons des paires pour différentes équipes: prenez chaque paire, jetez le premier joueur dans la première équipe, le second dans la seconde;
• Dans les équipes reçues, nous effectuons le rééquilibrage final: pour satisfaire la plupart des exigences, nous remplaçons certains joueurs d'une équipe par des joueurs d'une autre équipe.

L'équilibreur résultant fonctionnait 5 à 10 fois plus rapidement que la version précédente et réunissait initialement des équipes qui répondaient à toutes les exigences à l'époque. De nouvelles règles ont été ajoutées en écrivant des passes de rééquilibrage supplémentaires.

Au début, tout fonctionnait bien. Mais avec le temps, plus il y avait de règles ajoutées, plus il était difficile d'écrire un rééquilibrage. Le nouveau rééquilibrage ne devrait pas, du fait de ses travaux, rompre le travail des précédents. Il est devenu clair que c'est la route vers nulle part.


Bug dans le matchmaker - une équipe de 9 sur 9 s'est réunie

Équilibreur de recuit simulé

Dans la version finale, nous nous sommes installés sur un équilibreur qui fonctionne selon l'algorithme suivant. Tous les joueurs qui cliquent sur le bouton "To Battle" tombent dans la file d'attente générale. Un équilibreur de boucle sans fin effectue les opérations suivantes:

• Sélectionne les paramètres de bataille aléatoires (niveau de bataille aléatoire (de 1 à 10), mode aléatoire, carte aléatoire);
  
• Trouve dans la file d'attente tous les joueurs qui répondent aux critères sélectionnés ci-dessus (se sont affrontés sur un tank d'un niveau approprié, ont activé le mode sélectionné, ont chargé la carte sélectionnée);
  
• Essayer de former des équipes qui satisfont à toutes les exigences ci-dessus (description ci-dessous);
  
• S'il était possible de former une équipe, jetez ces joueurs hors de la file d'attente et la bataille commence.
  

Pour former des équipes à partir de la liste des joueurs appropriés, la méthode de simulation de recuit est utilisée. En savoir plus sur la méthode elle-même ici .


Rechercher un maximum global en simulant un recuit

Dans le cadre d'application à la formation d'équipes, l'algorithme est le suivant:

• Cela commence avec deux équipes vides;
  
• À chaque itération, il change aléatoirement l'état des commandes. Pour ce faire, effectue l'une des opérations suivantes:
  
  
  • Ajoute un joueur aléatoire de la liste des joueurs appropriés à la première ou à la deuxième équipe (nous prenons également une équipe aléatoire);
    
  • Supprime un joueur aléatoire d'une équipe aléatoire;
    
  • Remplace un joueur aléatoire de la liste des joueurs appropriés par l'un des joueurs existants dans la première ou la deuxième équipe;
    
  • Change un joueur aléatoire de la première équipe en un joueur aléatoire de la deuxième équipe.
    
  
  
• Obtient une estimation de l'état résultant. Pour ce faire, appelle la fonction d'évaluation. La fonction passe par la liste des exigences et pour violation de chaque élément augmente la pénalité. Plus le point est violé, plus la pénalité est élevée. Par exemple, la pénalité pour une équipe 2x2 sera plus élevée que la pénalité pour une équipe 6x6;
  
• En fonction de la variation de la valeur de la fonction estimée et de la température actuelle, nous déterminons la probabilité d'une transition vers un nouvel état;
  
• Nous continuons le processus jusqu'à ce que la température atteigne le minimum défini ou que la valeur de la fonction d'évaluation atteigne zéro (dans ce cas, toutes les exigences sont satisfaites et la bataille peut être lancée).
  

Le principal avantage de cette approche: pour ajouter de nouvelles exigences, il suffit de modifier la fonction d'évaluation. Il n'est pas nécessaire d'écrire du code qui décrira comment obtenir exactement ce que nous voulons. Ajoutez simplement une règle qui regarde l'équipe formée et indique si elle est bien équilibrée ou non.

Un bon exemple de l'ajout de telles règles est le classement des batailles. Dans les batailles de classement dans le matchmaker, plusieurs nouvelles règles sont apparues à la fois:

• Les équipes doivent être équilibrées en termes de notation (la différence dans la note totale des joueurs entre les équipes ne doit pas dépasser une valeur donnée);
  
• La différence de classement entre les joueurs doit être minime (les joueurs de la ligue de bronze ne doivent pas se battre avec les joueurs du diamant).
  

Exemple de profil de joueur Diamond League

La première règle est mise en œuvre en modifiant la fonction d'évaluation: une pénalité a été ajoutée pour avoir dépassé la différence maximale autorisée dans la note. La deuxième règle est implémentée en modifiant la fonction qui extrait les joueurs appropriés de la file d'attente.

L'inconvénient de cette approche est la vitesse lente. Par rapport à la version précédente, la version actuelle a commencé à fonctionner environ 10 fois plus lentement, malgré un certain nombre d'optimisations. Soit dit en passant, sur l'optimisation. La plupart du serveur (sauf réseau et physique) du jeu est écrit en Python. L'équilibreur a été réécrit en C ++ et mis en parallèle avec de nombreux threads. De Python, une demande pour former une commande arrive dans le code plus. En outre, chacun des flux démarre indépendamment le procédé de recuit. Dès qu'un thread trouve une solution, le reste des threads arrête le processus de recherche et la solution trouvée est renvoyée à Python.


Temps d'attente et taille de la file d'attente sur le serveur RU (5 secondes dans les batailles normales et 10 dans les batailles de classement)

À mesure que la croissance en ligne augmentait, la charge pesait également sur l'équilibreur. Cet automne, lorsque le serveur en ligne sur le serveur RU a atteint 120 000 (lors de l'événement Mad Games), l'équilibreur a cessé de faire face. À titre temporaire, nous avons désactivé certaines règles, ce qui nous a permis de réduire la charge. Pour éviter de tels problèmes à l'avenir, nous avons distribué le matchmaker.

Système de notation

Les meilleurs joueurs de la ligue des diamants, 21 avril 2019

Dans de nombreux jeux MMO, en plus des combats aléatoires, il existe également des notes / classements / etc. L'idée principale de ce mode: les adversaires ne sont pas recherchés au hasard, mais adaptés en compétence. Si vous êtes un joueur de compétence, vous jouerez avec les mêmes joueurs de compétence, et vice versa, si vous ne savez pas jouer, vous rencontrerez les mêmes nouveaux venus.

Au début de la saison, le joueur passe par une série de combats de calibrage, dont les résultats déterminent sa position de départ. Ensuite, selon le succès du jeu, le joueur monte ou descend dans le classement. Le système de notation de Blitz a été créé, tout d'abord, pour un bon équilibre. Il est affiné sur l'habileté des joueurs et est pratiquement indépendant du nombre de parties jouées.

Pour mettre en œuvre les batailles de classement, il fallait résoudre deux problèmes à la fois. Premièrement, il a fallu choisir un système de notation (selon quel principe les joueurs devraient être notés). Deuxièmement, il était nécessaire d'affiner l'équilibreur afin qu'il recueille les combats en tenant compte des restrictions de notation.

La principale exigence du système de notation est la capacité de déterminer avec précision le niveau du joueur. Afin d'évaluer la précision de fonctionnement de l'un ou l'autre système de notation, un simulateur a été créé, à l'entrée duquel l'historique des batailles et le système de notation sélectionné ont été soumis, et la sortie a été la précision du système.

La précision a été calculée comme suit:

• Tous les joueurs ont reçu une note de départ;
  
• Sur la base des résultats de chacune des batailles, la note des joueurs participant à cette bataille a été recalculée selon le système sélectionné;
  
• Avant chaque bataille, le système tentait de prédire quelle équipe gagnerait;
  
• En conséquence, le pourcentage de batailles pour lesquelles le système a donné la bonne prédiction a été calculé.
  

Les systèmes de calcul de notation les plus populaires: winrate, Elo , Glicko , TrueSkill . Le taux de victoire est le pourcentage habituel de victoires. Elo est un système de notation, créé à l'origine pour les jeux à deux (échecs, etc.). Dans ce système, un joueur se voit attribuer / retirer un certain nombre de points pour gagner / perdre, en fonction de la cote de l'adversaire. Glicko est généralement similaire à Elo, mais prend également en compte la durée d'inactivité du joueur. TrueSkill est un système de classement propriétaire de Microsoft, dans lequel chaque joueur a deux paramètres: le classement et la confiance du système dans ce classement.

Lors du développement de la première version des batailles de classement, nous avons considéré le taux de victoire et Elo (plusieurs options adaptées pour un jeu d'équipe), ainsi qu'un système de score simple (dans lequel les joueurs recevaient toujours un nombre fixe de points de classement pour la victoire et étaient emmenés pour la défaite).



Les meilleurs résultats ont été montrés par le système Elo, dans lequel Ra est la note du joueur et Rb est la différence entre la note totale de l'équipe adverse et la note totale de l'équipe du joueur, à l'exception du joueur lui-même.

Les principales difficultés rencontrées après le lancement:

• trop de variation dans le classement entre les joueurs;
  
• la vitesse mal prévisible à laquelle les joueurs marquent (atteindre la ligue).
  

Le premier problème n'a pas pu être complètement résolu car il y a trop peu de joueurs talentueux, ils doivent attendre longtemps avant le début de la bataille, et très souvent ils voient les joueurs de leurs équipes plus faibles. Pour atténuer l'effet, nous avons rendu les batailles de classement disponibles uniquement aux heures de grande écoute (c'est-à-dire à un moment où le nombre maximum de personnes jouait sur les serveurs).

Nous avons résolu le deuxième problème en introduisant un facteur de ralentissement (c'est-à-dire que plus le joueur est éloigné de la note moyenne, plus il lui est difficile de monter ou de descendre en dessous).

Nous avons également essayé de différentes manières d'améliorer la qualité du système de notation. Dans les premières versions, pour changer le classement, nous avons utilisé uniquement des informations sur la victoire / la défaite. Mais nous avons un jeu d'équipe, et pas toujours les bonnes actions d'un joueur spécifique mènent à la victoire de toute l'équipe. Autrement dit, même si le joueur a bien joué et que l'équipe a perdu, ce joueur a reçu le même moins au classement que tous les autres joueurs. Pour éviter cela, nous avons commencé à essayer de prendre en compte les actions individuelles du joueur au combat.

À ces fins, nous avons essayé d'utiliser l'apprentissage automatique: nous avons collecté divers facteurs et essayé de former le modèle pour prédire la victoire / la défaite de l'équipe en fonction des actions du joueur dans la bataille, puis d'utiliser ce modèle pour déterminer le coefficient de bonus de notation (c'est-à-dire, si l'équipe a perdu, mais le comportement du joueur était similaire sur le comportement des joueurs gagnants, donnez à ces joueurs un bonus supplémentaire).


Le joueur de l'équipe gagnante qui a bien joué a reçu une note de +40. Et ce qui est mauvais seulement +10

Nous avons pu construire un bon modèle qui a donné des résultats bien meilleurs que le modèle actuel, mais il y avait une difficulté (qui gâche souvent tout dans les problèmes d'apprentissage automatique). Le modèle était bon, mais il comportait parfois des erreurs clairement visibles par les gens. Il y avait périodiquement des situations où un joueur qui, du point de vue d'une personne montrait de bons résultats, recevait un faible bonus du point de vue du modèle, et vice versa.

En conséquence, nous avons abandonné le modèle ML et pris une formule manuelle plus simple. Cette formule ne prend en compte que l'expérience de combat sans tenir compte des bonus de victoire, x2 et autres. Il donne un résultat très décent, bien qu'il soit légèrement inférieur à celui du modèle ML.

Conclusion

• Un équilibreur basé sur une méthode de simulation de recuit nous a permis de passer d'une description de la solution (comment assembler l'équipe) à une description des exigences (quelles conditions ne doivent pas être violées);
  
• Dans les batailles de classement par équipes, le système Elo modifié s'est bien montré, prenant en compte les actions individuelles du joueur dans la bataille;
  
• Il n'est pas toujours utile d'utiliser des méthodes complexes d'apprentissage automatique (en particulier lorsque l'interprétabilité et l'intelligibilité du résultat par une personne sont importantes).
  

Nous continuons à développer et à améliorer l'équilibreur. Nous avons presque vaincu l'impression négative de déséquilibre de classe. Les principaux problèmes auxquels nos joueurs prêtent attention sont le déséquilibre des compétences, la turbulence et les joueurs afk. C'est un défi sérieux, nous continuons à travailler sur un équilibreur dans ces domaines.

Si vous avez des questions / suggestions sur un équilibreur dans WoT Blitz, désabonnez-vous dans les commentaires (ou sur notre forum ).