Infer-8-TrueSkill : Système de Classement et Apprentissage en Ligne

Serie : Programmation Probabiliste avec Infer.NET (8/19)
Duree estimee : 55 minutes
Prerequis : Infer-7-Skills-IRT

Objectifs

  • Comprendre le système TrueSkill (Xbox Live)
  • Implementer des matchs 1v1 et la mise a jour des skills
  • Gerer les matchs nuls
  • Maitriser l’apprentissage en ligne (posterieurs -> priors)
  • Etendre aux équipes et multi-joueurs

1. Configuration

Nous chargeons Infer.NET pour implementer le système TrueSkill, developpe par Microsoft Research pour Xbox Live. Ce système de classement bayesien estime les competences des joueurs a partir des résultats de matchs, tout en quantifiant l’incertitude sur ces estimations.

#r "nuget: Microsoft.ML.Probabilistic"
#r "nuget: Microsoft.ML.Probabilistic.Compiler"

using Microsoft.ML.Probabilistic;
using Microsoft.ML.Probabilistic.Distributions;
using Microsoft.ML.Probabilistic.Utilities;
using Microsoft.ML.Probabilistic.Math;
using Microsoft.ML.Probabilistic.Models;
using Microsoft.ML.Probabilistic.Algorithms;
using Microsoft.ML.Probabilistic.Compiler;

Console.WriteLine("Infer.NET pret !");
Installing Packages
  • Microsoft.ML.Probabilistic
  • Microsoft.ML.Probabilistic.Compiler
Infer.NET pret !

Chargement du helper de visualisation des graphes de facteurs.

// Chargement du helper pour visualiser les graphes de facteurs
#load "FactorGraphHelper.cs"

Console.WriteLine("FactorGraphHelper charge. Graphviz disponible : " + FactorGraphHelper.IsGraphvizAvailable());
FactorGraphHelper charge. Graphviz disponible : True

Environnement pret

Infer.NET est maintenant charge avec tous les namespaces necessaires pour la programmation probabiliste. Les principaux composants utilises dans ce notebook :

Namespace Usage
Microsoft.ML.Probabilistic.Distributions Gaussiennes pour modeliser les skills
Microsoft.ML.Probabilistic.Models Variables et contraintes du modèle
Microsoft.ML.Probabilistic.Algorithms Expectation Propagation (EP)

Note technique : TrueSkill utilise l’algorithme Expectation Propagation car les facteurs de comparaison (perf1 > perf2) ne sont pas conjugues avec les Gaussiennes. EP approxime ces facteurs par des Gaussiennes, permettant une inference efficace.

2. Introduction a TrueSkill

Contexte

TrueSkill est le système de classement developpe par Microsoft Research pour Xbox Live. Il est une generalisation bayesienne du système Elo.

Principe

Chaque joueur a un skill (competence) modelise par une distribution Gaussienne : - Moyenne (mu) : estimation du skill - Variance (sigma^2) : incertitude sur cette estimation

Formulation

\[\text{skill}_i \sim \mathcal{N}(\mu_i, \sigma_i^2)\]

\[\text{performance}_i = \text{skill}_i + \epsilon_i, \quad \epsilon_i \sim \mathcal{N}(0, \beta^2)\]

\[\text{Joueur 1 gagne si} \quad \text{performance}_1 > \text{performance}_2\]

Paramètres par defaut

Paramètre Valeur Description
mu_initial 25 Skill initial
sigma_initial 25/3 Incertitude initiale
beta sigma/2 Ecart-type de la performance

Comparaison TrueSkill vs Elo

Aspect Elo TrueSkill
Representation Score unique (ex: 1800) Distribution N(mu, sigma)
Incertitude Non modelisee Capturee par sigma
Convergence Lente (K fixe) Rapide (adaptatif via sigma)
Matchs nuls +/- points fixes Reduction d’incertitude
Équipes Moyenne des Elo Somme des performances
Multi-joueurs Decomposition en paires Natif via contraintes d’ordre

Note historique : TrueSkill a ete developpe par Ralf Herbrich, Tom Minka et Thore Graepel chez Microsoft Research (article NIPS 20, publié en 2007 — TrueSkill: A Bayesian Skill Rating System). Tom Minka est également l’auteur d’Expectation Propagation (EP), l’algorithme d’inférence au cœur de TrueSkill (voir section 6). Le système est utilisé sur Xbox Live depuis 2007 pour le matchmaking de millions de joueurs. Le notebook distille le chapitre 3 « Meeting Your Match » du Model-Based Machine Learning (Winn & Bishop).

Fidélité à la source : Ce notebook distille le chapitre 3 « Meeting Your Match » du Model-Based Machine Learning (Winn & Bishop, mbmlbook.com/TrueSkill.html), lui-même adapté de Herbrich, Minka & Graepel (2007). Le scénario (matchs Xbox Live/Halo 2, skill déduit du résultat), la mécanique bayésienne (performance = skill + bruit, facteur IsGreaterThan) et la nécessité d’Expectation Propagation (posterior exact non-Gaussien après troncation) suivent le livre. À distinguer de Infer-7-Skills-IRT qui distille le chapitre 2 (« Assessing People’s Skills ») : la skill y est déduite de réponses à un test (modèle Rasch/IRT), ici elle est déduite du résultat d’un match.

Elo : le prédécesseur déterministe que TrueSkill généralise

Avant TrueSkill, le classement compétitif était dominé par Elo (échecs, années 1960), que la cellule suivante implémente from-scratch. Chaque joueur y est représenté par un unique scalaire \(R\) (son rating) :

\[E_A = \frac{1}{1 + 10^{(R_B - R_A)/400}}, \qquad R_A \leftarrow R_A + K \cdot (S_A - E_A)\]

  • \(E_A\) : score attendu de A (probabilité de victoire implicite),
  • \(S_A\) : score observé (1 = gagne, 0 = perd, 0.5 = nul),
  • \(K\) : facteur de mise à jour FIXE (typiquement 16 à 32).

Elo est simple, robuste et éprouvé. Mais il est déterministe et ponctuel : il ne modélise pas son incertitude. La cellule suivante montre concrètement ce que cela implique, et pourquoi Microsoft a développé TrueSkill pour Xbox Live.

// Elo : le systeme de classement deterministe que TrueSkill generalise.
// Implementation from-scratch (pure C#, deterministe) pour servir de baseline.

double ExpectedScore(double ratingA, double ratingB)
    => 1.0 / (1.0 + Math.Pow(10, (ratingB - ratingA) / 400.0));

(double, double) UpdateElo(double ratingA, double ratingB, double scoreA, double K = 32)
{
    double ea = ExpectedScore(ratingA, ratingB);
    return (ratingA + K * (scoreA - ea), ratingB - K * (scoreA - ea)); // somme nulle
}

Console.WriteLine("ELO : LE PREDECESSEUR DETERMINISTE");
Console.WriteLine(new string('=', 60));
// Deux nouveaux joueurs, meme rating initial (convention Elo : 1500).
double R1 = 1500.0, R2 = 1500.0;
Console.WriteLine($"Avant : R1 = {R1:F1}, R2 = {R2:F1}  (deux nouveaux joueurs)");
Console.WriteLine($"  Score attendu de J1 : E = {ExpectedScore(R1, R2):F3}");
// Joueur 1 gagne (resultat = 1).
(R1, R2) = UpdateElo(R1, R2, scoreA: 1.0);
Console.WriteLine($"Apres (J1 gagne) : R1 = {R1:F1}, R2 = {R2:F1}  (Delta = +16,0 / -16,0)");

Console.WriteLine();
Console.WriteLine("CECITE A L'INCERTITUDE : Elo applique le meme K en permanence");
Console.WriteLine(new string('-', 60));
// Une serie de 5 victoires consecutives de J1.
R1 = 1500.0; R2 = 1500.0;
double prev = R1;
for (int k = 1; k <= 5; k++)
{
    (R1, R2) = UpdateElo(R1, R2, scoreA: 1.0);
    double delta = R1 - prev;
    Console.WriteLine($"  Victoire {k} : R1 = {R1,7:F1}  (increment +{delta:F1})");
    prev = R1;
}

Console.WriteLine();
Console.WriteLine(">>> Elo ne SAIT PAS qu'il est incertain. Un nouveau joueur et un");
Console.WriteLine("    veteran de 1000 matchs au meme rating sont traites identiquement.");
Console.WriteLine("    C'est ce defaut que TrueSkill corrige en modelisant sigma.");

ELO : LE PREDECESSEUR DETERMINISTE
============================================================
Avant : R1 = 1500,0, R2 = 1500,0  (deux nouveaux joueurs)
  Score attendu de J1 : E = 0,500
