Mastermind : combien de coups minimum pour gagner ? La preuve de Knuth en 5 essais
Cinq coups suffisent toujours pour trouver un code du mastermind classique (4 pions, 6 couleurs, doublons permis), à condition de bien choisir ses essais. C'est ce que Donald Knuth a montré en 1977. Voici les chiffres exacts, ce qu'ils deviennent sur les niveaux de ce site, et à partir de quel score tu peux te dire que tu joues bien. Tous les nombres de cette page ont été recalculés par programme sur la liste complète des codes.
La réponse courte
| Mastermind classique (1 296 codes) | Pire cas | Moyenne |
|---|---|---|
| Méthode de Knuth (1977) | 5 coups | 4,476 |
| Meilleure moyenne possible (Koyama et Lai, 1993) | 6 coups | 4,340 |
| Meilleure moyenne sans dépasser 5 coups | 5 coups | 4,341 |
| Jouer chaque fois le premier code encore possible | 9 coups | 5,765 |
Le dernier coup, celui qui affiche quatre pions noirs, est compris dans ces comptes.
5 coups au plus : ce que Knuth a montré
La méthode de Knuth ouvre par deux paires (par exemple rouge, rouge, bleu, bleu), puis choisit à chaque coup l'essai qui laisse le moins de codes possibles dans le pire des cas. Appliquée aux 1 296 codes, elle donne :
- 1 coup : 1 code (quand le code est justement l'ouverture)
- 2 coups : 6 codes
- 3 coups : 62 codes
- 4 coups : 533 codes
- 5 coups : 694 codes
Le total fait 1 296 codes et 5 801 essais, soit 4,476 coups en moyenne. Aucune méthode ne peut garantir 4 coups : 5 est bien le minimum que l'on puisse promettre. Le fonctionnement détaillé est expliqué dans l'algorithme optimal pour résoudre le mastermind, et une partie complète est déroulée coup par coup dans le guide gagner au mastermind en 5 coups.
4,340 coups : la meilleure moyenne possible
Garantir 5 coups et jouer le moins de coups possible en moyenne sont deux objectifs différents. En 1993, Kenji Koyama et Tony Lai ont établi que la meilleure moyenne atteignable est de 4,340 coups (5 625 essais pour les 1 296 codes). Cette stratégie accepte de monter une fois à 6 coups. Si l'on tient à ne jamais dépasser 5, la meilleure moyenne est de 4,341.
Retiens l'ordre de grandeur : même une machine qui joue parfaitement a besoin d'un peu plus de quatre coups en moyenne.
Et sans calculer comme une machine ?
Personne ne tient 1 296 codes en tête. Mais une règle très simple donne déjà de bons résultats : ne jouer que des codes compatibles avec tous les verdicts reçus. Nous avons simulé la version la plus bête de cette règle, qui joue à chaque fois le premier code encore possible dans l'ordre de la liste : elle trouve toujours en 9 coups au plus, et en 5,765 coups en moyenne. En ouvrant par deux paires plutôt que par le premier code de la liste, la même règle tombe à 5,022 coups de moyenne et 8 au maximum.
Autrement dit, la seule discipline « mon essai doit pouvoir être le code » te met à environ un demi-coup de la machine. Le reste se gagne en choisissant, parmi les essais compatibles, celui qui sépare le mieux les possibilités.
Sur les niveaux de ce site
| Niveau | Codes possibles | Essais accordés | Ce que l'on sait |
|---|---|---|---|
| Facile | 360 | 12 | Une méthode du type de Knuth trouve toujours en 5 coups (4,14 en moyenne, calcul maison) |
| Classique | 1 296 | 10 | 5 coups garantis, 4,340 de moyenne au mieux |
| Moyen | 4 096 | 12 | Pas de chiffre vérifié par nos soins |
| Difficile | 32 768 | 12 | Pas de chiffre vérifié par nos soins |
| Extrême | 100 000 | 12 | Pas de chiffre vérifié par nos soins |
Pour le niveau Facile (4 couleurs toutes différentes parmi 6), nous avons fait tourner la même méthode en ouvrant par quatre couleurs distinctes et en ne jouant que des essais sans doublon : 1 code trouvé en 1 coup, 3 en 2 coups, 53 en 3, 191 en 4 et 112 en 5. Ce n'est pas une preuve d'optimalité, seulement la garantie qu'on peut toujours y arriver en 5.
Pour les niveaux à 8 et 10 couleurs, nous préférons ne pas avancer de nombre que nous n'avons pas recalculé. Les douze essais accordés laissent de toute façon une marge confortable à un joueur méthodique.
Trouver en 1 ou 2 coups : de la chance, pas un record
Trouver du premier coup arrive : une fois sur 1 296 au Classique, une fois sur 360 en Facile. Cela ne dit rien du niveau du joueur, comme l'explique notre article le mastermind peut-il se résoudre en un seul coup ?. Ce qui mesure vraiment ta façon de jouer, c'est ta moyenne sur beaucoup de parties.
Quel score viser ?
- Au Classique : une moyenne proche de 5 coups est celle d'un joueur rigoureux. S'approcher de 4,5 demande de choisir ses essais comme le ferait la machine.
- En Facile : 4 à 5 coups, régulièrement, est un très bon rythme.
- Au classement du site, on compare des séries de 3 parties jouées d'affilée : le total des essais d'abord, le temps cumulé ensuite. La vitesse ne compte donc qu'à total d'essais égal : mieux vaut réfléchir dix secondes de plus que jouer un coup de trop.
Pour t'entraîner à compter, le mode Entraînement affiche le nombre de codes encore possibles après chaque essai, et le solveur te montre, pour une partie que tu lui décris, quel coup aurait le mieux réduit la liste. Les bases sont dans nos 5 stratégies pour gagner au mastermind.
