Оптимальный алгоритм для победителя

Question

В игре Hangman, действительно ли жадный буквенно-частотный алгоритм эквивалентен алгоритму наилучшего шанса на выигрыш?

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

Дальнейшее разъяснение проблемы:

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

Мотивация: Этот вопрос вдохновлен интересной дискуссией на http://www.datagenetics.com/blog/april12012/index.html

Они предлагают алгоритм оптимального решения игры в слова "Палач".

Их стратегию можно обобщить следующим образом (отредактировано для уточнения):

• Можно предположить, что слово взято из определенного словаря
• Нам известно количество букв в слове
• Исключить все слова в словаре, которые не содержат правильное количество букв.
• Выберите еще не угаданную букву, которая встречается в наибольшем количестве слов в оставшемся подмножестве словаря.
• Если это письмо встречается, мы знаем его местонахождение.
• Если эта буква не встречается, мы знаем, что она не встречается в слове.
• Удалите все слова в подмножестве словаря, которые не соответствуют точно этому правильному шаблону, и повторите.
• Если 2 (или более) буквы появляются одинаково часто, алгоритм может выполнить более глубокий анализ позиций, чтобы определить, какая из них предпочтительнее (если это разумно?)

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

Существует некоторая мотивация для того, чтобы полюбить этот алгоритм - у нас всегда есть минимальная вероятность потерять жизнь.

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

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

Вопрос: это тот случай, когда этот жадный алгоритм эквивалентен алгоритму с наилучшими шансами на выигрыш, или нет? И можете ли вы доказать это?

Пример словаря + игра идеально подойдет для опровержения.

Answer 1

Допустим, следующий словарь: ABC ABD AEF EGH. (Я буду использовать заглавные буквы.)
Предположим, у вас есть только 1 жизнь (что делает доказательство намного проще ...).

Алгоритм, предложенный выше:

Начиная с A, вы проигрываете (1/4) или оставляете с aBC aBD aEF (3/4).
Теперь угадайте B и проиграйте (1/3) или оставьте с abC abD (2/3).
Теперь угадайте C или D, и вы проиграете (1/2) или выиграете (1/2).
Вероятность выигрыша: 3/4 * 2/3 * 1/2 = 1 / 4.

Теперь попробуйте что-нибудь еще:

Начиная с E, вы проигрываете (1/2) или оставляете с AeF eGH (1/2).
Теперь вы знаете, что угадать и победить.
Вероятность выиграть: 1 / 2.

Очевидно, что предложенный алгоритм не является оптимальным.

Answer 2

Есть несколько критических предположений относительно игры «Палач».

• У вас есть только одно слово, которое вам нужно угадать, или вам нужно угадать фразу?
• Некоторые слова более вероятны, чем другие?

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

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

Прежде чем мы определим наш алгоритм, мы определим концепцию редукции. Если бы нам нужно было угадать буквы L1, L2, L3, ... LN в ОДНОМ, то мы бы сократили словарь до меньшего словаря: некоторые слова были бы исключены , и дополнительно некоторые буквы также может быть исключено. Например, если бы у нас был словарь {dog, cat, rat} и мы угадали a, мы удалили бы {d, g}, если предположение было верно, или также исключили бы {c, r, t}, если это было ложно.

Оптимальный алгоритм выглядит следующим образом:

• Рассмотрим игровое дерево
• Посмотрите на все узлы, где [#guesses left == 1]
• Если нет узла, игра невозможна; если есть узел, это ваш ответ

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

Повторите следующее на каждом шаге:

• Рассмотрим каждую букву: выберите букву, которая максимизирует ожидаемое словарное сокращение на ожидаемый штраф: то есть выберите букву L, которая максимизирует (frac words with L#words without L + frac words without L#words with L) / (# words without L / # words total) ... обратите внимание, что это может быть бесконечно, если все слова имеют определенную букву, и в этом случае продолжайте и угадывайте, так как штраф отсутствует.
• Догадайся, получи обновленное состояние доски
• Исключить все слова, недействительные новой доской

Конечно, если ваш словарь содержит более 2^[max number of guesses] записей, игра «Палач» в большинстве случаев невозможна в мире равных вероятностей (если только словарь не сильно ограничен), поэтому вы должны работать в мире неравных вероятностей. , В этом мире вместо того, чтобы максимизировать количество исключений, которые вы делаете, вы максимизируете «ожидаемый сюрприз» (также называемый энтропией). Каждое слово, которое вы связываете с предыдущей вероятностью (например, скажем, есть вероятность 0,00001 слова «гнилостный» и вероятность 0,002 слова «палач»). Неожиданность равна шансу, измеренному в битах (отрицательный логарифм шанса). Ответ на предположение не даст никаких букв, одной буквы или более одной буквы (много возможностей). Таким образом:

• Для каждого возможного предположения, рассмотрите эффект, который будет иметь предположение
• Для каждого возможного результата предположения учитывайте вероятность этого результата. Например, если вы угадали «А» для трехбуквенного слова, вам нужно будет рассмотреть каждый возможный результат в наборе {A__, _A_, __A, AA_, A_A, _AA, AAA}. Для каждого результата вычислите вероятность, используя правило Байеса , а также новые возможные словари (например, в одном случае у вас будет словарь _A_:{cAt, bAt, rAt, ...} и A__:{Art, Ark, Arm, ...} и т. Д.). Каждый из этих новых словарей также имеет отношение правдоподобия в виде size(postOutcomeDictionary dictionary)/size(preOutcomeDictionary); отрицательный логарифм этого отношения - это количество информации (в битах), которую выбор передает вам.
• Таким образом, вы хотите максимизировать соотношение ожидаемого объема информации (в битах), которую вы получаете, к ожидаемой стоимости (штраф за штраф составляет 1, если вы терпите неудачу, и 0, если вы этого не делаете). Для каждого предположения и для каждого результата предположения полученные биты информации составляют bitsGainedFromOutcome[i] = -log(size(postOutcomeDictionary)/size(preOutcomeDictionary)). Мы берем взвешенную сумму из них: sum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] ), затем делим на вероятность, что мы ошибаемся: prob(outcome=='___').
• Подбираем буквы с минимумом sum{i}( prob(outcome[i])*bitsGainedFromOutcome[i] )/prob(outcome=='___'); если это бесконечность, терять нечего, и мы автоматически выбираем ее.

---

Итак, чтобы ответить на ваш вопрос:

> В игре Палач, является ли случай, когда жадный буквенно-частотный алгоритм эквивалентен алгоритму наилучшего шанса на выигрыш?

Очевидно, нет: если словарь был

cATs
bATs
rATs
vATs
sATe
mole
vole
role

ваш алгоритм будет угадывать a или t, которые с вероятностью 5/8 уменьшают ваш словарь до 5/8 размера бесплатно, и с вероятностью 3/8 уменьшают ваш словарь до 3/8 размера для стоимость 1. Вы хотите выбрать буквы, которые раскрывают больше всего информации. В этом случае вы должны угадать S, потому что у него есть шанс 4/8 уменьшить ваш словарь до 4/8 размера бесплатно, шанс 1/8 уменьшить ваш словарь до 1/8 размера бесплатно, и 3 / 8 шанс уменьшить ваш словарь до 3/8 размера по цене 1. Это строго лучше.

