Tester l'équité des dés.

Je racontais dans un article précedent que pour améliorer ma connaissance du typescript, et à l'occasion de la sortie de la nouvelle édition 5.5; j'avais commencé à implémenter les règles de Donjons & Dragons.

Dans ce jeu de rôle, comme dans la plupart des jeux de rôle (pas tous), une des composantes principales du système de jeu est le lancer de dés. Il faut donc que le notre soit irréprochable.

Définir par les tests.

Avant de parler statistiques et math, parlons un peu méthode.

Quand vous vous apprétez à coder un nouveau système, la première étape n'est souvent pas de déterminer comment vous allez faire, quel langage, quel algorithme,... Mais plutôt comment on va déterminer que le projet est clôt et réussi.

Je m'explique.

Le vrai métier d'un·e dévelopeureuse c'est de modéliser : transcrire en un code formel des besoins exprimés de manière naturelle ( par opposition à formelle ). Attention, je ne dis pas que c'est le travail du chercheur ou de la chercheuse en informatique, qui travaillent sur l'informatique en tant qu'outil technique. Mais pour les gens qui gagnent leur vie avec le développement informatique, la plus grande valeur ajoutée une fois la syntaxe du langage maitrisée, c'est de savoir définir ce qu'on attend du code.

Les méthodes diffèrent mais comme je l'avais dis une fois sur les réseaux de manière à moitié sérieuse, j'ai tendance à apprécier la méthode qu'on appelle le BDD (Behavior-Driven development). Si on vous demande "Ha tiens j'aimerais une app qui me prédit la Température de demain", j'aurais tendance à écrire ceci : 


function tomorrowTemp():number {
  return 14.5 ; //Température moyenne en France
}

