TrueSkill — un classement bayésien pour le baby-foot connecté

On a décrit l’architecture Rails de Foosball Society il y a un an et demi. Le système de classement qu’on avait mis en place est simple : +5 par partie jouée, +5 pour la victoire, plus ou minus le delta de score. Ça fonctionne. Mais au bout de quelques centaines de parties, les joueurs réguliers ont commencé à poser les bonnes questions :

“Pourquoi je suis classé en dessous de Marc alors que je le bats 3 fois sur 4 ?”

Parce que Marc joue plus souvent. Dans notre système, tout le monde monte — jouer, même en perdant, rapporte des points. C’est un choix de design pour l’engagement : on ne veut pas qu’un joueur qui perd quelques parties se retrouve à zéro et arrête de jouer. Mais c’est un choix qui sacrifie la précision du classement au profit de la rétention.

On a décidé de proposer les deux. Chaque compte peut basculer entre deux modes de classement :

Le classement classique — celui qui existe déjà. Inspiré des systèmes à points façon StarCraft, League of Legends, ou les jeux de ranked ladder. Tu gagnes des points en jouant, tu en gagnes plus en gagnant. Tout le monde progresse, les écarts se creusent lentement. C’est motivant, c’est lisible, c’est addictif. C’est le mode par défaut.

Le classement TrueSkill — un algorithme développé par Microsoft Research pour Xbox Live. Au lieu d’un score unique, il maintient une distribution de probabilité de ton niveau : une gaussienne avec une moyenne (μ, ce qu’on pense être ton vrai niveau) et un écart-type (σ, à quel point on en est sûr). C’est mathématiquement plus juste, mais aussi plus opaque pour l’utilisateur.

Pourquoi deux classements ?

La réponse courte : parce qu’ils servent des objectifs différents.

Le classement classique est un score de progression. Il récompense l’investissement. C’est le bon choix pour un bar où l’objectif est que les gens continuent de jouer — personne ne veut voir son score baisser après une soirée de parties.

Le classement TrueSkill est une estimation de compétence. Il récompense le talent. C’est le bon choix pour les compétiteurs qui veulent savoir qui est vraiment le meilleur — indépendamment du nombre de parties jouées.

On propose les deux parce que notre communauté a les deux profils. Les joueurs du bar d’en bas veulent un ranking fun. L’équipe de compétition de l’entreprise qui a six tables Tekbak veut un ranking juste. Et nous, entre développeurs, on voulait surtout un prétexte pour implémenter un algorithme de Microsoft Research.

TrueSkill : l’intuition

L’algorithme TrueSkill a été publié en 2006 par Ralf Herbrich, Tom Minka et Thore Graepel chez Microsoft Research. Il est utilisé par Xbox Live pour le matchmaking — l’idée étant de mettre en face des joueurs de niveau similaire pour que les parties soient intéressantes.

L’article de référence, c’est le papier de Moserware — “The Math Behind TrueSkill” — qui rend l’algorithme accessible sans un doctorat en statistiques. On l’a relu trois fois avant de comprendre vraiment ce qui se passe sous le capot.

L’idée fondamentale : on ne connaît pas le vrai niveau d’un joueur. On ne peut que l’estimer. Et cette estimation a un degré d’incertitude.

Prenons un nouveau joueur. On ne sait rien de lui. Sa compétence pourrait être n’importe quoi. On modélise cette ignorance par une gaussienne large — une courbe en cloche centrée sur 25 (le niveau moyen) avec un écart-type élevé (σ = 8.33). Ça veut dire : “on pense qu’il est moyen, mais on n’en est pas du tout sûr”.

Au fur et à mesure qu’il joue, deux choses se passent :

1. μ bouge — si le joueur gagne, μ monte. S’il perd, μ descend. L’ampleur du mouvement dépend de contre qui il a joué. Battre un joueur fort fait monter μ beaucoup plus que battre un joueur faible.

2. σ rétrécit — chaque partie apporte de l’information. Plus on a de données, plus on est sûr de notre estimation. Un joueur avec 200 parties aura un σ minuscule — on sait à peu près où il se situe.

Le score affiché est μ - 3σ. C’est une estimation conservative : on prend la moyenne et on retranche trois écarts-types. Un nouveau joueur avec μ=25 et σ=8.33 a un score de 25 - 3×8.33 = 0. C’est volontaire : on ne veut pas qu’un joueur qui n’a joué que deux parties (et qui a eu de la chance) se retrouve en tête du classement. Le score ne monte que quand on a à la fois un μ élevé et un σ faible — c’est-à-dire quand on est bon et qu’on l’a prouvé sur un nombre suffisant de parties.

