Was ist der optimale Algorithmus zum Spielen des Galgenmännchen-Wortspiels?

cs.stackexchange https://cs.stackexchange.com/questions/128667

Frage

Angenommen, wir spielen das Spiel Henker.Mein Gegner und ich haben während des Spiels beide Zugriff auf das Wörterbuch.Mein Gegner wählt mit Kenntnis des Algorithmus ein Wort aus dem Wörterbuch aus, mit dem ich sein geheimes Wort erraten werde.Sobald mein Gegner ein Wort ausgewählt hat, wird mir nur die Länge des Wortes angezeigt.Ich kann einen Buchstaben erraten, von dem ich denke, dass er in dem Wort vorkommt, und wenn er in dem Wort vorkommt, identifiziert mein Gegner alle Positionen dieses Buchstabens in diesem Wort.Wenn ich einen Buchstaben errate, der nicht im Wort vorkommt, zählt das als ein Fehler.Wenn ich das Wort erraten kann, bevor zu viele Fehler passieren, gewinne ich.

Das Ziel meines Gegners sollte darin bestehen, ein Wort auszuwählen, das die Anzahl der Fehler (falschen Vermutungen) maximiert, die ich mache, bevor ich das Wort erraten kann.Mein Ziel ist es, sie zu minimieren.(Traditionell verliere ich das Spiel, wenn die Anzahl der Fehler > eine bestimmte Zahl ist, aber wir können diese Einschränkung lockern.)

Betrachten Sie drei Algorithmen zum Erraten von Buchstaben.Dies sind die wichtigsten, an die ich gedacht habe, aber es gibt wahrscheinlich noch mehr, und ich begrüße alternative Ideen.Bei allen drei Algorithmen besteht der erste Schritt darin, die Liste der Wörter zusammenzustellen, die dieselbe Länge wie das geheime Wort haben.Zählen Sie dann für jeden Buchstaben im Alphabet die Anzahl der Wörter im Wörterbuch, die diesen Buchstaben enthalten.Beispielsweise enthalten vielleicht 5000 „a“, 300 enthalten „b“ und so weiter.Hier ist es in 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

Danach weichen die drei Algorithmen voneinander ab.

  1. Im ersten Algorithmus erraten wir den Buchstaben, der die meisten verbleibenden Wörter enthält.Wenn also 5000 verbleibende Wörter „a“ enthalten und keine anderen Buchstaben in so vielen Wörtern vorkommen, wählen wir jedes Mal „a“.Wenn „a“ korrekt ist, erhalten wir Positionsinformationen, mit denen wir die Liste weiter filtern können.Beispielsweise könnten wir die Liste nach allen Wörtern filtern, die mit „.a..“ übereinstimmen.(Punkte sind unbekannte Buchstaben.) Wenn „a“ falsch ist, filtern wir alle Wörter heraus, die „a“ enthalten.Wenn es einen Gleichstand gibt und zwei Buchstaben in einer gleichen Anzahl von Wörtern vorkommen, werden die Buchstaben alphabetisch ausgewählt.Wenn wir also wissen, dass das Wort mit „.ays“ übereinstimmt, erraten wir die Wörter einfach in alphabetischer Reihenfolge.

  2. Dies unterscheidet sich nur geringfügig vom ersten Algorithmus.Anstatt immer die alphabetische Reihenfolge zu wählen, wählen wir im Falle eines Gleichstands die Buchstaben zufällig aus.Das hat den Vorteil, dass unser Gegner nicht weiß, was wir wählen werden.Bei der ersten Strategie ist „Strahlen“ immer besser als „Tage“.Dadurch wird dieses Problem vermieden.

  3. In diesem Fall wählen wir Buchstaben mit einer Wahrscheinlichkeit aus, die proportional zur Anzahl der Wörter ist, die diesen Buchstaben enthalten.Als wir zu Beginn die Anzahl der Wörter zählten, die „a“ enthielten, und die Zahl, die „b“ enthielt usw., da „a“ zufällig in den meisten Wörtern vorkam, wählten wir in den Strategien 1 und 2 „ a" 100 % der Zeit.Stattdessen werden wir immer noch „a“ in vielen Fällen wählen, aber ein paar Mal werden wir „z“ wählen, obwohl a in 10x mehr Wörtern vorkommen könnte.Ich habe meine Zweifel, ob diese Strategie optimal ist, aber Es wurde 2010 in der Forschung eingesetzt.