Apres (J1 gagne) : R1 = 1516,0, R2 = 1484,0  (Delta = +16,0 / -16,0)

CECITE A L'INCERTITUDE : Elo applique le meme K en permanence
------------------------------------------------------------
  Victoire 1 : R1 =  1516,0  (increment +16,0)
  Victoire 2 : R1 =  1530,5  (increment +14,5)
  Victoire 3 : R1 =  1543,7  (increment +13,2)
  Victoire 4 : R1 =  1555,8  (increment +12,1)
  Victoire 5 : R1 =  1566,8  (increment +11,0)

>>> Elo ne SAIT PAS qu'il est incertain. Un nouveau joueur et un
    veteran de 1000 matchs au meme rating sont traites identiquement.
    C'est ce defaut que TrueSkill corrige en modelisant sigma.

Lecture : Elo est aveugle à sa propre incertitude

Les incréments rétrécissent (16,0 → 14,5 → 13,2 → 12,1 → 11,0) au fil des victoires consécutives. Ce n’est pas parce qu’Elo « apprend » qu’il est confiant : c’est un effet mécanique. À mesure que \(R_1\) monte, le score attendu \(E_A\) grimpe vers 1, donc l’écart \((S_A - E_A)\) diminue, et la même mise \(K\) produit un delta plus petit. C’est une conséquence arithmétique de la formule, pas une modélisation de l’incertitude.

La limite fondamentale : un nouveau joueur (0 match) et un vétéran (1000 matchs) au même rating reçoivent exactement le même \(K\). Elo ne sait pas distinguer « je suis sûr à 25,0 ± 8,3 » de « je suis sûr à 25,0 ± 0,1 ». C’est précisément ce défaut que TrueSkill corrige en représentant chaque compétence par une distribution \(\mathcal{N}(\mu, \sigma^2)\) : \(\sigma\) diminue avec chaque match observé, et la mise à jour s’adapte à l’incertitude courante plutôt qu’à un \(K\) figé.

Le tableau de comparaison ci-dessus (axes Représentation, Incertitude, Convergence…) prend maintenant tout son sens : TrueSkill n’est pas « un meilleur Elo », c’est une généralisation bayésienne qui substitue une distribution au scalaire, rendant l’incertitude explicite et exploitée.

3. Modèle Deux Joueurs

Construction du modèle étape par étape

Le code suivant construit le modèle TrueSkill en quatre phases :

  1. Paramètres : Definition des hyperparametres (mu=25, sigma=8.33, beta=4.17)
  2. Priors : Chaque joueur commence avec la même distribution Gaussienne
  3. Performances : Ajout de bruit pour modeliser la variabilite d’un match
  4. Observation : Le résultat du match (qui a gagne) est observe

Cette structure separe clairement les croyances initiales (priors) des données observees (résultat du match).

// Parametres TrueSkill
double muInitial = 25.0;
double sigmaInitial = 25.0 / 3.0;
double beta = sigmaInitial / 2.0;  // Variabilite de la performance

// Skills des joueurs (priors)
Variable<double> skill1 = Variable.GaussianFromMeanAndVariance(muInitial, sigmaInitial * sigmaInitial).Named("skill1");
Variable<double> skill2 = Variable.GaussianFromMeanAndVariance(muInitial, sigmaInitial * sigmaInitial).Named("skill2");

// Performances (skill + bruit)
Variable<double> perf1 = Variable.GaussianFromMeanAndVariance(skill1, beta * beta).Named("perf1");
Variable<double> perf2 = Variable.GaussianFromMeanAndVariance(skill2, beta * beta).Named("perf2");

// Resultat du match : Joueur 1 gagne
Variable<bool> joueur1Gagne = (perf1 > perf2).Named("joueur1Gagne");

// Observation : Joueur 1 a effectivement gagne
joueur1Gagne.ObservedValue = true;

Console.WriteLine("Modele TrueSkill deux joueurs defini.");
Modele TrueSkill deux joueurs defini.

Structure du modèle graphique

Le modèle TrueSkill peut etre represente comme un graphe de facteurs :

skill1 ~ N(25, 8.33^2)     skill2 ~ N(25, 8.33^2)
    |                           |
    v                           v
  perf1 = skill1 + eps       perf2 = skill2 + eps
    |                           |
    +-----------> > <-----------+
                  |
                  v
           joueur1Gagne = true (observe)

Intuition : L’observation que “joueur 1 gagne” impose la contrainte perf1 > perf2. L’inference propage cette information vers les skills, augmentant skill1 et diminuant skill2.

Exécution de l’inference

Nous allons maintenant executer l’inference pour calculer les posterieurs des skills après avoir observe que le joueur 1 a gagne. L’algorithme EP va propager l’information du résultat vers les distributions de skill.

// Inference apres le match
InferenceEngine moteur = new InferenceEngine(new ExpectationPropagation());
moteur.Compiler.CompilerChoice = CompilerChoice.Roslyn;
moteur.ShowFactorGraph = true;  // Activer la generation du graphe de facteurs

Gaussian skill1Post = moteur.Infer<Gaussian>(skill1);
Gaussian skill2Post = moteur.Infer<Gaussian>(skill2);

Console.WriteLine("=== Apres un match (Joueur 1 gagne) ===");
Console.WriteLine($"\nAvant le match :");
Console.WriteLine($"  Skill1 = N({muInitial:F1}, {sigmaInitial:F2})");
Console.WriteLine($"  Skill2 = N({muInitial:F1}, {sigmaInitial:F2})");

Console.WriteLine($"\nApres le match :");
Console.WriteLine($"  Skill1 = N({skill1Post.GetMean():F2}, {Math.Sqrt(skill1Post.GetVariance()):F2})");
Console.WriteLine($"  Skill2 = N({skill2Post.GetMean():F2}, {Math.Sqrt(skill2Post.GetVariance()):F2})");

Console.WriteLine($"\nChangement de skill :");
Console.WriteLine($"  Joueur 1 : +{skill1Post.GetMean() - muInitial:F2}");
Console.WriteLine($"  Joueur 2 : {skill2Post.GetMean() - muInitial:F2}");
Compiling model...done.
=== Apres un match (Joueur 1 gagne) ===

Avant le match :
  Skill1 = N(25,0, 8,33)
  Skill2 = N(25,0, 8,33)

Apres le match :
  Skill1 = N(29,21, 7,19)
  Skill2 = N(20,79, 7,19)

Changement de skill :
  Joueur 1 : +4,21
  Joueur 2 : -4,21

Analyse détaillée du résultat

Avant le match : Les deux joueurs sont identiques N(25, 8.33) Après le match : Skill1 = N(29.21, 7.19), Skill2 = N(20.79, 7.19)

Observations clés :

Aspect Valeur Explication
Gain du gagnant +4.21 Augmentation significative
Perte du perdant -4.21 Symétrique (priors identiques)
Réduction sigma 8.33 → 7.19 Plus d’info = moins d’incertitude

Intuition : Un match entre deux joueurs de même niveau (selon les priors) est informatif. Le gagnant a démontré qu’il est probablement meilleur.

Comparaison avec Elo : Contrairement au système Elo classique qui utilise des changements fixes (±16 points), TrueSkill adapte le changement en fonction de l’incertitude. Un joueur avec grand sigma (nouveau) verra son rating changer plus rapidement.

// Visualisation du graphe de facteurs TrueSkill
display(HTML(FactorGraphHelper.GetLatestFactorGraphHtml()));
Model_08_19_26_02_22_45_04.svg
Model node0 25 node1 GaussianFromMeanAndVariance node0->node1 mean node3 skill1 node1->node3 node2 69,44444444444446 node2->node1 variance node4 GaussianFromMeanAndVariance node3->node4 mean node6 perf1 node4->node6 node5 17,361111111111114 node5->node4 variance node7 Minus node6->node7 a node9 vdouble10 node7->node9 node8 perf2 node8->node7 b node16 IsPositive node9->node16 x node10 skill2 node11 GaussianFromMeanAndVariance node10->node11 mean node11->node8 node12 17,361111111111114 node12->node11 variance node13 25 node14 GaussianFromMeanAndVariance node13->node14 mean node14->node10 node15 69,44444444444446 node15->node14 variance node17 True node16->node17

Lecture du graphe de facteurs TrueSkill 1v1

Le graphe ci-dessus montre la structure du modèle TrueSkill pour un match a deux joueurs :

