Gagner au mastermind en 5 coups : la méthode de Knuth coup par coup
Le cadre : le niveau Classique
La garantie des 5 coups vaut pour le mastermind classique : 4 pions, 6 couleurs, doublons permis, soit 1 296 codes. C'est le niveau Classique de ce site, disponible en solo, en multijoueur, à l'entraînement et au défi du jour. Les six couleurs sont rouge, bleu, vert, jaune, orange et violet.
La méthode en deux règles
- Ouvrir par deux paires : deux pions d'une couleur, deux d'une autre.
- Ensuite, jouer l'essai qui laisse le moins de codes possibles dans le pire des cas. On regarde, pour chaque essai envisageable, le verdict le plus défavorable, et on choisit l'essai pour lequel ce verdict défavorable laisse le moins de codes. À égalité, on préfère un essai qui peut encore être le code.
C'est la méthode publiée par Donald Knuth en 1977. Le calcul de la règle 2 est un travail de machine ; ce qui nous intéresse ici, c'est de voir ce qu'il produit.
La partie, coup par coup
Code à trouver (que le joueur ne connaît pas) : vert, orange, rouge, orange.
Essai 1 : rouge, rouge, bleu, bleu. Verdict : 0 noir, 1 blanc
Aucun noir : pas de rouge dans les deux premières cases, pas de bleu dans les deux dernières. Un seul blanc : le code contient soit un seul rouge (en case 3 ou 4) et aucun bleu, soit un seul bleu (en case 1 ou 2) et aucun rouge. Les autres cases sont prises parmi vert, jaune, orange et violet.
De 1 296 codes, il en reste 256.
Essai 2 : bleu, vert, jaune, jaune. Verdict : 0 noir, 1 blanc
La méthode introduit deux couleurs nouvelles (vert et jaune) et rejoue un bleu à une place où il n'était pas. Aucun noir : pas de bleu en case 1, pas de vert en case 2, pas de jaune en cases 3 et 4. Un seul blanc : une seule de ces trois couleurs est présente, et si c'est le jaune, il n'y en a qu'un.
Il reste 44 codes.
Essai 3 : vert, orange, rouge, violet. Verdict : 3 noirs
Trois pions sur quatre sont à leur place. On ne sait pas lesquels, mais en recoupant avec les deux premiers verdicts, il ne reste que 4 codes :
- vert, orange, rouge, vert
- vert, orange, rouge, orange
- vert, violet, rouge, violet
- jaune, orange, rouge, violet
Essai 4 : rouge, rouge, jaune, orange. Le coup qui ne peut pas gagner
C'est le moment le plus instructif de la partie. La méthode joue un essai qui n'est pas l'un des quatre codes possibles : elle sait qu'il ne peut pas gagner. Pourquoi ? Parce qu'il donne un verdict différent pour chacun des quatre candidats :
| Si le code est… | rouge, rouge, jaune, orange donne |
|---|---|
| vert, orange, rouge, vert | 0 noir, 2 blancs |
| vert, orange, rouge, orange | 1 noir, 1 blanc |
| vert, violet, rouge, violet | 0 noir, 1 blanc |
| jaune, orange, rouge, violet | 0 noir, 3 blancs |
Quel que soit le verdict, le code est connu après cet essai, et le cinquième coup gagne à coup sûr. Si l'on avait tenté directement l'un des quatre candidats, on aurait gagné une fois sur quatre au quatrième coup, mais dans les autres cas il aurait pu rester deux ou trois codes en lice, donc une partie en six coups ou plus.
Le verdict tombe : 1 noir, 1 blanc. Il ne reste qu'un code.
Essai 5 : vert, orange, rouge, orange. Quatre noirs
Le code est trouvé au cinquième essai. Compte des codes possibles au fil de la partie : 1 296, 256, 44, 4, 1.
Est-ce toujours 5 coups ?
Non, c'est 5 au plus. En appliquant la méthode aux 1 296 codes, on obtient :
| Code trouvé en | Nombre de codes | Part |
|---|---|---|
| 1 coup | 1 | 0,1 % |
| 2 coups | 6 | 0,5 % |
| 3 coups | 62 | 4,8 % |
| 4 coups | 533 | 41,1 % |
| 5 coups | 694 | 53,5 % |
La moyenne est de 4,476 coups. La partie de ce guide fait donc partie de la majorité : un peu plus d'un code sur deux demande les cinq coups.
Ce que tu peux appliquer sans ordinateur
Personne ne calcule le minimax de tête. Mais la partie ci-dessus contient quatre idées que tu peux reprendre telles quelles :
- Ouvre par deux paires au niveau Classique.
- Au deuxième essai, introduis des couleurs nouvelles tout en gardant une couleur déjà jouée, pour lever le doute qu'a laissé le premier verdict.
- À partir du troisième essai, ne propose que des codes compatibles avec tous les verdicts reçus, sauf si tu joues exprès un coup de tri.
- Quand il reste trois ou quatre codes possibles et que tu peux les lister, cherche un essai qui donnerait un verdict différent pour chacun, même s'il ne peut pas gagner. C'est le coup 4 de notre partie.
Avec ces seules règles, tu ne trouveras pas toujours en 5 coups, mais les 10 essais du niveau Classique te laisseront de la marge.
Pour t'exercer
- Le mode Entraînement affiche le nombre de codes encore possibles après chaque essai : compare tes chiffres à ceux de la partie ci-dessus (256, 44, 4, 1).
- Le solveur reprend une partie que tu lui décris et te donne les codes restants et un coup conseillé.
- Sur la page l'ordinateur devine, tu choisis un code et tu regardes la machine le trouver.
Pour comprendre le calcul derrière la règle 2, lis l'algorithme optimal pour résoudre le mastermind. Les chiffres complets (moyennes, autres niveaux) sont dans combien de coups minimum pour gagner, et les méthodes sans calcul dans nos 5 stratégies pour gagner au mastermind.