Алгоритм классификации слов по уровням сложности «палач» на «легкий», «средний» или «жесткий»

Каков хороший алгоритм определения «сложности» слова для игры в палач, чтобы игра могла выбирать слова, соответствующие заданному уровню сложности?

Казалось бы, трудность связана с количеством требуемых отгаданий, относительной частотой использования букв (например, слова с большим количеством необычных букв может быть труднее угадать) и, возможно, с длиной слова.

Есть также некоторые субъективные факторы, которые необходимо (попытаться) компенсировать, например, вероятность того, что слово находится в словарном запасе игрока и может быть распознано, что позволяет перейти от стратегии угадывания, основанной только на частотах букв, к угадыванию на основе списка известные совпадающие слова.

Моя попытка пока представлена ​​рубином ниже. Есть предложения по улучшению категоризации?

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, есть один промах ( DEED);
• если угадаете R, есть два промаха ( DEEDи DEAD);
• если вы угадаете любую другую букву, будет три промаха.

Так что в данной ситуации можно предположить либо, 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. Примеры результатов

Используя эту стратегию, можно оценить сложность угадывания каждого слова в коллекции. Здесь я рассматриваю слова из шести букв в моем системном словаре:

>>> 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. Выбор словаря

Конечно, при составлении списков слов для своих детей вы не начнете с системного словаря вашего компьютера, а начнете со списка слов, которые, по вашему мнению, они могут знать. Например, вы можете посмотреть в Викисловаре списки наиболее часто используемых слов в различных английских корпусах.

Например, среди 1700 шестибуквенных слов из 10 000 наиболее распространенных слов в Project Gutenberg по состоянию на 2006 г. самые трудные десять следующие:

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

(Сомс Форсайт - персонаж саги о Форсайтах Джона Голсуорси ; список слов был преобразован в нижний регистр, поэтому я не мог быстро удалить имена собственные.)

Очень простой способ - вычислить балл на основе отсутствия гласных в слове, количества уникальных букв и общности каждой буквы:

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

И вывод:

432 the
3360 potato
7200 school
7800 egypt
194271 floccinaucinihilipilification

Затем вы можете подсчитать слова:

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

Вы можете использовать метод Монте-Карло, чтобы оценить сложность слова:

• Смоделируйте игру, каждый раз угадывая случайную букву, взвешенную по частоте букв на вашем целевом языке, и подсчитайте, сколько угаданий потребовалось вашему рандомизированному игроку, чтобы прийти к решению. Обратите внимание: поскольку каждое предположение исключает букву, этот процесс является конечным и возвращает число от 1 до 26 включительно.
• Повторите этот процесс несколько 2*Nраз, где N- количество уникальных букв в вашем слове,
• Подсчитайте балл, усреднив результаты 2*Nзапусков,
• Определите уровень сложности: оценка меньше десяти означает легкое слово, а оценка выше шестнадцати означает трудное слово; все остальное среднее.

Предыдущее аналогичное обсуждение той же темы: Определение сложности английского слова

Мне нравится ответ в конце ссылки ^. Для детской игры с палачом просто примените подход, подобный тому, как это делает скрабл.

Присвойте каждой букве балл, а затем просто сложите буквы.

Некоторое время назад я написал решатель палача, используя очевидный алгоритм: учитывая исходный словарь всех возможных слов, на каждом шаге мы выбираем букву, которая встречается в большинстве слов, оставшихся в словаре, затем удаляем несовпадающие слова (в зависимости от ответ) из словаря.

Алгоритм не так прост, как этот, поскольку часто бывает несколько букв, каждая из которых встречается в одном и том же количестве слов в словаре. В этом случае выбор буквы может существенно повлиять на то, сколько угадываний требуется для слова. Мы выбираем максимумы, при которых результирующая информация о размещении этой буквы (если она действительно находится в слове) дает максимальную информацию о системе (буква с максимальной энтропией информации ). например, если два оставшихся возможных слова - «энциклопедия» и «энциклопедический», буква «c» имеет такую ​​же вероятность появления, как e, n, y, l, o, p, e, d, i (т.е. гарантированно попадает в слово), но сначала мы должны спросить о букве c, поскольку она имеет ненулевую информационную энтропию.

Исходный код (C ++, GPL) здесь

