Comment résoudre le jeu de devinettes "Mastermind" ?

Question

Comment créeriez-vous un algorithme pour résoudre l'énigme suivante, "Mastermind" ?

Votre adversaire a choisi quatre couleurs différentes parmi un ensemble de six (jaune, bleu, vert, rouge, orange, violet). Vous devez deviner lesquelles il a choisies et dans quel ordre. Après chaque devinette, votre adversaire vous dit combien (mais pas lesquelles) des couleurs que vous avez devinées étaient la bonne couleur au bon endroit ["noirs"] et combien (mais pas lesquelles) étaient la bonne couleur mais au mauvais endroit ["blancs"]. Le jeu se termine lorsque vous avez deviné correctement (4 noirs, 0 blanc).

Par exemple, si votre adversaire a choisi (bleu, vert, orange, rouge), et que vous devinez (jaune, bleu, vert, rouge), vous obtiendrez un "noir" (pour le rouge), et deux blancs (pour le bleu et le vert). Vous obtiendrez le même score en devinant (bleu, orange, rouge, violet).

Je suis intéressé par l'algorithme que vous choisiriez et (éventuellement) par la façon dont vous le traduisez en code (de préférence Python). Je suis intéressé par les solutions codées qui sont :

1. Clair (facilement compréhensible)
2. Concise
3. Efficace (rapide dans la formulation d'une hypothèse)
4. Efficace (le plus petit nombre de suppositions pour résoudre l'énigme)
5. Flexible (peut facilement répondre à des questions sur l'algorithme, par exemple, quel est son pire cas ?)
6. Général (peut être facilement adapté à d'autres types de puzzle que le Mastermind)

Je suis satisfait d'un algorithme très efficace mais pas très performant (à condition qu'il ne soit pas simplement mal implémenté !); en revanche, un algorithme très efficace et performant implémenté de manière inflexible et impénétrable ne sert à rien.

J'ai ma propre solution (détaillée) en Python que j'ai postée, mais ce n'est en aucun cas la seule ou la meilleure approche, alors n'hésitez pas à en poster d'autres ! Je ne m'attends pas à un essai ;)

Answer 1

Outils clés : entropie, avidité, branchement et liaison ; Python, générateurs, itertools, modèle décoratif et non décoratif.

En répondant à cette question, j'ai voulu construire un langage de fonctions utiles pour explorer le problème. Je vais passer en revue ces fonctions, en les décrivant et en précisant leur but. À l'origine, ces fonctions disposaient d'une documentation complète, avec de petits tests unitaires intégrés testés à l'aide de doctest ; je ne saurais trop louer cette méthodologie, qui constitue un moyen brillant de mettre en œuvre le développement piloté par les tests. Cependant, elle ne se traduit pas bien sur StackOverflow, donc je ne la présenterai pas de cette façon.

Tout d'abord, j'aurai besoin de plusieurs modules standard et futur (je travaille avec Python 2.6).

from __future__ import division # No need to cast to float when dividing
import collections, itertools, math

J'aurai besoin d'une fonction de notation. A l'origine, cela retournait un tuple (noirs, blancs), mais j'ai trouvé la sortie un peu plus claire si j'utilisais un namedtuple :

Pegs = collections.namedtuple('Pegs', 'black white')
def mastermindScore(g1,g2):
  matching = len(set(g1) & set(g2))
  blacks = sum(1 for v1, v2 in itertools.izip(g1,g2) if v1 == v2)
  return Pegs(blacks, matching-blacks)

Pour rendre ma solution générale, je passe tout ce qui est spécifique au problème Mastermind comme arguments de mots-clés. J'ai donc créé une fonction qui crée ces arguments une fois, et j'utilise la syntaxe **kwargs pour la faire circuler. Cela me permet également d'ajouter facilement de nouveaux attributs si j'en ai besoin plus tard. Notez que je permets aux devinettes de contenir des répétitions, mais contraint l'adversaire à choisir des couleurs distinctes ; pour changer cela, il suffit de changer G ci-dessous. (Si je voulais autoriser les répétitions dans le secret de l'adversaire, je devrais également modifier la fonction de notation).

def mastermind(colours, holes):
  return dict(
    G           = set(itertools.product(colours,repeat=holes)),
    V           = set(itertools.permutations(colours, holes)),
    score       = mastermindScore,
    endstates   = (Pegs(holes, 0),))

def mediumGame():
    return mastermind(("Yellow", "Blue", "Green", "Red", "Orange", "Purple"), 4)

Avant de me lancer dans la solution proprement dite, j'aurai besoin de quelques outils à usage général pour clarifier le code. A multiset est comme un ensemble, sauf que les valeurs peuvent apparaître plusieurs fois. Mon implémentation bon marché utilise simplement un dict qui met en correspondance les clés avec le nombre de fois où ces clés sont présentes :

def multiset(vals):
  multiset = collections.defaultdict(int)
  for val in vals: multiset[val] += 1
  return multiset

Deuxièmement, parfois j'ai besoin de partition un ensemble basé sur le résultat de l'application d'une fonction à chaque élément de l'ensemble. Par exemple, les nombres 1..10 peuvent être partitionnés en nombres pairs et impairs par la fonction n % 2 (les impairs donnent 1, les pairs donnent 0). La fonction suivante renvoie une telle partition, mise en œuvre sous la forme d'une carte du résultat de l'appel de la fonction à l'ensemble des éléments qui ont donné ce résultat (par exemple, { 0 : pairs, 1 : impairs }).

def partition(S, func, *args, **kwargs):
  partition = collections.defaultdict(set)
  for v in S: partition[func(v, *args, **kwargs)].add(v)
  return partition

J'ai décidé d'explorer un solveur qui utilise un approche gourmande et entropique . À chaque étape, il calcule l'information qui pourrait être obtenue à partir de chaque hypothèse possible, et sélectionne l'hypothèse la plus informative. À mesure que le nombre de possibilités augmente, cette méthode sera mal adaptée (quadratiquement), mais essayons-la ! Tout d'abord, j'ai besoin d'une méthode pour calculer l'entropie (information) d'un ensemble de probabilités. Il s'agit simplement de -∑p log p. Cependant, pour des raisons de commodité, je vais autoriser des entrées qui ne sont pas normalisées, c'est-à-dire dont la somme n'est pas égale à 1 :

def entropy(P):
  total = sum(P)
  return -sum(p*math.log(p, 2) for p in (v/total for v in P if v))

Alors comment vais-je utiliser cette fonction ? Eh bien, pour un ensemble de possibilités donné, V, et une estimation donnée, g, les informations que nous obtenons de cette estimation ne peuvent provenir que de la fonction de notation : plus précisément, de la façon dont cette fonction de notation divise notre ensemble de possibilités. Nous voulons faire une proposition qui distingue le mieux les possibilités restantes, c'est-à-dire qui les divise en un grand nombre de petits ensembles, car cela signifie que nous sommes beaucoup plus proches de la réponse. C'est exactement ce que la fonction d'entropie ci-dessus chiffre : un grand nombre de petits ensembles obtiendra un score plus élevé qu'un petit nombre de grands ensembles. Tout ce que nous avons à faire, c'est de le mettre à plat.

def decisionEntropy(V, g, score):
  return entropy(multiset(score(gi, g) for gi in V).values())

Bien sûr, à chaque étape, nous aurons en fait un ensemble de possibilités restantes, V, et un ensemble de suppositions possibles que nous pourrions faire, G, et nous devrons choisir la supposition qui maximise l'entropie. De plus, si plusieurs suppositions ont la même entropie, il faut préférer en choisir une qui pourrait aussi être une solution valide ; cela garantit que l'approche se terminera. Pour ce faire, j'utilise le modèle standard python decorate-undecorate ainsi que la méthode max intégrée :

def bestDecision(V, G, score):
  return max((decisionEntropy(V, g, score), g in V, g) for g in G)[2]

Il ne me reste plus qu'à appeler cette fonction de manière répétée jusqu'à ce que le bon résultat soit deviné. J'ai passé en revue un certain nombre d'implémentations de cet algorithme jusqu'à ce que j'en trouve une qui me semble correcte. Plusieurs de mes fonctions voudront aborder cette question de différentes manières : certaines énumèrent toutes les séquences possibles de décisions (une par supposition que l'adversaire a pu faire), tandis que d'autres ne sont intéressées que par un seul chemin à travers l'arbre (si l'adversaire a déjà choisi un secret, et que nous essayons simplement d'atteindre la solution). Ma solution est un "arbre paresseux", où chaque partie de l'arbre est un générateur qui peut être évalué ou non, permettant à l'utilisateur d'éviter des calculs coûteux dont il n'aura pas besoin. J'ai également fini par utiliser deux namedtuples supplémentaires, toujours pour la clarté du code.

Node = collections.namedtuple('Node', 'decision branches')
Branch = collections.namedtuple('Branch', 'result subtree')
def lazySolutionTree(G, V, score, endstates, **kwargs):
  decision = bestDecision(V, G, score)
  branches = (Branch(result, None if result in endstates else
                   lazySolutionTree(G, pV, score=score, endstates=endstates))
              for (result, pV) in partition(V, score, decision).iteritems())
  yield Node(decision, branches) # Lazy evaluation

La fonction suivante évalue un seul chemin dans cet arbre, sur la base d'une fonction de notation fournie :

def solver(scorer, **kwargs):
  lazyTree = lazySolutionTree(**kwargs)
  steps = []
  while lazyTree is not None:
    t = lazyTree.next() # Evaluate node
    result = scorer(t.decision)
    steps.append((t.decision, result))
    subtrees = [b.subtree for b in t.branches if b.result == result]
    if len(subtrees) == 0:
      raise Exception("No solution possible for given scores")
    lazyTree = subtrees[0]
  assert(result in endstates)
  return steps

On peut maintenant l'utiliser pour construire un jeu interactif de Mastermind où l'utilisateur note les suppositions de l'ordinateur. En jouant avec ce jeu, on découvre des choses intéressantes. Par exemple, la première réponse la plus informative est de la forme (jaune, jaune, bleu, vert) et non (jaune, bleu, vert, rouge). On obtient des informations supplémentaires en utilisant exactement la moitié des couleurs disponibles. Cela vaut également pour le jeu Mastermind à 3 trous à 6 couleurs - (jaune, bleu, vert) - et le jeu Mastermind à 5 trous à 8 couleurs - (jaune, jaune, bleu, vert, rouge).

Mais il reste encore de nombreuses questions auxquelles il n'est pas facile de répondre avec un solveur interactif. Par exemple, quel est le nombre maximum d'étapes nécessaires à l'approche entropique gloutonne ? Et combien d'entrées nécessitent autant d'étapes ? Pour faciliter la réponse à ces questions, je produis d'abord une fonction simple qui transforme l'arbre paresseux ci-dessus en un ensemble de chemins à travers cet arbre, c'est-à-dire, pour chaque secret possible, une liste de suppositions et de scores.

def allSolutions(**kwargs):
  def solutions(lazyTree):
    return ((((t.decision, b.result),) + solution
             for t in lazyTree for b in t.branches
             for solution in solutions(b.subtree))
            if lazyTree else ((),))
  return solutions(lazySolutionTree(**kwargs))

Trouver le pire cas est une simple question de trouver la solution la plus longue :

def worstCaseSolution(**kwargs):
  return max((len(s), s) for s in allSolutions(**kwargs)) [1]

Il s'avère que ce solveur se termine toujours en 5 étapes ou moins. Cinq étapes ! Je sais que lorsque je jouais à Mastermind dans mon enfance, je mettais souvent plus de temps que cela. Cependant, depuis que j'ai créé ce solveur et que j'ai joué avec, j'ai grandement amélioré ma technique, et 5 étapes est en effet un objectif réalisable même si vous n'avez pas le temps de calculer la supposition entropiquement idéale à chaque étape ;)

Quelle est la probabilité que le solveur prenne 5 étapes ? Va-t-il jamais finir en 1 ou 2 étapes ? Pour le savoir, j'ai créé une autre petite fonction simple qui calcule la distribution de la longueur de la solution :

def solutionLengthDistribution(**kwargs):
  return multiset(len(s) for s in allSolutions(**kwargs))

Pour l'approche entropique gourmande, avec répétitions autorisées : 7 cas prennent 2 étapes ; 55 cas prennent 3 étapes ; 229 cas prennent 4 étapes ; et 69 cas prennent le maximum de 5 étapes.

Bien sûr, il n'y a aucune garantie que l'approche entropique gourmande minimise le nombre d'étapes dans le pire des cas. La dernière partie de mon langage polyvalent est un algorithme qui décide si oui ou non il y a des étapes à franchir. tout solutions pour une limite donnée dans le pire des cas. Cela nous permettra de savoir si l'entropie gourmande est idéale ou non. Pour ce faire, j'adopte une stratégie de branch-and-bound :

def solutionExists(maxsteps, G, V, score, **kwargs):
  if len(V) == 1: return True
  partitions = [partition(V, score, g).values() for g in G]
  maxSize = max(len(P) for P in partitions) ** (maxsteps - 2)
  partitions = (P for P in partitions if max(len(s) for s in P) <= maxSize)
  return any(all(solutionExists(maxsteps-1,G,s,score) for l,s in
                 sorted((-len(s), s) for s in P)) for i,P in
             sorted((-entropy(len(s) for s in P), P) for P in partitions))

Il s'agit sans aucun doute d'une fonction complexe, c'est pourquoi un peu plus d'explications sont nécessaires. La première étape consiste à partitionner les solutions restantes en fonction de leur score après une estimation, comme précédemment, mais cette fois nous ne savons pas quelle estimation nous allons faire, donc nous stockons toutes les partitions. Maintenant, nous pourrait Il serait possible d'effectuer une récursion dans chacun d'entre eux, en énumérant effectivement l'univers entier des arbres de décision possibles, mais cela prendrait un temps horriblement long. Au lieu de cela, j'observe que, si à ce stade il n'y a pas de partition qui divise les solutions restantes en plus de n ensembles, alors il ne peut y avoir de telle partition à aucune étape future non plus. Si nous avons encore k étapes, cela signifie que nous pouvons distinguer entre au plus n k-1 solutions avant d'être à court de suppositions (à la dernière étape, nous devons toujours deviner correctement). Ainsi, nous pouvons rejeter toutes les partitions qui contiennent un score associé à plus de ce nombre de solutions. Ce sont les deux lignes de code suivantes.

La dernière ligne de code effectue la récursion, en utilisant les fonctions any et all de Python pour plus de clarté, et en essayant d'abord les décisions à plus forte entropie pour espérer minimiser le temps d'exécution dans le cas positif. Il récursionne également dans la plus grande partie de la partition en premier, car c'est la plus susceptible d'échouer rapidement si la décision était mauvaise. Une fois de plus, j'utilise le modèle standard decorate-undecorate, cette fois-ci pour envelopper la fonction Python trié fonction.

def lowerBoundOnWorstCaseSolution(**kwargs):
  for steps in itertools.count(1):
    if solutionExists(maxsteps=steps, **kwargs):
      return steps

En appelant solutionExists à plusieurs reprises avec un nombre croissant d'étapes, nous obtenons une limite inférieure stricte sur le nombre d'étapes nécessaires dans le pire des cas pour une solution Mastermind : 5 étapes. L'approche entropique gourmande est en effet optimale.

Par curiosité, j'ai inventé un autre jeu de devinette, que j'ai surnommé "twoD". Dans ce jeu, vous essayez de deviner une paire de chiffres ; à chaque étape, on vous dit si votre réponse est correcte, si les chiffres que vous avez devinés ne sont pas inférieurs aux chiffres correspondants dans le secret, et si les chiffres ne sont pas supérieurs.

Comparison = collections.namedtuple('Comparison', 'less greater equal')
def twoDScorer(x, y):
  return Comparison(all(r[0] <= r[1] for r in zip(x, y)),
                    all(r[0] >= r[1] for r in zip(x, y)),
                    x == y)
def twoD():
  G = set(itertools.product(xrange(5), repeat=2))
  return dict(G = G, V = G, score = twoDScorer,
              endstates = set(Comparison(True, True, True)))

Pour ce jeu, l'approche entropique avide a un pire cas de cinq étapes, mais il existe une meilleure solution possible avec un pire cas de quatre étapes, confirmant mon intuition que l'avidité myopique n'est idéale que par coïncidence pour Mastermind. Plus important encore, cela a montré la flexibilité de mon langage : toutes les mêmes méthodes fonctionnent pour ce nouveau jeu de devinette que pour Mastermind, ce qui me permet d'explorer d'autres jeux avec un minimum de codage supplémentaire.

Qu'en est-il des performances ? Évidemment, étant implémenté en Python, ce code ne sera pas d'une rapidité fulgurante. J'ai également abandonné certaines optimisations possibles au profit d'un code clair.

Une optimisation bon marché consiste à observer que, lors du premier coup, la plupart des suppositions sont fondamentalement identiques : (jaune, bleu, vert, rouge) n'est pas vraiment différent de (bleu, rouge, vert, jaune), ou (orange, jaune, rouge, violet). Cela réduit considérablement le nombre de suppositions que nous devons prendre en compte lors de la première étape - autrement la décision la plus coûteuse du jeu.

Cependant, en raison du taux de croissance élevé de ce problème, je n'ai pas été en mesure de résoudre le problème Mastermind à 8 couleurs et 5 trous, même avec cette optimisation. Au lieu de cela, j'ai porté les algorithmes en C++, en gardant la même structure générale et en utilisant des opérations bitwise pour améliorer les performances dans les boucles internes critiques, pour une accélération de plusieurs ordres de grandeur. Je laisse au lecteur le soin de faire cet exercice :)

Answer 2

J'ai écrit une fois un solveur "Jotto" qui est essentiellement "Master Mind" avec des mots. (Nous choisissons chacun un mot et nous devinons à tour de rôle le mot de l'autre, en marquant des points pour les correspondances exactes et pour les correspondances erronées (lettre/couleur correcte, mais mauvais placement).

La clé pour résoudre un tel problème est de réaliser que la fonction de notation est symétrique.

En d'autres termes, si score(myguess) == (1,2) alors je peux utiliser la même score() pour comparer mon estimation précédente avec toute autre possibilité et éliminer celles qui ne donnent pas exactement le même résultat.

Laissez-moi vous donner un exemple : Le mot caché (cible) est "score" ... la supposition actuelle est "fools" --- le score est 1,1 (une lettre, 'o', est "juste" ; une autre lettre, 's', est "ailleurs"). Je peux éliminer le mot "deviner" car le `score("deviner") (contre "fous") renvoie (1,0) (le "s" final correspond, mais rien d'autre ne correspond). Donc le mot "guess" n'est pas compatible avec "fools" et un score contre un mot inconnu qui a donné retourne un score de (1,1).

Je peux donc maintenant parcourir chaque mot de cinq lettres (ou combinaison de cinq couleurs/lettres/chiffres, etc.) et éliminer tout ce qui n'obtient pas un score de 1,1 contre les "fous". Faites-le à chaque itération et vous convergerez très rapidement vers la cible. (Pour les mots de cinq lettres, j'ai pu obtenir moins de 6 essais à chaque fois... et généralement seulement 3 ou 4). Bien sûr, il n'y a que 6000 "mots" environ et vous éliminez près de 95% de chaque tentative.

Remarque : pour la discussion qui suit, je parle de "combinaison" de cinq lettres plutôt que de quatre éléments de six couleurs. Les mêmes algorithmes s'appliquent ; cependant, le problème est beaucoup plus petit pour l'ancien jeu "Master Mind" ... il n'y a que 1296 combinaisons (6**4) de pions de couleur dans le programme "Master Mind" classique, en supposant que les doublons sont autorisés. Le raisonnement qui conduit à la convergence fait appel à la combinatoire : il y a 20 scores possibles non gagnants pour une cible à cinq éléments ( n = [(a,b) for a in range(5) for b in range(6) if a+b <= 5] pour les voir tous si vous êtes curieux. On peut donc s'attendre à ce que toute sélection aléatoire valide ait environ 5 % de chances de correspondre à notre score... les 95 % restants n'y correspondront pas et seront donc éliminés pour chaque réponse. Cela ne tient pas compte des regroupements possibles dans les modèles de mots, mais le comportement dans le monde réel est assez proche pour les mots et certainement encore plus proche pour les règles de "Master Mind". Cependant, avec seulement 6 couleurs dans 4 emplacements, nous n'avons que 14 scores non gagnants possibles, donc notre convergence n'est pas aussi rapide).

Pour Jotto, les deux défis mineurs sont les suivants : générer une bonne liste de monde ( awk -f 'length($0)==5' /usr/share/dict/words ou similaire sur un système UNIX) et ce qu'il faut faire si l'utilisateur a choisi un mot qui n'est pas dans notre dictionnaire (générer chaque combinaison de lettres, de 'aaaaa' à 'zzzzz' --- ce qui fait 26 ** 5 ... ou ~1,1 million). Un générateur de combinaison trivial en Python prend environ 1 minute pour générer toutes ces chaînes de caractères ... un générateur optimisé devrait faire beaucoup mieux. (Je peux également ajouter une exigence selon laquelle chaque "mot" doit avoir au moins une voyelle ... mais cette contrainte n'aide pas beaucoup --- 5 voyelles * 5 emplacements possibles pour cela et ensuite multiplié par 26 ** 4 autres combinaisons).

Pour Master Mind, vous utilisez le même générateur de combinaisons ... mais avec seulement 4 ou 5 "lettres" (couleurs). Chaque combinaison de 6 couleurs (15 625 d'entre elles) peut être générée en moins d'une seconde (en utilisant le même générateur de combinaisons que j'ai utilisé ci-dessus).

Si j'écrivais ce programme "Jotto" aujourd'hui, en Python par exemple, je "tricherais" en ayant un thread générant toutes les combinaisons de lettres en arrière-plan pendant que j'élimine encore des mots du dictionnaire (pendant que mon adversaire me note, devine, etc.). Au fur et à mesure que je les générais, j'éliminais également tous les mots devinés jusqu'à présent. Ainsi, après avoir éliminé tous les mots connus, je n'aurais qu'une liste relativement restreinte de possibilités et, face à un joueur humain, j'aurais "caché" la majeure partie de mon retard de calcul en le faisant en parallèle avec ses entrées. (Et, si j'écrivais une version serveur web d'un tel programme, je ferais en sorte que mon moteur web communique avec un démon local pour demander des séquences cohérentes avec un ensemble de scores. Le démon conserverait une liste générée localement de toutes les combinaisons de lettres et utiliserait une fonction select.select() pour renvoyer des possibilités à chacune des instances du jeu en cours d'exécution --- chacune renverrait à mon démon des paires mot/score que mon démon appliquerait comme un filtre sur les possibilités qu'il renvoie à ce client).

(En comparaison, j'ai écrit ma version de "Jotto" il y a environ 20 ans sur un XT en utilisant Borland TurboPascal ... et il pouvait faire chaque itération d'élimination --- en commençant par sa liste compilée de quelques milliers de mots --- en bien moins d'une seconde. J'ai construit sa liste de mots en écrivant un simple générateur de combinaisons de lettres (voir ci-dessous) ... j'ai enregistré les résultats dans un fichier de taille moyenne, puis j'ai lancé le correcteur orthographique de mon traitement de texte avec une macro pour supprimer tout ce qui était "mal orthographié" --- puis j'ai utilisé une autre macro pour envelopper toutes les lignes restantes dans la ponctuation correcte pour en faire des affectations statiques valides à mon tableau, qui était un fichier #include de mon programme. Tout cela m'a permis de construire un programme de jeu autonome qui "connaissait" à peu près tous les mots anglais valides de 5 lettres ; le programme était un .COM --- moins de 50KB si je me souviens bien).

Pour d'autres raisons, j'ai récemment écrit un générateur de combinaisons arbitraires simple en Python. C'est environ 35 lignes de code et je l'ai posté sur mon wiki "trite snippets" sur bitbucket.org ... ce n'est pas un "générateur" au sens de Python ... mais une classe que vous pouvez instancier pour obtenir une séquence infinie de combinaisons "numériques" ou "symboliques" d'éléments (essentiellement en comptant dans n'importe quelle base d'entiers positifs).

Vous pouvez le trouver à l'adresse suivante : Trite Snippets : Générateur de combinaisons de séquences arbitraires

Pour la partie de correspondance exacte de notre score() vous pouvez simplement utiliser cette fonction :

def score(this, that):
    '''Simple "Master Mind" scoring function'''
    exact = len([x for x,y in zip(this, that) if x==y])
    ### Calculating "other" (white pegs) goes here:
    ### ...
    ###
    return (exact,other)

Je pense que cela illustre une partie de la beauté de Python : zip() up les deux séquences, retourner celles qui correspondent, et prendre la longueur des résultats).

Trouver les correspondances dans les "autres" endroits est trompeusement plus compliqué. Si les répétitions n'étaient pas autorisées, il suffirait d'utiliser des ensembles pour trouver les intersections.

[Dans mon édition précédente de ce message, quand j'ai réalisé comment je pouvais utiliser zip() pour les correspondances exactes, j'ai pensé à tort qu'on pouvait s'en sortir avec other = len([x for x,y in zip(sorted(x), sorted(y)) if x==y]) - exact ... mais il était tard et j'étais fatigué. En dormant dessus, j'ai réalisé que la méthode était défectueuse. Mauvais, Jim ! Ne postez pas sans adéquat testing!* (Testé plusieurs cas qui se sont avérés fonctionner) ].

Dans le passé, l'approche que j'utilisais était de trier les deux listes, de comparer les têtes de chacune : si les têtes sont égales, incrémenter le compte et sortir de nouveaux éléments des deux listes. Sinon, sortir une nouvelle valeur dans la plus petite des deux têtes et réessayer. Interrompez dès que l'une des listes est vide.

Cela fonctionne, mais c'est assez verbeux. Le meilleur résultat que j'ai pu obtenir avec cette approche est un peu plus d'une douzaine de lignes de code :

other = 0
x = sorted(this)   ## Implicitly converts to a list!
y = sorted(that)
while len(x) and len(y):
    if x[0] == y[0]:
        other += 1
        x.pop(0)
        y.pop(0)
    elif x[0] < y[0]:
        x.pop(0)
    else:
        y.pop(0)
other -= exact

En utilisant un dictionnaire, je peux réduire ce chiffre à environ neuf :

other = 0
counters = dict()
for i in this:
    counters[i] = counters.get(i,0) + 1
for i in that:
    if counters.get(i,0) > 0:
        other += 1
        counters[i] -= 1
other -= exact

(En utilisant la nouvelle classe "collections.Counter" (Python3 et prévue pour Python 2.7 ?), je pourrais sans doute réduire encore un peu plus cet aspect ; trois lignes ici initialisent la collection de compteurs).

Il est important de décrémenter le "compteur" lorsque nous trouvons une correspondance et il est vital de vérifier que le compteur est supérieur à zéro dans notre test. Si une lettre ou un symbole donné apparaît une fois dans "ceci" et deux fois dans "cela", il ne doit être considéré comme une correspondance qu'une seule fois.

La première approche est certainement un peu plus délicate à écrire (il faut veiller à éviter les limites). De plus, dans quelques tests rapides (testant un million de paires de lettres générées aléatoirement), la première approche prend environ 70% plus de temps que celle utilisant des dictionnaires. (La génération du million de paires de chaînes de caractères à l'aide de random.shuffle() a pris plus de deux fois plus de temps que la plus lente des fonctions de notation, d'autre part).

Une analyse formelle de la performance de ces deux fonctions serait compliquée. La première méthode a deux tris, donc ce serait 2 * O(n*log(n)) ... et elle itère à travers au moins une des deux chaînes et doit éventuellement itérer jusqu'à la fin de l'autre chaîne (meilleur cas O(n), pire cas O(2n)) -- je dois mal utiliser la notation big-O ici, mais c'est juste une estimation approximative. Le deuxième cas dépend entièrement des caractéristiques de performance du dictionnaire. Si nous utilisions des b-trees, les performances seraient approximativement de O(n*log(n) pour la création et la recherche de chaque élément à partir de l'autre chaîne serait une autre opération de O(n*log(n)). Cependant, les dictionnaires Python sont très efficaces et ces opérations devraient être proches du temps constant (très peu de collisions de hachage). On peut donc s'attendre à une performance d'environ O(2n) ... ce qui se simplifie bien sûr en O(n). Cela correspond à peu près aux résultats de mon benchmark.

En parcourant l'article de Wikipedia sur " Master Mind " Je vois que Donald Knuth a utilisé une approche qui commence de manière similaire à la mienne (et 10 ans plus tôt) mais il a ajouté une optimisation significative. Après avoir rassemblé toutes les possibilités restantes, il sélectionne celle qui élimine le plus grand nombre de possibilités au tour suivant. J'ai envisagé une telle amélioration de mon propre programme et j'ai rejeté l'idée pour des raisons pratiques. Dans son cas, il recherchait une solution (mathématique) optimale. Dans mon cas, je me préoccupais de la jouabilité (sur un XT, en utilisant de préférence moins de 64 Ko de RAM, bien que je puisse passer au format .EXE et utiliser jusqu'à 640 Ko). Je voulais que le temps de réponse soit de l'ordre d'une ou deux secondes (ce qui était facile avec mon approche mais qui serait beaucoup plus difficile avec la notation spéculative). (Rappelez-vous que je travaillais en Pascal, sous MS-DOS ... pas de threads, bien que j'aie implémenté un support pour une interrogation asynchrone grossière de l'interface utilisateur, qui s'est avérée inutile).

Si j'écrivais une telle chose aujourd'hui, j'ajouterais un fil pour faire la meilleure sélection, aussi. Cela me permettrait de donner la meilleure estimation que j'ai trouvée dans une certaine limite de temps, afin de garantir que mon joueur n'ait pas à attendre trop longtemps mon estimation. Naturellement, ma sélection/élimination se déroulerait en attendant les estimations de mon adversaire.

Answer 3

Avez-vous vu Raymond Hettingers tentative ? Ils correspondent certainement à certaines de vos exigences.

Je me demande comment ses solutions se comparent aux vôtres.

Answer 4

Il existe un excellent site sur la stratégie MasterMind. ici . L'auteur commence par des problèmes MasterMind très simples (en utilisant des chiffres plutôt que des lettres, et en ignorant l'ordre et la répétition) pour arriver progressivement à un problème MasterMind complet (en utilisant des couleurs, qui peuvent être répétées, dans n'importe quel ordre, même avec la possibilité d'erreurs dans les indices).

Les sept tutoriels présentés sont les suivants :

• Tutoriel 1 - La configuration de jeu la plus simple ( pas d'erreurs, ordre fixe, pas de répétitions )
• Tutorial 2 - Le code peut contenir des espaces vides ( pas d'erreurs, ordre fixe, pas de répétitions )
• Tutoriel 3 - Les conseils peuvent contenir des erreurs ( ordre fixe, pas de répétition )
• Tutoriel 4 - Début du jeu à partir du milieu ( pas d'erreurs, ordre fixe, pas de répétitions )
• Tutoriel 5 - Les chiffres / couleurs peuvent être répétés ( pas d'erreurs, ordre fixe, chaque couleur répétée au maximum 4 fois )
• Tutoriel 6 - Chiffres / couleurs disposés dans un ordre aléatoire ( pas d'erreurs, ordre aléatoire, pas de répétition )
• Tutoriel 7 - Tout mettre en place ( pas d'erreurs, ordre aléatoire, chaque couleur répétée au maximum 4 fois )

Answer 5

J'ai juste pensé que je pourrais contribuer avec mes 90 lignes de code. Je me suis basé sur @Jim Dennis La réponse est "oui", ce qui enlève surtout l'indication de la notation symétrique. J'ai implémenté l'algorithme minimax tel qu'il est décrit sur le site du Article de Mastermind wikipedia par Knuth, à une exception près : Je limite mon prochain mouvement à la liste actuelle des solutions possibles, car j'ai trouvé que la performance se détériorait gravement en prenant en compte toutes les solutions possibles à chaque étape. L'approche actuelle me laisse dans le pire des cas 6 suppositions pour toute combinaison, chacune étant trouvée en moins d'une seconde.

Il est peut-être important de noter que je n'impose aucune restriction à la séquence cachée, autorisant un nombre illimité de répétitions.

from itertools import product, tee
from random import choice

COLORS = 'red ', 'green', 'blue', 'yellow', 'purple', 'pink'#, 'grey', 'white', 'black', 'orange', 'brown', 'mauve', '-gap-'
HOLES = 4

def random_solution():
    """Generate a random solution."""
    return tuple(choice(COLORS) for i in range(HOLES))

def all_solutions():
    """Generate all possible solutions."""
    for solution in product(*tee(COLORS, HOLES)):
        yield solution

def filter_matching_result(solution_space, guess, result):
    """Filter solutions for matches that produce a specific result for a guess."""
    for solution in solution_space:
        if score(guess, solution) == result:
            yield solution

def score(actual, guess):
    """Calculate score of guess against actual."""
    result = []
    #Black pin for every color at right position
    actual_list = list(actual)
    guess_list = list(guess)
    black_positions = [number for number, pair in enumerate(zip(actual_list, guess_list)) if pair[0] == pair[1]]
    for number in reversed(black_positions):
        del actual_list[number]
        del guess_list[number]
        result.append('black')
    #White pin for every color at wrong position
    for color in guess_list:
        if color in actual_list:
            #Remove the match so we can't score it again for duplicate colors
            actual_list.remove(color)
            result.append('white')
    #Return a tuple, which is suitable as a dictionary key
    return tuple(result)

def minimal_eliminated(solution_space, solution):
    """For solution calculate how many possibilities from S would be eliminated for each possible colored/white score.
    The score of the guess is the least of such values."""
    result_counter = {}
    for option in solution_space:
        result = score(solution, option)
        if result not in result_counter.keys():
            result_counter[result] = 1
        else:
            result_counter[result] += 1
    return len(solution_space) - max(result_counter.values())

def best_move(solution_space):
    """Determine the best move in the solution space, being the one that restricts the number of hits the most."""
    elim_for_solution = dict((minimal_eliminated(solution_space, solution), solution) for solution in solution_space)
    max_elimintated = max(elim_for_solution.keys())
    return elim_for_solution[max_elimintated]

def main(actual = None):
    """Solve a game of mastermind."""
    #Generate random 'hidden' sequence if actual is None
    if actual == None:
        actual = random_solution()

    #Start the game of by choosing n unique colors
    current_guess = COLORS[:HOLES]

    #Initialize solution space to all solutions
    solution_space = all_solutions()
    guesses = 1
    while True:
        #Calculate current score
        current_score = score(actual, current_guess)
        #print '\t'.join(current_guess), '\t->\t', '\t'.join(current_score)
        if current_score == tuple(['black'] * HOLES):
            print guesses, 'guesses for\t', '\t'.join(actual)
            return guesses

        #Restrict solution space to exactly those hits that have current_score against current_guess
        solution_space = tuple(filter_matching_result(solution_space, current_guess, current_score))

        #Pick the candidate that will limit the search space most
        current_guess = best_move(solution_space)
        guesses += 1

if __name__ == '__main__':
    print max(main(sol) for sol in all_solutions())

Si quelqu'un voit des améliorations possibles au code ci-dessus, je serais très intéressé par vos suggestions.