Algorithmus zum Klassifizieren von Wörtern für Henker-Schwierigkeitsgrade als "Leicht", "Mittel" oder "Schwer"

Was ist ein guter Algorithmus, um die "Schwierigkeit" eines Wortes für ein Henker-Spiel zu bestimmen, damit das Spiel Wörter auswählen kann, die einem bestimmten Schwierigkeitsgrad entsprechen?

Die Schwierigkeit scheint mit der Anzahl der erforderlichen Vermutungen, der relativen Häufigkeit der Verwendung von Buchstaben (z. B. Wörter mit vielen ungewöhnlichen Buchstaben sind möglicherweise schwerer zu erraten) und möglicherweise der Länge des Wortes verbunden zu sein.

Es gibt auch einige subjektive Faktoren, die zu kompensieren sind (zu versuchen), wie z. B. die Wahrscheinlichkeit, dass ein Wort im Vokabular des Spielers enthalten ist und erkannt werden kann, sodass von einer Schätzstrategie, die nur auf Buchstabenhäufigkeiten basiert, zu einer auf einer Liste von Raten basierenden Rate übergegangen werden kann bekannte passende Wörter.

Mein Versuch für jetzt ist unten in Rubin. Irgendwelche Vorschläge zur Verbesserung der Kategorisierung?

def classify_word(w)
  n = w.chars.to_a.uniq.length # Num. unique chars in w
  if n < 5 and w.length > 4
    return WordDifficulty::Easy
  end
  if n > w.length / 2
    return WordDifficulty::Hard
  else
    return WordDifficulty::Medium
  end
end

Ich schreibe ein Henker-Spiel, das meine Kinder spielen sollen. Ich bin eher zu alt, um "Hausaufgaben" zu machen, weshalb die Frage möglicherweise so viele Abwärtsstimmen erhält ... Wörter werden zufällig aus großen Wortdatenbanken gezogen, die viele dunkle Wörter enthalten, und nach Schwierigkeitsgrad gefiltert bestimmt für das Wort.

1. Einleitung

Hier ist eine Möglichkeit, dieses Problem systematisch anzugehen: Wenn Sie einen Algorithmus haben, der Henker gut spielt, können Sie die Schwierigkeit jedes Wortes als die Anzahl der falschen Vermutungen ansehen, die Ihr Programm beim Erraten dieses Wortes annehmen würde.

2. Neben der Henker-Strategie

Es gibt eine Idee, die in einigen anderen Antworten und Kommentaren impliziert ist, dass die optimale Strategie für den Löser darin besteht, seine Entscheidungen auf die Häufigkeit von Buchstaben in Englisch oder auf die Häufigkeit von Wörtern in einem Korpus zu stützen. Dies ist eine verführerische Idee, aber nicht ganz richtig. Der Löser ist am besten geeignet, wenn er die Verteilung der vom Setter ausgewählten Wörter genau modelliert , und ein menschlicher Setter kann Wörter aufgrund ihrer Seltenheit oder Vermeidung häufig verwendeter Buchstaben auswählen. Obwohl zum Beispiel Ein Englisch die am häufigsten verwendeten Buchstaben sind, wenn der Einrichter wählt immer aus den Worten JUGFUL, RHYTHM, SYZYGY, und ZYTHUMdann ein perfekter Löser nicht startet durch Erraten E!

Der beste Ansatz zur Modellierung des Setters hängt vom Kontext ab, aber ich denke, dass eine Art Bayes'sche induktive Inferenz in einem Kontext gut funktioniert, in dem der Solver viele Spiele gegen denselben Setter oder gegen eine Gruppe ähnlicher Setter spielt.

3. Ein Henker-Algorithmus

Hier werde ich einen Löser skizzieren, der ziemlich gut ist (aber alles andere als perfekt). Es modelliert den Setter so, dass er Wörter einheitlich aus einem festen Wörterbuch auswählt. Es ist ein gieriger Algorithmus : In jeder Phase wird der Buchstabe erraten, der die Anzahl der Fehler minimiert, dh Wörter, die die Vermutung nicht enthalten. Zum Beispiel, wenn keine Vermutungen wurden so weit, und die möglichen Worte sind gemacht DEED, DEADund DAREdann:

