Les records de rapidité au Mastermind : résoudre en un minimum de coups
Le Mastermind, ce jeu de déduction inventé par Mordecai Meirowitz en 1970, cache derrière son apparente simplicité des profondeurs mathématiques fascinantes. Depuis des décennies, mathématiciens et informaticiens cherchent à répondre à une question fondamentale : quel est le nombre minimum de coups nécessaire pour trouver à coup sûr le code secret ? Et les joueurs humains, jusqu’où peuvent-ils approcher ces limites théoriques ?
La preuve de Knuth : 5 coups suffisent toujours
En 1977, le célébre informaticien Donald Knuth a publié un article fondateur qui a révolutionné notre compréhension du Mastermind. En analysant systématiquement le jeu classique (4 positions, 6 couleurs, soit 1 296 combinaisons possibles), il a démontré qu’il existe une stratégie garantissant la victoire en 5 coups maximum, quelle que soit la combinaison secrète.
L’algorithme optimal de Knuth fonctionne selon le principe du minimax : à chaque étape, il choisit la proposition qui minimise le nombre maximum de combinaisons restantes dans le pire cas. Concrètement, après chaque réponse (pions noirs et blancs), l’algorithme élimine le plus grand nombre possible de candidats.
La première proposition recommandée par Knuth est AABB (deux paires de couleurs). Ce choix n’est pas anodin : il maximise l’information obtenue en réponse. Après ce premier coup, il ne reste jamais plus de 256 possibilités à explorer, et chaque coup suivant réduit drastiquement l’espace de recherche.
4,34 coups : la performance moyenne optimale
Si 5 coups constituent la garantie dans le pire cas, la performance moyenne est bien meilleure. L’algorithme de Knuth résout le Mastermind en 4,34 coups en moyenne sur l’ensemble des 1 296 combinaisons possibles. Voici la distribution détaillée :
- 1 coup : 1 combinaison (quand la première proposition est la bonne)
- 2 coups : 4 combinaisons
- 3 coups : 25 combinaisons
- 4 coups : 108 combinaisons
- 5 coups : 305 combinaisons (les plus résistantes)
Des recherches ultérieures ont montré qu’il est possible d’améliorer légèrement la moyenne en acceptant parfois 6 coups dans le pire cas. Certains algorithmes atteignent une moyenne de 4,28 coups avec cette flexibilité, mais au prix de ne plus garantir une résolution systématique en 5 essais.
Les limites théoriques : ce que disent les mathématiques
La théorie de l’information fournit une borne inférieure absolue pour le Mastermind. Avec 1 296 combinaisons possibles et 14 réponses différentes (les différentes combinaisons de pions noirs et blancs), chaque coup fournit au maximum log2(14) ≈ 3,81 bits d’information. Comme il faut log2(1296) ≈ 10,34 bits pour identifier la combinaison, la limite théorique est d’au moins 2,71 coups.
Cette borne n’est cependant jamais atteignable en pratique, car les réponses ne sont pas uniformément distribuées. L’écart entre la limite théorique (2,71) et la performance réelle (4,34) mesure la complexité structurelle du jeu.
Quand le nombre de couleurs change tout
Les records varient considérablement selon la configuration du jeu. Avec 5 couleurs au lieu de 6, l’algorithme optimal garantit la victoire en 4 coups maximum. Avec 8 couleurs, la limite passe à 6 coups. La relation n’est pas linéaire : chaque couleur supplémentaire multiplie l’espace des possibilités et complique exponentiellement la tâche.
Le cas extrême du « Super Mastermind » à 5 positions et 8 couleurs (32 768 combinaisons) a été résolu informatiquement : il faut au maximum 6 coups avec une stratégie optimale, pour une moyenne d’environ 5,1 coups.
Les records humains : des performances impressionnantes
Si les algorithmes fournissent les bornes théoriques, les joueurs humains démontrent des capacités de déduction remarquables. Dans les communautés de joueurs en ligne, certains passionnés maintiennent des statistiques précises de leurs performances.
Les meilleurs joueurs humains réguliers atteignent une moyenne de 4,5 à 4,8 coups sur le Mastermind classique, soit très proche de l’optimum algorithmique. Leurs secrets :
- Des ouvertures mémorisées : comme aux échecs, les meilleurs joueurs connaissent les réponses optimales pour les premiers coups
- L’élimination systématique : ils maintiennent mentalement la liste des combinaisons encore possibles
- La reconnaissance de patterns : après des milliers de parties, certaines configurations deviennent familières
- La gestion de l’information : choisir des propositions qui maximisent l’information même si elles ne sont pas candidates à la solution
Les compétitions informelles en ligne ont révélé des joueurs capables de maintenir une moyenne inférieure à 4,5 coups sur 100 parties consécutives, une performance qui nécessite non seulement de la logique mais aussi une concentration soutenue et une excellente mémoire de travail.
Stratégies pour approcher l’optimal
Comment un joueur humain peut-il s’approcher des performances algorithmiques ? Voici les principes clés.
Le premier coup : maximiser l’information
Commencez toujours par une proposition avec deux paires de couleurs (par exemple, Rouge-Rouge-Bleu-Bleu). Ce choix divise l’espace des possibilités de manière plus équilibrée qu’une proposition à quatre couleurs différentes. Le retour d’information (nombre de pions noirs et blancs) vous donnera un maximum de déductions utiles.
Le deuxième coup : tester les couleurs restantes
Au deuxième coup, introduisez les couleurs non encore testées. Si votre premier coup était RR-BB, essayez JJ-VV (Jaune-Jaune-Vert-Vert). En deux coups, vous aurez des informations sur les six couleurs disponibles, ce qui réduit considérablement le champ des possibles.
À partir du troisième coup : la déduction pure
Dès le troisième coup, vous devriez avoir suffisamment d’informations pour éliminer la majorité des combinaisons. C’est là que la capacité de raisonnement logique fait la différence. Croisez les indices des deux premiers coups pour déterminer quelles couleurs sont présentes et à quelles positions elles peuvent se trouver.
Les défis communautaires et compétitions
Bien qu’il n’existe pas de fédération officielle du Mastermind compétitif, des communautés de passionnés organisent régulièrement des défis en ligne. Le format le plus populaire est le « speed challenge » : résoudre un maximum de grilles en un temps donné, avec un score combinant rapidité et nombre de coups.
D’autres compétitions se concentrent uniquement sur l’efficacité : les participants reçoivent tous les mêmes séries de codes à découvrir, et celui qui utilise le moins de coups au total l’emporte. Ce format élimine le facteur chance et met en valeur la pure capacité de déduction.
Certains défis proposent des variantes encore plus exigeantes : Mastermind à 5 positions, à 8 couleurs, ou même des versions où les réponses sont délibérément ambiguës. Ces formats poussent même les joueurs les plus expérimentés dans leurs retranchements.
Au-delà des chiffres : le plaisir de la déduction
Si les records et les performances optimales fascinent les esprits analytiques, l’essentiel du Mastermind réside dans le plaisir de la déduction. Chaque partie est un petit mystère à résoudre, et la satisfaction de trouver le code en 3 ou 4 coups n’a pas besoin d’être mesurée à l’aune d’un algorithme pour être savoureuse. Les mathématiques nous donnent des repères, mais c’est l’intuition humaine, cette capacité à « sentir » la bonne combinaison, qui rend chaque partie unique et captivante.