Les maths, sans la douleur

Le cœur de TrueSkill, c’est la mise à jour bayésienne. Après chaque partie, on met à jour les distributions de tous les joueurs en utilisant le résultat observé.

La mise à jour repose sur les gaussiennes tronquées. L’intuition est la suivante : si le joueur A (μ=30, σ=3) bat le joueur B (μ=25, σ=4), TrueSkill calcule la probabilité que ce résultat se produise étant donné les distributions actuelles. Si le résultat est surprenant (un joueur faible bat un joueur fort), la mise à jour est forte. Si c’est attendu, la mise à jour est faible.

Concrètement, les formules de mise à jour sont :

Les deux fonctions clés sont v (la fonction de mise à jour de μ) et w (la fonction de mise à jour de σ). Ce sont des rapports de la densité gaussienne et de sa fonction de répartition — ce qu’on appelle des moments de la gaussienne tronquée.

L’intuition derrière v : c’est le “facteur surprise”. Si le résultat est attendu (le meilleur joueur gagne), v est petit et μ bouge peu. Si le résultat est surprenant (le plus faible gagne), v est grand et μ bouge beaucoup. C’est ce qui fait converger le système — après suffisamment de parties, les μ se stabilisent aux bons endroits.

L’intuition derrière w : c’est le “facteur d’apprentissage”. Après chaque partie, on en sait un peu plus sur le joueur, donc σ diminue. Mais w garantit que σ ne descend jamais à zéro — il y a toujours une incertitude résiduelle, parce qu’un joueur peut progresser (ou régresser) avec le temps.

L’implémentation : de la gem au fork

On a commencé avec la gem trueskill de saulabs. Elle implémente l’algorithme de base avec le factor graph (le graphe de facteurs utilisé pour propager les messages bayésiens). En Ruby, ça donne :

# Utilisation basique de la gem saulabs/trueskill
require 'saulabs/trueskill'

include Saulabs::TrueSkill

# Deux joueurs avec leurs ratings actuels
player1 = Rating.new(30.0, 3.0)  # μ=30, σ=3
player2 = Rating.new(25.0, 4.0)  # μ=25, σ=4

# Le joueur 1 a gagné
graph = FactorGraph.new(
  { player1 => [1] },  # rang 1 = gagnant
  { player2 => [2] }   # rang 2 = perdant
)
graph.update_skills

# player1 et player2 sont mis à jour in-place
puts "Player 1: μ=#{player1.mean}, σ=#{player1.deviation}"
puts "Player 2: μ=#{player2.mean}, σ=#{player2.deviation}"

Ça marche pour le cas simple (1v1). Mais on a vite rencontré des limites :

Le 2v2. Au baby-foot, on joue souvent en double. TrueSkill gère les équipes nativement — c’est même une de ses forces par rapport à Elo. L’implémentation de la gem les supporte, mais les performances de la skill estimée en double (la somme des μ des coéquipiers) ne convergeaient pas bien avec nos paramètres. On a dû ajuster la manière dont le résultat d’un double est réparti entre les deux coéquipiers.

La dynamique temporelle. La gem assume que σ ne remonte jamais. Or, un joueur qui n’a pas joué depuis trois mois n’est plus le même — il a peut-être progressé ou régressé. On a ajouté un facteur de “dynamique temporelle” (τ, tau) qui fait remonter σ lentement au fil du temps. C’est dans le papier original de Microsoft, mais pas dans la gem.

Le draw margin. Au baby-foot, il n’y a pas de match nul. La gem gère les draws avec un paramètre ε (epsilon), qu’on met à 0. Mais le code faisait quand même passer par le chemin du draw dans certains cas limites. On a simplifié.

Voici notre version modifiée du calcul de mise à jour :

