Outil/Solveur pour résoudre des Mastermind automatiquement en découvrant une combinaison de couleurs en un minimum de proposition.
Solveur Mastermind - dCode
Catégorie(s) : Jeux de Société
dCode est gratuit et ses outils sont une aide précieuse dans les jeux, les maths, les énigmes, les géocaches, et les problèmes à résoudre au quotidien !
Une suggestion ? un problème ? une idée ? Écrire à dCode !
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.
Chaque lettre représente une couleur au choix, il est conseillé d'utiliser l'initiale de la couleur (mais attention aux doublons : ne pas mettre B pour Blanc et Bleu à la fois ! Préférer replacer Bleu par C (pour Cyan ou Ciel).
Exemple : L'écriture RVNJ 2 0 correspond à une proposition avec en position 1 : R pour Rouge, en position 2 : V pour Vert, en position 3 : N pour Noir et enfin en position 4 : J pour Jaune
L'
Les chiffres 2 et 0 correspondent respectivement à 2 cases couleurs correctement placées et 0 mal placées.
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.
Exemple : Noir,Noir,Blanc,Vert (1 bien placé, 2 mal placés) s'écrit : NNBV 12
Exemple : Jaune,Rien,Rien,Rien (0 bien placé, 1 mal placé) s'écrit : J--- 01 (avec - = joker)
Exemple : Rouge,Vert,Blanc (1 bien placé, sans savoir combien sont mal placés) s'écrit : RVB 1? (avec ? = joker)
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.
dCode se réserve la propriété du code source pour "Solveur Mastermind". Sauf code licence open source explicite (indiqué Creative Commons / gratuit), l'algorithme pour "Solveur Mastermind", l'applet ou snippet (convertisseur, solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage, traducteur) ou les fonctions liées à "Solveur Mastermind" (calculer, convertir, résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire) codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les données, en téléchargement, script, ou les accès API à "Solveur Mastermind" ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone ou Android !
Rappel : dCode est gratuit.
Le copier-coller de la page "Solveur Mastermind" ou de ses résultats est autorisée (même pour un usage commercial) tant que vous créditez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant sur l'icone export
Citer comme source bibliographique :
Solveur Mastermind sur dCode.fr [site web en ligne], consulté le 05/10/2024,