Результатом всего этого является список слов с количеством угадываний, необходимых для каждого из них: сложность.txt (630 КБ). Сложнее всего найти для этого алгоритма слово «будет» (с 14 ошибочными догадками); i и двойное l угадываются довольно быстро, но затем варианты включают в себя счет, укроп, заливку, жабру, холм, убивать, мельницу, пилюлю, окунание, касание, будет, и с этого момента единственный вариант - угадать каждую букву перемена. Как это ни парадоксально, но более длинные слова отгадываются гораздо быстрее (их просто не так много на выбор).

Конечно, в человеческой игре в палач психология (и широта словарного запаса) играет гораздо большую роль, чем этот алгоритм учитывает ...

Просто сделай это! Играть в палача против слова. Подсчитайте, сколько штрафов (т. Е. Неверных догадок) нужно, чтобы победить.

Для игры вам понадобится стратегия. Вот человеческая (иш) стратегия. Вычеркните из словаря все слова, которые пока не подходят к раскрытию. Угадайте букву, которая встречается чаще всего среди оставшихся слов.

Если ваша стратегия является рандомизированной, вы можете определить свою меру как ожидаемое количество штрафов и оценить это эмпирически.

Еще одна детерминированная стратегия от бота-палача, который я написал несколько лет назад. Угадайте букву, которая минимизирует количество оставшихся слов в случае, если предположение неверно (т. Е. Оптимизируйте наихудший случай). Сегодня мне не нравится эта стратегия из-за того, что она слишком механична, я предпочитаю описанную выше.

Сначала вы, конечно, создадите список уникальных букв. Затем отсортируйте по частоте (на английском или другом языке - для этого есть списки ), при этом менее частые буквы имеют большую сложность.

Затем вам нужно решить, комбинируете ли вы оценки, складывая, умножая или используя другую схему.

Вы получаете отрицательное голосование, потому что просите нас разработать для вас очень сложный алгоритм.

Почему бы вам просто не создать три массива (легкий, средний и сложный) и заполнить каждый сотней или около того слов? Это займет минут 20.

Я обещаю, вашим детям надоест висеть задолго до того, как они прожигут несколько сотен игр ...: D

Что ж, потенциально может быть задействовано множество вещей:

1. Как все говорили, частота отдельных букв;
2. Длина слова определенно должна учитываться, но не линейно - длинное слово может привести к случайным угадыванию букв, в то время как короткое может быть трудно получить;
3. Кроме того, следует учитывать сами слова - «двудольный» может быть словом для людей на SO, но, возможно, не для нетехнического населения.

Фактически, вы можете попытаться совместно разработать несколько стратегий , половина из которых предназначена для определения ценности слова, а половина - для попытки выиграть игру. Последняя группа будет пытаться максимизировать оценку, а первая - минимизировать ее. Через некоторое время может появиться шаблон, и тогда половина для определения ценности слова может дать вам некоторые ориентиры.

Начните со списка слов и запустите поиск в Google для каждого из них. Пусть количество совпадений служит (грубо) показателем сложности термина.

В усовершенствованной версии вы сгруппируете слова по синониму «Связь на основе тезауруса» и определите самое сложное слово в категории, подсчитав результаты поиска в Google.

Развивая понятие n-граммов. Еще один шаг вперед: трудность слова можно оценить по частоте его слогов в прозе. Конечно, это зависит от качества статистики по слогам. Вероятно, вам придется различать лексемы и функциональные слова (определители, союзы и т. Д.) И нормализовать по количеству слогов в слове (похоже, что я пишу ...).

Мне нравится идея создания алгоритма, который обучается и изменяется в зависимости от пользователей. Вначале вы можете реализовать любой из алгоритмов, предложенных для составления списка, а затем, по мере того, как в игру играет больше людей, вы назначаете вес каждому из слов в зависимости от количества предположений (которое также постоянно отслеживается и вычисляется. ). Это предотвращает то, что сложные, но популярные слова получают сложную оценку, но хорошо известны людям.

Вычислите значение каждой буквы слова в точках Scrabble: E = 1, D = 2, V = 4, X = 8 и так далее. Сложите их и разделите на количество букв, чтобы получить среднее буквенное значение, и используйте это для оценки слова. Вычислите среднее значение для каждого слова в большом словаре и определите точки разрыва между квартилями. Назовите слова из нижнего квартиля «легкими», слова из двух средних квартилей «средними» и слова из верхнего квартиля как «жесткие».