Le Mastermind et la théorie de l'information : chaque indice réduit l'incertitude
Quand tu joues un essai au mastermind et que tu reçois des pions noirs et blancs, tu gagnes de l'information au sens mathématique du terme. La théorie de l'information, fondée par Claude Shannon en 1948, permet de la mesurer en bits. Le mastermind en est une illustration très propre : on peut compter exactement ce que chaque verdict rapporte. Tous les chiffres de cette page ont été calculés sur la liste complète des 1 296 codes du mastermind classique.
10,34 bits : l'incertitude de départ
Un bit, c'est ce que rapporte la réponse à une question par oui ou non dont les deux réponses sont aussi probables l'une que l'autre : elle coupe les possibilités en deux.
Au mastermind classique (4 pions, 6 couleurs, doublons permis), il y a 1 296 codes possibles, tous aussi probables. L'incertitude vaut :
log2(1 296) ≈ 10,34 bits
Autrement dit, il faudrait un peu plus de dix questions « oui ou non » parfaites pour isoler le code. Les essais du mastermind sont des questions bien plus riches, puisqu'elles admettent jusqu'à 14 réponses.
Combien rapporte un verdict ?
Un verdict qui fait passer de N codes possibles à n codes rapporte log2(N / n) bits. Plus il élimine, plus il rapporte.
Avec 4 pions, il existe 14 verdicts possibles : toutes les combinaisons de noirs et de blancs dont le total ne dépasse pas 4, sauf « 3 noirs, 1 blanc » qui est impossible (si trois pions sont à leur place, le quatrième ne peut pas être « ailleurs »). Si ces 14 verdicts étaient aussi probables les uns que les autres, chaque essai rapporterait log2(14) ≈ 3,81 bits. Ce plafond n'est jamais atteint, car les verdicts sont très inégalement fréquents.
Une conséquence simple : deux essais ne peuvent pas suffire à coup sûr. Deux verdicts distinguent au mieux 14 × 14 = 196 situations, et il y a 1 296 codes.
L'entropie : ce qu'un essai rapporte en moyenne
Avant de jouer, tu ne sais pas quel verdict tu obtiendras. L'entropie d'un essai est l'information qu'il rapporte en moyenne, pondérée par la fréquence de chaque verdict. Voici ce que cela donne pour les cinq formes d'ouverture du mastermind classique :
| Ouverture | Verdicts possibles | Entropie (bits) |
|---|---|---|
| AAAA (une seule couleur) | 5 | 1,50 |
| AAAB | 11 | 2,69 |
| AABB (deux paires) | 13 | 2,89 |
| AABC | 14 | 3,04 |
| ABCD (quatre couleurs) | 14 | 3,06 |
Deux enseignements. D'abord, ouvrir avec quatre pions de la même couleur est un gâchis : 1,5 bit, deux fois moins que les bonnes ouvertures. Ensuite, et c'est moins connu, l'ouverture qui rapporte le plus d'information en moyenne n'est pas celle de Knuth. Quatre couleurs différentes font un peu mieux (3,06 bits) que deux paires (2,89 bits).
Knuth a pourtant choisi les deux paires, parce qu'il ne cherchait pas la meilleure moyenne mais le meilleur pire cas : après AABB, il reste au plus 256 codes, contre 312 après ABCD. Ce sont deux critères différents, que nous comparons dans la première tentative au mastermind et dans l'algorithme optimal.
L'entonnoir d'une vraie partie
Voici le nombre de codes restants au fil d'une partie jouée avec la méthode de Knuth (celle que nous détaillons dans gagner au mastermind en 5 coups) :
| Moment | Codes possibles | Incertitude restante |
|---|---|---|
| Avant de jouer | 1 296 | 10,34 bits |
| Après l'essai 1 | 256 | 8 bits |
| Après l'essai 2 | 44 | 5,46 bits |
| Après l'essai 3 | 4 | 2 bits |
| Après l'essai 4 | 1 | 0 bit |
Le cinquième essai ne fait que jouer le code, désormais connu. Chaque essai a rapporté entre 2 et 3,5 bits.
Le verdict vide : quand « rien » en dit long
Recevoir « 0 noir, 0 blanc » donne l'impression d'un coup pour rien. C'est le contraire : toutes les couleurs jouées sont éliminées d'un coup. Ce que ce verdict rapporte dépend de l'ouverture :
- Après deux paires (AABB) : il reste les codes faits des quatre autres couleurs, soit 256 (4 × 4 × 4 × 4). Cela arrive pour 19,8 % des codes et rapporte 2,34 bits.
- Après quatre couleurs différentes (ABCD) : il ne reste que les codes faits des deux autres couleurs, soit 16. Cela n'arrive que pour 1,2 % des codes, mais rapporte 6,34 bits d'un coup.
- Après quatre pions identiques (AAAA) : il reste 625 codes, presque la moitié. Un bit à peine.
C'est une règle générale de la théorie de l'information : un résultat rare apprend beaucoup, un résultat attendu apprend peu. Le niveau Facile en donne une autre illustration : comme le code y contient quatre couleurs différentes sur six, un essai de quatre couleurs différentes reçoit toujours au moins deux repères. Le verdict vide y est impossible.
Éliminer, c'est mettre à jour ses probabilités
Le raisonnement du mastermind est un cas très simple de mise à jour bayésienne. Au départ, tous les codes ont la même probabilité. Après un verdict, les codes incompatibles tombent à zéro et les codes compatibles se partagent la probabilité à égalité. S'il reste 8 codes, chacun a une chance sur 8 d'être le bon, ni plus ni moins.
Cela a une conséquence pratique : aucune des hypothèses encore compatibles n'est « plus vraie » qu'une autre parce qu'elle t'est venue en premier. Notre article sur les biais cognitifs au mastermind revient sur ce piège.
Penser en bits pour mieux jouer
- Un essai dont tu connais déjà le verdict ne t'apprend rien. Avant de valider, demande-toi quelles réponses sont possibles : s'il n'y en a qu'une, change d'essai.
- Le bon essai est celui dont les réponses possibles sont nombreuses et équilibrées, pas celui qui « a l'air d'être le code ».
- En fin de partie, un essai impossible peut être le meilleur. Quand il reste trois ou quatre codes, un essai qui les sépare tous vaut mieux que tenter l'un d'eux au hasard.
Tu peux voir ces nombres pendant que tu joues : le mode Entraînement affiche les codes encore possibles après chaque essai, et le solveur fait le même calcul pour une partie que tu lui décris. La façon dont l'incertitude grandit avec la taille du code est traitée dans allonger le code ou ajouter des couleurs, et le raisonnement pas à pas dans la logique de déduction au mastermind.
