Le cerveau de l'opération

Mastermind est un jeu de déchiffrage dans lequel un joueur (ou l'ordinateur) définit un code secret — une séquence de pions colorés — et l'autre joueur tente de le deviner en un nombre limité d'essais. Après chaque tentative, le créateur du code fournit des indications précisant combien de pions sont de la bonne couleur et à la bonne position (pions noirs) et combien sont de la bonne couleur mais à la mauvaise position (pions blancs). La version classique utilise 4 positions et 6 couleurs, ce qui permet d’effectuer entre 10 et 12 tentatives.

Règles

1. Le créateur de code élabore un code secret composé de 4 pions colorés, choisis parmi 6 couleurs possibles. Les couleurs peuvent se répéter.
2. Le déchiffreur fait une supposition en plaçant 4 pions colorés sur une ligne.
3. Le créateur de code répond en indiquant la position des pions :

• Piquet noir : un piquet est de la bonne couleur et à la bonne position.
• Piquet blanc : un piquet est de la bonne couleur mais à la mauvaise position.

1. Chaque couleur de la supposition ne peut correspondre qu’une seule fois : les correspondances exactes (noir) ont la priorité sur les correspondances de couleur (blanc).
2. Le déchiffreur utilise ces indications pour affiner ses tentatives suivantes.
3. Le jeu se termine lorsque le code est deviné correctement ou lorsque le nombre maximal de tentatives est épuisé.

Stratégies

• L'algorithme de Knuth : En 1977, Donald Knuth a prouvé que le Mastermind classique à 4 pions et 6 couleurs peut toujours être résolu en 5 tentatives au maximum. Son algorithme minimax commence par la tentative (1, 1, 2, 3) et choisit chaque tentative suivante de manière à minimiser le nombre de possibilités restantes dans le pire des cas.
• Optimisation de la première tentative : Commencez par une tentative contenant deux paires de couleurs (par exemple, AABB). Cela fournit un maximum d’informations sur les couleurs présentes.
• Suivi des codes éliminés : Après chaque retour d’information, éliminez mentalement ou physiquement tous les codes incompatibles avec les retours reçus jusqu’à présent. Votre prochaine hypothèse doit être cohérente avec tous les retours d’information précédents.
• Maximisation de l’information : Choisissez des hypothèses qui divisent les possibilités restantes en groupes aussi égaux que possible en taille. L’hypothèse qui crée la répartition la plus équilibrée fournit le plus d’informations, quel que soit le retour d’information.
• Comptage des couleurs : Utilisez vos premières suppositions pour déterminer quelles couleurs apparaissent dans le code et combien de fois. Une fois que vous connaissez la composition des couleurs, concentrez-vous sur la recherche de l’agencement correct.
• Procédé d’élimination : si une supposition reçoit un retour « 0 noir, 0 blanc », aucune de ces couleurs n’apparaît dans le code. Cela peut considérablement réduire l’espace de recherche.

Mastermind a été inventé en 1970 par Mordecai Meirowitz, un chef de poste israélien et expert en télécommunications. Après avoir été rejeté par plusieurs fabricants de jouets, le jeu a finalement été produit et distribué par Invicta Plastics, une petite entreprise britannique basée à Leicester, en Angleterre. Sorti en 1971, il a connu un succès international, avec plus de 50 millions d’exemplaires vendus au cours de sa première décennie.

La conception du jeu s'inspire d'un ancien jeu sur papier appelé « Bulls and Cows » (également connu sous le nom de « Moo »), dont l'origine remonte au moins au début du XXe siècle. Dans « Bulls and Cows », les joueurs devinent un nombre secret et reçoivent des indications sur les chiffres corrects placés aux bonnes positions (« bulls ») et sur les chiffres corrects placés aux mauvaises positions (« cows »). L’innovation de Meirowitz a consisté à transformer ce jeu de chiffres abstrait en un jeu de société visuellement attrayant avec des pions colorés, le rendant ainsi accessible à un public plus large.

Mastermind a suscité un vif intérêt chez les mathématiciens et les informaticiens. En 1977, Donald Knuth a publié un article de référence démontrant que le déchiffreur peut toujours déterminer le code en cinq tentatives au maximum en utilisant une stratégie minimax. Cette analyse a établi un lien entre le jeu et la théorie de l’information, la combinatoire et la conception d’algorithmes. La question de la stratégie optimale au Mastermind a depuis fait l’objet d’études approfondies, et des variantes comportant différents nombres de pions et de couleurs ont été analysées quant à leur complexité algorithmique — en effet, il a été démontré en 2005 que le Mastermind avec un nombre arbitraire de pions et de couleurs est un problème NP-complet.

Le jeu a donné naissance à de nombreuses variantes, notamment le Super Mastermind (5 pions, 8 couleurs), le Grand Mastermind (5 pions avec des formes de motifs) et des versions électroniques. Il a également influencé la conception de jeux de manière plus générale, le mécanisme du Mastermind apparaissant dans des jeux vidéo tels que « Fallout » (piratage de terminaux) et le jeu mobile « Wordle » (qui applique un mécanisme de retour d’information similaire à la devinette de mots). Le Mastermind reste un incontournable des collections de jeux de logique et une introduction populaire au raisonnement combinatoire.