edit: Я хотел использовать пример словаря английского языка (выше), чтобы продемонстрировать, как это не искусственно, и предположил, что люди могут экстраполировать этот пример, не зацикливаясь на нестрогом равенстве. Однако вот однозначно контрпример: у вас 2000 слов. 1000 слов содержат букву A на первом месте. Другие 1000 слов содержат уникальную комбинацию B s, встроенную в другом месте. Например, ?B???, ??B??, ???B?, ????B, ?BB??, ?B?B? и т. Д. ? s представляют случайно выбранные символы. В первом? Нет ни одного A с, за исключением одного слова (чье? Это 'A'), так что частота A с строго больше, чем частота B с. Предложенный алгоритм будет угадывать A, что приведет к {50%: choices_halved, 50%: choices_halved & lost_one_life}, тогда как этот алгоритм будет диктовать выбор B, что приведет к {50%: YOU_WIN, 50%: choices_halved & lose_one_life}. Проценты были округлены очень немного. (И нет, слово с двойными буквами не вносит двойной вклад в «частоту», но даже если это произошло в безумном определении, вы можете тривиально изменить этот пример, начав слова с AAA...A.)

(в отношении комментариев: в этом примере нецелесообразно жаловаться на строгое равенство, например, «999/2000», поскольку вы можете сделать вероятности произвольно близкими друг к другу.)

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

Answer 3

Я написал скрипт, который оптимально решает палач [github].

Моя основная стратегия такова:

• Для шаблона, такого как ..e .. с проверенными буквами: e, s, t
• Проверка на словатолько n цифр (в данном случае 5)
• Создать список возможных слов
  • Создать регулярное выражение из предоставленной информации
  • В этом случае это будет [^est][^est]e[^est][^est]
  • Анализ вашего списка слов на наличие слов, соответствующих этому регулярному выражению
• Перебирайте каждое слово, подсчитывая количество раз, когда каждая буква появляется
• Ваш оптимальный следующийдумаю, наиболее вероятная буква

Answer 4

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

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

Например, технические, медицинские, юридические и т. Д. Слова будут иметь гораздо меньшие шансы.

Возьмите этот словарь (с некоторыми примерами весов использования):

frost    6
guilt    5
genes    1
fever    2
meter    1

Здесь e - самая частая буква, поэтому она будет выбрана. Это означало бы оставить только медицинские термины, что очень маловероятно. Но если решение принято:

weight(letter) = w * frequency +
              (1 - w) * sum( usage_weight(word) where letter in word )

тогда, скорее всего, будет выбран t.

---

Потому что (скажем w = 0.2):

weight(e) = 0.2 * 3   +   0.8 * (1 + 2 + 1)
          = 3
weight(r) = 0.2 * 3   +   0.8 * (1 + 2 + 6)
          = 7.8
weight(t) = 0.2 * 3   +   0.8 * (1 + 5 + 6)
          = 10.2

Примечание. Конечно, мы должны использовать нормализованные веса, например frequency / num_words, для точного измерения веса.

Примечание: этот алгоритм может и должен быть адаптирован к противнику:

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

Answer 5

Выберите букву, которая делит оставшиеся действительные слова на 2 набора почти одинакового размера. С позиционной информацией может быть более 2 комплектов. Повторяйте, пока ваш набор не будет иметь размер 1. Это лучший способ. Доказательство оставлено в качестве упражнения.

Answer 6

Нет, этот жадный алгоритм не самый лучший, и я могу доказать это, предложив лучшее решение:

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

EDIT:

После того, как вопрос был уточнен и были сделаны дополнительные спецификации, я пришел к выводу, что алгоритм является оптимальным.

Если у нас есть n слов заданной длины, содержащих все правильные догадки («хорошие буквы») и не содержащих неправильных догадок («плохих букв»), x жизней, мы можем посмотреть на частоту букв в все еще возможные слова и выберите букву с наибольшей частотой, предположим, что y слов содержали букву.

В этом случае степень достоверности этого предположения равна y / n, что больше, чем степень достоверности любых других букв, что дает более высокий шанс на выживание. Так что такой шаг оптимален. Если вы выполните серию шагов, содержащих только шаги в этом духе, последовательность шагов также будет оптимальной, поэтому этот алгоритм является оптимальным.

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