Оптимальный алгоритм для выигрыша "Виселица"

В игре «Виселица» жадный алгоритм частоты букв эквивалентен алгоритму с наибольшей вероятностью выигрыша?

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

Дальнейшее уточнение задачи:

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

Мотивация: Этот вопрос навеян интересным обсуждением на http:/ /www.datagenetics.com/blog/april12012/index.html

Они предлагают алгоритм оптимального решения игры в слова «Виселица».

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

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

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

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

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

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

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

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