将刽子手难度级别的单词分类为 "Easy","Medium"或 "Hard"的算法

Question

什么是确定刽子手游戏单词“难度”的好算法，以便游戏可以选择匹配指定难度级别的单词？

难度似乎与所需的猜测次数、字母使用的相对频率(例如，包含许多不常见字母的单词可能更难猜到)以及潜在的单词长度有关。

还有一些主观因素需要(尝试)补偿，例如一个词在玩家词汇表中的可能性，并且可以被识别，从而允许从仅基于字母频率的猜测策略转变为基于猜测的策略在已知匹配词列表上。

我现在的尝试是在 ruby​​ 中。关于如何改进分类有什么建议吗？

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

我正在写一个刽子手游戏，我希望我的 children 玩；我太老了，不能尝试“家庭作业”，这可能就是为什么这个问题收到这么多反对票的原因......单词是从大型单词数据库中随机抽取的，其中包含许多晦涩难懂的单词，并根据为单词确定的难度级别进行过滤。

Answer 1

1。简介

这里有一种系统地解决这个问题的方法:如果您有一个可以很好地玩刽子手的算法，那么您可以将每个单词的难度作为您的程序在猜测该单词时将进行的错误猜测次数。

2。抛开刽子手策略

其他一些答案和评论中隐含了一个想法，即求解器的最佳策略是根据英语字母的频率或某些语料库中的单词频率做出决定。这是一个诱人的想法，但并不完全正确。如果求解器准确地模拟设置者选择的单词的分布，那么求解器就会做得最好，而人类设置者很可能会根据单词的稀有性或避免使用常用字母来选择单词。例如，虽然 E 是英语中最常用的字母，但如果设置者总是从单词中选择 JUGFUL、RHYTHM、 SYZYGY 和 ZYTHUM，那么完美的求解器不会从猜测 E 开始!

为二传手建模的最佳方法取决于上下文，但我猜想某种贝叶斯归纳推理在求解器与同一个二传手或一组相似二传手进行许多游戏的情况下会很有效。

3。刽子手算法

在这里，我将概述一个相当不错(但远非完美)的求解器。它将 setter 建模为从固定字典中统一选择单词。这是一个greedy algorithm :在每个阶段，它都会猜测使未命中次数最少的字母，即不包含猜测的单词。例如，如果到目前为止没有做出任何猜测，并且可能的单词是 DEED、DEAD 和 DARE，那么:

• 如果你猜的是D或E，没有失误；
• 如果您猜A，则有一个未命中 (DEED)；
• 如果您猜R，则有两次未命中(DEED 和DEAD)；
• 如果您猜任何其他字母，则有 3 次未猜中。

所以在这种情况下，D 或 E 是一个很好的猜测。

(感谢 Colonel Panic in comments 指出正确的猜测在 hangman 中是免费的——我在第一次尝试时完全忘记了这一点!)

4。实现

下面是这个算法在 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。示例结果

使用此策略可以评估猜测集合中每个单词的难度。在这里，我考虑了我的系统词典中的六个字母的单词:

>>> 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。词表的选择

当然，在为您的 child 准备单词表时，您不会从计算机的系统词典开始，而是从您认为他们可能知道的单词列表开始。例如，您可能会查看 Wiktionary's lists of the most frequently used words在各种英语语料库中。

例如，在 10,000 most common words in Project Gutenberg as of 2006 中的 1,700 个六个字母的单词中，最难的十个是这些:

[(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 是 Forsyte Saga by John Galsworthy 中的一个字符；单词列表已转换为小写，因此我无法快速删除专有名称。)