Noeuds de variables (ellipses) : - skill1, skill2 : Les competences latentes des joueurs (Gaussiennes) - perf1, perf2 : Les performances observees pendant le match - joueur1Gagne : Le résultat du match (observe = true)

Noeuds de facteurs (rectangles) : - GaussianFromMeanAndVariance : Lie les priors aux skills et les skills aux performances - IsGreaterThan (ou >) : La contrainte de comparaison entre performances

Flux d’information : L’algorithme Expectation Propagation (EP) propage des messages le long de ce graphe : 1. L’observation joueur1Gagne = true envoie un message vers le facteur de comparaison 2. Ce facteur propage l’information vers perf1 (augmente) et perf2 (diminue) 3. Les changements de performance se propagent vers les skills correspondants

Note technique : Le facteur IsGreaterThan n’est pas conjugue avec les Gaussiennes. EP l’approxime par des moments de Gaussienne, ce qui explique pourquoi TrueSkill utilise EP plutot que VMP.

Pourquoi EP ? Le coût de l’inférence exacte

La note précédente dit que TrueSkill utilise EP plutôt que VMP — mais une question plus fondamentale reste en suspens : pourquoi approximer l’inférence du tout ? Pourquoi ne pas calculer le posterior exact des skills ?

Le problème vient du facteur IsGreaterThan. Les priors et les facteurs de performance (GaussianFromMeanAndVariance) sont Gaussiens, donc conjugués : leur produit reste Gaussien. Mais la contrainte \(\text{perf}_1 > \text{perf}_2\) tronque la Gaussienne (elle annule tout le demi-plan où le joueur 2 gagnerait). Le message qui en résulte n’est plus Gaussien : c’est une Gaussienne cumulée (une sigmoïde), et le posterior exact du skill est le produit d’une Gaussienne par cette sigmoïde — une courbe asymétrique, non-Gaussienne.

  • Un posterior exact a trop de paramètres. Une Gaussienne se résume à 2 nombres (\(\mu\), \(\sigma\)). Le posterior exact (Gaussienne \(\times\) Gaussienne cumulée) nécessite 4 paramètres. Or chaque match ajoute un tel facteur : après \(k\) matchs, la représentation exacte du posterior accumule \(2(k{+}1)\) paramètres. C’est insoutenable pour un système qui classe des millions de joueurs sur des milliers de matchs.

C’est là qu’intervient Expectation Propagation (EP). Plutôt que de traîner un posterior exact de plus en plus complexe, EP reprojette le posterior sur une Gaussienne après chaque facteur (en matchant les moments — moyenne et variance). Le nombre de paramètres reste borné (toujours 2 par skill), au prix d’une approximation locale.

Lecture du résultat cellule 12 : le posterior affiché N(29.21, 7.19) (skill du gagnant) n’est pas le posterior exact — c’est la projection Gaussienne calculée par EP. Le vrai posterior est légèrement asymétrique ; EP en capture la moyenne et la variance, ce qui suffit pour le matchmaking. C’est ce compromis précision/coût qui rend TrueSkill déployable à l’échelle d’Xbox Live.

Lien avec MBML Ch.3 : cette motivation (explosion paramétrique de l’inférence exacte → nécessité d’EP) est développée en détail dans Model-Based Machine Learning (Winn & Bishop), chapitre « Meeting Your Match », dont cette série est distillée.

4. Gestion des Matchs Nuls

Modèle

Un match nul se produit quand la différence de performances est dans un intervalle \([-\epsilon, \epsilon]\).

\[|\text{perf}_1 - \text{perf}_2| < \epsilon \Rightarrow \text{match nul}\]

Implementation avec Variable.ConstrainBetween

Pour modeliser un match nul, nous utilisons Variable.ConstrainBetween qui impose que la différence de performances soit dans un intervalle. Cela remplace la contrainte binaire “>” par une contrainte d’intervalle.

// Modele avec possibilite de match nul

double epsilon = 1.0;  // Marge pour match nul

Variable<double> skillA = Variable.GaussianFromMeanAndVariance(muInitial, sigmaInitial * sigmaInitial).Named("skillA");
Variable<double> skillB = Variable.GaussianFromMeanAndVariance(muInitial, sigmaInitial * sigmaInitial).Named("skillB");

Variable<double> perfA = Variable.GaussianFromMeanAndVariance(skillA, beta * beta).Named("perfA");
Variable<double> perfB = Variable.GaussianFromMeanAndVariance(skillB, beta * beta).Named("perfB");

// Difference de performances
Variable<double> diff = (perfA - perfB).Named("diff");

// Match nul : diff dans [-epsilon, epsilon]
Variable.ConstrainBetween(diff, -epsilon, epsilon);

InferenceEngine moteurNul = new InferenceEngine(new ExpectationPropagation());
moteurNul.Compiler.CompilerChoice = CompilerChoice.Roslyn;
moteurNul.ShowFactorGraph = true;  // Activer la generation du graphe de facteurs

Gaussian skillAPostNul = moteurNul.Infer<Gaussian>(skillA);
Gaussian skillBPostNul = moteurNul.Infer<Gaussian>(skillB);

Console.WriteLine("=== Apres un match nul ===");
Console.WriteLine($"\nSkillA = N({skillAPostNul.GetMean():F2}, {Math.Sqrt(skillAPostNul.GetVariance()):F2})");
Console.WriteLine($"SkillB = N({skillBPostNul.GetMean():F2}, {Math.Sqrt(skillBPostNul.GetVariance()):F2})");

Console.WriteLine($"\n=> Les deux joueurs gardent le meme skill moyen");
Console.WriteLine($"   mais l'incertitude diminue (on sait qu'ils sont proches)");
Compiling model...done.
=== Apres un match nul ===

SkillA = N(25,00, 6,46)
SkillB = N(25,00, 6,46)

=> Les deux joueurs gardent le meme skill moyen
   mais l'incertitude diminue (on sait qu'ils sont proches)

Analyse du match nul

Résultat : Les deux joueurs gardent mu=25.00 mais sigma baisse de 8.33 à 6.46

Interprétation :

Un match nul entre joueurs de même niveau prior ne change pas l’estimation moyenne, mais réduit fortement l’incertitude car : - On a observé qu’ils performent de manière similaire - C’est cohérent avec l’hypothèse qu’ils ont le même skill - Donc on est plus confiant dans cette estimation

Paradoxe apparent : Un match “sans résultat” apporte quand même de l’information ! Il confirme que les skills sont proches.

Application : Dans les échecs, une nulle entre deux joueurs de ratings similaires ne change presque pas leurs ratings Elo. Mais avec TrueSkill, leur incertitude diminue, ce qui affectera les futurs matchs.

Exercice : Impact du paramètre beta sur la mise a jour des skills

Le paramètre beta contrôle la variance de la performance (bruit dans un match). Un beta faible signifie que le résultat du match reflete fidelement le skill, tandis qu’un beta eleve signifie beaucoup de variance (chance/peur de gagner).

Objectif : Comparez la mise a jour des skills pour un même match (joueur 1 gagne) avec trois valeurs de beta : 2.0 (faible), 4.17 (defaut), et 8.0 (eleve).

Étapes : 1. Pour chaque valeur de beta, créez le modèle TrueSkill 1v1 avec les priors par defaut (mu=25, sigma=8.33) 2. Observez que joueur 1 gagne 3. Calculez les posterieurs des deux joueurs 4. Affichez un tableau comparatif des changements de skill pour chaque beta

Indices : - Un beta faible => le match est très informatif => grand changement de skill - Un beta eleve => le match est peu informatif => petit changement de skill - Comparez aussi la reduction de sigma (incertitude) entre les trois cas

// Exercice : Impact du parametre beta sur la mise a jour des skills
double muInit = 25.0;
double sigmaInit = 25.0 / 3.0;

// TODO: Definir les trois valeurs de beta a tester
// Indice: double[] betas = { 2.0, 4.17, 8.0 };

// TODO: Boucler sur chaque beta et creer le modele TrueSkill 1v1
// Indice: Pour chaque beta, Variable<double> skill1 = Variable.GaussianFromMeanAndVariance(muInit, sigmaInit^2);
// Variable<double> perf1 = Variable.GaussianFromMeanAndVariance(skill1, beta^2);
// Meme chose pour skill2/perf2, puis Variable<bool> win = (perf1 > perf2); win.ObservedValue = true;