• Wenn Sie raten Doder E, gibt es keine Fehler;
• Wenn Sie raten A, gibt es einen Fehler ( DEED);
• Wenn Sie raten R, gibt es zwei Fehler ( DEEDund DEAD);
• Wenn Sie einen anderen Buchstaben erraten, gibt es drei Fehler.

Also entweder Doder Eist eine gute Vermutung in dieser Situation.

(Dank an Colonel Panic in den Kommentaren für den Hinweis, dass korrekte Vermutungen in Henker frei sind - das habe ich bei meinem ersten Versuch völlig vergessen!)

4. Implementierung

Hier ist eine Implementierung dieses Algorithmus in Python:

from collections import defaultdict
from string import ascii_lowercase

def partition(guess, words):
    """Apply the single letter 'guess' to the sequence 'words' and return
    a dictionary mapping the pattern of occurrences of 'guess' in a
    word to the list of words with that pattern.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> sorted(list(partition('e', words).items()))
    [(0, ['star']), (2, ['mews']), (5, ['even', 'eyes']), (6, ['deed', 'peep'])]

    """
    result = defaultdict(list)
    for word in words:
        key = sum(1 << i for i, letter in enumerate(word) if letter == guess)
        result[key].append(word)
    return result

def guess_cost(guess, words):
    """Return the cost of a guess, namely the number of words that don't
    contain the guess.

    >>> words = 'deed even eyes mews peep star'.split()
    >>> guess_cost('e', words)
    1
    >>> guess_cost('s', words)
    3

    """
    return sum(guess not in word for word in words)

def word_guesses(words, wrong = 0, letters = ''):
    """Given the collection 'words' that match all letters guessed so far,
    generate tuples (wrong, nguesses, word, guesses) where
    'word' is the word that was guessed;
    'guesses' is the sequence of letters guessed;
    'wrong' is the number of these guesses that were wrong;
    'nguesses' is len(guesses).

    >>> words = 'deed even eyes heel mere peep star'.split()
    >>> from pprint import pprint
    >>> pprint(sorted(word_guesses(words)))
    [(0, 1, 'mere', 'e'),
     (0, 2, 'deed', 'ed'),
     (0, 2, 'even', 'en'),
     (1, 1, 'star', 'e'),
     (1, 2, 'eyes', 'en'),
     (1, 3, 'heel', 'edh'),
     (2, 3, 'peep', 'edh')]

    """
    if len(words) == 1:
        yield wrong, len(letters), words[0], letters
        return
    best_guess = min((g for g in ascii_lowercase if g not in letters),
                     key = lambda g:guess_cost(g, words))
    best_partition = partition(best_guess, words)
    letters += best_guess
    for pattern, words in best_partition.items():
        for guess in word_guesses(words, wrong + (pattern == 0), letters):
            yield guess

5. Beispielergebnisse

Mit dieser Strategie ist es möglich, die Schwierigkeit zu bewerten, jedes Wort in einer Sammlung zu erraten. Hier betrachte ich die Wörter mit sechs Buchstaben in meinem Systemwörterbuch:

>>> words = [w.strip() for w in open('/usr/share/dict/words') if w.lower() == w]
>>> six_letter_words = set(w for w in words if len(w) == 6)
>>> len(six_letter_words)
15066
>>> results = sorted(word_guesses(six_letter_words))

Die Wörter, die in diesem Wörterbuch am einfachsten zu erraten sind (zusammen mit der Reihenfolge der Vermutungen, die der Löser benötigt, um sie zu erraten), lauten wie folgt:

>>> from pprint import pprint
>>> pprint(results[:10])
[(0, 1, 'eelery', 'e'),
 (0, 2, 'coneen', 'en'),
 (0, 2, 'earlet', 'er'),
 (0, 2, 'earner', 'er'),
 (0, 2, 'edgrew', 'er'),
 (0, 2, 'eerily', 'el'),
 (0, 2, 'egence', 'eg'),
 (0, 2, 'eleven', 'el'),
 (0, 2, 'enaena', 'en'),
 (0, 2, 'ennead', 'en')]

und die schwierigsten Wörter sind diese:

>>> pprint(results[-10:])
[(12, 16, 'buzzer', 'eraoiutlnsmdbcfg'),
 (12, 16, 'cuffer', 'eraoiutlnsmdbpgc'),
 (12, 16, 'jugger', 'eraoiutlnsmdbpgh'),
 (12, 16, 'pugger', 'eraoiutlnsmdbpcf'),
 (12, 16, 'suddle', 'eaioulbrdcfghmnp'),
 (12, 16, 'yucker', 'eraoiutlnsmdbpgc'),
 (12, 16, 'zipper', 'eraoinltsdgcbpjk'),
 (12, 17, 'tuzzle', 'eaioulbrdcgszmnpt'),
 (13, 16, 'wuzzer', 'eraoiutlnsmdbpgc'),
 (13, 17, 'wuzzle', 'eaioulbrdcgszmnpt')]

Der Grund dafür ist, dass Sie nach dem Erraten -UZZLEnoch sieben Möglichkeiten haben:

>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle')))
'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'

6. Wahl der Wortliste

Wenn Sie Wortlisten für Ihre Kinder erstellen, beginnen Sie natürlich nicht mit dem Systemwörterbuch Ihres Computers, sondern mit einer Liste von Wörtern, von denen Sie glauben, dass sie sie wahrscheinlich kennen. Sie können sich beispielsweise die Wiktionary-Listen der am häufigsten verwendeten Wörter in verschiedenen englischen Korpora ansehen .

Unter den 1.700 Wörtern mit sechs Buchstaben in den 10.000 häufigsten Wörtern in Project Gutenberg ab 2006 sind die schwierigsten zehn:

[(6, 10, 'losing', 'eaoignvwch'),
 (6, 10, 'monkey', 'erdstaoync'),
 (6, 10, 'pulled', 'erdaioupfh'),
 (6, 10, 'slaves', 'erdsacthkl'),
 (6, 10, 'supper', 'eriaoubsfm'),
 (6, 11, 'hunter', 'eriaoubshng'),
 (6, 11, 'nought', 'eaoiustghbf'),
 (6, 11, 'wounds', 'eaoiusdnhpr'),
 (6, 11, 'wright', 'eaoithglrbf'),
 (7, 10, 'soames', 'erdsacthkl')]

(Soames Forsyte ist eine Figur in der Forsyte Saga von John Galsworthy . Die Wortliste wurde in Kleinbuchstaben umgewandelt, sodass ich Eigennamen nicht schnell entfernen konnte.)

Ein wirklich einfacher Weg wäre, eine Punktzahl zu berechnen, die auf dem Fehlen von Vokalen im Wort, der Anzahl der eindeutigen Buchstaben und der Gemeinsamkeit jedes Buchstabens basiert:

letters = 'etaoinshrdlcumwfgypbvkjxqz'
vowels = set('aeiou')

def difficulty(word):
    unique = set(word)
    positions = sum(letters.index(c) for c in word)

    return len(word) * len(unique) * (7 - len(unique & vowels)) * positions

words = ['the', 'potato', 'school', 'egypt', 'floccinaucinihilipilification']

for word in words:
    print difficulty(word), word

Und die Ausgabe:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Sie könnten dann die Wörter mit bewerten:

        score < 2000   # Easy
 2000 < score < 10000  # Medium
10000 < score          # Hard

Mit der Monte-Carlo-Methode können Sie die Schwierigkeit eines Wortes abschätzen:

• Simulieren Sie ein Spiel, indem Sie jedes Mal einen zufälligen Buchstaben erraten, gewichtet nach der Häufigkeit des Buchstabens in Ihrer Zielsprache, und zählen Sie, wie viele Vermutungen Ihr zufälliger Spieler benötigt hat, um zu einer Lösung zu gelangen. Beachten Sie, dass dieser Prozess endlich ist und eine Zahl von 1 bis einschließlich 26 zurückgibt, da jede Vermutung einen Buchstaben eliminiert.
• Wiederholen Sie diesen Vorgang 2*Nmal, wobei Ndie Anzahl der eindeutigen Buchstaben in Ihrem Wort ist.
• Berechnen Sie die Punktzahl, indem Sie die Ergebnisse der 2*NLäufe mitteln .
• Bestimmen Sie den Komplexitätsgrad: Werte unter zehn geben ein einfaches Wort an, und Werte über sechzehn geben ein hartes Wort an. alles andere ist mittelgroß.

