[解決済み] ハングマンの難易度を「易しい」「中くらい」「難しい」に分類するためのアルゴリズム

質問

ハングマンゲームで、指定された難易度に合う単語を選択できるように、単語の難易度を決定するための良いアルゴリズムは何ですか?

難易度は、必要な推測の数、文字の相対的な使用頻度 (たとえば、多くの珍しい文字を持つ単語は推測しにくいかもしれません)、および潜在的に単語の長さに関連していると思われます。

また、単語がプレイヤーの語彙の中にあり、認識できる可能性など、補うべき (試みる) いくつかの主観的要素もあり、文字の頻度だけに基づく推測戦略から、既知の一致する単語のリストに基づく推測に移行することを可能にします。

今のところ、私の試みは以下の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

私は自分の子供たちに遊んでもらいたいハングマンゲームを書いています。私は宿題をしようとするには年を取りすぎており、そのためかこの質問には多くの反対票が寄せられています...。 単語は、多くの無名単語を含む大規模な単語データベースからランダムに抽出され、その単語に対して決定された難易度によってフィルタリングされます。

どのように解決するのですか？

1. はじめに

この問題に体系的にアプローチする方法を紹介します。ハングマンをうまく演じるアルゴリズムがある場合、それぞれの単語の難易度を、その単語を推測した場合にプログラムが取るであろう間違った推測の回数とすることができます。

2. ハングマンの戦略について

他の回答やコメントにもあるように、解答者の最適な戦略は、英語の文字の頻度やコーパスの単語の頻度に基づいて決定することだという考えがあります。これは魅力的なアイデアですが、全く正しくありません。ソルバーが最もうまくいくのは 設定者によって選択された単語の分布を正確にモデル化する場合 人間の設定者は、希少性や頻繁に使用される文字の回避に基づいて単語を選択する可能性があります。たとえば E は英語で最も頻繁に使われる文字ですが、もし設定者が常に JUGFUL , RHYTHM , SYZYGY そして ZYTHUM であれば、完全なソルバーは E !

セッターをモデル化するのに最適なアプローチはコンテキストに依存しますが、ソルバーが同じセッターや類似のセッターのグループに対して多くのゲームをプレイするようなコンテキストでは、ある種のベイズ的帰納推論がうまく機能すると推測されます。

3. ハングマンアルゴリズム

ここでは、かなり良い（しかし完璧にはほど遠い）ソルバーの概要を説明します。これは、設定者が固定された辞書から一様に単語を選択するようにモデル化しています。これは 貪欲アルゴリズム である。各ステージで、ミス、つまり推測を含まない単語の数を最小にするような文字を推測する。例えば、ここまでで推測が行われず、可能性のある単語が DEED , DEAD と DARE というように、その後に

• とすれば D または E の場合、ミスはありません。
• とすれば A を当てると、1つだけ外れがあります ( DEED );
• とすれば R を推測した場合、2つの失敗があります ( DEED と DEAD );
• 他の文字を当てた場合、3つの外れがあります。

ということは、どちらか D または E は、この状況では良い推測です。

(おかげさまで コメントでパニック大佐 のおかげで、ハングマンの正解はタダだということを知りました。）

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. 結果例

この方法を用いると、コレクション内の各単語を推測する難易度を評価することが可能です。ここでは、私のシステム辞書にある6文字の単語を考えてみます。

>>> 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 を当てた後でも、まだ7つの可能性が残っているからです。

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

6. 単語リストの選択

もちろん、子供のための単語リストを作成するときは、コンピュータのシステム辞書から始めるのではなく、子供が知っていると思われる単語のリストから始めるでしょう。たとえば、次のようなものがあります。 Wiktionary の最も頻繁に使われる単語のリスト を見てみましょう。

たとえば、6文字の単語1,700個のうち 10,000 most common words in Project Gutenberg as of 2006（2006年現在、プロジェクト グーテンベルクで最も一般的な10,000語 の1,700語のうち、最も難しいのはこの10語です。

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

(ソームズ・フォーサイトは、登場人物である John Galsworthy による Forsyte Saga の登場人物です。 の登場人物です。単語リストは小文字に変換されているので、固有名詞をすばやく削除することはできませんでした)。