1. Wstęp
Oto sposób systematycznego podejścia do tego problemu: jeśli masz algorytm, który dobrze gra w kata, możesz przyjąć, że trudność każdego słowa jest liczbą błędnych zgadnięć, które Twój program podjąłby, odgadując to słowo.
2. Pomijając strategię kata
W niektórych innych odpowiedziach i komentarzach jest ukryta idea, że optymalną strategią dla rozwiązującego byłoby oparcie decyzji na częstotliwości liter w języku angielskim lub częstotliwości słów w jakimś korpusie. To kuszący pomysł, ale nie do końca. Rozwiązujący radzi sobie najlepiej, jeśli dokładnie modeluje rozkład słów wybranych przez ustawiającego , a osoba ustawiająca może wybierać słowa na podstawie ich rzadkości lub unikania często używanych liter. Na przykład, chociaż Ejest najczęściej używany list w języku angielskim, jeśli rozgrywający zawsze wybiera ze słów JUGFUL, RHYTHM, SYZYGY, i ZYTHUM, a następnie doskonały solver nie zacząć od zgadywania E!
Najlepsze podejście do modelowania rozgrywającego zależy od kontekstu, ale wydaje mi się, że pewien rodzaj wnioskowania indukcyjnego bayesowskiego dobrze sprawdziłby się w kontekście, w którym solver gra wiele gier przeciwko temu samemu rozgrywającemu lub grupie podobnych rozgrywających.
3. Algorytm kata
Tutaj opiszę solver, który jest całkiem niezły (ale daleki od doskonałości). Modeluje ustawiającego jako jednolity wybór słów ze stałego słownika. To chciwy algorytm : na każdym etapie odgaduje literę, która minimalizuje liczbę chybionych, czyli słów, które nie zawierają domysłów. Na przykład, jeśli nie ma przypuszczenia zostały wykonane do tej pory, a słowa są możliwe DEED, DEADa DARE, a następnie:
- jeśli zgadniesz
Dlub E, nie ma chybionych;
- jeśli zgadniesz
A, jest jedna miss ( DEED);
- jeśli zgadniesz
R, są dwie chybienia ( DEEDi DEAD);
- jeśli zgadniesz jakąkolwiek inną literę, są trzy chybienia.
Więc albo Dalbo Ejest dobrym przypuszczeniem w tej sytuacji.
(Dziękuję Colonel Panic w komentarzach za wskazanie, że poprawne domysły są darmowe w przypadku wisielca - całkowicie zapomniałem o tym za pierwszym razem!)
4. Wdrożenie
Oto implementacja tego algorytmu w Pythonie:
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. Przykładowe wyniki
Korzystając z tej strategii, można ocenić trudność odgadnięcia każdego słowa w zbiorze. Tutaj rozważam sześcioliterowe słowa w moim słowniku systemowym:
>>> 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))
Najłatwiejsze do odgadnięcia słowa w tym słowniku (wraz z sekwencją odpowiedzi potrzebną rozwiązującemu do ich odgadnięcia) są następujące:
>>> 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')]
a najtrudniejsze są te słowa:
>>> 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')]
Powodem, dla którego są one trudne, jest to, że po odgadnięciu -UZZLEnadal pozostaje siedem możliwości:
>>> ' '.join(sorted(w for w in six_letter_words if w.endswith('uzzle')))
'buzzle guzzle muzzle nuzzle puzzle tuzzle wuzzle'
6. Wybór listy słów
Oczywiście, przygotowując listy słów dla swoich dzieci, nie zaczynałbyś od słownika systemowego komputera, lecz od listy słów, które Twoim zdaniem prawdopodobnie będą znać. Na przykład, możesz rzucić okiem na listy Wikisłowników zawierające najczęściej używane słowa w różnych angielskich korpusach.
Na przykład spośród 1700 sześcioliterowych słów z 10000 najczęściej występujących słów w Projekcie Gutenberg w 2006 r. Najtrudniejsze dziesięć to:
[(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 to postać z sagi Forsyte autorstwa Johna Galsworthy'ego ; lista słów została zamieniona na małe litery, więc nie mogłem szybko usunąć nazw własnych.)
f(w) = (# unique letters) * (7 - # vowels) * (sum of the positions of unique letters in a list, ordered by frequency). Stamtąd możesz po prostu podzielić zakres funkcji na trzy segmenty i nazwać je swoimi trudnościami.