Vorherige ähnliche Diskussion zum gleichen Thema: Bestimmen Sie die Schwierigkeit eines englischen Wortes

Ich mag die Antwort am Ende des Links ^. Wenden Sie für ein Hangman-Spiel für Kinder einfach einen Ansatz wie Scrabble an.

Weisen Sie jedem Buchstaben einen Punktwert zu und addieren Sie die Buchstaben.

Vor einiger Zeit habe ich einen Henker-Löser unter Verwendung des offensichtlichen Algorithmus geschrieben: Bei einem anfänglichen Wörterbuch aller möglichen Wörter wählen wir in jeder Runde den Buchstaben aus, der in den meisten im Wörterbuch verbleibenden Wörtern vorkommt, und entfernen dann nicht übereinstimmende Wörter (abhängig von der Antwort) aus dem Wörterbuch.

Der Algorithmus ist nicht ganz so einfach, da es häufig mehrere Buchstaben gibt, die jeweils in der gleichen Anzahl von Wörtern im Wörterbuch vorkommen. In diesem Fall kann die Wahl des Buchstabens einen signifikanten Unterschied dazu machen, wie viele Vermutungen für ein Wort erforderlich sind. Wir wählen die Maxima aus, bei denen die resultierenden Informationen über die Platzierung dieses Buchstabens (falls tatsächlich im Wort enthalten) die maximale Information über das System ergeben (der Buchstabe mit der maximalen Informationsentropie ). Wenn beispielsweise die beiden verbleibenden möglichen Wörter "Enzyklopädie" und "Enzyklopädie" sind, hat der Buchstabe "c" die gleiche Wahrscheinlichkeit des Erscheinens wie e, n, y, l, o, p, e, d, i (dh es ist) garantiert im Wort), aber wir sollten zuerst nach 'c' fragen, da es eine Informationsentropie ungleich Null hat.

Quelle (C ++, GPL) ist hier

Das Ergebnis all dessen ist eine Liste von Wörtern mit der Anzahl der für jedes Wort erforderlichen Vermutungen: schwierigkeit.txt (630 KB). Das am schwersten zu findende Wort für diesen Algorithmus ist "Wille" (mit 14 fehlgeschlagenen Vermutungen); Das i und das doppelte l werden ziemlich schnell erraten, aber dann umfassen die Optionen Rechnung, Dill, Füllung, Kieme, Hügel, Tötung, Mühle, Pille, Rille, bis, Wille, und von da an besteht die einzige Option darin, jeden Buchstaben zu erraten Wende. Etwas intuitiv gesehen werden längere Wörter viel schneller erraten (es gibt einfach keine, aus denen man wählen kann).

Natürlich spielen in einem menschlichen Henkerspiel die Psychologie (und die Breite des Wortschatzes) eine viel größere Rolle, als dieser Algorithmus erklärt ...

Mach es einfach! Spielen Sie Henker gegen das Wort. Zählen Sie, wie viele Verluste (dh falsche Vermutungen) erforderlich sind, um zu schlagen.

Sie benötigen eine Strategie zum Spielen. Hier ist eine menschliche (ish) Strategie. Streichen Sie aus dem Wörterbuch alle Wörter aus, die bisher nicht zu den Enthüllungen passen. Erraten Sie den häufigsten Buchstaben unter den verbleibenden Wörtern.

Wenn Ihre Strategie randomisiert ist, können Sie Ihr Maß als die erwartete Anzahl von Verlusten definieren und diese empirisch schätzen.

Eine andere deterministische Strategie von einem Henker-Bot, den ich vor einigen Jahren geschrieben habe. Erraten Sie den Buchstaben, der die Anzahl der verbleibenden Wörter minimiert, falls die Vermutung falsch ist (dh den schlimmsten Fall optimieren). Heute mag ich diese Strategie nicht, weil sie zu mechanisch ist. Ich bevorzuge die obige.

