Quel est l'algorithme optimal pour jouer au jeu de mots de pendentif?

Question

Supposons que nous jouons au jeu Hangman . Mon adversaire et moi avons tous deux accès au dictionnaire pendant le match. Mon adversaire choisit un mot du dictionnaire avec la connaissance de l'algorithme que je vais utiliser pour deviner son mot secret. Une fois que mon adversaire a choisi un mot, je n'ai que la longueur du mot. Je peux deviner une lettre que je pense être dans le mot, et si c'est dans le mot mon adversaire identifie toutes les positions de cette lettre dans ce mot. Si je suppose une lettre qui n'est pas dans le mot, cela comptait une erreur. Si je peux deviner le mot avant trop d'erreurs, je gagne.

L'objectif de mon adversaire devrait être de choisir un mot qui optimise le nombre d'erreurs (suppositions incorrectes) que je fais avant de pouvoir deviner le mot. Mon objectif est de les minimiser. (Traditionnellement, si le nombre d'erreurs est> Quelque numéro, je perds le jeu, mais nous pouvons nous détendre cette contrainte.)

Considérons trois algorithmes pour la lettre de devinette. Ce sont les principaux que j'ai pensés, mais il y a probablement plus, et je me félicite d'autres idées. Dans les trois algorithmes, la première étape consistera à rassembler la liste des mots qui ont la même longueur que le mot secret. Ensuite, pour chaque lettre de l'alphabet, comptez le nombre de mots dans le dictionnaire contenant cette lettre. Par exemple, peut-être 5000 contiennent "A", 300 contiennent "B", etc. Ici c'est en python:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

Après c'est là que les trois algorithmes divergent.

1. Dans le premier algorithme, nous devinons la lettre que le plus nombre de mots restants contiennent. Donc, si 5000 mots restants contiennent "A" et aucune autre lettre ne sont dans ce nombre de mots, nous choisirons "A" à chaque fois. Si "A" est correct, cela nous donne des informations positionnelles américaines que nous pouvons filtrer la liste. Par exemple, nous pourrions filtrer la liste par tous les mots correspondant à ".a ..". (Les points sont des lettres inconnues.) Si "A" est incorrect, nous filtrons tous les mots contenant "A". Dans le cas où il y a une cravate et deux lettres se trouvent dans un nombre égal de mots, les lettres sont choisies par ordre alphabétique. Donc, si nous connaissons le mot correspondant ".As", nous devinerons des mots par ordre alphabétique.

2. Ceci n'est que légèrement différent de la première algorithme. Au lieu de toujours choisir un ordre alphabétique, dans le cas d'une cravate, nous choisissons des lettres au hasard. Cela a l'avantage que notre adversaire ne sait pas ce que nous allons choisir. Dans la première stratégie, "rayons" est toujours meilleur que "jours". Cela évite ce problème.

3. Dans ce cas, nous choisissons des lettres avec une probabilité proportionnelle au nombre de mots contenant cette lettre. Au début, lorsque nous avons compté le nombre de mots contenant "A" et le nombre qui contiennent "B", etc., puisque "A" se trouvait dans le plus grand nombre de mots, dans les stratégies 1 et 2, nous avons choisi " un "100% du temps. Au lieu de cela, nous choisirons toujours "A" une pluralité du temps, mais un petit nombre de fois que nous choisirons "Z", même si une puissance peut être trouvée dans 10 fois plus de mots. J'ai mes doutes sur cette stratégie étant optimale mais Il a été utilisé dans la recherche en 2010 .

J'ai donc deux questions:

1. Quelle est la stratégie de lettre optimale que je devrais utiliser en supposant que mon adversaire sait que je vais utiliser cette stratégie ? Dans ce que nous voulons minimiser le nombre moyen de suppositions qu'il faudra pour deviner le mot secret.
2. Pour un mot donné, disons "paie", quel est le nombre moyen d'erreurs que je devrais être censée faire? Existe-t-il un moyen de calcul de forme fermée de calculer M, par opposition à l'exécution de cette simulation plusieurs fois et à la moyenne des résultats?

Clarifications

• Tout dictionnaire anglais peut être utilisé. Par exemple, Ce dictionnaire anglais avec des mots de 84k. . Les sous-ensembles de dictionnaires soigneusement choisis pour que l'ambiguïté puisse également être intéressant, mais sont en dehors du champ d'application de cette question.
• Il n'y a pas de contrainte sur la taille du mot tant que le mot est dans le dictionnaire. Le devineur connaîtra la taille du mot avant qu'il ne commence à deviner.
• Seul le nombre total de erreurs importe, ce qui est indépendant de la taille du mot. Vous n'obtenez pas plus de chances de mots plus longs, ou moins de chances de plus courte.
• Je ne suis que si vous souhaitez minimiser le nombre moyen d'erreurs. S'il y a deux algorithmes optimaux qui ont un nombre moyen d'erreurs moyen équivalent, les deux sont acceptables.
• en principe, il est possible que là-bas soit une situation où choisir une lettre (dire "B") conduit à plus d'informations que d'autres (dire "A") même si "A" se produit dans des mots plus possibles que "B" Est-ce que. Je suis ouvert à cette possibilité dans la pratique aussi. Les trois algorithmes illustrés ci-dessus supposent que th

Cela ne se produit pas en raison du fait qu'une hypothèse correcte a tendance à donner plus d'informations que d'informations incorrectes (c'est-à-dire des informations positionnelles sur une lettre correcte, c'est généralement meilleur que "cette lettre n'est pas dans le mot").Mais un algorithme optimal n'a pas besoin de faire cette hypothèse.

Answer 1

Il est possible de calculer la stratégie optimale, mais le calcul pourrait être assez intensif, et je ne sais pas si cela vous donnera une grande partie d'un gain sur de simples heuristiques. Je vais expliquer comment ci-dessous. L'idée principale est d'utiliser la programmation dynamique.

Stratégies déterministes

Permettez-moi de commencer à commencer par le cas particulier des stratégies déterministes de choisir quelle lettre deviner ensuite, car elles sont les plus faciles à analyser. Cela nous donnera une échauffement avant de passer à des stratégies randomisées (qui seront probablement supérieures).

L'état du jeu à tout moment peut être résumé par la paire $ (g, r) $ , où $ g $ est l'ensemble de lettres qui ont été devinées jusqu'à présent et $ r $ est les réponses (c.-à-d. La séquence des blancs et des lettres de $ g $ visible au lecteur). L'ordre des suppositions passées n'a pas d'importance (c'est pourquoi il suffit d'avoir un ensemble $ g $ des suppositions antérieures). Nous dirons qu'un mot $ w $ est cohérent avec $ (g, r) $ s'il Reste possible, c'est-à-dire que si le mot de l'adversaire est $ w $ et vous faites les suppositions dans $ g $ , alors vous obtiendriez la réponse $ r $ .

let $ p (g, r)= 1 $ S'il est possible de gagner à partir d'ici, si vous commencez à partir de l'état $ (g, r) $ . Cela signifie qu'il existe une stratégie de gagner: où quelle que soit le mot que l'adversaire pense (tant qu'il est cohérent avec $ (g, r) $ ) , le nombre de mauvaises suppositions que vous avez faites jusqu'à présent, ainsi que le nombre que vous apportez à l'avenir avec cette stratégie, ne dépassera pas la limite supérieure. Sinon, définissez $ p (g, r)= 0 $ .

