Algorithme pour classer les mots pour les niveaux de difficulté du bourreau comme "Facile", "Moyen" ou "Difficile"

Quel est un bon algorithme pour déterminer la «difficulté» d'un mot pour un jeu du pendu, afin que le jeu puisse sélectionner des mots correspondant à un niveau de difficulté spécifié?

La difficulté semble liée au nombre de suppositions requises, à la fréquence relative d'utilisation des lettres (par exemple, les mots avec de nombreuses lettres inhabituelles peuvent être plus difficiles à deviner) et potentiellement à la longueur du mot.

Il y a aussi quelques facteurs subjectifs à (tenter de) compenser, tels que la probabilité qu'un mot soit dans le vocabulaire du joueur, et puisse être reconnu, permettant de passer d'une stratégie de devinettes basée uniquement sur la fréquence des lettres à une estimation basée sur une liste de mots correspondants connus.

Ma tentative pour l'instant est ci-dessous en rubis. Des suggestions pour améliorer la catégorisation?

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

J'écris un jeu du pendu auquel j'aimerais que mes enfants jouent; Je suis un peu trop vieux pour faire des "devoirs", ce qui explique peut-être pourquoi la question reçoit autant de votes négatifs ... Les mots sont tirés au hasard dans de grandes bases de données contenant de nombreux mots obscurs et sont filtrés par niveau de difficulté déterminé pour le mot.

1. Introduction

Voici une façon d'aborder ce problème de manière systématique: si vous avez un algorithme qui joue bien au pendu, alors vous pouvez considérer la difficulté de chaque mot comme le nombre de fausses suppositions que votre programme prendrait si vous deviniez ce mot.

2. Mis à part la stratégie du bourreau

Il y a une idée implicite dans certaines autres réponses et commentaires, que la stratégie optimale pour le solveur serait de baser ses décisions sur la fréquence des lettres en anglais ou sur la fréquence des mots dans certains corpus. C'est une idée séduisante, mais ce n'est pas tout à fait juste. Le solveur réussit mieux s'il modélise avec précision la distribution des mots choisis par le setter , et un setter humain peut très bien choisir des mots en fonction de leur rareté ou de l'évitement des lettres fréquemment utilisées. Par exemple, bien que Ela lettre la plus fréquemment utilisée en anglais, si le compositeur choisit toujours des mots JUGFUL, RHYTHM, SYZYGYet ZYTHUM, puis un solveur parfait ne démarre pas en essayant de deviner E!

La meilleure approche pour modéliser le setter dépend du contexte, mais je suppose qu'une sorte d'inférence inductive bayésienne fonctionnerait bien dans un contexte où le solveur joue de nombreux jeux contre le même setter, ou contre un groupe de setters similaires.

3. Un algorithme du pendu

Ici, je vais décrire un solveur assez bon (mais loin d'être parfait). Il modélise le passeur en choisissant les mots uniformément à partir d'un dictionnaire fixe. C'est un algorithme gourmand : à chaque étape, il devine la lettre qui minimise le nombre de ratés, c'est-à-dire les mots qui ne contiennent pas la supposition. Par exemple, si aucune estimation n'a été faite jusqu'à présent et que les mots possibles sont DEED, DEADet DARE, alors:

• si vous devinez Dou E, il n'y a pas de ratés;
• si vous devinez A, il y a un manque ( DEED);
• si vous devinez R, il y a deux ratés ( DEEDet DEAD);
• si vous devinez une autre lettre, il y a trois échecs.

Donc, soit Dou Eest une bonne estimation dans cette situation.

(Merci au colonel Panic dans ses commentaires pour avoir souligné que les suppositions correctes sont gratuites dans le bourreau - j'ai totalement oublié cela lors de ma première tentative!)

4. Mise en œuvre

Voici une implémentation de cet algorithme en 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. Exemples de résultats

En utilisant cette stratégie, il est possible d'évaluer la difficulté de deviner chaque mot d'une collection. Ici, je considère les mots de six lettres dans mon dictionnaire système:

>>> 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))

Les mots les plus faciles à deviner dans ce dictionnaire (ainsi que la séquence de suppositions nécessaires au solveur pour les deviner) sont les suivants:

>>> 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')]

et les mots les plus durs sont les suivants:

>>> 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')]

La raison pour laquelle ils sont difficiles est qu'après avoir deviné -UZZLE, il vous reste sept possibilités:

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