Zunächst würden Sie natürlich eine Liste eindeutiger Buchstaben erstellen. Dann nach Häufigkeit sortieren (in Englisch oder einer anderen Sprache - dafür gibt es Listen ), wobei weniger häufige Buchstaben einen höheren Schwierigkeitsgrad haben.

Dann müssen Sie entscheiden, ob Sie die Ergebnisse kombinieren, indem Sie sie addieren, multiplizieren oder ein anderes Schema verwenden.

Sie werden abgelehnt, weil Sie uns bitten, einen sehr komplexen Algorithmus für Sie zu erstellen.

Warum erstellen Sie nicht einfach drei Arrays (einfach, mittel und schwer) und füllen jedes mit ungefähr hundert Wörtern? Es würde ungefähr 20 Minuten dauern.

Ich verspreche, Ihre Kinder werden sich langweilen, bevor sie ein paar hundert Spiele durchbrennen ...: D.

Nun, möglicherweise könnte es eine Menge Dinge geben:

1. Wie alle sagten, die Häufigkeit der einzelnen Buchstaben;
2. Die Länge eines Wortes sollte auf jeden Fall zählen, aber nicht linear - ein langes Wort kann dazu führen, dass zufällige Vermutungen die Buchstaben treffen, während ein kurzes Wort schwer zu bekommen sein kann.
3. Auch die Wörter selbst sollten berücksichtigt werden - "zweiteilig" könnte ein Wort für Leute auf SO sein, aber vielleicht nicht für nicht technische Bevölkerung.

Tatsächlich könnten Sie versuchen, mehrere Strategien gemeinsam zu entwickeln , die eine Hälfte für die Entscheidung über den Wert eines Wortes und die andere Hälfte für den Versuch, das Spiel zu gewinnen. Die letztere Gruppe wird versuchen, die Punktzahl zu maximieren, während die erste versucht, die Punktzahl zu minimieren. Nach einer Weile könnte es ein Muster geben, und dann kann die Hälfte für die Entscheidung über den Wert eines Wortes einige Benchmarks geben.

Beginnen Sie mit einer Liste von Wörtern und starten Sie eine Google-Suche für jedes einzelne. Die Anzahl der Treffer soll als (grober) Indikator für die Schwierigkeit des Begriffs dienen.

In einer verfeinerten Version würden Sie Wörter nach einem Synonym gruppieren. Beziehung basierend auf einem Thesaurus und das schwierigste Wort einer Kategorie bestimmen, indem Sie die Ergebnisse der Google-Suche zählen.

Den Begriff n-Gramm nehmen Einen Schritt weiter könnte die Schwierigkeit eines Wortes anhand der Häufigkeit seiner Silben in der Prosa bewertet werden. Kommt natürlich auf die Qualität der Silbenstatistik an. Sie müssten wahrscheinlich zwischen Lexemen und Funktionswörtern (Determinatoren, Konjunktionen usw.) unterscheiden und nach Anzahl der Silben im Wort normalisieren (fühlt sich beim Schreiben wie Overkill an ...).

Ich mag die Idee, einen Algorithmus zu erstellen, der je nach Benutzer lernt und sich ändert. Zu Beginn können Sie jeden der vorgeschlagenen Algorithmen implementieren, um die Liste zu erstellen. Wenn dann mehr Leute das Spiel spielen, weisen Sie jedem der Wörter eine Gewichtung zu, abhängig von der Anzahl der Vermutungen (die auch kontinuierlich verfolgt und berechnet werden) ). Dies verhindert, dass das Problem komplexer, aber populärer Wörter schwer bewertet wird, aber den Menschen bekannt ist.

Berechnen Sie den Wert jedes Buchstabens eines Wortes in Scrabble-Punkten: E = 1, D = 2, V = 4, X = 8 usw. Addieren Sie sie und dividieren Sie sie durch die Anzahl der Buchstaben, um einen durchschnittlichen Buchstabenwert zu erhalten. Verwenden Sie diesen Wert, um das Wort zu bewerten. Berechnen Sie den Durchschnitt für jedes Wort in einem großen Wörterbuch und bestimmen Sie die Haltepunkte zwischen Quartilen. Nennen Sie Wörter im untersten Quartil "leicht", Wörter in den beiden mittleren Quartilen "mittel" und Wörter im höchsten Quartil "schwer".