Daher habe ich zwei Fragen:

  1. Was ist die optimale Strategie zum Erraten von Buchstaben, die ich verwenden sollte? Vorausgesetzt, dass mein Gegner weiß, dass ich diese Strategie anwenden werde?Dabei wollen wir die durchschnittliche Anzahl an Vermutungen minimieren, die erforderlich sind, um das geheime Wort zu erraten.
  2. Wie hoch ist die durchschnittliche Anzahl an Fehlern M, die ich für ein bestimmtes Wort, sagen wir „lohnt“, erwarten muss?Gibt es eine geschlossene Methode zur Berechnung von M, anstatt diese Simulation mehrmals auszuführen und die Ergebnisse zu mitteln?

Erläuterungen

  • Es kann jedes englische Wörterbuch verwendet werden.Zum Beispiel, Dieses englische Wörterbuch mit 84.000 Wörtern..Teilmengen von Wörterbüchern, die sorgfältig auf Mehrdeutigkeit hin ausgewählt wurden, könnten ebenfalls interessant sein, fallen aber nicht in den Rahmen dieser Frage.
  • Es gibt keine Einschränkung hinsichtlich der Wortgröße, solange das Wort im Wörterbuch vorhanden ist.Der Ratende kennt die Wortgröße, bevor er mit dem Raten beginnt.
  • Entscheidend ist nur die Gesamtzahl der Fehler, die unabhängig von der Wortgröße ist.Sie erhalten nicht mehr Chancen für längere Wörter oder weniger Chancen für kürzere.
  • Mir geht es nur darum, die durchschnittliche Fehleranzahl zu minimieren.Wenn es zwei optimale Algorithmen gibt, die eine gleich kleine durchschnittliche Fehleranzahl aufweisen, sind beide akzeptabel.
  • Grundsätzlich ist es möglich, dass die Wahl eines Buchstabens (z. B. „b“) zu mehr Informationen führt als ein anderer (z. B. „a“), obwohl „a“ in mehr möglichen Wörtern vorkommt als „b“.Ich bin auch in der Praxis offen für diese Möglichkeit.Die drei oben dargestellten Algorithmen gehen davon aus, dass dies nicht geschieht, da eine richtige Schätzung tendenziell mehr Informationen liefert als eine falsche (d. h.Positionsangaben zu einem korrekten Buchstaben sind in der Regel besser als „Dieser Buchstabe kommt nicht im Wort vor“).Ein optimaler Algorithmus muss diese Annahme jedoch nicht treffen.
War es hilfreich?

Lösung

Es ist möglich, die optimale Strategie zu berechnen, aber die Berechnung kann ziemlich aufwändig sein, und ich bin mir nicht sicher, ob Sie dadurch einen großen Vorteil gegenüber einfachen Heuristiken erzielen.Wie das geht, erkläre ich weiter unten.Die Hauptidee besteht darin, dynamische Programmierung zu verwenden.

Deterministische Strategien

Lassen Sie mich zunächst mit dem Sonderfall deterministischer Strategien zur Auswahl des nächsten zu erratenden Buchstabens beginnen, da diese am einfachsten zu analysieren sind.Dies gibt uns eine Aufwärmphase, bevor wir zu randomisierten Strategien übergehen (die wahrscheinlich überlegen sein werden).

Der Stand des Spiels zu jedem Zeitpunkt kann durch das Paar zusammengefasst werden $(g,r)$, Wo $g$ ist die Menge der Buchstaben, die bisher erraten wurden, und $r$ sind die Antworten (d. h. die Reihenfolge der Leerzeichen und Buchstaben von). $g$ der für den Spieler sichtbar ist).Die Reihenfolge früherer Vermutungen spielt keine Rolle (weshalb es ausreicht, eine Menge zu haben). $g$ früherer Vermutungen).Wir werden das kurz sagen $w$ stimmt mit überein $(g,r)$ wenn es möglich bleibt, d. h. wenn das Wort des Gegners möglich ist $w$ und Sie machen die Vermutungen $g$, dann würden Sie die Antwort erhalten $r$.

