Algorytm klasyfikowania słów według poziomów trudności kata jako „Łatwy”, „Średni” lub „Trudny”

Jaki jest dobry algorytm do określania „trudności” słowa w grze w kata, tak aby gra mogła dobrać słowa do określonego poziomu trudności?

Wydaje się, że trudność jest związana z liczbą wymaganych odgadnięć, względną częstotliwością używania liter (np. Słowa z wieloma rzadkimi literami mogą być trudniejsze do odgadnięcia) i potencjalnie długością słowa.

Istnieją również pewne subiektywne czynniki, które należy (próbować) skompensować, takie jak prawdopodobieństwo, że słowo znajduje się w słowniku gracza i może zostać rozpoznane, umożliwiając przejście od strategii zgadywania opartej wyłącznie na częstotliwości liter do zgadywania na podstawie listy znane pasujące słowa.

Moja próba na razie jest poniżej w rubinie. Jakieś sugestie, jak ulepszyć kategoryzację?

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

Piszę grę w kata, w którą chciałbym grać moje dzieci; Jestem raczej za stary, aby próbować „odrabiać lekcje”, co może być przyczyną tego, że pytanie otrzymuje tak wiele głosów negatywnych ... Słowa są losowane z dużych baz danych zawierających wiele niejasnych słów i są filtrowane według poziomu trudności zdecydowany na słowo.

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

Naprawdę prostym sposobem byłoby obliczenie wyniku na podstawie braku samogłosek w słowie, liczby unikalnych liter i powszechności każdej litery:

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

A wynik:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Następnie możesz ocenić słowa za pomocą:

        score < 2000   # Easy
 2000 < score < 10000  # Medium
10000 < score          # Hard

Możesz użyć metody Monte Carlo, aby oszacować trudność słowa:

• Symuluj grę, zgadując za każdym razem losową literę, ważoną częstotliwością litery w Twoim języku docelowym, i policz, ile domysłów potrzebował losowy gracz, aby znaleźć rozwiązanie. Zwróć uwagę, że ponieważ każde przypuszczenie eliminuje literę, proces ten jest skończony i zwraca liczbę od 1 do 26 włącznie.
• Powtórz ten proces 2*Nrazy, gdzie Njest liczba unikalnych liter w Twoim słowie,
• Oblicz wynik, uśredniając wyniki 2*Nprzejazdów,
• Określ poziom złożoności: wyniki mniejsze niż dziesięć oznaczają łatwe słowo, a wyniki powyżej szesnastu oznaczają trudne słowo; wszystko inne jest średnie.

Poprzednia podobna dyskusja na ten sam temat: Określ stopień trudności angielskiego słowa

Podoba mi się odpowiedź na końcu linku ^. W przypadku gry w kata dla dzieci zastosuj podejście takie jak w scrabble.

Przypisz wartość punktową do każdej litery, a następnie po prostu dodaj litery.

Jakiś czas temu napisałem pomocnika kata, używając oczywistego algorytmu: mając wstępny słownik wszystkich możliwych słów, za każdym razem wybieramy literę, która występuje w większości słów pozostałych w słowniku, a następnie usuwamy niepasujące słowa (w zależności od odpowiedź) ze słownika.

Algorytm nie jest tak prosty, jak ten, ponieważ często występuje kilka liter, z których każda występuje w tej samej liczbie słów w słowniku. W takim przypadku wybór litery może mieć znaczący wpływ na to, ile domysłów jest wymaganych dla słowa. Wybieramy maksima, w których wynikowa informacja o położeniu tej litery (jeśli jest rzeczywiście w słowie) daje maksimum informacji o systemie (litera z maksymalną entropią informacyjną ). np. jeśli dwa pozostałe możliwe słowa to „encyklopedia” i „encyklopedia”, litera „c” ma takie samo prawdopodobieństwo pojawienia się jak e, n, y, l, o, p, e, d, i (tj. na pewno znajduje się w słowie), ale najpierw powinniśmy zapytać o „c”, ponieważ ma ono niezerową entropię informacyjną.

Źródło (C ++, GPL) jest tutaj

Rezultatem tego wszystkiego jest lista słów wraz z liczbą domysłów wymaganych dla każdego z nich: trudność.txt (630KB). Najtrudniejszym słowem dla tego algorytmu do znalezienia jest „wola” (14 nieudanych prób); i i podwójne l są odgadywane dość szybko, ale opcje obejmują bill, dill, fill, gill, hill, kill, mill, pill, rill, till, will, a jedyną opcją jest odgadnięcie każdej litery w skręcać. Nieco sprzecznie z intuicją, dłuższe słowa są odgadywane znacznie szybciej (po prostu nie ma ich zbyt wiele do wyboru).

