La méthode mathématique pour hacker Mastermind
Le Mastermind, inventé en 1970 par l’expert en télécommunications Mordecai Meirowitz, est bien plus qu’un simple jeu de société : c’est un véritable exercice de logique combinatoire. S’inscrivant dans la lignée historique des grands systèmes de décryptage, de la Seconde Guerre mondiale à la cybersécurité moderne, ce duel entre un codificateur et un décodeur exige d’extraire une information cachée avec une précision quasi scientifique.
Pour augmenter ses chances de gagner, il est conseillé d’adopter une méthode mathématique rigoureuse en plus de l’intuition humaine. En s’appuyant sur les probabilités et un raisonnement déductif, le joueur peut filtrer des milliers de combinaisons possibles pour isoler rapidement le code secret. Cette approche transforme le jeu en un défi algorithmique, permettant de réduire le nombre des possibilités en un temps record.
Régles du jeu Mastermind
Avant de s’intéresser aux méthodes de résolution, commençons par rappeler les règles du Mastermind. Le jeu oppose deux personnes : le créateur du code (le « codificateur ») et celui qui doit le briser (le « décodeur »).
Le codificateur choisit secrètement une combinaison de couleurs composée de 4 pions qu’il cache derrière un petit clapet. Dans la version standard, il dispose de 6 couleurs différentes. Il peut choisir de mettre quatre pions de couleurs différentes ou, pour corser l’affaire, d’utiliser plusieurs fois la même couleur (les doublons). À chaque tour, le décodeur propose une combinaison. Le codificateur donne des indications sur la position et la couleur des petits pions de la manière suivante:
- pion noir (bien placé) : la couleur est correcte et se trouve à la bonne place,
- pion blanc (Mal placé) : la couleur est présente dans le code, mais elle n’est pas au bon endroit,
- rien du tout : la couleur n’est pas dans le code à trouver.
Le but du Mastermind est simple : trouver la bonne combinaison le plus rapidement possible, en général en moins de 10 coups. Le décodeur doit faire preuve de raisonnement logique et utiliser un processus de déduction efficace.
Comment trouver la bonne combinaison sans tricher ?
Pour gagner, la plupart des joueurs avancent à tâtons, en espérant avoir de la chance. Mais si le décodeur joue au hasard, il se trouve rapidement face à un mur de combinaisons possibles. En logique combinatoire, on calcule cela en multipliant le nombre de choix par le nombre de positions. Ici, avec 6 couleurs et 4 emplacements, le calcul est : 6×6×6×6=1296 solutions potentielles.
Déroulement d’une partie
Imaginons que ton adversaire ait choisi le code secret suivant : (Rouge – Bleu – Rouge – Jaune). Ton but est de réduire l’espace des possibilités le plus vite possible. Tu décides de lancer ton premier assaut avec une combinaison simple, souvent recommandée par le raisonnement logique : (Bleu – Bleu – Vert – Vert).
Le codificateur analyse la proposition de couleurs : Le premier bleu est dans le code mais mal placé (1 pion blanc). Le deuxième bleu est bien placé (1 pion noir). Les pions verts n’existent pas dans le code. Le résultat affiché sera 1 noir, 1 blanc.
Avec ces informations, tu peux commencer à réfléchir. Tu sais que le pion « Vert » n’est pas dans le code à trouver, donc ce n’est plus la peine de l’inclure dans les futures propositions. Le pion » Bleu » en première position est à déplacer soit en 3ème position ou en 4ème position.
Résoudre avec les probabilités
En 1977, le mathématicien Donald Knuth a publié un article démontrant qu’il est possible de casser n’importe quel code secret de Mastermind en 5 coups maximum. Pour réussir cet exploit, il utilise un algorithme de résolution basé sur une stratégie appelée « Minimax ».
L’idée de Knuth est basée sur la réduction de l’incertitude. Au lieu de chercher les pions bien placés dès le départ, Donald Knuth se concentre sur l’essai qui éliminera le plus de mauvaises combinaisons.
Voici comment fonctionne son raisonnement logique étape par étape :
- Générer l’ensemble de départ: lister l’intégralité de combinaisons possibles pour 6 couleurs, soit les 1 296 codes potentiels
- Commencer la partie: Knuth a calculé que le meilleur départ est toujours une combinaison de type « AABB », par exemple (Rouge – Rouge – Bleu – Bleu)
- Mettre à jour l’ensemble: supprimer dans l’ensemble de départ toutes les combinaisons impossibles. Par exemple, si dans le premier coup, on sait qu’il n’y a pas de pion rouge, supprimer toutes les combinaisons qui possèdent au moins un pion rouge.
- Proposer une nouvelle combinaison: on choisit l’essai qui garantit de minimiser le nombre de solutions restantes, quel que soit l’indice (bien placé / mal placé) reçu en éliminant le maximum de tirage d’un coup.
- Répétez l’étape 3 et 4 jusqu’à la solution
Maîtriser le Mastermind ne relève pas d’une intuition magique. Bien au contraire, le décodeur talentueux se sert d’une méthode mathématique afin de minimiser le nombre de coups. Les travaux de Donald Knuth ont démontré que le hasard n’a aucune place dans le Mastermind. Celui qui veut percer rapidement le code devra choisir avec soin chacune de ses propositions de quatre pions.
Publications similaires