// TODO: Inferer les posterieurs et afficher le tableau comparatif
// Console.WriteLine($"| beta={b:F2} | skill1={s1.GetMean():F2} | sigma={Math.Sqrt(s1.GetVariance()):F2} | delta={s1.GetMean()-muInit:F2} |");
Console.WriteLine("Exercice a completer : Impact du parametre beta");
Exercice a completer : Impact du parametre beta
// Visualisation du graphe de facteurs pour le match nul
display(HTML(FactorGraphHelper.GetLatestFactorGraphHtml()));
Model_08_19_26_02_22_47_00.svg
Model node0 25 node1 GaussianFromMeanAndVariance node0->node1 mean node3 skillA node1->node3 node2 69,44444444444446 node2->node1 variance node4 GaussianFromMeanAndVariance node3->node4 mean node6 perfA node4->node6 node5 17,361111111111114 node5->node4 variance node7 Minus node6->node7 a node9 diff node7->node9 node8 perfB node8->node7 b node16 IsBetween node9->node16 x node10 skillB node11 GaussianFromMeanAndVariance node10->node11 mean node11->node8 node12 17,361111111111114 node12->node11 variance node13 25 node14 GaussianFromMeanAndVariance node13->node14 mean node14->node10 node15 69,44444444444446 node15->node14 variance node19 vbool1 node16->node19 node17 -1 node17->node16 lowerBound node18 1 node18->node16 upperBound node21 Equal node19->node21 B node20 True node20->node21 A

Lecture du graphe de facteurs - Match nul

Ce graphe differe du modèle 1v1 par le facteur de contrainte :

Différence structurelle : - diff : Variable intermediaire representant perfA - perfB - ConstrainBetween : Facteur imposant que diff soit dans l’intervalle [-epsilon, epsilon]

Comparaison avec le modèle 1v1 :

Aspect Match 1v1 Match nul
Facteur de résultat IsGreaterThan ConstrainBetween
Information Ordre strict Proximite
Effet sur mu Augmente/diminue Inchange
Effet sur sigma Reduit Reduit davantage

Le facteur ConstrainBetween est plus informatif car il impose une double contrainte (borne inf et sup), ce qui explique la reduction plus importante de l’incertitude.

5. Apprentissage en Ligne

Principe

Après chaque match, les posterieurs deviennent les priors pour le match suivant.

Match 1 : Prior -> Inference -> Posterieur
                                    |
                                    v
Match 2 : Prior (= Posterieur 1) -> Inference -> Posterieur
                                                     |
                                                     v
Match 3 : ...

Implementation de la classe TrueSkillOnline

La classe suivante encapsule la logique d’apprentissage en ligne :

  • Dictionary skills : Stocke le posterieur actuel de chaque joueur
  • GetSkill() : Retourne le prior initial si le joueur est nouveau
  • EnregistrerMatch() : Met a jour les posterieurs après un match
  • AfficherClassement() : Affiche le rating conservatif (mu - 3*sigma)

Le rating conservatif mu - 3*sigma est la metrique publique utilisee par Xbox Live. Il represente une borne inferieure a 99.7% de confiance sur le vrai skill.

// Classe pour gerer l'apprentissage en ligne

public class TrueSkillOnline
{
    private double muInit;
    private double sigmaInit;
    private double beta;
    private InferenceEngine moteur;
    
    // Skills actuels des joueurs
    private Dictionary<string, Gaussian> skills;
    
    public TrueSkillOnline(double muInit = 25, double sigmaInit = 8.33, double beta = 4.17)
    {
        this.muInit = muInit;
        this.sigmaInit = sigmaInit;
        this.beta = beta;
        this.skills = new Dictionary<string, Gaussian>();
        this.moteur = new InferenceEngine(new ExpectationPropagation());
        this.moteur.Compiler.CompilerChoice = CompilerChoice.Roslyn;
    }
    
    public Gaussian GetSkill(string joueur)
    {
        if (!skills.ContainsKey(joueur))
        {
            skills[joueur] = Gaussian.FromMeanAndVariance(muInit, sigmaInit * sigmaInit);
        }
        return skills[joueur];
    }
    
    public void EnregistrerMatch(string gagnant, string perdant)
    {
        // Priors actuels
        Gaussian priorGagnant = GetSkill(gagnant);
        Gaussian priorPerdant = GetSkill(perdant);
        
        // Modele
        Variable<Gaussian> priorG = Variable.Observed(priorGagnant);
        Variable<Gaussian> priorP = Variable.Observed(priorPerdant);
        
        Variable<double> skillG = Variable.Random<double, Gaussian>(priorG);
        Variable<double> skillP = Variable.Random<double, Gaussian>(priorP);
        
        Variable<double> perfG = Variable.GaussianFromMeanAndVariance(skillG, beta * beta);
        Variable<double> perfP = Variable.GaussianFromMeanAndVariance(skillP, beta * beta);
        
        Variable<bool> resultat = (perfG > perfP);
        resultat.ObservedValue = true;  // Le gagnant a gagne
        
        // Inference
        skills[gagnant] = moteur.Infer<Gaussian>(skillG);
        skills[perdant] = moteur.Infer<Gaussian>(skillP);
    }
    
    public void AfficherClassement()
    {
        var classement = skills.OrderByDescending(kv => kv.Value.GetMean());
        Console.WriteLine("\n=== Classement ===");
        int rang = 1;
        foreach (var kv in classement)
        {
            double mu = kv.Value.GetMean();
            double sigma = Math.Sqrt(kv.Value.GetVariance());
            double conservatif = mu - 3 * sigma;  // TrueSkill rating
            Console.WriteLine($"{rang}. {kv.Key,-10} : mu={mu:F1}, sigma={sigma:F2}, rating={conservatif:F1}");
            rang++;
        }
    }
}

Console.WriteLine("Classe TrueSkillOnline definie.");
Classe TrueSkillOnline definie.

Architecture de l’apprentissage en ligne

La classe TrueSkillOnline implemente le pattern bayesien fondamental :

Cycle d’apprentissage :

\[P(\theta | D_{1:n}) \propto P(D_n | \theta) \cdot P(\theta | D_{1:n-1})\]

En pratique : 1. Le posterieur après le match n-1 devient le prior pour le match n 2. Chaque match apporte de l’information incrementale 3. Le système “n’oublie jamais” mais l’influence des anciens matchs diminue naturellement

Avantage computationnel : Contrairement a un recalcul global, l’apprentissage en ligne a une complexite O(1) par match, permettant de gerer des millions de joueurs en temps reel.

Une nuance essentielle : l’apprentissage en ligne n’est pas une évolution du skill

L’affirmation ci-dessus (« le système n’oublie jamais ») décrit fidèlement le modèle à skill fixe : chaque joueur possède une compétence unique et immuable, et l’apprentissage en ligne resserre simplement l’incertitude (σ) autour de cette valeur fixe. Une idée reçue fréquente consiste à croire que ce mécanisme permet au skill de dériver dans le temps — ce n’est pas le cas. Le posterior se resserre sur une inconnue fixe ; il ne modélise pas une compétence qui évolue.

La conséquence est importante : après de nombreux matchs, σ s’effondre (ex. 8,33 → ~1). Si le joueur s’améliore ensuite réellement (entraînement, coaching), le posterior étroit résiste au suivi : la mise à jour devient minuscule car le prior est trop confiant dans l’ancien niveau. C’est précisément le défaut rapporté par les bêta-testeurs Xbox Live et corrigé au climax du chapitre MBML (§3.5, Allowing the skills to vary) : certains joueurs voyaient leur skill « bloqué » à bas niveau malgré une progression réelle.

La correction (modèle à skill dynamique) : remplacer le skill fixe par une marche aléatoire gaussienne

\[\text{skill}_t = \text{skill}_{t-1} + \mathcal{N}(0, \gamma^2)\]

où γ ( change variance ) contrôle la vitesse de variation admissible entre deux matchs. Le posterior d’un match sert de moyenne au suivant, élargi par γ, ce qui laisse au système la souplesse de suivre une trajectoire. C’est ce modèle étendu, dit TrueSkill Through Time (Dangauthier, Herbrich, Minka & Graepel, 2007), qui permet de comparer des joueurs d’échecs d’époques différentes — y compris des champions n’ayant jamais joué ensemble.

Le présent notebook modélise le skill fixe (cas pédagogique de base, §3.1–3.4 du MBML). Cette limitation est déjà signalée §10 (Résumé → Limitations). L’extension dynamique (§3.5) constitue le grain de fond naturel d’une suite.

Simulation d’un tournoi complet

Nous simulons maintenant un petit tournoi de 6 matchs entre 4 joueurs. Observez comment les skills evoluent au fur et a mesure des matchs, et comment le classement emerge des résultats.

// Simulation d'un tournoi

var ts = new TrueSkillOnline();

Console.WriteLine("=== Tournoi TrueSkill ===");

