用于将hangman难度级别的单词分类为“简单”，“中”或“硬”的algorithm
什么是一个好的algorithm来确定一个hang子手游戏的单词的“难度”，以便游戏可以select单词来匹配指定的难度级别？
难度似乎与所需的猜测次数有关，字母使用的相对频率（例如，带有许多罕见字母的单词可能难以猜测）以及潜在的单词长度。
还有一些主观因素（试图）补偿，比如一个单词在玩家词汇中的可能性，并且可以被识别，允许从仅基于字母频率的猜测策略转移到基于列表的猜测已知的匹配词。
我现在的尝试是在ruby下面。 有关如何改进分类的build议？
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 我正在写一个hang子手游戏，我希望我的孩子们玩; 我太老了，不能尝试“作业”，这可能是为什么问题是接受这么多的倒票…单词是从大字数据库中随机抽取的，其中包含许多难懂的单词，并且正在被难度级别过滤确定的话。
1.介绍
下面是一个系统地解决这个问题的方法：如果你有一个能够很好地玩hang子手的algorithm，那么你可以把每个单词的难度看作是猜测这个单词的程序将要做的错误猜测的次数。
除了hang子手战略
在其他一些答案和评论中隐含着一个想法，即解决者的最佳策略是根据英文字母的频率或某些语料库中的词频来决定。 这是一个诱人的想法，但不完全正确。 如果解算器能够精确地模拟二传手所select的单词的分布，那么解算器就能达到最好的效果，而一个人类二传手可能会根据其经常使用的字母的稀有性或避免select单词。 例如，尽pipeE是英语中使用最频繁的字母，但是如果二字母总是从单词JUGFUL ， RHYTHM ， SYZYGY和ZYTHUM ，那么完美的求解器并不是从猜测E开始的！
对二传手build模的最佳方法取决于上下文，但是我猜想某种贝叶斯归纳推理在解决方法与同一个二传手或者一组相似二传手进行许多比赛的情况下可以很好地工作。
3.一个hang子手algorithm
在这里，我将概述一个相当不错的求解器（但很不完美）。 它把二传手build模为从固定字典中统一select单词。 这是一个贪婪的algorithm ：在每一个阶段，它猜测最小化错过次数的字母，即不包含猜测的单词。 例如，如果到目前为止还没有猜测，可能的词是DEED ， DEAD和DARE ，那么：
- 如果你猜测
D或E，那就没有错过; - 如果你猜
A，有一个小姐（DEED）; - 如果你猜
R，有两个错过（DEED和DEAD）; - 如果你猜其他信，就会有三次错过。
所以在这种情况下D或E是一个很好的猜测。
（感谢Panic上校在评论中指出正确的猜测在hang子手中是免费的 – 我完全忘记了这一点！）
4.实施
下面是Python中这个algorithm的一个实现：
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.示例结果
使用这个策略，可以评估猜测集合中每个单词的难度。 在这里，我考虑我的系统字典中的六个字母的单词：
>>> 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))
在这本词典中猜测最简单的单词（连同猜测所需的猜测顺序）如下：
>>> 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')]
最难的是这些：
>>> 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')]
之所以这么难是因为在你猜到了-UZZLE ，你还剩下七种可能：
>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle'))) 'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'
6.选词列表
当然，当为孩子准备单词列表时，你不会从你的电脑的系统字典开始，你会从你认为他们可能知道的单词列表开始。 例如，您可能会看到维基词典中各种英语语料库中最常用词汇的列表 。
例如， 截至2006年古腾堡计划中10,000个最常用单词中的1700个六个字母的单词中，最困难的十个单词是：
[(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是John Galsworthy的Forsyte Saga中的一个angular色;这个单词表已经被转换为小写字母，所以我不能快速删除正确的名字。）
一个非常简单的方法是根据单词中缺less元音，独特字母的数量和每个字母的共同性来计算得分：
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
而输出：
432 the 3360 potato 7200 school 7800 egypt 194271 floccinaucinihilipilification
然后你可以用
score < 2000 # Easy 2000 < score < 10000 # Medium 10000 < score # Hard
你可以用蒙特卡洛方法来估计一个单词的难度：
- 通过每次猜测随机字母来模拟游戏，用目标语言的字母频率加权，并计算随机玩家到达解决scheme所花费的时间。 请注意，由于每个猜测消除了一个字母，这个过程是有限的，它返回一个从1到26的数字。
- 重复这个过程
2*N次，其中N是你的单词中唯一字母的数量， - 通过平均
2*N运行的结果来计算分数， - 确定复杂程度：小于十的分数表示一个简单的词，十六分以上的分数表示硬的词; 其他一切都是中等的。
先前围绕同一主题的类似讨论： 确定英语单词的难度
我喜欢链接末尾的答案^。 对于一个孩子hang子手游戏，只需要像拼字游戏一样的方法。
为每个字母指定一个点值，然后加上字母。
前一段时间，我用一个明显的algorithm写了一个hang子手求解器：给出一个所有可能的单词的初始字典，每一次我们select字典中剩下的大多数单词中出现的字母，然后删除不匹配的单词（取决于回应）从字典。
该algorithm不像这样直截了当，因为经常有几个字母，每个字母出现在字典中相同的字数。 在这种情况下，字母的select可能会对一个单词需要多less次猜测产生重大影响。 我们select最大值，在那里得到关于该字母放置的信息（如果确实在字中）给出有关系统的最大信息（具有最大信息熵的字母）。 例如，如果剩余的两个词是“百科全书”和“百科全书”，那么字母“c”与e，n，y，l，o，p，e，d，i出现的概率相同保证在这个词里），但是我们应该首先询问'c'，因为它有一个非零的信息熵。
源（C ++，GPL）在这里
所有这一切的结果是一个单词列表，每个单词所需的猜测数量： 难度 .txt（630KB）。 这个algorithm最难find的是“will”（有14次失败的猜测）; 我和双我猜很快，但是然后选项包括法案，莳萝，填充，鳃，山，杀，磨，丸，小溪，直到，将，并从那时起唯一的select是猜测每个字母转。 有些违反直觉的是，更长的单词被更快地推测出来（他们可能没有那么多的select）。
当然，在一个人类的hang子手游戏中，心理学（和词汇的广度）比这个algorithm所起的作用要大得多。
去做就对了！ 玩反对这个词的hang子手。 计算需要击败多less次失败（即不正确的猜测）。
你需要一个策略来玩。 这是一个人（ish）的策略。 从字典中，挑出所有不适合揭示的话。 猜猜剩下的单词中最频繁的一个字母。
如果您的策略是随机的，您可以将您的测量定义为预期的丧失数量，并根据经验进行估计。
另一个确定性的策略，从几年前我写的一个hang子手机器人 。 猜猜这个字母可以最大限度地减less在猜测不正确的情况下剩余的字数（即优化最坏的情况）。 今天我不喜欢这个太机械的策略，我更喜欢上面的那个。
首先，当然，你会生成一个唯一的字母列表。 然后按频率（以英文或其他语言 – 有这个列表）进行sorting，频率较低的字母有较高的难度。
然后，您需要决定是否通过添加，相乘或使用其他scheme来合并分数。
你会因为要求我们为你build立一个非常复杂的algorithm而陷入低谷。
你为什么不创build三个数组（简单，中等和难），并填充每一百个左右的单词？ 这将需要大约20分钟。
我保证你的孩子在烧几百个游戏之前就会感到厌倦
那么，可能会涉及很多事情：
- 正如大家所说，个别字母的频率;
- 一个字的长度一定要算，而不是一个线性的方式 – 一个长的单词可以使随机的猜测碰到字母，而一个短的可以很难得到;
- 而且，这个词本身也应该被考虑 – “二分”可能是SO上的一个词，但也许不是非技术人口。
实际上，你可以尝试共同发展几种策略 ，其中一半是为了决定一个词的价值，另一半是为了赢得比赛。 后者将尝试最大化分数，而第一个尝试最小化分数。 一段时间后，可能会有一个模式，然后决定一个词的价值的一半可能会给你一些基准。
从单词列表开始，为每个单词启动Googlesearch。 让Hits的数量作为该术语难度的（粗略）代理。
在一个精致的版本中，您可以按同义词“基于同义词库的关系”对单词进行分组，并通过计算Googlesearch结果来确定类别中最难的单词。
使用n-gram的概念更进一步，单词的难度可以用散文的音节频率来评价。 当然取决于音节统计的质量。 你可能不得不区分Lexemes和function词（确定者，连词等），并通过Word中音节的数量规范化（感觉像我写的过度杀伤…）。
我喜欢构build一个根据用户学习和变化的algorithm。 开始的时候，你可以实现任何提出的列表的algorithm，然后随着更多的人玩游戏，你根据猜测的数量为每个单词指定一个权重（这也是连续跟踪和计算的）。 这样可以防止复杂而stream行的单词难以评分，但却是人们所熟知的。
在拼字游戏点计算一个单词的每个字母的值：E = 1，D = 2，V = 4，X = 8等等。 把它们加起来，除以字母的数量得到一个平均的字母值，然后用它来评分这个词。 计算大字典中每个单词的平均值，并确定四分位数之间的中断点。 在最低的四分位数中称为“容易”的单词，在中间的两个四分位数中的单词为“中”，而最高四分位数的单词为“硬”。