Vous pouvez maintenant calculer $ p (g, r) $ avec programmation dynamique, en utilisant la relation récurrence

$$ p (g, r)=bigvee_a \ bigwege _ {(g ', r')} p (g ', r'), $$

où $ a $ gammes sur toutes les lettres non dans $ g $ (c'est-à-dire toutes les possibilités de Quelle lettre à deviner ensuite), et $ (g ', r') $ gammes sur toutes les réponses possibles si vous devinez $ A $ suivant (c.-à-d. $ g '= g \ tasse \ {A \} $ , et nous gangons tous les mots $ w $ qui sont cohérents avec $ (g, r) $ et calculez la réponse $ R '$ à devine $ g' $ si le mot est $ w $ ) .

en particulier, je vous suggère de calculer $ p (g, r) $ à l'aide de la première recherche et de la mémoire de profondeur. Alors, $ p (\ videtset, - - \ CDOTS -) $ vous dira s'il est possible de gagner dans la limite supérieure, peu importe le mot que l'adversaire choisit . En traçant le calcul en arrière, vous pouvez reconstruire la stratégie optimale.

est-ce réalisable? Je m'attends à ce que ce soit. Je pense que le nombre d'états possibles $ (g, r) $ n'est pas trop grand. (En particulier, vous pouvez ignorer les états $ (g, r) $ où vous avez déjà fait trop d'hypothèses incorrectes, et n'importe quel état où un seul mot est cohérent avec Cet état est automatiquement une victoire, il n'a donc pas besoin d'une analyse plus poussée.) Comme une optimisation, étant donné un état $ (G, R) $ , vous pouvez essayer d'énumérer Tous les mots $ w $ qui sont cohérents avec eux et simulent certaines heuristiques fixes et vérifient si elle gagnera pour chaque mot; Si tel est le cas, vous n'avez pas besoin de faire plus d'autre trershasse de profondeur et vous pouvez immédiatement marquer $ p (g, r)= 1 $ . En outre, il vous suffit de considérer devinesses $ a $ qui apparaît dans au moins un mot cohérent avec $ (g, r) $ .

Il devrait donc être assez simple de calculer la stratégie déterministe optimale.

