Algorithme permettant de classer les mots pour les niveaux de difficulté du bourreau, tels que «Facile», «Moyen» ou «Difficile»

Qu’est-ce qu’un bon algorithme pour déterminer la “difficulté” d’un mot pour un jeu du pendu, de sorte que le jeu puisse sélectionner des mots correspondant à un niveau de difficulté spécifié?

La difficulté semblerait liée au nombre de suppositions requirejses, à la fréquence relative d’utilisation des lettres (par exemple, les mots comportant de nombreuses lettres inhabituelles peuvent être plus difficiles à deviner), et éventuellement à la longueur du mot.

Il existe également des facteurs subjectifs pour (tenter de) compenser, tels que la probabilité qu’un mot soit dans le vocabulaire du lecteur, et peuvent être reconnus, permettant de passer d’une stratégie de devinette basée uniquement sur les fréquences des lettres à mots correspondants connus.

Ma tentative pour le moment est en dessous de ruby. Des suggestions sur la façon d’améliorer la catégorisation?

def classify_word(w) n = w.chars.to_a.uniq.length # Num. unique chars in w if n  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 que j’aimerais que mes enfants jouent; Je suis un peu trop vieux pour tenter un “devoir”, ce qui explique peut-être pourquoi la question reçoit autant de votes négatifs … Les mots sont tirés au hasard à partir de grandes bases de données de mots contenant de nombreux mots obscurs. déterminé pour le mot.

1. Introduction

Voici un moyen d’aborder ce problème de manière systématique: si vous avez un algorithme qui joue bien le bourreau, vous pouvez prendre la difficulté de chaque mot comme étant le nombre de suppositions erronées que votre programme prendrait si vous deviniez ce mot.

2. Outre la stratégie du pendu

Il y a une idée implicite dans certaines autres réponses et commentaires, à savoir 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 correct. Le solveur fait de son mieux s’il modélise avec précision la dissortingbution des mots choisis par le passeur , et un setter humain pourrait bien choisir des mots en fonction de leur rareté ou de leur évitement des lettres fréquemment utilisées. Par exemple, bien que E soit la lettre la plus utilisée en anglais, si le setter choisit toujours parmi les mots JUGFUL , RHYTHM , SYZYGY et ZYTHUM , alors un solveur parfait ne commence pas par 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 avec le même setter, ou avec un groupe de parameters similaires.

3. Un algorithme du pendu

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

  • si vous devinez D ou E , il n’y a pas de raté;
  • si vous devinez A , il y a un raté ( DEED );
  • si vous devinez R , il y a deux ratés ( DEED et DEAD );
  • si vous devinez une autre lettre, il y a trois ratés.

Donc, soit D ou E est une bonne supposition dans cette situation.

(Merci au colonel Panic dans ses commentaires pour souligner 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 ssortingng 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. Exemple de résultats

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

 >>> words = [w.ssortingp() 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 pour que le solveur les devine) 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 difficiles sont ceux-ci:

 >>> 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 en est que, après avoir deviné -UZZLE , vous avez encore 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 entendu, lorsque vous préparez des listes de mots pour vos enfants, vous ne commencerez pas avec le dictionnaire système de votre ordinateur, mais vous commencerez par une liste de mots susceptibles de vous intéresser. Par exemple, vous pouvez consulter les listes de Wiktionnaire des mots les plus fréquemment utilisés dans différents corpus anglais.

Par exemple, parmi les 1 700 mots de six lettres figurant dans les 10 000 mots les plus courants du projet Gutenberg en 2006 , les dix 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 minuscule, ce qui m’a empêché de supprimer rapidement les noms propres.)

Une façon très simple serait de calculer un score basé sur l’absence de voyelles dans le mot, le nombre de lettres uniques et la nature 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 au hasard à chaque fois, pondérée par la fréquence des lettres dans votre langue cible et comptez combien de fois il a fallu à votre joueur randomisé pour trouver une solution. Notez que puisque chaque supposition élimine une lettre, ce processus est fini et renvoie un nombre compris entre 1 et 26 inclus.
  • Répétez ce processus 2*N fois, où N est le nombre de lettres uniques dans votre mot,
  • Calculer le score en faisant la moyenne des résultats de 2*N runs,
  • Déterminer le niveau de complexité: les notes inférieures à dix indiquent un mot facile et les notes supérieures à 16 indiquent un mot difficile; tout le rest 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 de pendu, il suffit d’appliquer une approche comme le scrabble.

Atsortingbuez une valeur de point à chaque lettre, puis ajoutez simplement les lettres.

