Löse Hangman auf KI-Art

Aktualisierte Idee

1. Laden Sie ein Wörterverzeichnis herunter und fügen Sie es in eine Datenbank oder Struktur Ihrer Wahl ein
2. Wenn Sie mit einem Wort konfrontiert werden, beschränken Sie Ihre Schätzungen auf Wörter gleicher Länge und führen Sie eine Häufigkeitsverteilung des Buchstabens durch (Sie können ein Wörterbuch und / oder eine Listensammlung für schnelle Verteilungsanalyse und -sortierung verwenden)
3. Wählen Sie den häufigsten Buchstaben aus dieser Liste
4. Wenn der Buchstabe gefunden wurde, erstellen Sie ein Regex-Muster basierend auf den bekannten Buchstaben und der Wortlänge und wiederholen Sie die Schritte ab Schritt 2
5. Sie sollten in der Lage sein, ein einzelnes Wort, das sich aus Ihrer Mustersuche ergibt, schnell einzugrenzen

Für die Nachwelt:

Sehen Sie sich diese Wiki-Seite an. Es enthält eine Tabelle der Häufigkeiten der ersten Buchstaben der Wörter, die Ihnen helfen können, Ihren Algorithmus abzustimmen.

Sie können auch die Tatsache berücksichtigen, dass, wenn Sie einen oder zwei Vokale in einem Wort finden, die Wahrscheinlichkeit, andere Vokale zu finden, signifikant abnehmen wird und Sie stattdessen stattdessen häufigere Konsonanten verwenden sollten. Das Beispiel aus der Wiki-Seite, die Sie aufgelistet haben, beginnt mit E und dann T und versucht dann drei Vokale hintereinander: A, O und I. Die ersten zwei Buchstaben werden verpasst, aber sobald der dritte Buchstabe gefunden wurde, sollte der Prozess zweimal auf Common umgestellt werden Konsonanten und überspringen versuchen für mehr Vokale, da es wahrscheinlich weniger geben wird.

Alle nützlichen Strategien werden sicherlich Häufigkeitsverteilungstabellen für Buchstaben und möglicherweise Wörter, z. einige Wörter sind sehr gebräuchlich, während andere nur selten verwendet werden. Daher kann es hilfreich sein, wenn Sie eine Häufigkeitsverteilung auf einer Gruppe von gebräuchlicheren Wörtern durchführen. Sie können davon ausgehen, dass einige Wörter häufiger vorkommen als andere, aber das hängt von Ihrem Algorithmus ab "gemeinsame" Verwendung berücksichtigen.

Sie könnten auch spezialisierte Brieffrequenztabellen und möglicherweise sogar on-the-fly erstellen. Zum Beispiel, in Anbetracht der Wikipedia h a ngm a n Beispiel: Sie finden den Buchstaben A zweimal in einem Wort an zwei Stellen 2. und 6. Stelle. Sie wissen, dass das Wort sieben Buchstaben hat und mit einer ziemlich einfachen Anweisung könnten Sie Wörter aus einem Wörterbuch isolieren, die mit diesem Muster übereinstimmen:

Führen Sie dann eine Buchstabenhäufigkeit für diese Wörtergruppe aus, die mit diesem Muster übereinstimmt, und verwenden Sie diese für Ihre nächste Schätzung. Spülen und wiederholen. Ich denke, einige der Dinge, die ich erwähnt habe, zu tun, aber vor allem die letzten werden wirklich Ihre Chancen auf Erfolg erhöhen.

Die Strategien auf der verlinkten Seite scheinen "Reihenfolge nach Häufigkeit" zu sein und "rate die Vokale, dann rate Reihenfolge nach Buchstaben"

Ein paar Beobachtungen über Henker:

1) Da das Raten eines Buchstabens, der nicht im Wort steht, uns weh tut, sollten wir Buchstaben nach Worthäufigkeit (Prozentsatz der Wörter, die Buchstaben X enthalten), nicht Buchstabenhäufigkeit (Anzahl der Male, dass X in allen Wörtern erscheint) erraten. . Dies sollte unsere Chancen maximieren, einen schlechten Brief zu erraten.

2) Wenn wir einige Buchstaben richtig erraten haben, wissen wir mehr über das Wort, das wir zu erraten versuchen.

Hier sind zwei Strategien, die die Brieffrequenzstrategie übertreffen sollten. Ich gehe davon aus, dass wir ein Wörterbuch mit Wörtern haben, die auftauchen könnten.

