Какой оптимальный алгоритм для игры в рубашке Word Word?

https://cs.stackexchange.com/questions/128667

29-09-2020
|

Вопрос

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

Цель моего оппонента должна быть выбрать слово, которое максимизирует количество ошибок (неверные догадки), которые я делаю, прежде чем я смогу угадать слово. Моя цель - минимизировать их. (Традиционно, если количество ошибок> Некоторые число, то я теряю игру, но мы можем расслабиться, чтобы ограничить.)

Рассмотрим три алгоритма для подачи письма. Это главные, которые я думал, но, вероятно, больше, и я приветствую альтернативные идеи. Во всех трех алгоритмах первого шага будет собирать список слов, которые являются одинаковой длиной, что и секретное слово. Затем для каждой буквы в алфавите подсчитайте количество слов в словаре, которые содержат это письмо. Например, может быть, 5000 содержит «A», 300 содержат «B» и так далее. Вот это в Python:

    alphabet = list('abcdefghijklmnopqrstuvwxyz')

    while not found:
        probabilities = dict.fromkeys(alphabet, 0)

        for word in dictionary:
            for letter in word:
                if letter in alphabet:
                    probabilities[letter] += 1

        # now we have the letter frequencies

После этого, где три алгоритмы расходятся.

В первом алгоритме мы предполагаем, что буква, которое содержит наибольшее количество оставшихся слов. Итак, если 5000 оставшихся слов содержат «А», и никакие другие буквы не имеют много слов, мы выберем «A» каждый раз. Если «A» верна, это дает нам позиционную информацию, которую мы можем дополнительно отфильтровать список. Например, мы можем отфильтровать список всеми словами, которые соответствуют «. ..». (Точки неизвестные буквы.) Если «A» неверно, мы отфилялируем все слова, которые содержат «a». В случае, когда есть галстук, и две буквы находятся в равном количестве слов, буквы выбраны в алфавитном порядке. Поэтому, если мы знаем слово спички «.ay», мы просто угадаем слова в алфавитном порядке.

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

В этом случае мы выбираем буквы с вероятностью пропорциональны количеству слов, которые содержат это письмо. В начале, когда мы подсчитали количество слов, которые содержат «a» и номер, который содержат «b», и так далее, поскольку «A» произошло, на котором можно найти в самом количестве слов, в стратегиях 1 и 2 мы выбрали » «100% времени. Вместо этого мы все еще будем выбирать «» множество времени, но небольшое количество раз мы выберете «Z», хотя можно найти в 10 раз больше слов. У меня есть сомнения в этой стратегии, являющейся оптимальной, но Он использовался в исследовании в 2010 году .

поэтому у меня есть два вопроса:

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

Разъяснения

.
любой английский словарь можно использовать. Например, Этот английский словарь с 84K словами. . Подмножества словарей тщательно выбранные для двусмысленности, могут быть также интересными, но находятся за пределами объема этого вопроса.

нет ограничения на размер слов, пока слово находится в словаре. Участье будет знать размер слова, прежде чем он начинает угадать.

Только общее количество ошибок имеет значение, которое не зависит от размера слова. Вы не получаете больше шансов на более длинные слова или меньше шансов на более короткие.

Я заинтересован только в минимизации среднего количества ошибок. Если есть два оптимальных алгоритма, которые имеют эквивалентное небольшое среднее количество ошибок, оба являются приемлемыми.

в принципе возможно, чтобы быть ситуацией, когда выбирая одну букву (скажем, «B») приводит к большему количеству информации, чем другое (скажем, «A»), хотя «A» происходит в более возможных словах, чем «B» делает. Я открыт для этой возможности на практике. Три алгоритма, показанные выше, предполагают, что

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

Решение

Можно вычислить оптимальную стратегию, но вычисления могут быть довольно интенсивными, и я не уверен, даст вам большую выгоду над простыми эвристиками. Я объясню, как ниже. Основная идея состоит в том, чтобы использовать динамическое программирование.

Детерминированные стратегии

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

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

Пусть $ P (G, R)= 1 $ Если можно выиграть отсюда, если начать с состояния $ (g, r) $ . Это означает, что существует стратегия для победы: где независимо от того, какое слово противник думает о (до тех пор, пока он согласуется с $ (G, R) $ ) , количество неправильных догадок, которые вы сделали до сих пор, плюс номер, который вы делаете в будущем с этой стратегией, не превышают верхний предел. В противном случае определите $ p (g, r)= 0 $ .

Теперь вы можете вычислить $ p (g, R) $ с динамическим программированием, используя отношение рецидива

$$ p (g, r)=bigvee_a \ bigwegy _ {(g ', r')} p (g ', r'), $$