// Serie de matchs
var matchs = new (string, string)[] {
    ("Alice", "Bob"),     // Alice bat Bob
    ("Charlie", "Dave"),  // Charlie bat Dave
    ("Alice", "Charlie"), // Alice bat Charlie
    ("Bob", "Dave"),      // Bob bat Dave
    ("Alice", "Dave"),    // Alice bat Dave
    ("Charlie", "Bob")    // Charlie bat Bob
};

foreach (var (gagnant, perdant) in matchs)
{
    Console.WriteLine($"Match : {gagnant} bat {perdant}");
    ts.EnregistrerMatch(gagnant, perdant);
}

ts.AfficherClassement();
=== Tournoi TrueSkill ===
Match : Alice bat Bob
Compiling model...done.
Match : Charlie bat Dave
Compiling model...done.
Match : Alice bat Charlie
Compiling model...done.
Match : Bob bat Dave
Compiling model...done.
Match : Alice bat Dave
Compiling model...done.
Match : Charlie bat Bob
Compiling model...done.

=== Classement ===
1. Alice      : mu=33,3, sigma=6,01, rating=15,2
2. Charlie    : mu=28,3, sigma=5,58, rating=11,6
3. Bob        : mu=21,7, sigma=5,58, rating=4,9
4. Dave       : mu=16,7, sigma=6,01, rating=-1,3

Analyse du classement final

Classement obtenu : Alice > Charlie > Bob > Dave

Joueur V-D Rating Sigma
Alice 3-0 15.2 6.01
Charlie 2-1 11.6 5.58
Bob 1-2 4.9 5.58
Dave 0-3 -1.3 6.01

Observations :

  1. Transitivité respectée : Alice > Charlie (directement) et Charlie > Bob (directement) implique Alice > Bob
  2. Rating conservatif : mu - 3σ pénalise les joueurs avec peu de matchs (plus grande incertitude)
  3. Sigma décroît : Plus de matchs = moins d’incertitude sur le skill

Pourquoi utiliser mu - 3σ ? - Évite de surclasser un joueur chanceux avec peu de matchs - Avec 3σ, on a ~99.7% de confiance que le vrai skill est supérieur - Xbox Live utilise cette métrique pour le matchmaking public

6. Extension aux Équipes

Modèle

Pour un match par équipes, la performance d’équipe est la somme des performances individuelles.

Modelisation de la performance d’équipe

Dans ce modèle 2v2, la performance d’une équipe est la somme des performances individuelles. Ce choix de modelisation implique que :

  • Un bon joueur peut “porter” un coequipier plus faible
  • La variance de l’équipe augmente avec le nombre de joueurs
  • L’attribution du credit est uniforme entre coequipiers
// Modele par equipes (2v2)

// Equipe 1 : Joueurs A et B
Variable<double> skillA2 = Variable.GaussianFromMeanAndVariance(25, 70).Named("skillA2");
Variable<double> skillB2 = Variable.GaussianFromMeanAndVariance(25, 70).Named("skillB2");

// Equipe 2 : Joueurs C et D
Variable<double> skillC = Variable.GaussianFromMeanAndVariance(25, 70).Named("skillC");
Variable<double> skillD = Variable.GaussianFromMeanAndVariance(25, 70).Named("skillD");

// Performances individuelles
Variable<double> perfA2 = Variable.GaussianFromMeanAndVariance(skillA2, 17).Named("perfA2");
Variable<double> perfB2 = Variable.GaussianFromMeanAndVariance(skillB2, 17).Named("perfB2");
Variable<double> perfC2 = Variable.GaussianFromMeanAndVariance(skillC, 17).Named("perfC2");
Variable<double> perfD2 = Variable.GaussianFromMeanAndVariance(skillD, 17).Named("perfD2");

// Performances d'equipe (somme)
Variable<double> perfEquipe1 = (perfA2 + perfB2).Named("perfEquipe1");
Variable<double> perfEquipe2 = (perfC2 + perfD2).Named("perfEquipe2");

// Equipe 1 gagne
Variable<bool> equipe1Gagne = (perfEquipe1 > perfEquipe2).Named("equipe1Gagne");
equipe1Gagne.ObservedValue = true;

InferenceEngine moteurEquipe = new InferenceEngine(new ExpectationPropagation());
moteurEquipe.Compiler.CompilerChoice = CompilerChoice.Roslyn;
moteurEquipe.ShowFactorGraph = true;  // Activer la generation du graphe de facteurs

Console.WriteLine("=== Match par equipes (2v2) ===");
Console.WriteLine("Equipe 1 (A+B) bat Equipe 2 (C+D)\n");

Console.WriteLine($"Skill A apres : {moteurEquipe.Infer<Gaussian>(skillA2).GetMean():F2}");
Console.WriteLine($"Skill B apres : {moteurEquipe.Infer<Gaussian>(skillB2).GetMean():F2}");
Console.WriteLine($"Skill C apres : {moteurEquipe.Infer<Gaussian>(skillC).GetMean():F2}");
Console.WriteLine($"Skill D apres : {moteurEquipe.Infer<Gaussian>(skillD).GetMean():F2}");

Console.WriteLine("\n=> Tous les membres de l'equipe gagnante voient leur skill augmenter");
=== Match par equipes (2v2) ===
Equipe 1 (A+B) bat Equipe 2 (C+D)

Compiling model...done.
Skill A apres : 27,99
Skill B apres : 27,99
Skill C apres : 22,01
Skill D apres : 22,01

=> Tous les membres de l'equipe gagnante voient leur skill augmenter

Analyse du match par équipes

Résultats :

Joueur Équipe Skill avant Skill après Delta
A Gagnante 25.00 27.99 +2.99
B Gagnante 25.00 27.99 +2.99
C Perdante 25.00 22.01 -2.99
D Perdante 25.00 22.01 -2.99

Observations cles :

  1. Attribution uniforme : Chaque membre recoit le même changement (priors identiques)
  2. Gain plus faible qu’en 1v1 : +2.99 vs +4.21 car l’information est “diluee” entre coequipiers
  3. Problème de l’attribution : Impossible de distinguer le “carry” du “porte”

Limitation : TrueSkill basique attribue également le credit/blame. Des extensions comme TrueSkill 2 (2018) utilisent des statistiques individuelles (kills, assists) pour une attribution plus fine.

// Visualisation du graphe de facteurs pour le match par equipes 2v2
display(HTML(FactorGraphHelper.GetLatestFactorGraphHtml()));
Model_08_19_26_02_22_49_78.svg
Model node0 25 node1 GaussianFromMeanAndVariance node0->node1 mean node3 skillA2 node1->node3 node2 70 node2->node1 variance node4 GaussianFromMeanAndVariance node3->node4 mean node6 perfA2 node4->node6 node5 17 node5->node4 variance node7 Plus node6->node7 a node9 perfEquipe1 node7->node9 node8 perfB2 node8->node7 b node16 Minus node9->node16 a node10 skillB2 node11 GaussianFromMeanAndVariance node10->node11 mean node11->node8 node12 17 node12->node11 variance node13 25 node14 GaussianFromMeanAndVariance node13->node14 mean node14->node10 node15 70 node15->node14 variance node18 vdouble88 node16->node18 node17 perfEquipe2 node17->node16 b node34 IsPositive node18->node34 x node19 perfC2 node20 Plus node19->node20 a node20->node17 node21 perfD2 node21->node20 b node22 skillD node23 GaussianFromMeanAndVariance node22->node23 mean node23->node21 node24 17 node24->node23 variance node25 25 node26 GaussianFromMeanAndVariance node25->node26 mean node26->node22 node27 70 node27->node26 variance node28 skillC node29 GaussianFromMeanAndVariance node28->node29 mean node29->node19 node30 17 node30->node29 variance node31 25 node32 GaussianFromMeanAndVariance node31->node32 mean node32->node28 node33 70 node33->node32 variance node35 True node34->node35

Lecture du graphe de facteurs - Match par équipes 2v2

Le graphe 2v2 illustre l’extension du modèle TrueSkill aux équipes :

Structure hiérarchique :

          skillA2   skillB2          skillC   skillD
             |         |                |        |
             v         v                v        v
          perfA2   perfB2           perfC2   perfD2
              \       /                  \      /
               \     /                    \    /
                v   v                      v  v
             perfEquipe1              perfEquipe2
                   \                      /
                    \                    /
                     v                  v
                   equipe1Gagne (observe = true)

Facteurs d’agregation : - Plus (ou +) : Combine les performances individuelles en performance d’équipe - IsGreaterThan : Compare les performances d’équipe

