Elo, qui est le meilleur ?
Rédaction Blog
Il y a 4 ans
Learning Innovation
Savez-vous qui est cette personne et comment elle a réussi ?
C’est Mark Zuckerberg, le co-fondateur et CEO de Facebook. Le film de David Fincher, The Social Network, nous montre son ascension fulgurante, d’étudiant à Harvard à la création du réseau social le plus utilisé du monde. Zuckerberg nous est décrit dans le film comme une personne n’ayant pas d’affection particulière pour les gens et les filles en général. Avant Facebook, l’une de ses premières idées sera de créer Facemash, un système de classement des filles d’Harvard, dont il a récupéré toutes les photos.
©The Social Network
Dans le film, nous le voyons demander l’algorithme pour faire ce “tri”. Son associé, Eduardo Saverin, lui montre alors la formule, sur une vitre, à utiliser dans son algorithme de tri de la population féminine d’Harvard. On y voit alors une formule, un peu floue, derrière laquelle se cachera la méthode de calcul de Facemash.
©The Social Network
Savez-vous ce qu’elle représente ? C’est la méthode de classement Elo, qui permet d’attribuer à chaque joueur un rang, un score. Elle est utilisée dans les jeux en un-contre-un, en particulier aux échecs. Nous allons voir dans cet article comment cette méthode fonctionne, ce qu’il se cache derrière la formule, et comment cette méthode de classement pourrait être utilisée chez Coorpacademy.
TL;DR
ELO est un système de classement qui tend à ordonner un ensemble dans le temps. Plus le temps passe, plus l’ensemble est correctement ordonné. Le principe est de prédire le résultat d’une rencontre entre deux joueurs et de réaliser cette rencontre. Si la prédiction ne correspond pas à la réalité, on procède à un ajustement des scores des deux parties. Et on répète l’opération.
Comment ça marche ?
Prenons un classement existant de jeu d’échecs. Tous les joueurs ont déjà un score qui représente une estimation de leur niveau, c’est ce qu’on appelle la cote. Si un nouveau joueur veut rentrer, il lui faut une cote initiale. Aux échecs, elle est de 1200.
©The Social Network
Sur le schéma suivant, nous avons deux personnes, qui n’ont jamais joué l’une contre l’autre. Une personne est à 1200, une autre à 1600. Avec le calcul de la formule Elo que nous voyons dans le film The Social Network, nous pouvons calculer la chance de victoire de quelqu’un par rapport à un autre.
En appliquant la formule ci-dessus, nous avons calculé une probabilité de victoire.
Là, nous savons que la personne avec 1200 points a 10 % de chances de gagner, quand l’autre personne (avec 1600 points), en a 90 %.
Ensuite, nous comparons ce qui a été prédit et ce qui a réellement eu lieu lors de l’affrontement entre les deux joueurs.
Par exemple, dans le premier schéma, le joueur violet a gagné alors qu’il n’avait que 10 % de chances de gagner. Il gagne 27 points, quand l’autre en perd 27. Le score des deux joueurs s’ajuste. Finalement, quand deux personnes s’affrontent plusieurs fois, si chacun gagne la moitié des parties, ils vont avoir exactement le même score, cela va s’équilibrer. S’il y en a un qui est beaucoup plus fort, il va être au-dessus de lui en termes de score, mais son score va stagner au bout d’un moment (nous le verrons plus tard dans l’article).
Dans ce cas-là, c’est celui qui avait peu de chances de gagner qui gagne, donc qui remporte beaucoup de points (27).
Dans le deuxième schéma, s’il perd, et c’est quelque chose qui avait été “prévu” à 90 %, il ne va perdre que 3 points. La probabilité de victoire influe sur le score et le gain de points final.
Dans Facemash, l’idée de Zuckerberg représentée dans le film était de comparer les filles d’Harvard entre elles selon un degré de beauté. Si une fille est considérée comme “jolie” en affronte une autre considérée comme beaucoup moins “jolie”, et qu’elle gagne, c’était déjà prévu par la formule et son score va donc peu changer. Elle ne va pas beaucoup évoluer dans le classement. Si une fille considérée comme très “jolie” perd contre une fille considérée comme beaucoup moins “jolie”, les classements vont beaucoup évoluer. Cela aura été considéré comme une anomalie, et l’algorithme va donc tenter de rééquilibrer les forces, faire évoluer les personnes dans le classement pour tenter de “réparer l’anomalie”.
La formule écrite sur la vitre, dans le film, nous dit comment calculer cet Expected, la probabilité de victoire ou de défaite.
Dans le cadre d’un jeu d’échecs, cela donne les formules suivantes. R étant le score actuel, E l’Expected, la probabilité de victoire ou de défaite.
Globalement, cette méthode de calcul montre qu’en évoluant avec des gens de son niveau, voire sensiblement meilleurs – contre qui il est donc moins probable de gagner, nous évoluons beaucoup plus que lorsque nous jouons contre des adversaires beaucoup plus faibles. Cela se reflète sur le nombre de points gagnés, ou perdus, après chaque partie.
Il y a aussi une valeur d’ajustement – qui définit la fourchette de gain ou de perte et qui est prise arbitrairement (K dans le schéma). Dans l’exemple précédent et le duel entre bonhommes vert et violet, le K est de 30. 27 points gagnés est donc quasiment le maximum de points que l’on peut gagner, et cela se reflète par les probabilités qui étaient au départ, de 10 % de chances de gagner pour la personne qui a effectivement gagné. Aux échecs, et dans beaucoup d’autres systèmes, K varie. Les premières parties d’un joueur utilise un K élevé de 40 pour positionner rapidement le joueur vers des scores de son niveau. Ensuite il diminue à 20 pour limiter les fluctuations.
C’est la théorie. Quand on l’applique sur une grande population et que nous les faisons s’affronter beaucoup (au départ, ils ont tous le même niveau, le même nombre de points), on va retrouver une répartition naturelle de toutes ces personnes sous la forme d’une répartition en cloche (ou d’une courbe d’une fonction “normale”). Les gens qui ont le même niveau vont se regrouper naturellement. Les personnes très fortes ne peuvent pas évoluer à l’infini, auront moins de potentiels adversaires, et il est très dur de s’éloigner de la cloche du milieu.
Tout le monde va être attiré par le centre de la cloche. Même les personnes extrêmement fortes et celles extrêmements faibles ne pourront s’éloigner trop loin. Ce qui permet ensuite de répartir la population de la manière suivante :
Aux échecs par exemple, seuls 13 joueurs ont dépassé le score de 2800. Aujourd’hui, le plus haut classement Elo de l’Histoire des échecs est détenu par le champion du monde, le Norvégien Magnus Carlsen avec 2889, 2 points devant le légendaire Garry Kasparov.
On ne peut pas gagner des points de manière illimitée, aussi puisque les probabilités de gagner, quand on est le meilleur joueur d’échecs au monde, tendent vers 100 %. Les joueurs sont attirés par le milieu de la cloche, ce qui permet ensuite de créer des “clusters” de population en fonction du niveau.
En découpant cette courbe, on peut donc regrouper des personnes qui ont approximativement le même niveau et donc les faire s’affronter entre elles.
Beaucoup de jeux mettent cette technique en place, car elle est simple, et crée automatiquement des ligues de joueurs de niveaux similaires. Comme dans cet exemple que nous retrouvons souvent dans les jeux tels que Counter Strike, Age of Empires ou League of Legends.
Les possibilités chez Coorpacademy ?
La question se pose d’utiliser cette méthode de classement pour notre système de “Battles”, quand deux joueurs s’affrontent sur un cours particulier et doivent répondre le plus rapidement et le plus justement possible à une courte série de questions sur ce cours Nous avons déjà eu des retours d’apprenants qui hésitent à répondre à des demandes de Battles parce qu’ils ont peur que certains joueurs soient beaucoup plus forts qu’eux. C’est une réaction classique dans des jeux en mode multijoueurs, où existe toujours cette frustration de “est-ce que je vais me faire écraser ou non ?”
Chez Coorpacademy, un système comme Elo pourrait réduire cette appréhension et rassurer les apprenants.
Ainsi, constituer un système de matchmaking avec cette méthode précise permettrait à des personnes fortes en digital, ou en management, par exemple, d’affronter en Battle des personnes de leur niveau dans les mêmes compétences. Nous avons choisi pour l’instant le hasard comme un élément fondamental des Battles, mais avec notre nouvelle fonctionnalité de la Massive Battle qui permet de défier toute une population d‘apprenants simultanément, chaque apprenant a un adversaire avec un niveau prédéfini. Nous vous en parlerons très prochainement !
Pour aller plus loin.
Microsoft’s TrueSkill (un système Elo amélioré développé par Microsoft pour Halo et les jeux multijoueurs en équipe, et non seulement en un contre un).
Arthur est Software Architect chez Coorpacademy depuis maintenant 5 ans. Tous les mois, il anime les lundis matins la Tekacademy, qui rassemble l’équipe développement de Coorpacademy autour de sujets liés à des innovations techniques. Le classement Elo avait été présenté en Février à l’équipe Produit.