Oczywiście w ludzkiej grze w kata psychologia (i bogactwo słownictwa) odgrywa znacznie większą rolę niż ten algorytm wyjaśnia ...

Po prostu to zrób! Zagraj w kata przeciwko słowu. Policz, ile przepadek (tj. Błędnych domysłów) wymaga pokonania.

Będziesz potrzebować strategii do gry. Oto ludzka (ish) strategia. Ze słownika wykreśl wszystkie słowa, które do tej pory nie pasują do ujawnień. Odgadnij literę najczęściej występującą wśród pozostałych słów.

Jeśli Twoja strategia jest losowa, możesz zdefiniować swoją miarę jako oczekiwaną liczbę przepadków i oszacować to empirycznie.

Kolejna deterministyczna strategia od bota kata, którego napisałem kilka lat temu. Odgadnij literę, która minimalizuje liczbę pozostałych słów w przypadku, gdy odgadnięcie jest nieprawidłowe (tj. Zoptymalizuj najgorszy przypadek). Dziś nie podoba mi się ta strategia, ponieważ jest zbyt mechaniczna, wolę tę powyżej.

Najpierw oczywiście wygenerowałbyś listę unikalnych liter. Następnie posortuj według częstotliwości (po angielsku lub w jakimkolwiek innym języku - są do tego listy ), przy czym rzadsze litery mają większą trudność.

Następnie musisz zdecydować, czy połączysz wyniki, dodając, mnożąc lub używając innego schematu.

Zostajesz odrzucony, ponieważ prosisz nas o zbudowanie dla Ciebie bardzo złożonego algorytmu.

Dlaczego po prostu nie utworzysz trzech tablic (łatwych, średnich i trudnych) i nie zapełnisz każdej stu lub więcej słów? Zajmie to około 20 minut.

Obiecuję, że twoje dzieci znudzą się wisielcem na długo zanim przepalą kilkaset gier ...: D

Cóż, potencjalnie może być zaangażowanych wiele rzeczy:

1. Jak wszyscy powiedzieli, częstotliwość poszczególnych liter;
2. Długość słowa zdecydowanie powinna się liczyć, ale nie w sposób liniowy - długie słowo może powodować przypadkowe zgadywanie liter, podczas gdy krótkie może być trudne do ustalenia;
3. Należy również wziąć pod uwagę same słowa - „dwustronny” może być słowem dla osób z SO, ale może nie dla populacji nietechnicznej.

Właściwie możesz spróbować wspólnie rozwinąć kilka strategii , połowę z nich do decydowania o wartości słowa, a połowę do próby wygrania gry. Druga grupa będzie starała się maksymalizować wynik, podczas gdy pierwsza będzie próbować zminimalizować wynik. Po chwili może pojawić się wzorzec, a potem połowa decydująca o wartości słowa może dać pewne punkty odniesienia.

Zacznij od listy słów i rozpocznij wyszukiwanie w Google dla każdego z nich. Niech liczba trafień posłuży jako (przybliżony) wskaźnik trudności terminu.

W udoskonalonej wersji można pogrupować słowa według synonimu Relacja oparta na tezaurusie i określić najtrudniejsze słowo w kategorii, licząc wyniki wyszukiwania w Google.

Idąc dalej z pojęciem n-gramów O krok dalej, trudność słowa można ocenić na podstawie częstotliwości jego sylab w prozie. Oczywiście zależy to od jakości statystyk sylab. Prawdopodobnie musiałbyś rozróżniać między leksemami i słowami funkcyjnymi (wyznaczniki, spójniki itp.) I normalizować na podstawie liczby sylab w słowie (wydaje się przesadą, gdy piszę ...).

Podoba mi się pomysł zbudowania algorytmu, który uczy się i zmienia w zależności od użytkowników. Na początku możesz zaimplementować dowolny z algorytmów sugerowanych do stworzenia listy, a następnie, gdy więcej osób gra w grę, przypisujesz wagę każdemu ze słów w zależności od liczby zgadnięć (która jest również stale śledzona i obliczana ). Zapobiega to przypisywaniu trudnej oceny skomplikowanym, ale popularnym słowom, ale są one dobrze znane ludziom.

Oblicz wartość każdej litery słowa w punktach Scrabble: E = 1, D = 2, V = 4, X = 8 i tak dalej. Dodaj je i podziel przez liczbę liter, aby otrzymać średnią wartość litery, i użyj jej do oceny słowa. Oblicz średnią dla każdego słowa w dużym słowniku i określ punkty przerwania między kwartylami. Nazwij słowa z najniższego kwartylu „łatwymi”, słowa z dwóch środkowych kwartylami „średnimi”, a słowa z najwyższego kwartylu „twardymi”.