Propagation de credit : L’information “équipe 1 gagne” se propage : 1. Vers perfEquipe1 (augmente) et perfEquipe2 (diminue) 2. Via les facteurs Plus, vers chaque performance individuelle 3. Puis vers chaque skill individuel

Dilution du signal : Avec 4 joueurs au lieu de 2, l’information est diluee. Chaque joueur recoit environ la moitie du changement de skill qu’il aurait eu en 1v1. C’est le “problème d’attribution de credit” inherent aux jeux d’équipe.

7. Multi-joueurs (Free-for-all)

Modèle

Pour N joueurs, on decompose le résultat en N-1 comparaisons par paires : - 1er > 2e > 3e > … > Ne

Implementation avec contraintes d’ordre transitives

Pour N joueurs classes du 1er au Neme, nous imposons N-1 contraintes transitives : - perf[0] > perf[1] (1er bat 2e) - perf[1] > perf[2] (2e bat 3e) - … - perf[N-2] > perf[N-1] (avant-dernier bat dernier)

Infer.NET resout ce système de contraintes simultanement grace a EP.

// Modele multi-joueurs (4 joueurs)
// Resultat : P1 > P2 > P3 > P4

Variable<double>[] skillsMulti = new Variable<double>[4];
Variable<double>[] perfsMulti = new Variable<double>[4];

for (int i = 0; i < 4; i++)
{
    skillsMulti[i] = Variable.GaussianFromMeanAndVariance(25, 70).Named($"skill_P{i+1}");
    perfsMulti[i] = Variable.GaussianFromMeanAndVariance(skillsMulti[i], 17).Named($"perf_P{i+1}");
}

// Contraintes d'ordre : perf1 > perf2 > perf3 > perf4
Variable.ConstrainTrue(perfsMulti[0] > perfsMulti[1]);
Variable.ConstrainTrue(perfsMulti[1] > perfsMulti[2]);
Variable.ConstrainTrue(perfsMulti[2] > perfsMulti[3]);

InferenceEngine moteurMulti = new InferenceEngine(new ExpectationPropagation());
moteurMulti.Compiler.CompilerChoice = CompilerChoice.Roslyn;
moteurMulti.ShowFactorGraph = true;  // Activer la generation du graphe de facteurs

Console.WriteLine("=== Course multi-joueurs ===");
Console.WriteLine("Classement : P1 > P2 > P3 > P4\n");

for (int i = 0; i < 4; i++)
{
    Gaussian post = moteurMulti.Infer<Gaussian>(skillsMulti[i]);
    Console.WriteLine($"Joueur {i+1} (position {i+1}) : mu={post.GetMean():F2}, sigma={Math.Sqrt(post.GetVariance()):F2}");
}
=== Course multi-joueurs ===
Classement : P1 > P2 > P3 > P4

Compiling model...done.
Iterating: 
.........|.........|.........|.........|.........| 50
Joueur 1 (position 1) : mu=32,73, sigma=6,42
Joueur 2 (position 2) : mu=27,23, sigma=5,83
Joueur 3 (position 3) : mu=22,77, sigma=5,83
Joueur 4 (position 4) : mu=17,27, sigma=6,42

Analyse du mode multi-joueurs

Résultats de la course :

Position Joueur Skill mu Sigma Delta mu
1er P1 32.73 6.42 +7.73
2e P2 27.23 5.83 +2.23
3e P3 22.77 5.83 -2.23
4e P4 17.27 6.42 -7.73

Structure mathematique :

Les contraintes transitives P1 > P2 > P3 > P4 impliquent : - Le 1er et le dernier ont les changements les plus extremes - Les positions intermediaires ont des changements moderes - Sigma est plus eleve aux extremes (moins d’info directe)

Application : Ce modèle est utilise pour les jeux Battle Royale (Fortnite, PUBG) ou les courses (Mario Kart). Le placement complet apporte plus d’information qu’une simple victoire/defaite.

// Visualisation du graphe de facteurs pour le mode multi-joueurs
display(HTML(FactorGraphHelper.GetLatestFactorGraphHtml()));
Model_08_19_26_02_22_50_42.svg
Model node0 25 node1 GaussianFromMeanAndVariance node0->node1 mean node3 skill_P1 node1->node3 node2 70 node2->node1 variance node4 GaussianFromMeanAndVariance node3->node4 mean node6 perf_P1 node4->node6 node5 17 node5->node4 variance node7 Minus node6->node7 a node9 vdouble109 node7->node9 node8 perf_P2 node8->node7 b node13 Minus node8->node13 a node42 IsPositive node9->node42 x node10 skill_P2 node11 GaussianFromMeanAndVariance node10->node11 mean node11->node8 node12 17 node12->node11 variance node15 vdouble110 node13->node15 node14 perf_P3 node14->node13 b node19 Minus node14->node19 a node35 IsPositive node15->node35 x node16 skill_P3 node17 GaussianFromMeanAndVariance node16->node17 mean node17->node14 node18 17 node18->node17 variance node21 vdouble111 node19->node21 node20 perf_P4 node20->node19 b node28 IsPositive node21->node28 x node22 skill_P4 node23 GaussianFromMeanAndVariance node22->node23 mean node23->node20 node24 17 node24->node23 variance node25 25 node26 GaussianFromMeanAndVariance node25->node26 mean node26->node22 node27 70 node27->node26 variance node29 vbool14 node28->node29 node31 Equal node29->node31 B node30 True node30->node31 A node32 25 node33 GaussianFromMeanAndVariance node32->node33 mean node33->node16 node34 70 node34->node33 variance node36 vbool12 node35->node36 node38 Equal node36->node38 B node37 True node37->node38 A node39 25 node40 GaussianFromMeanAndVariance node39->node40 mean node40->node10 node41 70 node41->node40 variance node43 vbool10 node42->node43 node45 Equal node43->node45 B node44 True node44->node45 A

Lecture du graphe de facteurs - Multi-joueurs (Free-for-all)

Le graphe multi-joueurs montre une structure en chaîne de contraintes :

Topologie du graphe :

skill_P1 -> perf_P1 -\
                      >-- (P1 > P2)
skill_P2 -> perf_P2 -/                \
                      \                >-- P2 joue 2 rôles
skill_P2 -> perf_P2 ---\              /
                        >-- (P2 > P3)
skill_P3 -> perf_P3 ---/
                        \
                         >-- (P3 > P4)
skill_P4 -> perf_P4 ----/

Caractéristiques cles :

  1. Chaîne de comparaisons : N-1 facteurs IsGreaterThan pour N joueurs
  2. Joueurs intermediaires : P2 et P3 participent a deux comparaisons chacun
  3. Correlation induite : Les contraintes couplent les variables entre elles

Propagation EP iterative : Le graphe montre pourquoi EP necessite des itérations : - L’info de P1>P2 affecte P2 - L’info de P2>P3 affecte aussi P2 - Ces deux sources d’info doivent etre reconciliees

Complexite computationnelle : Contrairement au cas 1v1 (solution analytique), le cas multi-joueurs necessite des itérations EP. C’est pourquoi on observe “Iterating: …” dans la sortie. La complexite est O(N^2) par itération pour N joueurs.

8. Analyse d’Echecs (Elo Bayesien)

Application aux echecs

Nous appliquons TrueSkill aux echecs avec des paramètres adaptes a l’echelle Elo :

Paramètre Valeur TrueSkill standard Valeur echecs
mu_initial 25 1500
sigma_initial 8.33 350
beta 4.17 175

L’echelle est simplement multipliee par 60 pour correspondre aux ratings Elo traditionnels.

// Simulation de parties d'echecs

var chess = new TrueSkillOnline(muInit: 1500, sigmaInit: 350, beta: 175);

// Donnees historiques simulees
var partiesEchecs = new (string, string)[] {
    ("Magnus", "Fabiano"),
    ("Magnus", "Ian"),
    ("Fabiano", "Ian"),
    ("Magnus", "Fabiano"),
    ("Magnus", "Ian"),
    ("Ian", "Fabiano"),  // Upset!
    ("Magnus", "Fabiano"),
    ("Magnus", "Ian"),
    ("Fabiano", "Ian"),
    ("Magnus", "Ian")
};

Console.WriteLine("=== Classement Echecs (Elo Bayesien) ===");
Console.WriteLine("\nParties :");
foreach (var (g, p) in partiesEchecs)
{
    Console.WriteLine($"  {g} bat {p}");
    chess.EnregistrerMatch(g, p);
}

chess.AfficherClassement();
=== Classement Echecs (Elo Bayesien) ===

Parties :
  Magnus bat Fabiano
Compiling model...done.
  Magnus bat Ian