module Foosball
  class TrueSkillCalculator
    # Paramètres calibrés pour le baby-foot
    INITIAL_MEAN      = 25.0
    INITIAL_DEVIATION = INITIAL_MEAN / 3.0  # σ = 8.33
    BETA              = INITIAL_DEVIATION / 2.0  # β = 4.17
    DYNAMICS_FACTOR   = INITIAL_DEVIATION / 100.0  # τ = 0.083
    DRAW_PROBABILITY  = 0.0  # pas de match nul au baby-foot

    TrueSkillRating = Struct.new(:mean, :deviation) do
      def score
        mean - 3 * deviation
      end
    end

    def initialize(winner_ratings, loser_ratings)
      @winners = winner_ratings  # Array de TrueSkillRating
      @losers  = loser_ratings
    end

    def compute
      # Appliquer la dynamique temporelle (σ remonte légèrement)
      apply_dynamics(@winners)
      apply_dynamics(@losers)

      # Somme des μ et σ² par équipe
      winner_mean  = @winners.sum(&:mean)
      loser_mean   = @losers.sum(&:mean)
      winner_var   = @winners.sum { |r| r.deviation**2 }
      loser_var    = @losers.sum { |r| r.deviation**2 }

      # Paramètre c (normalisation)
      team_size = @winners.size + @losers.size
      c = Math.sqrt(winner_var + loser_var + team_size * BETA**2)

      # Différence normalisée
      t = (winner_mean - loser_mean) / c

      # Facteurs de mise à jour (gaussienne tronquée)
      v = v_function(t)
      w = w_function(t, v)

      # Mise à jour de chaque joueur gagnant
      @winners.each do |r|
        mean_factor = r.deviation**2 / c
        var_factor  = r.deviation**2 / c**2
        r.mean      = r.mean + mean_factor * v
        r.deviation = r.deviation * Math.sqrt(1 - var_factor * w)
      end

      # Mise à jour de chaque joueur perdant
      @losers.each do |r|
        mean_factor = r.deviation**2 / c
        var_factor  = r.deviation**2 / c**2
        r.mean      = r.mean - mean_factor * v
        r.deviation = r.deviation * Math.sqrt(1 - var_factor * w)
      end
    end

    private

    def apply_dynamics(ratings)
      ratings.each do |r|
        r.deviation = Math.sqrt(r.deviation**2 + DYNAMICS_FACTOR**2)
      end
    end

    # v(t) = N(t) / Φ(t) — le ratio de Mills
    def v_function(t)
      gaussian_pdf(t) / gaussian_cdf(t)
    end

    # w(t, v) = v × (v + t)
    def w_function(t, v)
      v * (v + t)
    end

    def gaussian_pdf(x)
      Math.exp(-0.5 * x**2) / Math.sqrt(2 * Math::PI)
    end

    def gaussian_cdf(x)
      0.5 * (1 + Math.erf(x / Math.sqrt(2)))
    end
  end
end

C’est ce graphe qui rend TrueSkill si élégant : le facteur de mise à jour (la fonction v) est asymétrique. Quand un joueur faible bat un joueur fort (côté gauche), la mise à jour est massive — le système apprend beaucoup de cette surprise. Quand un joueur fort bat un joueur faible (côté droit), la mise à jour est minime — rien de nouveau sous le soleil.

C’est exactement ce que notre classement à points ne faisait pas. Gagner 5-0 contre le dernier du classement rapportait autant que gagner 5-0 contre le premier. TrueSkill corrige ça de manière mathématiquement fondée.

L’intégration dans le pipeline

On branche le calcul TrueSkill dans le StatisticsWorker existant. Après chaque partie, en plus du calcul de points classique, on met à jour les paramètres TrueSkill :

# app/workers/statistics_worker.rb — modifié
class StatisticsWorker
  include Sidekiq::Worker

  def perform(game_id)
    game = Game.find(game_id)

    # 1. Classement classique (inchangé)
    game.game_participations.each do |gp|
      gp.update_rating_for_event(game.event)
    end

    # 2. Classement TrueSkill
    update_trueskill(game)

    # 3. Recalcul des rankings
    RecomputeRankingsWorker.perform_async(game.game_type, game.genders)
  end

  private

  def update_trueskill(game)
    game_type = game.single? ? :single : :double

    winner_ratings = game.winners.map { |u| load_trueskill_rating(u, game_type) }
    loser_ratings  = game.losers.map  { |u| load_trueskill_rating(u, game_type) }

    calculator = Foosball::TrueSkillCalculator.new(winner_ratings, loser_ratings)
    calculator.compute

    game.winners.zip(winner_ratings).each { |u, r| save_trueskill_rating(u, r, game_type) }
    game.losers.zip(loser_ratings).each   { |u, r| save_trueskill_rating(u, r, game_type) }
  end

  def load_trueskill_rating(user, game_type)
    ts = user.trueskill_ratings.find_by(game_type: game_type)
    if ts
      Foosball::TrueSkillCalculator::TrueSkillRating.new(ts.mean, ts.deviation)
    else
      Foosball::TrueSkillCalculator::TrueSkillRating.new(
        Foosball::TrueSkillCalculator::INITIAL_MEAN,
        Foosball::TrueSkillCalculator::INITIAL_DEVIATION
      )
    end
  end

  def save_trueskill_rating(user, rating, game_type)
    ts = user.trueskill_ratings.find_or_initialize_by(game_type: game_type)
    ts.update!(
      mean:      rating.mean,
      deviation: rating.deviation,
      score:     rating.score
    )
  end
end