Где $ a $ диапазоны во всех буквах не в $ g $ (то есть все возможности для Какое письмо догадается дальше), и $ (G ', R') $ диапазоны на всех возможных ответах, если вы угадаете $ a $ next (т.е. $ g '= g \ cup \ {a \} $ , и мы варьируемся над всеми словами $ w $ , которые согласуются с $ (g, r) $ и вычислить ответ $ r '$ догадается до угаданий $ g' $ Если слово $ W $ ) ,

В частности, я предлагаю вам вычислять $ p (g, r) $ с использованием первого поиска и метеоризования глубины. Тогда $ P (\ EPRONSET, - - \ CDOTS -) $ скажет вам, можно ли выиграть в верхнем пределе, независимо от того, какое слово противник выбирает Отказ Отслеживая вычисление назад, вы можете восстановить оптимальную стратегию.

Это осуществимо? Я ожидаю, что это. Я думаю, что количество возможных состояний $ (g, r) $ не слишком велик. (В частности, вы можете игнорировать состояния $ (G, R) $ , где вы уже сделали слишком много неверных догадок, и любое состояние, где только одно слово соответствует Это состояние автоматически выигрывает, поэтому ему не нужен дополнительный анализ.) Как оптимизация, учитывая состояние $ (G, R) $ , вы можете попробовать перечислить Все слова $ W $ , которые согласуются с ними и смоделируют некоторые фиксированные эвристики и проверьте, будет ли она победить для каждого слова; Если это так, вам не нужно делать дальнейшую первую ошибку глубины, и вы можете сразу отметьте $ p (g, r)= 1 $ . Кроме того, вам нужно только рассмотреть догадки $ a $ , которые появляются хотя бы по крайней мере, в соответствии с одним словом, который соответствует $ (G, R) $ .

Так что должно быть довольно простым, чтобы вычислить оптимальную детерминированную стратегию.

Рандомизированные стратегии

Мы можем следовать аналогичному методу для обработки рандомизированных стратегий, но он становится немного более вовлеченным. Теперь позвольте $ P (G, R) $ обозначим вероятность выигрыша отсюда, если мы используем оптимальные стратегии от здесь. Мы можем снова вычислить это, используя динамическое программирование.

Отличие ключей находится в отношении рецидивов, где мы вычисляем $ P (G, R) $ из величин $ p (g ', r') $ где $ (g ', R') $ диапазон во всех состояниях, которые могут быть

у тебя дальше после угадания еще одна буква. Здесь у нас есть простая игра из двух игроков. Сначала мы выбираем распределение вероятностей по буквам, а не в $ G $ . Тогда противник видит наше распределение и выбирает распределение на слова $ W $ , которые соответствуют $ (G, R) $ . Наша выплата (и сумма противника теряет) равна вероятности, которую мы победим отсюда, данного теми. Обратите внимание, что это может быть вычислено из $ p (g ', R') $ значения. Оказывается, поскольку мы идем первым, и противник видит наш выбор, противник не нуждается в рандомизированной стратегии; Они могут сделать одинаково хорошо с детерминированной стратегией, то есть, выбирая одно слово $ W $ на основе нашего распространения. Затем, если мы сформируем матрицу $ m $ где $ m_ {w, i} $ содержит вероятность Выберете, если мы выберем письмо $ i $ Далее и противник выбирает слово $ W $ ; Мы можем заполнить $ m_ {w, i} $ как $ p (g ', r') $ Где $ g '= g \ cup \ {i \} $ и $ R' $ Ответ на угадать $ G '$ Если слово является $ W $ . Затем мы стремимся решить проблему оптимизации $$ \ max_v \ min_w (mv) _w= - \ min_v \ max_w - (mv) _w= - \ min_v \ | -mv \ | _ \ infty. $$ Это можно решить Использование линейного программирования . Итак, мы можем вычислить $ P (G, R) $ с использованием линейного программирования из значений $ P (G ', R ') $ где $ g' $ один больше, чем $ G $ . .

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

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

Некоторые оптимизации возможны, как предложено @J_RANDOM_HACKER. Сначала вы можете вычислить $ P (G, R) $ для детерминированных стратегий; Тогда вам нужно только рассмотреть рандомизированные стратегии для государств $ (G, R) $ где $ P (G, R)= 0 $ .

Эвристические стратегии

Вы перечислили некоторые разумные эвристики для выбора стратегии. Вот еще один эвристический. Учитывая состояние $ (G, R) $ , перечисляйте все возможности для следующего угадателя $ A \ Notin G $ . Давайте сосредоточимся на одной букве $ a $ . Затем для каждого $ (g ', r') $ это может произойти в качестве следующего состояния после угадания $ A $ < / span> (поэтому $ g '= g \ Cup \ {A \} $ ), подсчитайте количество слов $ W $ Последовательный с $ (G ', R') $ ; Возьмите максимум по этим номерам и используйте это в качестве количества, связанного с $ A $ . Эвристическая стратегия состоит в том, чтобы выбрать букву $ a $ , чья счет меньше.

Вычисление ожидаемого количества ошибок

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

$$ p (g, r)=min_w \ mathbb {e} [p (g ', r')], $$

Где $ W $ диапазоны над всеми словами, соответствующими $ (G, R) $ и $ (g ', r') $ - это распределение в следующем состоянии, если слово $ W $ И следующая догадка выбора выбрана вашей стратегией. Учитывая вашу стратегию и слово $ W $ , легко вычислять распределение по догадкам и тем самым получить распределение на следующих государствах, поэтому легко вычислять <класс SPAN= «Математический контейнер»> $ \ mathbb {e} [p (g ', r')] $ .

Лицензировано под: CC-BY-SA с атрибуция

Не связан с cs.stackexchange