Compiling model...done.
  Fabiano bat Ian
Compiling model...done.
  Magnus bat Fabiano
Compiling model...done.
  Magnus bat Ian
Compiling model...done.
  Ian bat Fabiano
Compiling model...done.
  Magnus bat Fabiano
Compiling model...done.
  Magnus bat Ian
Compiling model...done.
  Fabiano bat Ian
Compiling model...done.
  Magnus bat Ian
Compiling model...done.

=== Classement ===
1. Magnus     : mu=1923,7, sigma=213,54, rating=1283,1
2. Fabiano    : mu=1344,7, sigma=183,39, rating=794,6
3. Ian        : mu=1217,4, sigma=182,68, rating=669,4

Analyse du classement echecs

Résultats :

Joueur Victoires Defaites Mu Sigma Rating
Magnus 7 0 1923.7 213.54 1283.1
Fabiano 2 4 1344.7 183.39 794.6
Ian 1 6 1217.4 182.68 669.4

Observations :

  1. Magnus domine : 7-0 (7 victoires sur les 10 matchs) avec un gain de +423.7 points (1500 -> 1923.7)
  2. L’upset compte : Ian bat Fabiano (match 6), ce qui explique pourquoi Ian n’est pas beaucoup plus bas
  3. Sigma decroit : Plus de matchs = plus de certitude sur le niveau reel

Comparaison avec le vrai classement FIDE (2024) :

Joueur FIDE Elo Notre estimation
Magnus Carlsen ~2830 1923.7
Fabiano Caruana ~2800 1344.7
Ian Nepomniachtchi ~2790 1217.4

Note : Les vrais ecarts sont plus faibles (30-40 points), car notre simulation suppose que Magnus gagne toujours, ce qui est irrealiste au plus haut niveau.

9. Exemple guide : Simuler un Tournoi

Enonce

Créez un tournoi avec 6 joueurs et simulez 15 matchs aleatoires. Comparez le classement final aux “vrais skills” que vous aurez définis.

Indice

  • Definissez des skills “vrais” pour chaque joueur
  • Simulez le résultat de chaque match en fonction des skills
  • Utilisez TrueSkillOnline pour mettre a jour les estimations

Simulation avec “vrais skills” connus

Cet exercice illustre un cas fondamental en statistique bayesienne : nous connaissons les vrais skills (simulation) et pouvons evaluer la qualite des estimations.

Protocole experimental : 1. Définir les vrais skills de 6 joueurs (inconnus du modèle) 2. Simuler 15 matchs ou le meilleur joueur gagne plus souvent 3. Comparer les estimations TrueSkill aux vrais skills

Notez que le joueur ne gagne pas toujours même s’il est meilleur : on ajoute du bruit (+/- 5 points) pour simuler la variance de performance.

// Exemple guide : Tournoi simule

// Vrais skills (inconnus du systeme)
var vraisSkills = new Dictionary<string, double>
{
    ["Elite1"] = 35,
    ["Elite2"] = 32,
    ["Moyen1"] = 25,
    ["Moyen2"] = 24,
    ["Debutant1"] = 18,
    ["Debutant2"] = 15
};

var joueurs = vraisSkills.Keys.ToArray();
var rng = new Random(42);
var tournoi = new TrueSkillOnline();

Console.WriteLine("=== Tournoi Simule ===");
Console.WriteLine("\nVrais skills :");
foreach (var kv in vraisSkills.OrderByDescending(x => x.Value))
    Console.WriteLine($"  {kv.Key}: {kv.Value}");

Console.WriteLine("\nMatchs :");

// 15 matchs aleatoires
for (int m = 0; m < 15; m++)
{
    // Choisir deux joueurs differents
    int i = rng.Next(joueurs.Length);
    int j;
    do { j = rng.Next(joueurs.Length); } while (j == i);
    
    string j1 = joueurs[i];
    string j2 = joueurs[j];
    
    // Simuler le match (le meilleur gagne avec plus de probabilite)
    double perf1 = vraisSkills[j1] + rng.NextDouble() * 10 - 5;  // +/- 5
    double perf2 = vraisSkills[j2] + rng.NextDouble() * 10 - 5;
    
    string gagnant = perf1 > perf2 ? j1 : j2;
    string perdant = perf1 > perf2 ? j2 : j1;
    
    Console.WriteLine($"  {gagnant} bat {perdant}");
    tournoi.EnregistrerMatch(gagnant, perdant);
}

tournoi.AfficherClassement();

Console.WriteLine("\n=> Comparez le classement estime aux vrais skills !");
=== Tournoi Simule ===

Vrais skills :
  Elite1: 35
  Elite2: 32
  Moyen1: 25
  Moyen2: 24
  Debutant1: 18
  Debutant2: 15

Matchs :
  Elite1 bat Debutant1
Compiling model...done.
  Elite2 bat Debutant1
Compiling model...done.
  Elite2 bat Debutant1
Compiling model...done.
  Elite2 bat Moyen1
Compiling model...done.
  Elite1 bat Debutant1
Compiling model...done.
  Elite1 bat Debutant1
Compiling model...done.
  Elite1 bat Debutant1
Compiling model...done.
  Moyen2 bat Debutant1
Compiling model...done.
  Elite2 bat Moyen2
Compiling model...done.
  Moyen2 bat Debutant1
Compiling model...done.
  Elite1 bat Debutant1
Compiling model...done.
  Elite2 bat Debutant1
Compiling model...done.
  Elite1 bat Moyen2
Compiling model...done.
  Moyen1 bat Debutant1
Compiling model...done.
  Elite1 bat Moyen1
Compiling model...done.

=== Classement ===
1. Elite1     : mu=34,3, sigma=5,08, rating=19,1
2. Elite2     : mu=33,8, sigma=5,48, rating=17,4
3. Moyen2     : mu=24,1, sigma=5,44, rating=7,8
4. Moyen1     : mu=22,4, sigma=5,92, rating=4,6
5. Debutant1  : mu=12,6, sigma=4,48, rating=-0,8

=> Comparez le classement estime aux vrais skills !

Analyse de la simulation

Comparaison vrais skills vs estimations :

Joueur Vrai skill Skill estimé Écart
Elite1 35 34.3 -0.7 ✓
Elite2 32 33.8 +1.8 ✓
Moyen1 25 22.4 -2.6
Moyen2 24 24.1 +0.1 ✓
Debutant1 18 12.6 -5.4
Debutant2 15 - (pas assez de matchs)

Observations :

  1. Élites bien identifiés : Le modèle distingue clairement le groupe “élite”
  2. Debutant1 sous-estimé : A joué beaucoup mais toujours perdu (malchance statistique)
  3. Debutant2 absent : Sans matchs, reste au prior (invisible dans le classement)

Leçon : TrueSkill converge vers les vrais skills avec suffisamment de matchs, mais des séries malchanceuses peuvent biaiser temporairement les estimations. L’incertitude (sigma) capture ce risque.

10. Resume

Concept Description
TrueSkill Système de classement bayesien
Skill Gaussienne N(mu, sigma^2)
Performance Skill + bruit gaussien
Match nul Différence de perf dans [-epsilon, epsilon]
Online learning Posterieurs -> Priors
Rating conservatif mu - 3*sigma

Forces de TrueSkill

  • Quantification explicite de l’incertitude via sigma
  • Convergence rapide pour les nouveaux joueurs (sigma eleve = grands changements)
  • Gestion native des équipes et multi-joueurs
  • Apprentissage en ligne efficace (O(1) par match)

Limitations

  • Suppose une skill stable dans le temps (pas d’apprentissage du joueur)
  • Attribution uniforme dans les équipes
  • Sensible au choix des hyperparametres (beta, epsilon)

Extensions modernes

  • TrueSkill 2 (2018) : Utilise les statistiques in-game pour attribution fine
  • Glicko-2 : Alternative populaire avec “volatilite” (changement de skill)
  • OpenSkill : Implementation open-source compatible multi-plateformes

Pour aller plus loin : L’article original “TrueSkill: A Bayesian Skill Rating System” (Herbrich, Minka & Graepel, 2007 — NIPS 20) détaille les approximations EP et les calculs de messages.

Prochaine étape

Dans Infer-9-Classification, nous explorerons :

  • La classification bayesienne
  • Le Bayes Point Machine
  • Les tests cliniques A/B bayesiens

11. Exercice : Ligue de Football : 4 Équipes

Enonce

