L'algorithme optimal pour résoudre le mastermind
En 1977, l'informaticien Donald Knuth publie un court article, « The Computer as Master Mind », dans lequel il montre qu'avec la bonne méthode, n'importe quel code du mastermind classique se trouve en cinq essais au plus. Cet article explique sa méthode, donne les chiffres exacts (que nous avons recalculés en faisant tourner l'algorithme sur les 1 296 codes) et précise ce que « optimal » veut dire, car il y a deux façons de l'entendre.
Le problème posé
Le mastermind classique se joue avec 4 pions et 6 couleurs, doublons permis. Cela fait exactement 1 296 codes possibles (64). C'est la configuration du jeu de plateau, et celle du niveau Classique sur ce site.
La question est la suivante : comment choisir ses essais pour être certain de trouver le code en un minimum de coups, quel que soit ce code ? Chaque essai est une question, chaque verdict (tant de pions noirs, tant de pions blancs) est une réponse qui élimine une partie des 1 296 codes.
La méthode de Knuth, pas à pas
Knuth applique un principe appelé minimax : à chaque coup, jouer l'essai dont le pire verdict possible laisse le moins de codes en lice.
1. Ouvrir par deux paires
Le premier essai est toujours le même : deux pions d'une couleur, deux pions d'une autre (noté AABB, ou 1122 chez Knuth). Après cet essai, 13 verdicts différents peuvent tomber, et le plus gros groupe de codes restants en compte 256. Aucune autre ouverture ne fait mieux dans le pire cas.
| Verdict après AABB | Codes encore possibles |
|---|---|
| 0 noir, 0 blanc | 256 |
| 0 noir, 1 blanc | 256 |
| 1 noir, 0 blanc | 256 |
| 1 noir, 1 blanc | 208 |
| 2 noirs, 0 blanc | 114 |
| 0 noir, 2 blancs | 96 |
| 1 noir, 2 blancs | 36 |
| 2 noirs, 1 blanc | 32 |
| 3 noirs, 0 blanc | 20 |
| 0 noir, 3 blancs | 16 |
| 2 noirs, 2 blancs | 4 |
| 0 noir, 4 blancs | 1 |
| 4 noirs | 1 (c'est gagné) |
Le total fait bien 1 296. Un verdict manque à l'appel : « 1 noir, 3 blancs », impossible à obtenir avec deux paires.
2. Tenir la liste des codes possibles
Après chaque verdict, on ne garde que les codes qui auraient donné exactement les mêmes verdicts à tous les essais déjà joués. Knuth appelle cette liste S.
3. Choisir l'essai qui limite la casse
Pour chacun des 1 296 codes (et pas seulement ceux de S), on regarde comment il découperait S selon les verdicts possibles, et on retient la taille du plus gros morceau. On joue le code dont le plus gros morceau est le plus petit. À égalité, on préfère un code qui appartient à S, puisqu'il a une chance d'être le bon.
Conséquence surprenante : l'algorithme joue parfois un essai dont il sait qu'il ne peut pas être le code, parce que cet essai sépare mieux les candidats restants. Tu peux le voir faire dans notre partie commentée, gagner au mastermind en 5 coups.
4. Recommencer jusqu'à quatre noirs
On répète les étapes 2 et 3 jusqu'à ce qu'il ne reste qu'un code.
Les résultats, code par code
En appliquant cette méthode aux 1 296 codes, on obtient la répartition suivante :
| 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 % |
Soit 5 801 essais pour 1 296 codes : 4,476 coups en moyenne, 5 au maximum. Plus de la moitié des codes demandent les cinq coups.
« Optimal » : dans le pire cas ou en moyenne ?
La méthode de Knuth est optimale pour le pire cas : aucune stratégie ne peut garantir moins de 5 coups. En revanche, elle n'est pas la meilleure en moyenne.
En 1993, Kenji Koyama et Tony Lai ont calculé la stratégie qui minimise le nombre moyen de coups : 4,340 coups (5 625 essais pour les 1 296 codes), au prix d'un pire cas de 6 coups. En s'interdisant de dépasser 5 coups, la meilleure moyenne possible est de 4,341 (5 626 essais). L'écart avec Knuth est faible : un peu plus d'un dixième de coup par partie.
Autre nuance : l'ouverture AABB est la meilleure pour le pire cas, mais ce n'est pas celle qui apporte le plus d'information en moyenne. Trois couleurs dont une doublée (AABC) ou quatre couleurs différentes (ABCD) laissent en moyenne un peu moins de codes derrière elles. Nous comparons ces ouvertures chiffres à l'appui dans la première tentative au mastermind, et l'approche par l'entropie dans le mastermind et la théorie de l'information.
Et avec plus de couleurs ou plus de pions ?
La méthode de Knuth compare chaque essai envisageable à chaque code restant. Avec 1 296 codes, c'est l'affaire d'un instant pour un ordinateur. Avec les 32 768 codes du niveau Difficile ou les 100 000 du niveau Extrême, le même calcul devient beaucoup plus lourd, et on lui préfère des méthodes approchées : choisir l'essai parmi un échantillon, ou utiliser des algorithmes génétiques comme l'ont proposé Berghman, Goossens et Leus.
Sur le plan théorique, Jeff Stuckman et Guo-Qiang Zhang ont montré en 2005 que décider s'il existe un code compatible avec une série d'essais et de verdicts est un problème NP-complet quand on laisse grandir le nombre de pions et de couleurs. Autrement dit, on ne connaît pas de méthode rapide qui marche pour toutes les tailles. La bataille navale pose un problème de recherche par élimination du même genre, voir l'algorithme chasse-cible.
Ce qu'un joueur peut en retenir
- Au niveau Classique, ouvre par deux paires : c'est simple et jamais mauvais.
- Avant de valider, vérifie que ton essai est compatible avec tous les verdicts reçus, sauf si tu joues exprès un coup de tri.
- Un essai qui ne peut pas gagner peut être le meilleur coup, s'il sépare bien les candidats restants.
- Si tu trouves régulièrement en 5 coups au Classique, tu joues déjà très bien : la machine elle-même en a besoin plus d'une fois sur deux.
Pour voir une machine raisonner par élimination, choisis un code sur la page l'ordinateur devine. Pour l'appliquer à ta propre partie, le solveur calcule les codes restants et un coup conseillé. Et si tu préfères une approche sans calcul, nos stratégies pour gagner au mastermind et la logique de déduction suffisent largement pour bien jouer.