Le modèle TrueskillRating est simple — trois colonnes numériques par joueur et par game_type :

class TrueskillRating < ActiveRecord::Base
  belongs_to :user

  validates :game_type, presence: true,
    inclusion: { in: %w[single double] }
  validates :mean, :deviation, :score, presence: true

  scope :for_game_type, ->(type) { where(game_type: type) }
  scope :ranked, -> { order(score: :desc) }
end

Et la migration :

class CreateTrueskillRatings < ActiveRecord::Migration
  def change
    create_table :trueskill_ratings do |t|
      t.references :user, null: false, index: true
      t.string  :game_type, null: false
      t.float   :mean,      null: false, default: 25.0
      t.float   :deviation, null: false, default: 8.333
      t.float   :score,     null: false, default: 0.0
      t.timestamps
    end

    add_index :trueskill_ratings, [:user_id, :game_type], unique: true
    add_index :trueskill_ratings, [:game_type, :score]
  end
end

Le choix du mode côté utilisateur

Côté app et site web, un toggle dans le profil permet de basculer entre les deux classements. Techniquement, les deux sont toujours calculés en parallèle — le toggle ne change que l’affichage :

class User < ActiveRecord::Base
  has_many :trueskill_ratings

  enum ranking_mode: { classic: 0, trueskill: 1 }

  def displayed_ranking(game_type)
    if trueskill?
      trueskill_ratings.for_game_type(game_type).first&.score || 0
    else
      send("cached_rating_#{game_type}") || 1000
    end
  end

  def displayed_position(game_type)
    if trueskill?
      # Position dans le classement TrueSkill
      TrueskillRating
        .for_game_type(game_type)
        .where("score > ?", displayed_ranking(game_type))
        .count + 1
    else
      send("cached_ranking_#{game_type}") || 0
    end
  end
end

Le classement global affiché sur le site dépend du mode de chaque utilisateur. Mais les tableaux de classement (leaderboards) montrent toujours les deux côte à côte — on peut voir sa position dans les deux systèmes en même temps.

Les résultats : ce que TrueSkill nous a appris

Après trois mois de données en parallèle sur une base de ~200 joueurs actifs et ~5000 parties, les résultats sont intéressants.

La convergence est rapide. Après 15-20 parties, le σ d’un joueur est suffisamment bas pour que son score TrueSkill soit stable. C’est bien plus rapide que Elo, qui nécessite typiquement 50+ parties pour converger.

Le top 10 est différent. Le classement à points met en tête les joueurs qui jouent le plus. Le classement TrueSkill met en tête les joueurs qui gagnent contre des adversaires forts. Deux joueurs qui étaient 35e et 42e en classique sont passés 3e et 5e en TrueSkill — ils jouent moins, mais ils battent régulièrement les meilleurs.

Le 2v2 est mieux géré. En classique, un bon joueur en double avec un mauvais joueur prend une pénalité injuste en cas de défaite. TrueSkill répartit la mise à jour en tenant compte du niveau des deux coéquipiers — le bon joueur perd moins de μ que le mauvais.

Le paramètre β est critique. On a commencé avec β = σ/2 (la valeur par défaut de Microsoft). Le baby-foot étant plus chaotique que Halo 2, on a dû monter β pour que les upsets ne déstabilisent pas trop les classements. On a fini sur β ≈ 5.5 après plusieurs itérations.

Classique vs TrueSkill : le bon outil pour le bon usage

Après ces mois de recul, notre conviction est que les deux approches ont leur place :

Le classement classique est meilleur pour l’engagement. Il est lisible, il est motivant, il ne punit jamais. Quand on installe un baby-foot dans un bar et qu’on veut que les gens scannent leur badge et reviennent le lendemain, c’est le bon choix. C’est un mécanisme de gamification plus qu’un classement — et il remplit très bien ce rôle.

Le TrueSkill est meilleur pour la compétition. Il est juste, il converge vite, il gère les équipes. Quand une entreprise organise un tournoi et veut savoir qui est vraiment le meilleur joueur, c’est le bon choix. C’est un outil statistique, et les joueurs qui s’y intéressent sont ceux qui aiment comprendre pourquoi ils sont classés où ils sont.

Et pour nous, développeurs, c’était surtout un excellent prétexte pour relire un papier de Microsoft Research, coder des gaussiennes tronquées en Ruby, et débattre pendant des heures du bon réglage de β autour du baby-foot. Le genre de projet qu’on fait parce que c’est intéressant — et qui se trouve aussi être utile.

---

Pour le contexte complet du projet Foosball Society : l’architecture Rails, le moteur de règles en AST, et les briques embarquées (extension C pour I2C, rendu typographique LED).