Solveur Mastermind

Mastermind est un jeu de plateau basé sur la déduction où le joueur doit découvrir une combinaison de couleurs en un minimum de proposition. Le jeu se joue généralement à 2 joueurs ayant des fonctions asymétriques : un est codeur, l'autre est décodeur. Le codeur enregistre une combinaison de couleurs secrète que son adversaire doit décoder en proposant lui-même des combinaisons. Le codeur doit répondre en indiquant si une ou plusieurs couleurs sont bien ou mal placées. Si le décodeur retrouve la combinaison du codeur, la partie se termine.

Le solveur de Mastermind est paramétrable en taille (nombre de pions colorés dans le code solution) et en choix (nombre de couleurs/items possibles) selon le type de partie de Mastermind à résoudre par le joueur.

La syntaxe à utiliser est CCCC A B avec CCCC la combinaison, A le nombre de pions bien positionnés, B le nombre de pions mal positionnés.

Dans sa version originale, un mastermind possède 4 cases et 6 couleurs possibles, à chaque tentative le joueur reçoit 2 informations : le nombre de positions correctes et le nombre de positions incorrectes.

Le solveur de dCode utilise une syntaxe abrégée pour décrire les propositions de combinaisons et en déduire les solutions possibles. Pour un jeu de taille N (combinaison avec N cases à trouver), chaque proposition doit contenir N lettres suivies de 2 chiffres indiquant les indices obtenus (nombre de cases bien et mal placés). Séparer chaque proposition par un retour à la ligne.

Il est également possible d'insérer des jokers (cases vides ou inconnues indiquées par ?,*,- ou _) aussi bien pour la combinaison que pour les positions correctes et incorrectes.

D'après Donald Knuth, et selon les règles originales (combinaison de 4 couleurs parmi 6) il est possible de trouver le code en 5 étapes (ou moins). L'algorithme à utiliser est :

1 - Générer l'ensemble E des 1296 codes possibles (de 1111 à 6666).

2 - Proposer comme première tentative 1122

3 - Si la réponse est juste, le jeu est terminé. Sinon, supprimer de l'ensemble E tous les codes qui donneraient la même réponse.

4 - Pour chaque code possible qui n'a pas été tenté, calculer combien de possibilités de l'ensemble E seraient éliminées pour chaque réponse possible (combinaison bien placées-mal placées). Donner un score à ce code égal au nombre minimum de possibilités éliminées dans E. Proposer un des codes avec le meilleur score (de préférence un code présent dans S). Reprendre à l'étape 3.

Cet algorithme permet de trouver le code en 5 étapes (ou moins).

Mathématiquement, si la stratégie du joueur qui devine est connue alors il existe en effet des combinaisons plus ou moins difficiles, mais comme indiqué (ci-dessus), en utilisant la stratégie optimale de Donald Knuth alors aucune combinaisons n'est vraiment difficile et toutes les solutions sont trouvables en 5 étapes ou moins. Toujours mathématiquement, si la stratégie du joueur n'est pas connue, alors il n'y a pas de combinaisons plus difficiles qu'une autre.

Pour information, en utilisant ce type d'algorithme, les meilleures combinaisons (les combinaisons les plus difficiles à résoudre) sont 1221, 2354, 3311, 4524, 5656, 6643.

Cependant, tous les joueurs ne raisonnent pas avec des algorithmes mathématiques, il est possible d'envisager des combinaisons plus difficiles à trouver en piégeant le cerveau.

— Les joueurs novices oublient souvent que la combinaison peut avoir plusieurs fois une même couleur, utiliser 2 ou 3 fois un même élément dans la combinaison peut rendre le jeu plus difficile.

— Si la combinaisons est faite de chiffres ou de lettres, utiliser des grands chiffres ou des lettres à la fin de l'alphabet en priorité, car les algorithmes et les joueurs vont commencer par tenter 1122 et non 5566 (et si ce n'est pas le cas, utiliser des chiffres au milieu).

— Si les joueurs se sont mis d'accord, une variante autorise les espaces vides dans la combinaison.

La variante la plus connue est d'utiliser des mots à faire deviner. Le jeu, parfois appelé Mastermot devient alors beaucoup plus compliqué car le nombre de combinaisons possible augmente exponentiellement.

Une variante (qui nécessite que les joueurs se soient mis d'accord) est d'autoriser un trou (une case sans pion/couleur).

Le Mastermind est souvent utilisé comme énigme dans les jeux vidéo, comme dans Old School RuneScape (OSRS) où un Mastermind fait suer les joueurs (Fremennik Exiles).

Le jeu de société Mastermind crédite Mordecai Meirovitz comme auteur en 1971.