(il y a une très bonne note de XKCD là dessus mais je crois qu'elle n'est que dans l'édition papier de ses "How to")

Et là vous allez me dire

  • Mais c'est complétement débile et complétement faux ?!.
  • Très bien, vous avez raison, pourquoi c'est faux ?

(évidemment que ca se passe pas littéralement comme ça)

  • C'est pas la même température à Toulouse et à Lyon ?! Il fait pas la même température partout
  • Ok donc déjà vous voulez une température par ville
  • et puis ca peut pas etre la même Témprature toute l'année.
  • …par date donc
  • Et puis c'est faux ? Il a pas fait 14 tous les jours ces dernières années
  • Ok donc pour valider la fonction on va la vérifier sur les archives de températures
  • Et faut pas que ca se trompe dans les prédictions plus de 95% du temps
  • (donc sans doute que ce qu'il veut c'est une cross entropy sur la cross validation )

Etc.

Le dialogue est extrêmement caricatural mais je pense qu'il illustre bien le fond de l'idée qui est de commencer par définir formellement ce qu'on attend d'un programme, qu'on doit considérer comme une boite noire, au lieu de se concentrer sur comment il va le faire. Et si vous trouvez ça vraiment débile, pensez à tous les programmes en cours d'intelligence artificielle ( nous somme en Novembre 2025 au moment où ce billet est écrit) qui ont juste spécifié "on va foutre de l'IA " au lieu de "on va améliorer le taux de détection", "on va réduire le temps d'attente", "on va augmenter la détection de taux de defection".

Pour être très concret, et juste pour montrer à quoi ca peut ressembler, cela veut dire que quelque part dans votre projet vous allez avoir un fichier qui ressemble à ça


import { describe, it, expect } from "vitest";
import DiceCup from "@models/DiceCup";
import constants from "@stdio/constant";

describe("Dice diceDescriptor string Parser", () => {
  it("should create One four sided face if you use 1D4", () => {
    const myCup = new DiceCup("1D4");

    expect(myCup.modifier).toBeUndefined();
    expect(myCup.dice.length).toBe(1);
    expect((myCup.dice[0].dieValue = 4));
  });
  
  it("should create not create 1Dsix+douze", () => {
    const myCup = new DiceCup("1Dsix+douze");

    expect(myCup.modifier).toBeUndefined();
    expect(myCup.dice.length).toBe(0);
  });

  it("should create not create 1Dboule", () => {
    const myCup = new DiceCup("1Dboule");

    expect(myCup.modifier).toBeUndefined();
    expect(myCup.dice.length).toBe(0);
  });

})
describe("Fair throw and expected value", () => {
  it("should respect chiSquared criteria for 1D6", () => {
    const startTime: number = performance.now();
    const faces = 6;
    const maxChisquared = constants.chiSquared005Table[faces];

    let myCup = new DiceCup("1D" + faces);
    const nRoll = 60000;
    const valueCount = new Array(faces).fill(0);

    for (let i = 0; i < nRoll; i++) {
      const r = myCup.roll();
      valueCount[r - 1]++;
    }

    /** Ok now go chi squared */
    const valuesExpected = new Array(faces).fill(nRoll / faces);

    let chiSquared = 0;
    for (let i = 0; i < faces; i++) {
      const a = (valueCount[i] - valuesExpected[i]) ** 2;
      chiSquared += a / (nRoll / faces);
    }
    const endTime: number = performance.now();
    const elapsedTime = endTime - startTime;
    expect(elapsedTime).toBeLessThan(200);
    expect(chiSquared).toBeLessThan(maxChisquared);
  });
})

Le fichier ci-dessus utilise une syntaxe courante à base de mots clés comme "it","should","expect", qui sont des vrais mots clé informatique dans ce cadre, interprétés très formellement par l'ordinateur.

Mais revenons en au sujet de l'article et regardons plus en détail ce test "it should respect chiSquared criteria for 1D6"

Quantifier l'aléatoire

Comme je suis très sérieux, je veux écrire un test pour vérifier que mes dés virtuels sont corrects pour jouer à Donjons & Dragons. Seuleument, la difficulté intrinsèque à tester un lancer de dés est qu'il n'y aucune certitudes sur ce qu'on peut attendre du résultat.

Dois-je lancer les dés 6 fois et vérifier que j'ai bien chaque chiffre ? 60 fois et vérifier que chaque chiffre apparait 10 fois ? Non, ca serait pas systématique. Alors lancer 100 fois 60 fois 1D6 et vérifier que dans 50% des cas j'ai bien 10 fois chaque chiffre ?

En matière d'aléatoire, les statistiques ne nous donnent qu'une certitude : plus j'effectue un même tirage (lancer un dé, une pièce, tirer une boule d'un sac,…) et plus le résultat va se rapprocher de la distribution théorique espérée.

Distribution

Le cœur des tests statistiques ce sont les distributions. Une distribution ce n'est ni plus ni moins qu'une valeur avec une autre valeur en face qui dit dans quelle proportion je devrais la trouver si j'effectue mon operation un million de fois, 100 milllions de fois, 100 000 milliards de fois…

Cela peut prendre 2 formes :

1. Un tableau qui recence toutes les valeurs et met en face la proportion attendue

1 1/6
2 1/6
3 1/6
4 1/6
5 1/6
1 1/6

