Le Mastermind et la théorie de l’information : chaque indice réduit l’incertitude
Quand vous posez une combinaison au Mastermind et recevez en retour des pions noirs et blancs, vous faites bien plus que « tester un code ». Vous acquérez de l’information au sens mathématique du terme. Chaque indice réduit l’espace des possibles, chaque tentative élimine des combinaisons incompatibles. Ce processus a un nom en science : la théorie de l’information, fondée par Claude Shannon en 1948. Et le Mastermind en est une illustration remarquablement pure.
L’entropie de Shannon : mesurer l’incertitude
Avant votre première tentative au Mastermind classique (4 positions, 6 couleurs, répétitions autorisées), il existe 1 296 combinaisons possibles (64). Comment quantifier cette incertitude ? Shannon a proposé une mesure : l’entropie, notée H, qui s’exprime en bits.
Pour 1 296 possibilités équiprobables, l’entropie est :
H = log2(1296) ≈ 10,34 bits
Cela signifie qu’il faut environ 10,34 bits d’information pour identifier le code secret. Chaque tentative doit donc en apporter le plus possible. L’algorithme optimal de Donald Knuth (1977) garantit de trouver le code en 5 tentatives au maximum, ce qui signifie qu’il extrait en moyenne plus de 2 bits par tentative.
Pour donner un ordre de grandeur : un bit, c’est la quantité d’information contenue dans la réponse à une question oui/non parfaitement équilibrée. Dix bits, c’est l’équivalent de dix telles questions posées de manière optimale.
Combien d’information par réponse ?
Au Mastermind, la réponse à chaque tentative est une paire (noirs, blancs) où « noirs » représente les pions bien placés et « blancs » les pions de bonne couleur mais mal placés. Pour 4 positions, il existe 14 réponses possibles (de 0 noir/0 blanc à 4 noirs, en excluant le cas impossible 3 noirs/1 blanc).
Si les 14 réponses étaient équiprobables, chaque tentative apporterait log2(14) ≈ 3,81 bits. En réalité, les réponses ne sont pas équiprobables : certaines (comme 0 noir/0 blanc ou 1 noir/1 blanc) correspondent à beaucoup plus de combinaisons que d’autres (comme 3 noirs/0 blanc). L’information réelle dépend de la distribution.
C’est précisément là que réside l’art de bien jouer au Mastermind : choisir des tentatives qui rendent les réponses les plus équiprobables possibles. Plus les réponses sont uniformément réparties, plus l’entropie de la réponse est élevée, et plus on gagne d’information.
La première tentative : maximiser l’information initiale
Pourquoi la plupart des stratégies recommandent-elles de commencer par une combinaison comme AABB (deux paires de couleurs) plutôt que AAAA (quatre fois la même) ? La réponse est purement informationnelle.
Avec AAAA, il n’y a que 5 réponses possibles (0, 1, 2, 3 ou 4 noirs, jamais de blancs). L’entropie de cette réponse est faible. Avec AABB, les 14 réponses sont toutes accessibles, et leur distribution est bien plus uniforme. On obtient en moyenne environ 2,6 bits d’information, contre seulement 1,5 pour AAAA.
L’ouverture optimale selon le critère de l’entropie maximale est AABB ou une permutation équivalente. C’est ce que Knuth avait identifié empiriquement, et que la théorie de l’information confirme élégamment. Comme expliqué dans notre article sur l’effet du nombre de couleurs sur la difficulté, cette logique s’amplifie considérablement quand on passe à 5 ou 6 couleurs.
La cascade de réduction : un entonnoir informationnel
Visualisons le processus complet d’une partie :
- Avant la tentative 1 : 1 296 combinaisons possibles (10,34 bits d’incertitude)
- Après la tentative 1 : typiquement 200-400 combinaisons restantes (~8 bits)
- Après la tentative 2 : 20-60 combinaisons (~5 bits)
- Après la tentative 3 : 2-10 combinaisons (~2-3 bits)
- Après la tentative 4 : 1-3 combinaisons (~0-1 bit)
Chaque tentative divise l’espace des possibles par un facteur qui dépend de la qualité de la question posée. Un joueur novice qui choisit ses tentatives au hasard obtient des facteurs de réduction faibles. Un joueur expert, ou l’algorithme de Knuth, maximise systématiquement ce facteur - c’est-à-dire qu’il maximise l’entropie de chaque réponse.
C’est ce que les informaticiens appellent une recherche binaire généralisée. Dans une recherche binaire classique, chaque question divise l’espace en deux (1 bit). Au Mastermind, chaque tentative peut potentiellement diviser l’espace en 14 (jusqu’à 3,81 bits), ce qui explique pourquoi 5 tentatives suffisent pour 1 296 possibilités : 5 × 2,07 ≈ 10,34.
Le parallèle avec la méthode scientifique
La théorie de l’information révèle une analogie profonde entre le Mastermind et la méthode scientifique. Dans les deux cas, le processus est identique :
- Formuler une hypothèse (choisir une combinaison à tester)
- Concevoir une expérience (choisir quelle combinaison maximise l’information attendue)
- Observer le résultat (lire les pions noirs et blancs)
- Mettre à jour ses croyances (éliminer les combinaisons incompatibles)
- Itérer jusqu’à identifier la vérité
Un bon scientifique, comme un bon joueur de Mastermind, ne cherche pas à confirmer ce qu’il pense déjà savoir - il cherche à discriminer entre les possibilités restantes. Une expérience dont le résultat est prévisible n’apporte aucune information. De même, une tentative au Mastermind dont la réponse est quasi certaine est une tentative gaspillée.
Le physicien E.T. Jaynes a formalisé cette idée sous le nom de conception expérimentale bayésienne : choisir l’expérience qui maximise l’information attendue, exactement comme on choisit la meilleure tentative au Mastermind. Les laboratoires de recherche du XXIe siècle utilisent des algorithmes qui sont, en essence, des versions sophistiquées du joueur de Mastermind.
L’information négative : quand « rien » dit tout
L’un des concepts les plus contre-intuitifs de la théorie de l’information appliquée au Mastermind est la valeur de l’information négative. Recevoir la réponse « 0 noir, 0 blanc » semble décevant - aucune couleur n’est présente dans le code. Pourtant, cette réponse est extrêmement informative !
Avec 6 couleurs et la tentative AABB, la réponse 0/0 élimine d’un coup toutes les combinaisons contenant A ou B, ne laissant que les combinaisons formées exclusivement des 4 couleurs restantes : soit 256 possibilités (44) sur les 1 296 initiales. C’est une réduction de 80 % en une seule tentative.
Ce principe a une résonance épistémologique profonde. Comme le disait Arthur Conan Doyle par la voix de Sherlock Holmes : « Quand vous avez éliminé l’impossible, tout ce qui reste, aussi improbable soit-il, doit être la vérité. » Au Mastermind, chaque réponse élimine de l’impossible et nous rapproche mécaniquement de la vérité.
Au-delà du jeu : penser en bits
La beauté de cette perspective informationnelle est qu’elle transforme notre façon de jouer. Au lieu de raisonner par intuition (« j’ai un bon pressentiment pour le rouge en deuxième position »), on apprend à raisonner par réduction d’incertitude (« quelle tentative me donnera le plus d’information, quel que soit le résultat ? »).
Ce changement de perspective dépasse le cadre du jeu. Dans la vie quotidienne, nous posons constamment des questions, faisons des choix et interprétons des réponses. La théorie de l’information nous enseigne qu’une bonne question n’est pas celle dont on espère une réponse particulière, mais celle dont toutes les réponses sont également utiles.
La prochaine fois que vous poserez une combinaison au Mastermind, pensez à Claude Shannon. Chaque pion noir et chaque pion blanc est un fragment d’information, une petite victoire contre l’incertitude. Et quand le code se révèle enfin, c’est le moment où l’entropie tombe à zéro - l’incertitude a été entièrement vaincue.