Lassen $p(g,r)=1$ ob es möglich ist, von hier aus zu gewinnen, wenn man vom Staat ausgeht $(g,r)$.Das bedeutet, dass es eine Strategie zum Gewinnen gibt:wobei es egal ist, an welches Wort der Gegner denkt (sofern es damit übereinstimmt). $(g,r)$), wird die Anzahl der falschen Schätzungen, die Sie bisher gemacht haben, plus die Anzahl, die Sie in Zukunft mit dieser Strategie machen werden, die Obergrenze nicht überschreiten.Ansonsten definieren $p(g,r)=0$.

Jetzt können Sie rechnen $p(g,r)$ mit dynamischer Programmierung unter Verwendung der Wiederholungsrelation

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

Wo $a$ erstreckt sich über alle Buchstaben nicht in $g$ (d. h. alle Möglichkeiten, welchen Buchstaben man als nächstes erraten muss) und $(g',r')$ erstreckt sich über alle möglichen Antworten, wenn Sie es erraten haben $a$ als nächstes (d. h. $g'=g\cup \{a\}$, und wir reichen über alle Wörter $w$ die im Einklang stehen mit $(g,r)$ und berechnen Sie die Antwort $r'$ zu Vermutungen $g'$ wenn das Wort ist $w$).

Insbesondere schlage ich vor, dass Sie rechnen $p(g,r)$ mit Tiefensuche und Memoisierung.Dann, $p(\emptyset, - - \cdots -)$ wird Ihnen sagen, ob es möglich ist, innerhalb der Obergrenze zu gewinnen, egal welches Wort der Gegner wählt.Indem Sie die Berechnung rückwärts verfolgen, können Sie die optimale Strategie rekonstruieren.

Ist das machbar?Ich gehe davon aus, dass es so ist.Ich denke, die Anzahl der möglichen Zustände $(g,r)$ ist nicht zu groß.(Insbesondere können Sie Zustände ignorieren $(g,r)$ wenn Sie bereits zu viele falsche Vermutungen angestellt haben und jeder Zustand, in dem nur ein Wort mit diesem Zustand übereinstimmt, automatisch ein Gewinn ist und daher keiner weiteren Analyse bedarf.) Als Optimierung, gegebener Zustand $(g,r)$, können Sie versuchen, alle Wörter aufzuzählen $w$ die mit ihnen konsistent sind und eine feste Heuristik simulieren und prüfen, ob sie für jedes Wort gewinnt;Wenn ja, müssen Sie keine weitere Tiefendurchquerung durchführen und können sofort markieren $p(g,r)=1$.Außerdem müssen Sie nur Vermutungen berücksichtigen $a$ die in mindestens einem Wort vorkommen, das mit übereinstimmt $(g,r)$.

Daher sollte es ziemlich einfach sein, die optimale deterministische Strategie zu berechnen.

Randomisierte Strategien

Wir können einer ähnlichen Methode folgen, um mit randomisierten Strategien umzugehen, aber sie ist etwas komplizierter.Nun lass $p(g,r)$ bezeichnen die Wahrscheinlichkeit, ab hier zu gewinnen, wenn wir von nun an die optimalen Strategien anwenden.Wir können dies wiederum mithilfe dynamischer Programmierung berechnen.

Der Hauptunterschied liegt in der Wiederholungsbeziehung, in der wir berechnen $p(g,r)$ aus den Mengen $p(g',r')$ Wo $(g',r')$ Bereich über alle Zustände, die nach dem Erraten eines weiteren Buchstabens als nächstes auftreten könnten.Hier haben wir ein einfaches Spiel für zwei Spieler.Zuerst wählen wir eine Wahrscheinlichkeitsverteilung über die Buchstaben, die nicht enthalten sind $g$.Dann sieht der Gegner unsere Verteilung und wählt eine Verteilung nach Wörtern $w$ die im Einklang stehen mit $(g,r)$.Unsere Auszahlung (und der Betrag, den der Gegner verliert) entspricht der Wahrscheinlichkeit, dass wir angesichts dieser Entscheidungen von nun an gewinnen.Beachten Sie, dass dies aus berechnet werden kann $p(g',r')$ Werte.Es stellt sich heraus, dass der Gegner keine zufällige Strategie benötigt, da wir zuerst gehen und der Gegner unsere Wahl sieht.Sie können genauso gut mit einer deterministischen Strategie zurechtkommen, d. h. indem sie ein einzelnes Wort auswählen $w$ basierend auf unserem Vertrieb.Dann bilden wir eine Matrix $M$ Wo $M_{w,i}$ enthält die Gewinnwahrscheinlichkeit, wenn wir den Buchstaben wählen $i$ Als nächstes wählt der Gegner das Wort $w$;wir können ausfüllen $M_{w,i}$ als $p(g',r')$ Wo $g'=g \cup \{i\}$ Und $r'$ ist die Antwort auf die Vermutung $g'$ wenn das Wort ist $w$.Dann versuchen wir, das Optimierungsproblem zu lösen $$\max_v \min_w (Mv)_w = -\min_v \max_w -(Mv)_w = -\min_v \|-Mv\|_\infty.$$ Das lässt sich lösen mit linearer Programmierung.Also können wir rechnen $p(g,r)$ unter Verwendung linearer Programmierung aus den Werten $p(g',r')$ Wo $g'$ ist eins größer als $g$.

Alles in allem verwenden wir Tiefendurchquerung mit Memoisierung (oder dynamische Programmierung) und verwenden bei jedem Schritt lineare Programmierung, um das 2-Spieler-Spiel zu lösen.Dies gibt uns die optimale zufällige Strategie, um Galgenmännchen zu spielen.

Die resultierende Berechnung kann sehr teuer sein, da sie Milliarden oder Billionen Schritte erfordert, wobei Sie in jedem Schritt ein lineares Programm lösen.Daher weiß ich nicht, ob es realistisch ist, es in der Praxis einzusetzen.

Einige Optimierungen sind möglich, wie von @j_random_hacker vorgeschlagen.Sie können zunächst rechnen $p(g,r)$ für deterministische Strategien;Dann müssen Sie nur noch randomisierte Strategien für Staaten berücksichtigen $(g,r)$ Wo $p(g,r)=0$.

Heuristische Strategien

Sie haben einige sinnvolle Heuristiken für die Auswahl einer Strategie aufgelistet.Hier ist noch eine Heuristik.Angesichts des Staates $(g,r)$, zählen Sie alle Möglichkeiten für die nächste Vermutung auf $a otin g$.Konzentrieren wir uns auf einen einzelnen Buchstaben $a$.Dann für jeden $(g',r')$ das könnte als nächster Zustand nach der Vermutung eintreten $a$ (Also $g'=g\cup \{a\}$), zählen Sie die Anzahl der Wörter $w$ im Einklang mit $(g',r')$;Nehmen Sie das Maximum dieser Zahlen und verwenden Sie es als zugehörigen Zählwert $a$.Die heuristische Strategie besteht darin, den Buchstaben auszuwählen $a$ deren Anzahl am kleinsten ist.

Berechnen der erwarteten Fehleranzahl

Sie können die erwartete Anzahl von Fehlern einer bestimmten randomisierten Strategie mithilfe dynamischer Programmierung berechnen.Die Details sind ähnlich wie oben, aber die Wiederholungsbeziehung wird einfacher:es wird

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

Wo $w$ reicht über alle Wörter, die mit übereinstimmen $(g,r)$, Und $(g',r')$ ist die Verteilung im nächsten Zustand, wenn das Wort vorhanden ist $w$ und der nächste erratene Buchstabe wird durch Ihre Strategie ausgewählt.Angesichts Ihrer Strategie und des Wortes $w$, ist es einfach, die Verteilung anhand von Schätzungen zu berechnen und dadurch die Verteilung für die nächsten Zustände zu erhalten, sodass die Berechnung einfach ist $\mathbb{E}[p(g',r')]$.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit cs.stackexchange
scroll top