Modelisez une ligue de football a 4 équipes avec TrueSkill. Résultats des matchs :

  • PSG bat Marseille (3-0)
  • Lyon bat Bordeaux (2-1)
  • Lyon bat PSG (2-1)
  • Lyon bat Marseille (1-0)
  1. Definissez une variable de skill gaussienne pour chaque équipe (a priori : Gaussian(100, 1/33))
  2. Encodez chaque résultat par le modèle TrueSkill (performance = Gaussian(skill, 1/beta^2))
  3. Inferez les skills posterieurs et etablissez le classement des équipes

Indice : Reutilisez la structure du modèle TrueSkill de la section 3.

// Exercice : Ligue de football avec TrueSkill - 4 equipes
double priorMean = 100.0;
double priorPrec = 1.0 / 33.333;
double beta = 8.333;  // Variance de performance

// TODO: Creer le moteur d'inference

// TODO: Definir les variables de skill pour les 4 equipes

// TODO: Pour chaque match, creer les variables de performance et observer que gagnant > perdant
// Exemple pour PSG bat Marseille :

// TODO: Inferer les skills posterieurs et afficher le classement
// Qui est classe premier ?
Console.WriteLine("Exercice a completer");
Exercice a completer

12. Exercice : Prediction de Match avec Incertitude

Enonce

Vous disposez des skills estimes de 4 joueurs après un tournoi. Votre objectif est de predire le résultat d’un match entre deux joueurs donnes, en retournant la probabilite que le joueur A gagne.

Données : Skills posterieurs après 10 matchs : - Alice : N(30, 5^2) - Bob : N(25, 4^2) - Charlie : N(22, 6^2) - Dave : N(20, 3^2)

Tâches : 1. Implementez un modèle qui predit la probabilite de victoire de Alice contre chaque autre joueur 2. Quel match est le plus incertain (probabilite la plus proche de 0.5) ? 3. Comment la probabilite change-t-elle si on double beta (variance de performance) ?

Indice

La probabilite que perf1 > perf2 se calcule en utilisant Variable.IsPositive sur la différence des performances. Observez la variable booleenne resultante avec moteur.Infer<Bernoulli>(...).

// Exercice : Prediction de victoire
// Skills posterieurs des joueurs
double muAlice = 30.0, sigmaAlice = 5.0;
double muBob = 25.0, sigmaBob = 4.0;
double muCharlie = 22.0, sigmaCharlie = 6.0;
double muDave = 20.0, sigmaDave = 3.0;
double beta = 4.17;  // Variabilite de performance

// TODO: Creer un modele qui calcule P(Alice gagne contre Bob)
// Etape 1: Definir les variables de skill (avec les posterieurs comme priors)
// Etape 2: Ajouter les performances (skill + bruit)
// Etape 3: Observer la contrainte perfAlice > perfBob
// Etape 4: Inférer P(Alice gagne) avec moteur.Infer<Bernoulli>(resultat)

// TODO: Repeter pour Alice vs Charlie et Alice vs Dave

// TODO: Identifier le match le plus incertain (P le plus proche de 0.5)

// TODO: Tester avec beta double (beta * 2). Laquelle des probabilites change le plus ?

Console.WriteLine("Exercice a completer : prediction de match");
Exercice a completer : prediction de match

13. Exercice : Suivi de l’apprentissage en ligne - Convergence du classement

Enonce

L’apprentissage en ligne (section 5) met a jour les skills après chaque match en utilisant les posterieurs comme nouveaux priors. Votre objectif est de tracer l’evolution des estimations de skill au fil d’une serie de 8 matchs entre 3 joueurs, afin de visualiser comment le système converge.

Joueurs et vrais skills (inconnus du modèle) : - Zoe : skill = 30 (forte) - Leo : skill = 25 (moyen) - Max : skill = 20 (faible)

Serie de matchs : 1. Zoe bat Leo 2. Zoe bat Max 3. Leo bat Max 4. Zoe bat Leo 5. Leo bat Zoe (upset) 6. Max bat Leo (upset) 7. Zoe bat Max 8. Leo bat Max

Tâches : 1. Utilisez la classe TrueSkillOnline définie en section 5 pour enregistrer les 8 matchs 2. Après chaque match, enregistrez le mu et le sigma de chaque joueur dans des listes 3. Affichez un tableau de l’evolution : pour chaque match, montrez le mu de chaque joueur 4. (Bonus) : Après le match 5 (upset Leo bat Zoe), comment evolue le sigma de Zoe par rapport a l’avant-match 5 ? L’upset augmente-t-il l’incertitude ?

Indices :

  • Initialisez TrueSkillOnline avec les paramètres par defaut
  • Après chaque EnregistrerMatch(), appelez GetSkill() pour chaque joueur et stockez GetMean() et Math.Sqrt(GetVariance())
  • Observez comment sigma diminue au fil des matchs (convergence) et comment un upset peut modifier la tendance
// Exercice : Suivi de l'apprentissage en ligne - Convergence du classement

string[] joueursOL = { "Zoe", "Leo", "Max" };
var tsOL = new TrueSkillOnline();

// Listes pour stocker l'evolution
var historiqueMu = new Dictionary<string, List<double>>
{
    ["Zoe"] = new List<double>(),
    ["Leo"] = new List<double>(),
    ["Max"] = new List<double>()
};
var historiqueSigma = new Dictionary<string, List<double>>
{
    ["Zoe"] = new List<double>(),
    ["Leo"] = new List<double>(),
    ["Max"] = new List<double>()
};

// Serie de matchs
var matchsOL = new (string gagnant, string perdant)[]
{
    ("Zoe", "Leo"),
    ("Zoe", "Max"),
    ("Leo", "Max"),
    ("Zoe", "Leo"),
    ("Leo", "Zoe"),  // Upset !
    ("Max", "Leo"),  // Upset !
    ("Zoe", "Max"),
    ("Leo", "Max")
};

// TODO 1 : Enregistrez chaque match et capturez les skills apres chaque match
// Indice : foreach (var (g, p) in matchsOL)
// {
//     tsOL.EnregistrerMatch(g, p);
//     foreach (var j in joueursOL)
//     {
//         var skill = tsOL.GetSkill(j);
//         historiqueMu[j].Add(skill.GetMean());
//         historiqueSigma[j].Add(Math.Sqrt(skill.GetVariance()));
//     }
// }

// TODO 2 : Affichez le tableau d'evolution des mu
// Indice : Console.WriteLine("Match | Zoe mu | Leo mu | Max mu");
// for (int i = 0; i < matchsOL.Length; i++)
//     Console.WriteLine($"{i+1} | {historiqueMu["Zoe"][i]:F1} | {historiqueMu["Leo"][i]:F1} | {historiqueMu["Max"][i]:F1}");

// TODO 3 : Affichez le classement final
// tsOL.AfficherClassement();

// TODO 4 : (Bonus) Analysez l'effet de l'upset (match 5) sur le sigma de Zoe
// Indice : comparez historiqueSigma["Zoe"][3] (avant upset) et historiqueSigma["Zoe"][4] (apres upset)
// L'upset (Leo bat Zoe) est-il "surprenant" pour le modele ? Cela augmente-t-il sigma ?

Console.WriteLine("Exercice a completer : suivi apprentissage en ligne");
Exercice a completer : suivi apprentissage en ligne

14. Pour aller plus loin : les formules fermées de TrueSkill

La mise à jour closed-form de TrueSkill (Herbrich, Minka & Graepel, NeurIPS 2007) — les fonctions de troncature V(t), W(t) et leur vérification numérique exacte contre le moteur EP de la section 3 — fait l’objet de la lettre dédiée Infer-8b-TrueSkill-Formules-Fermees.

Conclusion

Ce notebook a presente le système TrueSkill : classement bayesien par matchs 1v1, matchs nuls, apprentissage en ligne et extensions multi-joueurs/équipes.

Concept Point cle
Skill Gaussienne N(mu, sigma^2) : estimation + incertitude
Performance Skill + bruit : variabilite d’un match donne
Apprentissage en ligne Posterieur(n-1) = Prior(n), complexite O(1) par match
Match nul ConstrainBetween(-eps, +eps) : reduit sigma sans changer mu
Rating conservatif mu - 3*sigma : borne inferieure a 99.7% de confiance
Distribution Rôle
Gaussian Skills et performances des joueurs
ExpectationPropagation Algorithme pour les facteurs de comparaison non-conjugues

Apport TrueSkill : Contrairement a Elo (score ponctuel), TrueSkill propage l’incertitude via sigma. Un nouveau joueur (sigma eleve) converge rapidement ; un joueur etabli (sigma faible) est stable. L’apprentissage en ligne permet de mettre a jour des millions de joueurs en temps reel sur Xbox Live.

Retour au sommet