- SpawELO a été créé pour automatiser la sélection des équipes lors d’une LAN party organisée depuis 16 ans entre amis, où choisir manuellement les équipes de Dota 2 devenait de plus en plus difficile
- En raison des écarts de niveau et d’une participation fluctuante, le draft manuel produisait souvent des équipes similaires à répétition et des déséquilibres lorsqu’il y avait un nombre impair de joueurs
- La première implémentation utilisait 35 matchs passés et des scores Elo pour trouver la combinaison dont les scores cumulés par équipe étaient les plus proches, puis ajustait les scores en réinjectant les résultats des matchs
- Après le passage à un modèle de prédiction du taux de victoire, les Elo des joueurs ont été ajustés avec une perte L2 et la rétropropagation, mais le fait de traiter chaque victoire comme un résultat à 100 % a entraîné un surapprentissage qui mémorisait les matchs passés
- La méthode finale traite les résultats des matchs comme des victoires probabilistes à 75 % ou 95 % afin de réduire le surapprentissage, avec pour objectif un appariement d’équipes utilisable même avec un nombre impair de joueurs, par exemple en 4v5
Le problème de sélection des équipes révélé par les LAN parties
- Le groupe d’amis organise au moins une LAN party par an depuis 16 ans ; elle dure généralement 4 à 5 jours et réunit environ 12 participants aux heures de pointe
- Le jeu principal est Dota 2, mais ils jouent aussi à Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 et Blobby Volley
- Les participants n’arrivent pas et ne repartent pas tous au même moment, et certains doivent s’absenter pour s’occuper de leurs enfants ; les parties ne se jouent donc pas toujours avec les mêmes personnes
- Dota 2 se joue généralement en 5v5 et une partie dure environ 40 minutes ; les matchs déséquilibrés comme un 4v5 ont facilement tendance à pencher d’un côté
- Le groupe mélange des personnes qui jouent régulièrement à Dota 2 et d’autres qui n’y jouent que pendant la LAN party, ce qui crée de grands écarts de niveau
Les limites du draft manuel
- La méthode existante consistait généralement à désigner comme capitaines les deux meilleurs joueurs, ou les deux moins expérimentés, puis à choisir les coéquipiers à tour de rôle comme dans une cour d’école
- L’ordre de sélection était le suivant : le premier capitaine choisissait 1 joueur, le second en choisissait 2, le premier en reprenait 2, puis chacun des capitaines choisissait 1 dernier joueur
- C’est une variante destinée à réduire l’avantage du premier choix
- Comme les écarts de niveau étaient importants, on obtenait souvent des équipes similaires, voire identiques, et le plaisir de drafter diminuait à chaque fois
- La sélection manuelle des équipes prenait du temps, était fastidieuse, et personne ne voulait vraiment être capitaine
- Quand le nombre de joueurs ne tombait pas juste, le déséquilibre des équipes devenait particulièrement marqué
Première implémentation : matchs passés et somme des Elo
- Lors de la dernière LAN party, les frustrations autour de la sélection des équipes ayant augmenté, du code d’automatisation a été écrit rapidement
- D’abord, 35 matchs passés ont été rassemblés dans Colab ; chaque match contenait la liste des joueurs de l’équipe gagnante et de l’équipe perdante
- L’idée de base consistait à calculer les scores des joueurs avec le classement Elo
- Tous les joueurs commencent à 1000 points
- Une victoire fait gagner des points, une défaite en fait perdre
- La probabilité de victoire est calculée uniquement à partir de l’écart d’Elo entre deux joueurs
- La première implémentation simple ajoutait 20 points aux joueurs gagnants et retirait 20 points aux joueurs perdants
- La composition des équipes était générée en examinant toutes les combinaisons possibles parmi les joueurs demandés, puis en choisissant celle qui minimisait l’écart entre les sommes d’Elo des équipes
- Dans l’exemple, 8 personnes étaient réparties en deux équipes : l’une était calculée à 4100 points, l’autre à 4080
Amélioration du modèle Elo par calculs itératifs
- Parcourir une seule fois les 35 matchs a été jugé insuffisant pour exploiter les données ; les données historiques ont donc été traitées plusieurs fois de suite
- La mise à jour Elo améliorée n’applique pas simplement ±20 points : elle attribue davantage de points quand on bat un adversaire plus fort, et en retire moins quand on perd contre plus fort
- Par exemple, si Spawek, à 1260 points, bat Goovie, à 900 points, il ne gagne que 4,47 points
- Si Status, à 900 points, bat Dragon, à 1100 points, il gagne 30,38 points
- Comme le calcul se faisait au niveau des équipes plutôt qu’en un contre un, la somme des Elo de l’équipe gagnante et de l’équipe perdante était utilisée, puis la mise à jour du score était répartie équitablement entre les membres de l’équipe
- Cette approche a aussi été utilisée pendant la LAN party : après chaque partie, les nouvelles données étaient ajoutées pour recréer des équipes pour le reste de l’événement
- Lorsqu’un match manifestement déséquilibré était généré, un « faux match » indiquant le vainqueur attendu était parfois ajouté aux données, puis les équipes étaient générées à nouveau
Deuxième amélioration : passer à un modèle de prédiction du taux de victoire
- L’amélioration suivante consistait à traiter l’Elo non comme une simple table de scores, mais comme un modèle prédisant la probabilité de victoire d’une équipe
- Le modèle stocke l’Elo de chaque joueur et calcule la probabilité de victoire en comparant les
SUM(Elo)des deux équipes - Une simple perte L2 est appliquée à l’ensemble des données de matchs
- Calcul de la somme des Elo de l’équipe gagnante et de l’équipe perdante
- Calcul de la probabilité de victoire
- Ajout à la perte du carré de l’écart entre la probabilité réelle et la probabilité prédite
- L’apprentissage utilise la rétropropagation
- Le passage avant calcule le taux de victoire prédit
- Les dérivées de la perte et de la fonction de probabilité de victoire servent à calculer l’effet de l’Elo de chaque joueur sur la perte
- Les valeurs d’Elo sont mises à jour avec
LEARNING_RATE = 10_000.0etITERATIONS = 10001
- Cette approche a réussi à réduire la perte, mais les valeurs d’Elo n’ont pas convergé
Des résultats de match probabilistes pour réduire le surapprentissage
- Le modèle de type ML a surappris parce qu’il traitait le taux de victoire réel de tous les matchs passés comme 1,0, c’est-à-dire comme une victoire à 100 %
- En mémorisant chaque match au lieu de généraliser, le modèle produisait pour certains matchs des probabilités prédites presque égales à 1, comme 0.999994567526197
- L’objectif n’étant pas d’encoder tels quels les résultats passés, mais de constituer de bonnes équipes, le système a été modifié pour utiliser des résultats probabilistes plutôt que des victoires ou défaites certaines
- Les anciens enregistrements de matchs ont été réexaminés pour classer leur nature en deux catégories
- Pour les matchs serrés, la probabilité réelle de victoire de l’équipe gagnante a été fixée à 75 %
- Pour les matchs clairement à sens unique, la probabilité réelle de victoire de l’équipe gagnante a été fixée à 95 %
- Comme l’écart d’Elo nécessaire pour une probabilité de victoire de 75 % est d’environ 200 points, tandis que celui nécessaire pour 100 % se situe entre environ 500 points et l’infini, il devient plus difficile pour le modèle de mémoriser tous les matchs
- Après avoir remplacé
real_probability = 1parreal_probability = game["win_probability"]dans les fonctionslossetbackpropagation, la perte a rapidement diminué et les Elo des joueurs ont convergé vers des niveaux raisonnables
Des lineups même avec un nombre impair de joueurs
- Le nouveau système peut prédire les probabilités de victoire et créer des équipes même avec un nombre impair de joueurs
- Voici un exemple de premier lineup pour la LAN party qui commence dans deux semaines
- team 1: Elo 2660
- team 2: Elo 2655
- Cet exemple de lineup place 4 joueurs d’un côté et 5 de l’autre
- team 1: Spawek, Bixkog, Bania, Goovie
- team 2: Hypys, Muhah, J, Vifon, Status
1 commentaires
Commentaires sur Hacker News
Je me demande si certains ont déjà essayé, pour des jeux en équipe, des approches qui ne reposent pas sur Elo/TrueSkill.
Additionner ou moyenner l’Elo d’une équipe pour faire du matchmaking donne l’impression d’un bricolage qui force un modèle conçu pour le matchmaking individuel à s’appliquer au matchmaking par équipes.
On perd aussi beaucoup d’informations sur les affinités internes à l’équipe : A et B ensemble peuvent être plus forts que la somme de leurs Elo individuels, tandis que A et C ensemble peuvent être plus faibles.
Dans le sport, une équipe peut perdre et tout de même avoir un All-Star ou un MVP en fin de saison ; inversement, on peut appartenir à l’équipe championne sans en être un élément central.
Dans l’e-sport par équipes, tout repose sur la victoire, si bien que l’expression des joueurs de tout premier plan de la ligue — défenseurs, attaquants, supports — est mal suivie ou reconnue.
Il faudrait suivre et intégrer, dans une certaine mesure, des statistiques avancées, comme dans plusieurs sports. Un joueur n’est pas l’Elo lui-même, il ressemble davantage à des valeurs comme les passes décisives, rebonds, points par match, points produits ou yards.
On verrait alors plus facilement si une équipe a davantage besoin de scoring ou de défense, et le matchmaking pourrait s’ajuster plus naturellement que par un simple « il faut plus de gagnants/perdants ».
La force d’Elo, c’est la quantité d’information obtenue pour son coût. L’idée centrale est d’avoir un seul nombre qui représente tout.
Cela n’explique pas parfaitement la belle diversité de la nature, mais c’est proche de l’abstraction la plus efficace pour capturer 70 % de ce qu’il faut savoir sur le niveau de l’adversaire.
J’aimerais voir des vecteurs multidimensionnels de compétence des joueurs, ou des embeddings, qui contiennent plus d’informations, avec par-dessus des modèles plus non linéaires.
Par exemple, dans beaucoup de jeux, une équipe a généralement besoin d’un joueur support, mais un seul nombre ne suffit pas à faire entrer cette information dans le matchmaking.
Par exemple, au baby-foot, certains joueurs pratiquent à la fois le simple et le double, et deux excellents défenseurs mis ensemble peuvent perdre contre des adversaires plus faibles mais mieux adaptés à chaque poste.
C’est encore différent dans Counter-Strike, Apex, Overwatch, et dans une certaine mesure Dota, où l’équipe peut beaucoup soutenir un joueur. Dans Counter-Strike, un coéquipier faible, ou sans casque, peut ruiner toute la partie, tandis que dans Overwatch il peut choisir une classe support, rester en retrait tranquillement et attendre que le reste de l’équipe gagne.
Il y a aussi la chimie. Comme on le voit au travail, des synergies qui n’apparaissent que dans certaines combinaisons, ou de simples différences de style de jeu, peuvent changer le résultat.
Même dans des variantes de billard qui se ressemblent, certains joueurs brillent dans une discipline mais s’en sortent mal dans une autre.
Il me semble qu’il y a eu, ou qu’il y a encore, une compétition Kaggle sur les systèmes de classement.
https://www.kaggle.com/competitions/chess/discussion/107
Il existe pas mal de systèmes de classement plus performants qu’Elo.
Pour les tournois, j’aime bien le système suisse, que je crois populaire aux échecs.
[1]: https://en.wikipedia.org/wiki/Swiss-system_tournament
Avec le système suisse, sur 6 rondes, un maximum d’environ 40 personnes est raisonnable ; si l’on veut inviter plus de 100 personnes, il faut utiliser un tableau à double élimination. Sinon, le tournoi dure une semaine.
Le meilleur point, c’est le bon rapport valeur/coût. Quel que soit le résultat, on continue à jouer pendant tout le tournoi, et au fil des rondes les adversaires se rapprochent de son niveau, donc tout le monde peut s’amuser.
Je ne sais pas très bien comment décider du nombre de rondes nécessaires, ni si ce détail est vraiment essentiel.
D’après la partie analyse, par rapport à un tournoi à élimination directe, et en supposant qu’il n’y ait pas de match nul, le nombre de rondes nécessaires pour désigner un vainqueur clair est le même que dans un tournoi à élimination.
Le système suisse a l’avantage de n’éliminer personne, et le classement final reflète dans une certaine mesure le niveau relatif de l’ensemble des participants, pas seulement celui du vainqueur.
En revanche, si un joueur prend une trop grande avance, la victoire peut déjà être acquise avant la dernière ronde, donc la fin n’est pas toujours dramatique.
Je me demande ce que donnerait une tentative avec les valeurs de Shapley.
C’est presque mot pour mot l’introduction de Wikipedia, mais même après l’avoir lue, je ne comprends pas bien. Je me demande ce que représente ici le surplus total d’un jeu coopératif : par exemple la quantité de bois collectée par une équipe dans AoE ?
Je ne vois pas non plus en quoi le fait de le « répartir » aide ; j’aurais plutôt tendance à penser que cela devrait être le résultat du jeu. Ce serait bien si quelqu’un pouvait l’expliquer simplement.