"Oyun kelimeleri belirtilen bir zorluk seviyesi maç için seçebilirsiniz? adam asmaca oyunu için bir kelime, zorluk belirlemek için iyi bir algoritma nedir

Zorluk tahminler, harflerin kullanımını (çok nadir harfler gibi kelimeler daha zor tahmin edilebilir), ve kelime uzunluğu potansiyel olarak göreli frekans sayısı ile ilgili gibi görünüyor.

Ayrıca bazı öznel faktörler (girişimi) telafi etmek için, gibi ihtimali bir kelimedir bu kelime oyuncu, ve kabul, izin, hareketli bir tahmin stratejisi temel harf frekansları yalnız tahmin dayalı bilinen eşleşen kelimeler.

Şu an için benim girişimi ruby altındadır. Sınıflandırma nasıl geliştirileceği konusunda herhangi bir öneriniz var mı?

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

Çocuklarımla oynamak istiyorum cellat bir oyun yazıyorum; çalışıyor olmak çok yaşlıyım yerine "sorusuna o kadar çok oy aşağı alıyor neden olabilir...", ödev Kelimeler çok belirsiz kelimeler içeren büyük bir kelime veritabanı, rastgele çizilir ve zorluk seviyesi kelimesi için kararlı tarafından filtre ediliyor.

1. Giriş

Burada bir yaklaşım bu sorun sistematik olarak: eğer bir algoritma oynadığı adam asmaca o zaman alabilirsin zorluk her kelime için numarasının yanlış tahmin programı almak isteyen varsa sanırım bu kelimeyi.

2. Cellat strateji kenara

Bir fikri olan üstü kapalı bazı diğer cevaplar ve yorumlar, en uygun strateji için çözücü olurdu Bankası kararlarını frekans harflerle İngilizce ya da frekansın bir deyişle bazı corpus. Bu baştan çıkarıcı bir fikir, ama pek doğru değil. Çözücü eğer geleni yapardoğru modeller kelimeler ayarlayıcısı tarafından seçilmiş dağılımıinsan bir pasör de sık kullanılan harfler nadir veya kaçınma göre kelime seçimi olabilir. Örneğin, ancak E en sık kullanılan harf İngilizce, pasör her zaman seçer kelimeleri JUGFUL, RHYTHM, SYZYGY, ve ZYTHUM sonra mükemmel bir çözücü başlamaz tarafından tahmin E!

En iyi yaklaşım için modelleme belirleyici duruma bağlı, ama sanırım bu bir çeşit Bayesian tümevarımsal çıkarım ki iş iyi bir bağlam nerede çözücü oynadığı birçok oyun karşı aynı ayarlayıcı, veya karşı bir grup benzer belirleyiciler.

3. Cellat bir algoritma

Burada çok iyi bir çözücü (ama o kadar mükemmel değil) ana hatlarıyla anlatacağım. Bunu düzgün sabit bir sözlükten seçme sözler olarak kanepe modelleri. greedy algorithm bir: her aşamada özlüyor sayısı, tahmin içermeyen kelimeleri en aza indirir harfi tahmin eder. Eğer tahminler şimdiye kadar yapılmış, örneğin, ve olası sözleri DEED, DEAD DARE,:

• eğer D E, tahmin edersen özlüyor yok;
• eğer A, sanırım eğer bir bayan (DEED) var;
• R, tahmin edersen özlüyor iki (DEED DEAD) vardır;
• eğer başka bir harf tahmin ederseniz, orada üç özlüyor.

D E ya da bu durumda iyi bir tahmin.

(Doğru tahmin—ben cellat ücretsiz olduğunu işaret Colonel Panic in comments sayesinde tamamen benim ilk girişim bu unuttum!)

4. Uygulama

İşte Python bu algoritma uygulaması:

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. Örnek sonuçları

Bu strateji ile mümkün koleksiyonundaki her bir kelime tahmin zorluğu değerlendirmek için. Burada altı harfli sistemim sözlükte kelimeleri düşünün:

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

Bu sözlükte sanırım en kolay kelimeler (tahmin çözücü bunları tahmin etmek için yapılması gereken işlem sırası ile birlikte) aşağıdaki gibidir:

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

ve en zor kelimeler bunlar

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

Bu zor nedeni -UZZLE, tahmin ettik sonra hala yedi olasılıkları kaldı çünkü

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

6. Kelime listesi seçimi

Wordlists bilgisayarınızın sistem sözlük ile başlamak olmaz hazırlarken tabii ki, bilmek muhtemeldir düşündüğünüz kelimelik bir liste ile başlamak istiyorum. Örneğin, çeşitli İngilizce korpus Wiktionary's lists of the most frequently used words bir göz olabilir.

1700 arasında örneğin, altı harfli 10,000 most common words in Project Gutenberg as of 2006, en zor on bunlar kelime:

[(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 bana hızlı bir şekilde özel isimler kaldırmak mümkün değilmiş Forsyte Saga by John Galsworthy; kelime listesi dönüştürülmüş bir karakter küçük harf.)