Wenn wir erwarten, dass das Wort in unserem Wörterbuch ist:

1) Wir kennen die Länge des Zielwortes, n . Entfernen Sie alle Wörter im Wörterbuch, die nicht die Länge n

2) Berechnen Sie die Worthäufigkeit aller Buchstaben im Wörterbuch

3) Raten Sie den häufigsten Buchstaben, den wir nicht schon erraten haben.

4) Wenn wir richtig geraten haben, entfernen Sie alle Wörter aus dem Wörterbuch, die nicht mit den aufgedeckten Buchstaben übereinstimmen.

5) Wenn wir falsch geraten haben, entfernen Sie alle Wörter mit dem falsch erratenen Buchstaben

6) Weiter mit Schritt 2

Um den maximalen Effekt zu erzielen, berechnen Sie anstelle der Worthäufigkeiten aller Buchstaben in Schritt 2 die Worthäufigkeiten aller Buchstaben an Positionen, die im Zielwort noch leer sind.

Wenn wir nicht erwarten, dass das Wort in unserem Wörterbuch ist:

1) Erstellen Sie im Dictionary eine Tabelle mit n-grams für einen Wert von n (zB 2). Wenn Sie noch keine N-Gramme gefunden haben, handelt es sich um Gruppen aufeinanderfolgender Buchstaben innerhalb des Wortes. Zum Beispiel, wenn das Wort "word" ist, sind die 2-Gramm {^w,wo,or,rd,d$} , wobei ^ und $ den Anfang und das Ende des Wortes markieren. Zählen Sie die Worthäufigkeit dieser 2-Gramm.

2) Beginnen Sie mit dem Erraten einzelner Buchstaben nach Worthäufigkeit wie oben

3) Sobald wir einige Treffer erzielt haben, können wir die Tabelle der Worthäufigkeit von n-Gramm verwenden, um entweder Buchstaben aus unseren Schätzungen zu entfernen oder Buchstaben, die wir wahrscheinlich erraten können. Es gibt viele Möglichkeiten, dies zu erreichen:

Sie könnten beispielsweise 2 Gramm verwenden, um zu bestimmen, dass das Leerzeichen in w_rd wahrscheinlich nicht z ist. Oder Sie könnten feststellen, dass das Zeichen am Ende des Wortes ___e_ (sagen wir) d oder s sein könnte.

Alternativ könnten Sie die N-Gramme verwenden, um die Liste der möglichen Zeichen zu generieren (obwohl dies für lange Wörter teuer sein könnte). Denken Sie daran, dass Sie immer alle N-Gramme durchkreuzen können, die Buchstaben enthalten, von denen Sie vermutet haben, dass sie nicht im Zielwort enthalten sind.

Denk daran, dass du bei jedem Schritt versuchst, keine falsche Vermutung zu geben, denn das hält uns am Leben. Wenn die N-Gramme Ihnen sagen, dass eine Position wahrscheinlich nur (sagen wir) a, b oder c ist, und Ihre Worthäufigkeitstabelle Ihnen sagt, dass a in 30% der Wörter erscheint, aber b und c nur in 10% vorkommen, dann rate a .

Für den maximalen Nutzen können Sie die beiden Strategien kombinieren.

Die diskutierte Strategie ist eine für den Menschen geeignete Implementierung. Da Sie eine AI schreiben, können Sie Rechenleistung darauf werfen, um ein besseres Ergebnis zu erzielen.

Nehmen Sie Ihre Wortliste und filtern Sie sie auf nur die Wörter, die mit den Informationen über das Zielwort übereinstimmen. (Am Anfang wird das nur die Wortlänge sein.) Für jeden Buchstaben A bis Z vermerken Sie, wie viele Wörter mindestens einen von ihnen enthalten (das ist anders als die Anzahl der Buchstaben). Wählen Sie den Buchstaben mit der höchsten Punktzahl / p>

Sie MIGHT können sogar mehrere Zyklen davon ausführen, um eine Schätzung zu berechnen, aber das könnte selbst für moderne CPUs zu viel sein.

Klarstellung: Ich sage, dass Sie möglicherweise eine Vorausschau durchführen können. Wenn wir auf dieser Ebene "A" wählen, welche Optionen bietet das für die nächste Ebene? Dies ist ein O (x ^ n) -Algorithmus, offensichtlich können Sie nicht zu weit gehen.