2. Une fonction qui vous dit très précisemment pour chaque nombre (de son domaine) la proportion de valeur autour de ce nombre (c'est en réalité plus compliqué que ça mais ce n'est pas le sujet aujourd'hui)

f ( x ) = 1 σ ⁢ 2 ⁢ π ⁢ e - ( x - μ ) 2 2 ⁢ σ 2

Dans le cas qui nous intéresse on a juste besoin du tableau de nombre, qui est la "distribution d'un dé à 6 faces non biaisé". Il va donc falloir trouver un test qui vérifie que la distribution qu'on obtient avec un nombre suffisamment grand de lancer est proche de la distribution espérée.

χ²

Heureusement,ce test là est un test bien connu et maitrisé en statistique, c'est même l'un des premiers que vous apprenez, et s'appelle le test du chi-squared. La page wikipedia vous en dira plus mais elle un peu rude, même si elle donne précisemment le dé à 6 faces qui nous interesse comme exemple d'application.

Sans rentrer dans les détails de la démonstration, qui peut être difficile, voyons au moins le raisonnement et comment l'utiliser en tant que dev. La première utilité à noter c'est que le test du chi-squared vous donne pour n'importe quelle distribution un nombre et un seul. C'est particulièrement pratique pour nos tests puisqu'on va pouvoir lancer nos dés virtuels des milliers fois et réduire tous ces lancers à un seul nombre, puis décider quelle valeur notre test attend pour ce nombre.

Je met le raisonnement derrière ce nombre pour celles et ceux que ca intéressent

  1. On connait la loi qui régit le nombre de 1 ( et de 2, et de 3, et de 4...) que vous allez obtenir en lancant 1 million de fois un dé à 6 faces : c'est la même que celle de pile ou face. En effet, à chaque tirage vous avez 1 chance sur 6 d'obtenir un 1 et 5 chances sur 6 de NE PAS obtenir un 1. Pareil pour les autres valeurs.
  2. Si considère donc chaque tirage comme "obtenir un 1 ou ne pas obtenir un 1" , on a une formule qui nous dit combien on aura de 1 à la fin, de 2, de 3 etc…
  3. Evidemment on sait tous que en moyenne on aura 1/6 de chaque mais la loi ci dessus est beaucoup plus puissante, elle nous donne la probabilité qu'on ait a peu pres 10 000 fois le nombre 5 si on fait 60 000 lancer mais aussi la probabilité qu'on l'ait à peu pres 6000 fois, à peu pres 2000 fois, etc. Car souvenez-vous que meme si évènement se produit en moyenne 10000 fois sur 60000, ça ne veut pas du tout dire que il se produira 10000 fois à chaque fois que vous faites 60000 lancers. Le point important ici est que le compte de chaque valeur suit une distribution Normale (parfois appelée Gaussienne)
  4. Il se trouve qu'une autre loi, qui sert de titre à ce paragraphe, vous donne la valeur espéré des comptes, en gros, de plusieurs variables suivant une loi gaussienne, soit exactement notre cas !

    5. Bref, comme on a eu des cours de statistiques, on connait une loi qui nous dit quelle valeur espérer si je fais la somme des carrés (les carrés permettent de faciliter certaines operations mathématiques comme la dérivation, vous tracassez pas) de la difference entre ce que j'observe et ce que j'espere.

    Dont acte

    
const nRoll = 60000; // On lance le dé un nombre suffisamment grand de fois
const valueCount = new Array(faces).fill(0); // Au début , chaque nombre est obtenu zero fois

for (let i = 0; i < nRoll; i++) { // On va faire 60 000 jets virtuelles
  const r = myCup.roll(); // On note le résultat
  valueCount[r - 1]++; // On rajouter "+1" dans la case correspondante ( '0ème' case pour le résultat 1 et '5ème' case poru le résultat 6)
}

/** Ok now go chi squared */
const valuesExpected = new Array(faces).fill(nRoll / faces); // Notre distribution idéale POUR UN DE NON BIAISE serait de 1/6 de 60 000 pour chaque valeur de dé

let chiSquared = 0;
for (let i = 0; i < faces; i++) {    // Pour chaque valeur possible de dé
  const a = (valueCount[i] - valuesExpected[i]) ** 2; // on mesure la difference entre le nombre de fois où on l'a vue et le nombre de fois qu'on aurait espéré la voir, et on met au carré
  chiSquared += a / (nRoll / faces); // on divise par la le nombre de fois espéré (pour normaliser la somme) puis on additionne au total
}
const endTime: number = performance.now(); // Tant qu'on y est on mesure aussi le temps d'exécution
const elapsedTime = endTime - startTime;
expect(elapsedTime).toBeLessThan(200);
expect(chiSquared).toBeLessThan(maxChisquared);   // et enfin on vérifie que notre chisquared reste inférieur à une certaine valeur standard des statistiques.