Classements d'IA : quelques expériences avec TrueSkill
Manwe
Entre
tron et game of drones, j'avais commencé a regarder plus en détail
l'implémentation de trueskill qui calcule le fameux "score"
de nos IA. Je voulais plus particulièrement voir l'influence du
nombre de matchs joués, l'influence de remettre une IA dans le
leaderboard alors que les autres sont déja classées
etc.
TrueSkill
Si
je ne me trompe pas, c'est TrueSkill qui a été utilisé pour
classer les IA sur tron et game of drones. TrueSkill est un outil
développé chez Microsoft qui est utilisé pour classer les joueurs
du XBox live. Ils ont publiés les formules, et pour ceux que ça
intéresse, vous aurez les détails mathématiques ici
: http://www.moserware.com/2010/03/computing-your-skill.html.
Si
vous voulez jouer avec, vous trouverez une implémentation en python
ici : http://trueskill.org/
TrueSkill
permet en particulier de classer des joueurs lors de rencontres où
il y a un nombre d'équipes variés, ou le résultat peut avoir des
égalités, où le nombre de joueur dans chaque équipe peut être
différent, et même avec la possibilité pour un joueur de ne pas
faire toute la rencontre et d'avoir donc une contribution partielle.
Il permet donc de classer des joueurs sur des jeux très
variés.
Si
on résume, chaque joueur possède seulement deux variables : mu et
sigma. mu est l'évaluation de son niveau actuel, et sigma la
confiance qu'on a dans ce niveau. Un nouveau joueur commence
traditionnellement avec un mu à 25, et un Sigma à 25/3. Le score
d'un joueur est ensuite calculé en faisant mu-(3*sigma). C'est ce
qu'on voit afficher dans le leaderboard. Un nouveau joueur commence
donc avec un score de zero. Après chaque rencontre, on donne a
trueskill les valeurs de mu et sigma des joueurs qui se sont
affrontés, ainsi que le résultat de la rencontre. Il nous redonne
alors les nouvelles valeurs de mu et sigma de chacun. On peut donc en
déduire leur nouveau score.
Expérience
1
Ca
me semblais trop complexe d'estimer le niveau réel d'IA sur un jeu
simple, j'ai donc pris le parti de fixer le niveau des joueurs
(niveau réel), et de les faires jouer a un jeu dont le résultat est
défini en fonction de ce niveau afin de faire classer trueSkill ces
joueurs. Il n'y a donc aucun jeu derrière ces tests, mais ils
permettent par contre de voir l'influence de certaines
caractéristiques sur le résultat final d'un leaderboard.
Les
premiers tests que j'ai fait sont de considérer que l'IA qui a le
niveau réel le plus fort l'emporte toujours. J'ai donc pris 10
joueurs, P0 à P9, P9 étant le plus fort. P9 gagnera donc toujours
tous ses matchs, P8 gagnera contre tout le monde sauf P9, P0 perdra
toujours etc. Il faut ensuite choisir les matchs à jouer. J'ai donc
choisi de faire jouer en priorité le joueur qui avait fait le moins
de matchs. Ses adversaires sont alors pris aléatoirement en fonction
de leur score trueskill au moment de choisir le match avec un écart
de classement de +/- 5 places (donc le dernier joue seulement contre
les 5 derniers, le premier contre les 5 premiers, le 4e contre tout
le monde sauf le dernier etc). Cette stratégie permet de garantir un
nombre de match équitable à chaque IA, et dans les cas réels,
garantie aussi que le match est intéressant (il n'y a pas grand
intérêt a faire jouer le premier contre le dernier...)
En
faisant jouer 1000 matchs à chaque IA, j'obtiens alors les courbes
suivantes pour le score de chaque joueur:
Plutôt
pas mal non :) ?
Experience
2
Mais
bon dans la vrai vie, le premier ne gagne pas toujours, le dernier ne
perds pas toujours (si si, même ceux qui crashent toujours crashent
moins vite si ils ne crashent pas en premier :) ). Je me suis donc
dis qu'il serais bien d'ajouter un peu d'aléatoire sur les résultats
des matchs, tout en conservant une plus grande probabilité de
victoire pour le meilleur.
Si
on a deux joueurs avec des niveaux j1 et j2, J'ai choisi (et c'est
très certainement perfectible) que:
la
probabilité que j1 gagne seras:j1/(j1+j2)
la
probabilité que j2 gagne seras:j2/(j1+j2)
Si
on prends des exemples numériques avec j1=5 et j2=9, ça donne:
j1
gagne dans 5/14, et j2 gagne dans 9/14
Si
on a j1=1, j2=9, alors j1 gagne 1 fois sur 10 etc
En
faisant jouer 1000 matchs par IA, on obtiens alors les courbes
suivantes pour les scores de chaque joueur:
Gasp...
C'est loin de se stabiliser lorsque les niveaux des bots sont très
proches même malgré une augmentation du nombre de match.
En
fait c'est tout a fait logique : TrueSkill s’attend a une
probabilité de victoire en fonction du sigma et du mu de chaque
joueur. Or lorsqu'il fait le réajustement, progressivement, plus les
matchs sont éloignés, moins ils comptent dans le score final. L'IA
est donc classé par rapport a ses derniers matchs (difficile
d'évaluer un nombre exact). TrueSkill étant utilisé sur des
humains, c'est fiable dans le sens ou le niveau de chaque joueur
varie avec le temps, et il est donc normal que les résultats des
matchs anciens soient progressivement oubliés.
Cependant
nous ici quand on classe des programmes, tous les matchs ont la même
valeur.
Comment
on pourrais changer ça? Simplement en faisant la moyenne des
estimations trueskill : les matchs passés sont certes
progressivement oubliés pour établir le skill courant, mais
continuent d'être comptabilisés pour le skill final. Si on reprends
le chart précédent et qu'on fait la moyenne de tous les scores
calculés lors des itérations précédentes, on obtiens ça:
A
partir de 200/300 matchs par IA, non seulement on a les IA dans le
bon ordre, mais en plus, ça deviens très stable! Il n'y a plus de
variations de dernière minutes si frustrantes pour nos nerfs
:)
Expérience
3
Souvent
on a été frustré de devoir attendre que son IA remonte dans le
classement avant de voir si elle s’améliorait ou non. Qu'est ce
que ça donnerais si on ne remettais pas a 0 l’évaluation
trueSkill de notre bot? Imaginons que j'améliore mon bot: l'IA 7 a
fait une super mise a jour, et est donc maintenant la plus forte avec
un skill de 11:
On
observe bien une progression de l'IA, qui en une centaine de matchs a
pris sa position dans les meilleurs.
Ne
serait t'il pas préférable de faire un reset de l'IA lors de la
remise dans l'arène, et lui faire jouer beaucoup de matchs (c'est
comme ça qu'on était évalué sur tron et game of thrones)? Si je
fait un reset du skill d'une IA après que chacune en ais joué 500,
puis que je la remet dans l'arène pour 500 matchs où elle participe
à tous les matchs, ça donne ça:
L'IA
reviens rapidement autour de son classement réel si elle a
suffisament de matchs (~250 matchs), et arrive même a le dépasser a
force de jouer contre des IA plus faibles, et accumuler des victoires
pendant que les autres jouent beaucoup moins...
Conclusion
Mon
objectif n'est pas de remettre en question les classements des deux
précédents concours (les trois premiers de game of drones sont non
seulement largement devant, mais n'ont pas remis a jour au dernier
moment, et avaient donc suffisamment de matchs pour avoir un
classement stable), mais plutot de s'assurer que les prochains auront
un déroulement plus équitable, et des résultats plus stables. Si
j'avais le sentiment sur tron d'avoir été sous évalué, sur game
of drones c'est plutot l'inverse :D
En
conclusion, si j'avais des recommandations a faire, j'utiliserais
trueskill de la manière suivante:
Lors
des phase de qualifications, on souhaite avoir un ordre de grandeur
du niveau de notre IA. Lorsqu'on remet a jour on souhaite un feedback
rapide contre des IA de notre niveau. Je ne remettrais donc pas a
zéro les valeurs de mu et sigma de trueSkill. Dans l'idéal je
ferais jouer des matchs en continue a toutes les IA afin de garantir
un nombre de matchs équitables, mais si ça consomme trop de CPU,
lancer des matchs avec la nouvelle IA, sans remettre a zero ses
caractéristiques trueskill me parait raisonnable.
Pour
les phases finales, et afin d'avoir un résultat stable, il faut
remettre toutes les IA a zero (on est aussi certains que d'anciens
matchs contre des IA qui n'existent plus ne sont pas comptabilisés).
Puis toujours en répartissant les matchs sur les joueurs, on calcule
le score en faisant une moyenne du score trueskill sur tous les
matchs qui ont été joués. Ca devrait garantir une certaine
stabilité dans le classement final.
Vos
commentaires sont évidement les bienvenus. Des que j'ai du temps je
poste le code que j'ai utilisé pour obtenir ces résultats
:)
A+
Manwe
LouJo
Cependant nous ici quand on classe des programmes, tous les matchs ont la même valeur.
Comment on pourrais changer ça? Simplement en faisant la moyenne des estimations trueskill : les matchs passés sont certes progressivement oubliés pour établir le skill courant, mais continuent d'être comptabilisés pour le skill final. Si on reprends le chart précédent et qu'on fait la moyenne de tous les scores calculés lors des itérations précédentes, on obtiens ça:
Pour bien préciser, comme tu l'as dit, c'est une bonne idée mais ca ne devrait concerner que les matchs de classement final quand les IA ne bougent plus, pas ceux tout au long du challenge, sinon une IA depuis longtemps dans l'arène serait sur évaluée, ayant à son époque joué contre des IA moins fortes que actuellement.
Dans l'ensemble je plussoie ; après c'est un choix d'avoir un classement final qui est dans la continuité du classement pendant le concours, ou bien un classement complètement remis à 0 le plus juste possible.
Manwe
- Lors des phases préliminaires on utilise trueskill normalement afin "d'oublier" les matchs anciens. Une potentielle amélioration est de ne pas remettre à 0 le score d'une IA afin de lui éviter une chute dans le classement, mais bien conserver son mu et son sigma qui seront réajustés en fonction des progrès ou des régressions. On a alors certes un leaderboard qui ne se stabilise pas, mais au moins les mises a jours sont correctement prises en compte et les matchs passés ne sont progressivement plus comptabilisés
- Lors des phases finales, remettre tout le monde à zero, essayer de faire jouer autant de matchs à chacun, et calculer le skill en faisant des moyennes afin de stabiliser le leaderboard
En lisant ton message, je me suis aussi dis que comme c'est fait aujourd'hui, comme il n'y a pas de remise à zéro, les matchs contre des IA qui n'existent plus sont tout de même comptabilisés.
Frédéric Trégon
joanna....@gmail.com
Il faudrait aussi garantir le même nombre de match à chacun.
Par exemple je me suis fait ravir la 4ème place au dernier moment (après c'est un peu ma faute j'ai renvoyé une optimisation trop tard) parce que le 5ème pouvait jouer des matches (il y avait un 15eme à qui il restait des matches à faire) et m'a griller de 0.01 points, je n'ai pas eu la chance de rejouer un match après ça (le 15ème s'est retrouvé 16ème, et n'est plus remonté, plus possible de faire des matches).
En l’occurrence, les 3 premiers était vraiment au dessus, donc pas de problème, mais si c'était la 3ème place qui avait été en jeu...
joanna....@gmail.com
> C'est loin de se stabiliser lorsque les niveaux des bots sont très
> proches même malgré une augmentation du nombre de match.
>
> En
> fait c'est tout a fait logique : TrueSkill s’attend a une
> probabilité de victoire en fonction du sigma et du mu de chaque
> joueur. Or lorsqu'il fait le réajustement, progressivement, plus les
> matchs sont éloignés, moins ils comptent dans le score final. L'IA
> est donc classé par rapport a ses derniers matchs (difficile
> d'évaluer un nombre exact). TrueSkill étant utilisé sur des
> humains, c'est fiable dans le sens ou le niveau de chaque joueur
> varie avec le temps, et il est donc normal que les résultats des
> matchs anciens soient progressivement oubliés.
>
> Cependant
> nous ici quand on classe des programmes, tous les matchs ont la même
> valeur.
> Comment
> on pourrais changer ça? Simplement en faisant la moyenne des
> estimations trueskill : les matchs passés sont certes
> progressivement oubliés pour établir le skill courant, mais
> continuent d'être comptabilisés pour le skill final. Si on reprends
> le chart précédent et qu'on fait la moyenne de tous les scores
> calculés lors des itérations précédentes, on obtiens ça:
>
>
>
>
>
>
>
>
>
>
>
>
> partir de 200/300 matchs par IA, non seulement on a les IA dans le
> bon ordre, mais en plus, ça deviens très stable! Il n'y a plus de
> variations de dernière minutes si frustrantes pour nos nerfs
> :)
>
> Expérience
> 3
>
> Souvent
> on a été frustré de devoir attendre que son IA remonte dans le
> classement avant de voir si elle s’améliorait ou non. Qu'est ce
> que ça donnerais si on ne remettais pas a 0 l’évaluation
> trueSkill de notre bot? Imaginons que j'améliore mon bot: l'IA 7 a
> fait une super mise a jour, et est donc maintenant la plus forte avec
> un skill de 11:
>
>
>
>
>
>
>
>
>
>
>
>
>
> observe bien une progression de l'IA, qui en une centaine de matchs a
> pris sa position dans les meilleurs.
>
> Ne
> serait t'il pas préférable de faire un reset de l'IA lors de la
> remise dans l'arène, et lui faire jouer beaucoup de matchs (c'est
> comme ça qu'on était évalué sur tron et game of thrones)? Si je
> fait un reset du skill d'une IA après que chacune en ais joué 500,
> puis que je la remet dans l'arène pour 500 matchs où elle participe
> à tous les matchs, ça donne ça:
>
>
>
>
>
>
>
>
>
>
>
>
>
Pour des IA nettement plus fortes, le nombre de matches les avantages.
Par contre quand les IA sont plus proches, un "coup de chance" peut permettre une montée rapide et un positionnement un peu supérieure (d'où l'effet je remonte vite)
En tout cas il me semble utile de garantir le même nombre de matches à chacun après la fin de compétition, le coup des plus bas qui ont une chance de remonter grâce aux bot en cours est assez frustrant ;)
thomas.n...@gmail.com
Sur Game Of Drones, j'étais 15-20 sur la dernière demi heure de jeu. A 5s de l'heure de fin du concours, j'ai relancé la même IA par curiosité, je savais que je ne ferais pas mieux que la 15eme place et j'avais plus rien à perdre.
Ma curiosité fut satisfaite: Je me suis retrouvé 28eme :)
Je pense donc que lancer tardivement sa solution est pénalisant, pour un nombre de parties d'entrées trop faible.
Frédéric Trégon
joanna....@gmail.com
Autre question, ne faudrait-il pas que les terrains possibles soient limités et figés, et non complètement aléatoire ?
En en ayant un nombre suffisant pour éviter des IA trop spécifiques bien entendu...
Manwe
Tout d'abord je tiens a vous rassurer sur la qualité du concours et de sa réalisation : les graphismes donnent envie, la console est agréable, et même si les développeur plus avancés ne vont pas l'utiliser car ils ont leurs habitudes et leurs outils, elle permet a tout le monde de participer avec très peu de moyens. Et pour ça un grand MERCI! J'ai hate de voir et de participer au prochain challenge :)
Le sujet de GoD était très intéressant, et était parfaitement équitable pour chaque joueur puisque les positions de départs n'étaient pas différentes pour chaque joueur.
J'ai moi aussi le sentiment de passer pour le mauvais perdant de service, et ça me dérange, d'un autre coté je souhaite vraiment avoir un système d'évaluation qui ne dépends pas du dernier match. Ma démarche est plutot de donner des outils et des méthodes qui assureront au prochains concours une stabilité dans les résultats. Il n'y a qu'a voir les messages échangés à la fin du challenge sur le chat, on hésitais a remettre l'IA dans l'arène en connaissant les conditions de jeu. Et malheureusement augmenter ou diminuer le nombre de matchs joués n'est pas une solution car on n'a pas de stabilité des skills même si on était capable de faire des millions de matchs...En particulier la variable de confiance de trueskill au bout d'un moment ne s'approche pas de 0.
J'ai aucun doute sur les fait que les classements sont dans l'ensemble assez justes, et a quelques places prêt, on est bon. Les trois (deux?) premiers sur GoD avaient beaucoup d'avance. Quand il y a un gros écart de skill, trueSkill fait très rapidement la différence, et je pense que dès qu'il y a 1.5/2 points d'écarts dans le leaderboard, il n'y a quasiment aucune chance que les IA suivantes soient plus fortes. Ca explique pourquoi les IA qui ont un niveau intermediaire ou peu d'autres joueurs sont présents, rejoignent rapidement leur position. Par contre quand on est à 0.1, 0.2 d'écart, le prochain match, si on le gagne ou on le perd nous fera changer de place a coup sur.
On passe finalement beaucoup de temps sur ces challenge, déjà parce qu'on aime ça, mais aussi car on a envie de monter dans le leaderboard. Et quand tu as passés quelques heures voir dizaines d'heures sur un truc, tu souhaite évidement qu'il soit évalué avec un minimum de précision. Nergal me faisait remarquer que sur tron comme sur GoD j'ai fini à la première place qui n'a pas de prix avec mes 4e et 11e places ^^
Je vous joint trueskill.zip qui contient tout ce qu'il faut pour faire de nouveaux essais.
Le repertoire src contiens les sources en java. Vous pouvez monter ça dans un projet eclipse par exemple. Il faut juste telecharger jython-standalone-2.5.3.jar (http://www.jython.org/downloads.html) et l'ajouter au path afin de pouvoir executer du python a partir de java.
Ensuite, si on veut modifier la manière dont sont choisi les matchs, il faut modifier la classe engine.MatchPicker, et plus particulièrement les méthode pickMatch et pickMatchWithSeed. La première méthode selectione des joueurs en fonction du nombre de match qu'ils ont déjà joués. La deuxième selectionne les joueurs en imposant que le joueur en paramètre participe au match. Les matchs chacun pour soit a 2 3 ou 4 joueurs sont déjà supportés.
Si on veut modifier les probabilités de victoire de chaque joueur, il faut aller modifier la classe game.WithRandomSkilledGame. Il faut modifier la méthode runMatch qui doit renvoyer le classement final du match.
Cette classe a aussi le "main" permettant de lancer les trois expériences que j'ai décrites et qui va ecrire les historiques du leaderboard dans un fichier csv a chaque fois.
Pour le nombre de matchs a faire pour donner 100 matchs a chaque joueur, j'ai pas bien suivi le calcul. J'obtiens de mon coté beaucoup moins:
Si on veut 110 matchs pour chaque joueur, il faut donc lui faire jouer 110/3 matchs en 1v1, 110/3 matchs en 1v1v1 et 110/3 matchs en 1v1v1v1. Or a chaque match, il y a donc 2 3 ou 4 joueurs qui participent.
On doit donc faire au total : 650*110/(3*2) matchs a 2 joueurs, 650*110/(3*3)matchs a 3, et 650*110/(3*4), ce qui fait 650*110*13/12 = 77456 matchs
Les IA répondaient toutes très vites (la mienne en moins de 0.5ms, celle de LouJo quelques ms etc), et on avais d'ailleurs dans la console un résultat très rapide pour chaque match. Je pense d'autant plus que les IA assez faibles répondaient quasi instantanément. Imaginons (et on surestime certainement grandement) que chaque IA réponde en 5ms en moyenne. Alors, chaque IA va jouer ses 110 matchs, ou elle va donc consommer 200 tours de CPU. Ca fait donc 650*110*200*5/(1000*3600) = 19.86 heures sur... 1 CPU
Avec trois serveurs avec 4 coeurs, on divise par douze, et en moins d'une heure 30 tout le monde a joué ses 110 matchs. Imaginez le temps nécessaires si on achète du temps CPU sur un système de cloud. On boucle le tout en quelques minutes...
En plus il y a des possibilités pour affiner les résultats. Concrètement on peut tout a fait se permettre de voir la phase finale comme des étapes successives de qualifications : d'abord faire jouer tout le monde une centaine de matchs afin d'avoir une première idée, puis faire jouer 100 matchs supplémentaires au 250 premiers, puis 100 matchs supplémentaires au 100 premiers ainsi de suite jusqu’à arriver aux 20 premiers par exemple. C'est ce qui avait été mis en place sur les google AI Challenge par exemple. Un joueur ne viendra pas se plaindre d'être 333e au lieu de 332e, il mémorisera qu'il était top 400 voir top 350, par contre entre 2e et 1er, sans même considérer les prix, il sera beaucoup plus attaché à la place prêt.
Comme sur le premier poste, les commentaires sont les bienvenus :)
Ce qui me fait plaisir c'est qu'il y a des réactions, et donc cerainement que les choses s'amélioreront :)
joanna....@gmail.com
Et cela obligerait à tous de poster une IA au bout d'un certain temps, ainsi que de stabiliser son IA régulièrement, pour ensuite pouvoir éventuellement la retravailler, ça fait très compétition :)
Et le leaderboard ne serait là que pour avoir une idée de son positionnement mais ne compterait pas pour les matches officiels (ce serait des matches amicaux en sorte)
En tout cas je "plussoie" ta remarque du début, l'organisation est déjà très bonne, l'interface très pratique, et en l'occurrence aucune contestation possible sur les 3 premiers :)
Un grand merci pour ce concours très fun !
Manwe
Salut,
J'ai retravaillé mon outil pour faire des tests avec
trueskill. Il y a une interface graphique faite en JavaFX, et on peut
donc expérimenter pas mal de choses. En particulier, on peut choisir les
probabilités de victoires de chaque adversaires a partir d'un fichier.
On peut augmenter ou diminuer le nombre de joueurs.
Par exemple, avec le fichier suivant:
;P1;P2;P3
P1;0;1;0.5
P2;0;0;0.8
P3;0.5;0.2;0
On
a défini trois joueurs, P1, P2 et P3. Quand P1 oue contre P2, il gagne à
chaque fois, quand P1 joue contre P3, il a une chance sur deux de
gagner. Quand P2 joue contre P3, il a 80% de chances de gagner.
Attention,
vous pouvez parfaitement configurer des probabilités différentes
lorsque le joueur 1 joue contre le joueur 2 ou le joueur 2 joue contre
le joueur 1!
Ensuite quand on lance les matchs on obtient ça en quelques secondes:
Faites vos essais, et dites moi ce que vous en pensez!
Le code de l'appli est dispo sur github : https://github.com/Manwe56/trueskill-ai-contest-test-tool
Pour ceux qui passeraient au DEVOXX demain ou après demain, on pourra se croiser dans une conférence ou sur le stand Murex ;)
A+
Manwe
Frédéric Trégon
Manwe
Je l'ais pas dis dans mon post, mais j'ai décris pas mal de choses dans le readme sur gihub.