6. Choix de la liste de mots

Bien sûr, lors de la préparation de listes de mots pour vos enfants, vous ne commenceriez pas avec le dictionnaire système de votre ordinateur, vous commenceriez par une liste de mots que vous pensez qu'ils sont susceptibles de connaître. Par exemple, vous pouvez consulter les listes de Wiktionnaire des mots les plus fréquemment utilisés dans divers corpus anglais.

Par exemple, parmi les 1700 mots de six lettres dans les 10000 mots les plus courants du projet Gutenberg en 2006 , les dix les plus difficiles sont les suivants:

[(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 est un personnage de la saga Forsyte de John Galsworthy ; la liste de mots a été convertie en minuscules, il ne m'a donc pas été possible de supprimer rapidement les noms appropriés.)

Un moyen très simple serait de calculer un score basé sur le manque de voyelles dans le mot, le nombre de lettres uniques et la commune de chaque lettre:

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

Et la sortie:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Vous pouvez ensuite noter les mots avec:

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

Vous pouvez utiliser la méthode de Monte Carlo pour estimer la difficulté d'un mot:

• Simulez un jeu en devinant une lettre aléatoire à chaque fois, pondérée par la fréquence de la lettre dans votre langue cible, et comptez le nombre de suppositions qu'il a fallu à votre joueur aléatoire pour arriver à une solution. Notez que puisque chaque estimation élimine une lettre, ce processus est fini et renvoie un nombre de 1 à 26 inclus.
• Répétez ce processus 2*Nfois, où Nest le nombre de lettres uniques dans votre mot,
• Calculer le score en faisant la moyenne des résultats des 2*Ncourses,
• Déterminez le niveau de complexité: les scores inférieurs à dix indiquent un mot facile et les scores supérieurs à seize indiquent un mot difficile; tout le reste est moyen.

Discussion similaire précédente autour du même sujet: Déterminer la difficulté d'un mot anglais

J'aime la réponse à la fin du lien ^. Pour un jeu du pendu pour enfants, appliquez simplement une approche comme le scrabble.

Attribuez une valeur en points à chaque lettre, puis additionnez simplement les lettres.

Il y a quelque temps, j'ai écrit un solveur du pendu en utilisant l'algorithme évident: étant donné un dictionnaire initial de tous les mots possibles, à chaque tour, nous choisissons la lettre qui apparaît dans le plus de mots restant dans le dictionnaire, puis supprimons les mots qui ne correspondent pas (en fonction de la response) du dictionnaire.

L'algorithme n'est pas aussi simple que celui-ci, car il y a souvent plusieurs lettres qui apparaissent chacune dans le même nombre de mots dans le dictionnaire. Dans ce cas, le choix de la lettre peut faire une différence significative sur le nombre de suppositions nécessaires pour un mot. Nous choisissons les maxima où les informations résultantes sur le placement de cette lettre (si c'est bien dans le mot) donnent le maximum d'informations sur le système (la lettre avec l' entropie d'information maximale ). Par exemple, si les deux mots possibles restants sont 'encyclopédie' et 'encyclopédique', la lettre 'c' a la même probabilité d'apparaître que e, n, y, l, o, p, e, d, i (c'est-à-dire garantie d'être dans le mot), mais nous devrions d'abord poser la question de «c» car il a une entropie d'information non nulle.

La source (C ++, GPL) est ici

Le résultat de tout cela est une liste de mots, avec le nombre de suppositions nécessaires pour chacun: difficulté.txt (630KB). Le mot le plus difficile à trouver pour cet algorithme est «volonté» (avec 14 suppositions ratées); le i et le double l sont devinés assez rapidement, mais les options incluent le projet de loi, l'aneth, le remplissage, les branchies, la colline, le meurtre, le moulin, la pilule, la rigole, le till, la volonté, et à partir de là, la seule option est de deviner chaque lettre tour. De manière un peu contre-intuitive, les mots plus longs sont beaucoup plus vite devinés (il n'y en a tout simplement pas parmi lesquels choisir).

Bien sûr, dans un jeu humain de bourreau, la psychologie (et l'étendue du vocabulaire) jouent un rôle beaucoup plus important que cet algorithme ne le permet ...

Simplement fais-le! Jouez au bourreau contre le mot. Comptez le nombre de forfaits (c.-à-d. Suppositions incorrectes) qu'il faut pour battre.

Vous aurez besoin d'une stratégie pour jouer. Voici une stratégie humaine (ish). Dans le dictionnaire, supprimez tous les mots qui ne correspondent pas aux révélations jusqu'à présent. Devinez la lettre la plus fréquente parmi les mots restants.

Si votre stratégie est aléatoire, vous pouvez définir votre mesure comme le nombre attendu de forfaits et l'estimer empiriquement.

Une autre stratégie déterministe, d'un bot bourreau que j'ai écrit il y a quelques années. Devinez la lettre qui minimise le nombre de mots restants dans le cas où la supposition est incorrecte (c.-à-d. Optimiser le pire des cas). Aujourd'hui je n'aime pas cette stratégie parce qu'elle est trop mécanique, je préfère celle ci-dessus.

Tout d'abord, bien sûr, vous générez une liste de lettres uniques. Ensuite, triez par fréquence (en anglais ou dans n'importe quelle langue - il existe des listes pour cela ), les lettres moins fréquentes ayant une difficulté plus élevée.

Ensuite, vous devez décider si vous combinez les scores en ajoutant, en multipliant ou en utilisant un autre schéma.

Vous êtes critiqué parce que vous nous demandez de créer un algorithme très complexe pour vous.

Pourquoi ne pas créer simplement trois tableaux (facile, moyen et difficile) et remplir chacun d'une centaine de mots? Cela prendrait environ 20 minutes.

Je promets que vos enfants s'ennuieront du pendu bien avant de brûler quelques centaines de jeux ...: D

Eh bien, potentiellement, il pourrait y avoir beaucoup de choses impliquées:

1. Comme tout le monde l'a dit, la fréquence des lettres individuelles;
2. La longueur d'un mot doit certainement compter, mais pas de manière linéaire - un mot long peut faire des suppositions aléatoires sur les lettres, tandis qu'un mot court peut être difficile à obtenir;
3. En outre, les mots eux-mêmes devraient être considérés - «bipartite» pourrait être un mot pour les gens sur SO, mais peut-être pas pour la population non technique.

En fait, vous pouvez essayer de co-faire évoluer plusieurs stratégies , dont la moitié pour décider de la valeur d'un mot, et la moitié pour essayer de gagner la partie. Le dernier groupe essaiera de maximiser le score tandis que le premier tentera de minimiser le score. Après un certain temps, il pourrait y avoir un modèle, puis la moitié pour décider de la valeur d'un mot peut vous donner quelques repères.

Commencez par une liste de mots et lancez une recherche Google pour chacun d'eux. Laissez le nombre de Hits servir de proxy (grossier) de la difficulté du terme.

Dans une version raffinée, vous regrouperiez les mots par un synonyme Relation basée sur un thésaurus et détermineriez le mot le plus difficile d'une catégorie en comptant les résultats des recherches Google.

Prendre la notion de n-grammes Un peu plus loin, la difficulté d'un mot pourrait être évaluée par la fréquence de ses syllabes en prose. Cela dépend de la qualité des statistiques syllabiques, bien sûr. Vous auriez probablement à faire la différence entre les lexèmes et les mots de fonction (déterminants, conjonctions, etc.) et à normaliser par nombre de syllabes dans le mot (on dirait Overkill as I Write ...).

J'aime l'idée de construire un algorithme qui apprend et change en fonction des utilisateurs. Au début, vous pouvez implémenter l'un des algorithmes suggérés pour créer la liste, puis au fur et à mesure que de plus en plus de personnes jouent au jeu, vous attribuez un poids à chacun des mots en fonction du nombre de suppositions (qui est également continuellement suivi et calculé. ). Cela évite que la question des mots complexes mais populaires soit jugée difficile mais bien connue des gens.

Calculez la valeur de chaque lettre d'un mot en points de Scrabble: E = 1, D = 2, V = 4, X = 8 et ainsi de suite. Additionnez-les et divisez par le nombre de lettres pour obtenir une valeur de lettre moyenne, et utilisez-la pour noter le mot. Calculez la moyenne de chaque mot dans un grand dictionnaire et déterminez les points de rupture entre les quartiles. Appelez les mots du quartile le plus bas "facile", les mots des deux quartiles du milieu "moyen" et les mots du quartile le plus élevé "dur".