L’algorithme optimal pour résoudre le mastermind
En 1977, le mathématicien et informaticien Donald Knuth publie un article qui révolutionne la compréhension du mastermind. Il démontre qu’avec la bonne stratégie, n’importe quel code secret peut être découvert en cinq tentatives maximum. Cet article explore l’algorithme de Knuth, la stratégie minimax et les concepts de théorie de l’information qui transforment le mastermind en un problème mathématique fascinant.
Le problème mathématique du mastermind
Dans la version classique du mastermind (4 positions, 6 couleurs, répétitions autorisées), il existe exactement 1 296 combinaisons possibles (6&sup4;). Le défi algorithmique est le suivant : comment choisir ses tentatives de manière à identifier le code secret en un minimum de coups, quel que soit ce code ?
Ce problème relève de la théorie de la décision. Chaque tentative peut être vue comme une question posée à un oracle, et la réponse (pions noirs et blancs) est l’information reçue. L’objectif est de concevoir une séquence de questions qui identifie le code le plus rapidement possible.
L’algorithme de Knuth en détail
L’approche de Donald Knuth repose sur le principe minimax : à chaque étape, choisir la tentative qui minimise le nombre maximal de possibilités restantes dans le pire cas. Voici les étapes de l’algorithme :
Étape 1 : Premier coup fixe
Knuth démontre que le premier coup optimal est 1-1-2-2 (deux pions d’une couleur suivis de deux pions d’une autre). Ce choix n’est pas intuitif, mais il maximise l’information moyenne obtenue. Après ce premier coup, la réponse divise les 1 296 possibilités en groupes de taille inégale, et le plus grand groupe ne dépasse pas 256 combinaisons.
Étape 2 : Construire l’ensemble des possibles
Après chaque tentative, l’algorithme calcule l’ensemble S de tous les codes encore compatibles avec l’ensemble des indices reçus. Pour chaque code candidat dans S, on vérifie qu’il produirait exactement les mêmes indices que ceux observés pour chaque tentative précédente.
Étape 3 : Appliquer le minimax
Pour chaque tentative possible (pas seulement celles dans S, mais parmi les 1 296 codes), l’algorithme calcule la partition que cette tentative créerait dans S. Chaque réponse possible (combinaison de pions noirs et blancs) définit un sous-ensemble de S. La tentative retenue est celle dont le plus grand sous-ensemble est le plus petit (principe minimax).
Étape 4 : Répéter jusqu’à la solution
On répète le processus jusqu’à ce que S ne contienne plus qu’un seul code. Knuth prouve que cette stratégie garantit de trouver le code en 5 tentatives au maximum, avec une moyenne de 4,476 tentatives.
La théorie de l’information appliquée
Une approche alternative, basée sur la théorie de l’information de Shannon, consiste à maximiser l’entropie de la réponse plutôt que de minimiser le pire cas. L’idée est de choisir la tentative dont la réponse apporte le plus d’information en moyenne.
L’entropie se calcule ainsi : pour chaque tentative candidate, on évalue la probabilité de chaque réponse possible. Une tentative qui produit des réponses équiprobables (c’est-à-dire qui divise S en sous-ensembles de taille égale) a une entropie maximale et apporte donc le plus d’information.
En pratique, cette approche entropique donne des résultats très proches de l’algorithme minimax de Knuth, avec parfois une meilleure performance moyenne mais un pire cas légèrement inférieur.
Au-delà de Knuth : les améliorations modernes
Depuis les travaux de Knuth, de nombreux chercheurs ont affiné les algorithmes de résolution du mastermind :
- Ville (2013) a démontré qu’en optimisant le nombre moyen de tentatives (plutôt que le pire cas), on peut atteindre une moyenne de 4,340 coups.
- Berghman, Goossens et Leus ont exploré des approches par programmation linéaire entière pour des variantes étendues du mastermind.
- Les algorithmes génétiques ont été appliqués au mastermind étendu (plus de couleurs, plus de positions), où l’approche exhaustive de Knuth devient trop coûteuse en calcul.
La complexité computationnelle
Un aspect fascinant du mastermind est sa complexité computationnelle. Pour la version classique à 4 positions et 6 couleurs, l’algorithme de Knuth est parfaitement réalisable. Mais lorsque le nombre de positions et de couleurs augmente, le problème devient rapidement intraitable.
Stuckman et Zhang ont démontré en 2006 que le problème généralisé du mastermind est NP-complet. Cela signifie qu’il n’existe probablement pas d’algorithme efficace pour résoudre toutes les variantes du mastermind en temps polynomial. D’autres jeux de stratégie présentent des défis algorithmiques comparables, comme la bataille navale dont l’algorithme chasse-cible optimise également la recherche par élimination progressive.
Applications pratiques
Les algorithmes développés pour le mastermind ont des applications bien au-delà du jeu :
- Cryptographie : le mastermind est un modèle simplifié du problème de déchiffrement, où l’on cherche à découvrir une information cachée à partir d’indices partiels.
- Biologie moléculaire : des variantes de l’algorithme sont utilisées pour identifier des séquences génétiques par élimination progressive.
- Tests logiciels : la stratégie minimax inspire des méthodes de test où l’on cherche à identifier un bug avec un nombre minimal de tests.
- Intelligence artificielle : les techniques de propagation de contraintes développées pour le mastermind sont fondamentales en IA.
Peut-on faire mieux que 5 coups ?
Avec la version classique du mastermind, 5 coups est la garantie optimale dans le pire cas. Cependant, certains codes sont devinables en seulement 1, 2 ou 3 coups avec un peu de chance. La question mathématique intéressante est : quelle est la proportion de codes résolubles en k coups ? Avec l’algorithme de Knuth, environ 6 % des codes sont trouvés en 3 coups, 62 % en 4 coups et 32 % en 5 coups.
Pour approfondir la logique derrière ces méthodes, consultez notre article sur la logique de déduction au mastermind. Et si vous préférez une approche plus intuitive, nos stratégies pour débutants vous aideront à progresser sans formules mathématiques.