Stratégies randomisées

Nous pouvons suivre une méthode similaire pour gérer des stratégies randomisées, mais cela devient un peu plus impliqué. Maintenant, laissez $ p (g, r) $ dénote la probabilité de gagner ici, si nous utilisons les stratégies optimales d'ici. Nous pouvons à nouveau calculer cela à l'aide de la programmation dynamique.

La différence clé est dans la relation de récurrence où nous calculons $ p (g, r) $ des quantités $ p (g ', r') $ où $ (g ', r') $ gamme sur tous les états qui auraient pu occurrence

ur ensuite après avoir deviné une lettre de plus. Ici, nous avons un simple jeu à deux joueurs. Nous choisissons d'abord une distribution de probabilité sur les lettres non dans $ g $ . Ensuite, l'adversaire voit notre distribution et choisit une distribution sur des mots $ w $ cohérent avec $ (g, r) $ . Notre gain (et le montant que l'adversaire perd) est égal à la probabilité que nous gagnons d'ici à ces choix. Notez que cela peut être calculé à partir du $ P (G ', R') $ valeurs. Il s'avère que depuis que nous allons d'abord et que l'adversaire voit notre choix, l'adversaire n'a pas besoin d'une stratégie randomisée; Ils peuvent faire de même bien avec une stratégie déterministe, c'est-à-dire en cueillant un mot unique $ w $ basé sur notre distribution. Ensuite, si nous formons une matrice $ m $ où $ m_ {w, i} $ contient la probabilité de gagnant si nous choisissons la lettre $ i $ suivant et l'adversaire choisit le mot $ w $ ; Nous pouvons remplir $ m_ {w, i} $ comme $ p (g ', r') $ où $ g '= g \ tasse \ {i \} $ et $ r' $ est le réponse à deviner $ g '$ si le mot est $ w $ . Ensuite, nous cherchons à résoudre le problème d'optimisation $$ \ max_v \ min_w (mv) _w= - min_v \ max_w - (mv) _w= - \ min_v \ | -mv \ | _ \ \fty. $$ Ceci peut être résolu Utilisation de la programmation linéaire . Donc, nous pouvons calculer $ p (g, r) $ à l'aide de la programmation linéaire à partir des valeurs $ p (g ', r ') $ où $ g' $ est un plus grand que $ g $ .

Mettre tout cela ensemble, nous utiliserons une première traversée de profondeur avec la mémoire de mémoisation (ou une programmation dynamique), en utilisant une programmation linéaire à chaque étape pour résoudre le jeu à 2 joueurs. Cela nous donne la stratégie randomisée optimale pour jouer à Hangman.

Le calcul résultant peut être très coûteux, car il nécessite des milliards ou des milliards d'étapes, où vous résolvez un programme linéaire à chaque étape. Donc, je ne sais pas si c'est réaliste de l'utiliser dans la pratique.

Certaines optimisations sont possibles, comme suggéré par @j_Random_hacker. Vous pouvez d'abord calculer $ p (g, r) $ pour des stratégies déterministes; Ensuite, vous n'avez besoin que d'envisager des stratégies randomisées pour les états $ (g, r) $ où $ p (g, r)= 0 $ .

Stratégies heuristiques

Vous avez répertorié des heuristiques raisonnables pour choisir une stratégie. Voici une autre heuristique. Compte tenu de l'état $ (g, r) $ , énumérer toutes les possibilités de la prochaine GUEST $ A \ NOTEN G $ . Concentrons sur une seule lettre $ a $ . Ensuite, pour chaque $ (g ', r') $ qui pourrait se produire comme un état suivant après avoir devinant $ a $
/ span> (donc $ g '= g \ tasse \ {A \} $ ), comptez le nombre de mots $ w $ cohérent avec $ (g ', r') $ ; Prenez le maximum de ces chiffres et utilisez-le comme le comptage associé à $ a $ . La stratégie heuristique est de choisir la lettre $ a $ dont le nombre est le plus petit.

Informatique Le nombre attendu d'erreurs

Vous pouvez calculer le nombre attendu d'erreurs d'une stratégie randomisée particulière à l'aide de la programmation dynamique. Les détails sont similaires à ci-dessus, mais la relation récurrence devient plus simple: elle devient

$$ p (g, r)=min_w \ mathbb {e} [p (g ', r')], $$

où $ w $ gammes sur tous les mots cohérents avec $ (g, r) $ , et $ (g ', r') $ est la distribution sur l'état suivant si le mot est $ w $ Et la lettre suivante devinée est choisie par votre stratégie. Compte tenu de votre stratégie et du mot $ w $ , il est facile de calculer la distribution sur les suppositions et obtenez ainsi la distribution sur les états suivants, il est donc facile de calculer $ \ mathbb {e} [p (g ', r')] $ .