Il y a quelque temps, j’ai écrit un résolveur de pendu utilisant l’algorithme évident: avec un dictionnaire initial de tous les mots possibles, nous choisissons à chaque tour la lettre qui apparaît dans le dictionnaire, puis supprimons les mots non correspondants (en fonction du réponse) du dictionnaire.

L’algorithme n’est pas aussi simple que cela, car il y a souvent plusieurs lettres qui apparaissent 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 requirejses pour un mot. Nous choisissons les maxima où les informations résultantes sur le placement de cette lettre (si elles sont en effet dans le mot) donnent le maximum d’informations sur le système (la lettre avec le maximum d’entropie d’information ). 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, garanti d’être dans le mot), mais nous devrions d’abord demander à propos de ‘c’ car il a une entropie d’informations non nulle.

La source (C ++, GPL) est ici

Le résultat de tout ceci est une liste de mots, avec le nombre de suppositions requirejs pour chacun: difficulté.txt (630KB). Le mot le plus difficile à trouver pour cet algorithme est “will” (avec 14 suppositions échouées); le i et le double l sont devinés assez rapidement, mais alors les options incluent bill, aneth, remplissage, branchie, colline, tuer, moulin, pilule, rill, jusqu’à, volonté, et à partir de ce moment la seule option est de deviner chaque lettre dans tour. Un peu contre-intuitif, les mots plus longs sont beaucoup plus vite devinés (il n’ya tout simplement pas à choisir).

Bien sûr, dans un jeu humain du pendu, la psychologie (et l’ampleur du vocabulaire) joue un rôle beaucoup plus important que cet algorithme n’en explique pas …

Fais-le! Jouer le pendu contre le mot. Comptez le nombre de forfaits (c.-à-d. Les 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. Devinez la lettre la plus fréquente parmi les mots restants.

Si votre stratégie est randomisée, vous pouvez définir votre mesure comme le nombre prévu de forfaits et l’estimer de manière empirique.


Une autre stratégie déterministe, à partir d’un bot du bourreau que j’ai écrit il y a quelques années. Devinez la lettre qui minimise le nombre de mots restant dans le cas où la supposition est incorrecte (c.-à-d. Optimisez le pire des cas). Aujourd’hui, je n’aime pas cette stratégie pour être 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, sortingez par fréquence (en anglais ou dans n’importe quelle langue – il existe des listes pour cela ), avec des lettres moins fréquentes présentant 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 mis en veilleuse parce que vous nous demandez de construire un algorithme très complexe pour vous.

Pourquoi ne créez-vous pas simplement trois tableaux (facile, moyen et dur) et remplissez-les chacun d’une centaine de mots? Cela prendrait environ 20 minutes.

Je promets que vos enfants s’ennuieront de pendu bien avant qu’ils ne brûlent à travers 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 devrait certainement compter, mais pas de manière linéaire – un long mot peut faire apparaître 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 personnes sur SO, mais peut-être pas pour la population non technique.

En fait, vous pouvez essayer de co-développer plusieurs stratégies , dont la moitié pour décider de la valeur d’un mot, et la moitié d’entre elles pour essayer de gagner le jeu. Ce dernier groupe tentera de maximiser le score tandis que le premier tentera de minimiser le score. Après un certain temps, il pourrait y avoir un motif, 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. Laissez le nombre de hits servir de proxy (grossier) de la difficulté du terme.

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

Prendre la notion de n-gramme Un pas de plus, la difficulté d’un mot pourrait être évaluée par la fréquence de ses syllabes en prose. Dépend de la qualité des statistiques des syllabes, bien sûr. Vous devrez probablement différencier les mots Lexemes et Function (déterminants, conjonctions, etc.) et Normaliser par nombre de syllabes dans le mot (On dirait Overkill que j’écris …).

J’aime l’idée de construire un algorithme qui apprend et change en fonction des utilisateurs. Au début, vous pouvez implémenter n’importe lequel des algorithmes suggérés pour créer la liste, alors que plus de personnes jouent, vous atsortingbuez un poids à chacun des mots en fonction du nombre de suppositions (qui est également suivi et calculé en permanence). ). Cela évite la question des mots complexes, mais populaires, auxquels on atsortingbue une note difficile mais qui sont bien connus des gens.

Calculer la valeur de chaque lettre d’un mot en points Scrabble: E = 1, D = 2, V = 4, X = 8 et ainsi de suite. Ajoutez-les et divisez-les par le nombre de lettres pour obtenir une valeur de lettre moyenne, et utilisez-les pour noter le mot. Calculer la moyenne de chaque mot dans un grand dictionnaire et déterminer les points de rupture entre les quartiles. Appelez les mots dans le quartile inférieur “facile”, les mots dans les deux quartiles moyens “moyen”, et les mots dans le quartile supérieur “dur”.