Mastermind à 5 ou 6 couleurs : comment la difficulté explose avec chaque couleur ajoutée
Le Mastermind classique, tel que Mordechai Meirowitz l’a conçu en 1970, se joue avec 6 couleurs et 4 positions. Cela représente 1 296 combinaisons possibles. Mais que se passe-t-il si l’on ajoute une septième couleur ? Une huitième ? Ou si l’on passe à 5 positions au lieu de 4 ? La réponse est vertigineuse. Si vous connaissez déjà l’algorithme optimal pour résoudre le Mastermind, vous allez découvrir pourquoi cet algorithme vacille face à l’explosion combinatoire.
L’exponentielle : la mathématique de la difficulté
Le nombre de combinaisons possibles au Mastermind suit une formule simple : C = np, où n est le nombre de couleurs et p le nombre de positions. Avec les répétitions autorisées (une même couleur peut apparaître plusieurs fois), voici ce que cela donne :
- 6 couleurs, 4 positions : 64 = 1 296 combinaisons (version classique)
- 7 couleurs, 4 positions : 74 = 2 401 combinaisons (+85 %)
- 8 couleurs, 4 positions : 84 = 4 096 combinaisons (×3,2 par rapport au classique)
- 10 couleurs, 4 positions : 104 = 10 000 combinaisons (×7,7)
- 6 couleurs, 5 positions : 65 = 7 776 combinaisons (×6)
- 8 couleurs, 5 positions : 85 = 32 768 combinaisons (×25)
La croissance est exponentielle en le nombre de positions et polynomiale en le nombre de couleurs. Ajouter une position multiplie l’espace de recherche par n ; ajouter une couleur le multiplie par un facteur qui dépend du nombre de positions. Les deux effets se cumulent de manière dévastatrice.
L’impact concret sur le nombre de tentatives
En 1977, Donald Knuth a démontré que le Mastermind classique (6 couleurs, 4 positions) peut toujours être résolu en 5 tentatives maximum. Son algorithme minimax examine toutes les réponses possibles pour chaque proposition et choisit celle qui minimise le pire cas.
Mais cet algorithme repose sur l’évaluation de chaque combinaison candidate contre chaque combinaison restante. Pour 1 296 combinaisons, cela implique environ 1 296 × 1 296 = 1,68 million de comparaisons à chaque étape. Pour 10 000 combinaisons (10 couleurs), on passe à 100 millions de comparaisons. Pour 32 768 combinaisons (8 couleurs, 5 positions), c’est plus d’un milliard.
En termes de tentatives nécessaires, les recherches montrent :
- 6 couleurs, 4 positions : 5 tentatives maximum (Knuth, 1977)
- 8 couleurs, 4 positions : 6 tentatives maximum avec stratégie optimale
- 6 couleurs, 5 positions : 6 à 7 tentatives selon la stratégie
- 8 couleurs, 5 positions : 7 à 8 tentatives - le jeu devient un vrai marathon de déduction
La théorie de l’information : bits et entropie
Pour comprendre intuitivement pourquoi la difficulté explose, la théorie de l’information de Claude Shannon offre un cadre éclairant. Chaque tentative au Mastermind fournit de l’information, mesurée en bits.
La réponse du décodeur (« 2 bien placés, 1 mal placé ») réduit l’espace des combinaisons possibles. L’information maximale théorique d’une réponse est limitée par le nombre de réponses distinctes possibles. Avec 4 positions, il y a 14 réponses différentes (de « 0 bien placé, 0 mal placé » à « 4 bien placés »), soit environ 3,8 bits d’information par tentative.
Or, pour identifier une combinaison parmi 1 296, il faut log2(1 296) ≈ 10,3 bits. Avec 3,8 bits par tentative, il faut au minimum 10,3 / 3,8 ≈ 2,7 tentatives en théorie. En pratique, on ne peut pas toujours extraire le maximum d’information, d’où les 5 tentatives de l’algorithme de Knuth.
Avec 10 couleurs et 4 positions, il faut identifier une combinaison parmi 10 000, soit log2(10 000) ≈ 13,3 bits. Le nombre de réponses possibles reste à 14 (il dépend du nombre de positions, pas de couleurs), donc chaque tentative fournit toujours au mieux 3,8 bits. La borne inférieure théorique passe à 13,3 / 3,8 ≈ 3,5 tentatives. L’écart entre théorie et pratique se creuse.
L’adaptation des stratégies
L’algorithme de Knuth, dans sa version originale, devient inutilisable au-delà de 8 couleurs et 5 positions à cause de la complexité calculatoire. Des approches alternatives ont été développées :
- L’heuristique d’entropie : au lieu d’évaluer toutes les combinaisons, on choisit celle qui maximise l’entropie de la distribution des réponses. C’est une approximation plus rapide du minimax, souvent très proche de l’optimal.
- L’approche génétique : des algorithmes évolutionnistes génèrent des populations de propositions candidates et les évaluent selon leur capacité à discriminer les combinaisons restantes.
- Les réseaux de neurones : des travaux récents utilisent l’apprentissage profond pour apprendre des stratégies quasi-optimales sans énumérer l’espace complet.
Pour le joueur humain, la situation est encore plus délicate. Avec 6 couleurs, un joueur expérimenté peut tenir en tête les combinaisons restantes et raisonner par élimination. Avec 8 ou 10 couleurs, la charge cognitive dépasse les capacités de la mémoire de travail humaine (évaluée à 7 ± 2 éléments par George Miller).
Les variantes à nombre de couleurs variable
De nombreuses variantes du Mastermind jouent précisément sur ces paramètres pour ajuster la difficulté :
- Le Mini Mastermind (4 couleurs, 3 positions) : 64 combinaisons. Idéal pour les enfants, résoluble en 3 à 4 tentatives.
- Le Super Mastermind (8 couleurs, 5 positions) : 32 768 combinaisons. Créé par Invicta dans les années 1970, il représente un saut de difficulté majeur.
- Le Mastermind sans répétition : les couleurs ne peuvent pas se répéter. Avec 6 couleurs et 4 positions, on passe de 1 296 à 6 × 5 × 4 × 3 = 360 combinaisons. Le jeu est nettement plus facile, mais la stratégie d’élimination change radicalement.
Le premier coup : encore plus crucial
Avec plus de couleurs, le choix du premier coup devient stratégiquement déterminant. Dans le Mastermind classique, Knuth recommande le code 1-1-2-2 (deux paires de couleurs) comme premier coup optimal. Ce choix équilibre les couleurs testées et maximise l’information obtenue.
Avec 8 couleurs, le premier coup devrait-il tester 2, 3 ou 4 couleurs différentes ? Les analyses montrent qu’il vaut mieux tester davantage de couleurs dans le premier coup quand l’espace de recherche est plus grand. Avec 8 couleurs et 4 positions, un premier coup à 4 couleurs différentes (par exemple 1-2-3-4) est généralement préférable à un coup à 2 couleurs (1-1-2-2), car il sonde une plus grande portion de l’espace.
Au-delà du Mastermind : les implications scientifiques
L’explosion combinatoire du Mastermind n’est pas qu’un problème ludique. Elle illustre un phénomène omniprésent en informatique et en sciences : la malédiction de la dimensionnalité. En biologie, identifier la séquence d’un gène parmi des milliards de bases pose un problème analogue. En cryptographie, la sécurité des codes repose précisément sur cette croissance exponentielle : un mot de passe de 8 caractères est exponentiellement plus sûr qu’un mot de passe de 4 caractères.
Le Mastermind est ainsi un modèle pédagogique parfait pour comprendre l’exponentielle. Quand on dit qu’ajouter une couleur « complique le jeu », on touche du doigt une réalité mathématique profonde que les étudiants en informatique rencontrent sous le nom de classe de complexité NP.
Trouver son niveau : l’art du dosage
La beauté du Mastermind réside dans cette modularité. Contrairement à la plupart des jeux de société dont les règles sont figées, le Mastermind permet de régler la difficulté avec une précision chirurgicale. Un enfant peut jouer à 4 couleurs sans répétition (24 combinaisons), un joueur aguerri peut s’attaquer à 8 couleurs avec répétition (4 096 combinaisons), et un passionné de mathématiques peut défier un algorithme à 10 couleurs et 5 positions (100 000 combinaisons).
Chaque couleur ajoutée ne change pas seulement le nombre : elle transforme la nature même du défi. Et c’est peut-être ce qui rend le Mastermind éternel : il y a toujours un cran au-dessus pour ceux qui cherchent à se dépasser.