优化算法制胜刽子手 [英] Optimal Algorithm for Winning Hangman

问题描述

在游戏的刽子手，它是一个贪婪的信频算法相当于一个最好的机会 - - 中奖算法？

In the game Hangman, is it the case that a greedy letter-frequency algorithm is equivalent to a best-chance-of-winning algorithm?

是否有过的情况下这是值得牺牲你剩下的生命preservation，为求更好的机会猜测正确答案的？

Is there ever a case where it's worth sacrificing preservation of your remaining lives, for the sake of a better chance of guessing the correct answer?

问题的进一步澄清：

• 在所选择的字被猜测已采取从已知的字典。
• 您在指定N的生活，因而必须最大限度地猜测在字中的所有字母的可能性，而不会用N的错误的（即你可以有无限多个正确的猜测）。
• 在词典里，每个字都有相等的概率，为了这项工作（即这个词是随机选择）
  • 在一个较激烈的运动将拿出对恶意的，无所不知字选取器的策略（我不是要在这里）
  • The selected word to be guessed has been taken from a known dictionary.
  • You are given N lives, and thus have to maximise the probability of guessing all the letters in the word without making N mistakes (i.e. you may have an unlimited number of correct guesses).
  • Each word in the dictionary has equal probability, for the sake of this exercise (i.e. the word is chosen randomly)
    • a harder exercise would be to come up with a strategy against a malicious, omniscient word-chooser (I am not asking that here)

    动机：这个问题是在有趣的讨论<一个启发href="http://www.datagenetics.com/blog/april12012/index.html">http://www.datagenetics.com/blog/april12012/index.html

    Motivation: This question is inspired by the interesting discussion at http://www.datagenetics.com/blog/april12012/index.html

    他们提出的算法求解文字游戏刽子手最佳状态。

    They suggest an algorithm for solving the word game "Hangman" optimally.

    他们的策略可以概括这样（编辑澄清）：

    Their strategy can be summarised thus (edited for clarification):

    • 我们可以认为这个词是从一个特定的字典中抽取
    • 我们知道，字母在单词数量
    • 消除在字典中的所有单词没有字母的正确数量。
    • 选择发生在数量最多的字典中的其余子话的还未猜字母。
    • 如果出现这封信，我们知道它的位置。
    • 如果这封信没有出现，我们知道这不会发生在这个词。
    • 消除在字典中子集中的所有单词，不适合正是这种正确的模式，并重复。
    • 如果有2个（或以上）同样经常出现字母，该算法可以执行的位置更深入的分析，以确定哪一个是preferred（如果这是合理的？）

    在每一个阶段，大家都在猜测信（不是previously猜到了）发生人数最多的剩余可能的话。

    At each stage, we are guessing the letter (not previously guessed) which occurs in the largest number of remaining possible words.

    有一些动机喜欢这个算法 - 我们总是最小可能失去生命。

    There is some motivation to like this algorithm - we are always minimally likely to lose a life.

    不过，这让我感到这并不一定是最好的解决办法：如果我们尝试猜词（内有一定数量的生活），它不一定总是这样，最频繁出现的字母是最有用的信中剩余的可用区分词汇。

    But, it strikes me that this isn't necessarily the best solution: if we're trying to guess the word (within a certain number of lives), it's not necessarily always the case that the most frequently occurring letter is the most useful letter to distinguish between the remaining available words.

    我不知道，不过，因为它似乎时机，以避免失去生命尽可能。他会不会是因为优化策略使我们牺牲生命为更好的机会夺冠的情况？

    I'm not sure, though, as it does seem opportune to avoid losing a life wherever possible. Will it ever be the case that optimal strategy permits us to sacrifice a life for a better opportunity to win?

    问：是这样，这个贪心算法相当于一个最好的机会 - - 中奖算法，还是没有？ 你可以证明这一点？

    Question: is it the case that this greedy algorithm is equivalent to a best-chance-of-winning algorithm, or not? And can you prove it?

    这是例子词典+游戏将是理想的显示反证。

    An example dictionary+game would be ideal to show a disproof.

    推荐答案

    假定以下词典： ABC，ABD AEF EGH 。 （我会利用unguessed字母。）
    假设你只有1点生命（使得证明变得更轻松...）。

    Assume the following dictionary: ABC ABD AEF EGH. (I'll capitalize unguessed letters.)
    Assume you have only 1 life (makes the proof so much easier...).

    上面提出的算法：

    与 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

    Starting with A, you lose (1/4) or are left with aBC aBD aEF (3/4).
    Now guess B and lose (1/3) or are left with abC abD (2/3).
    Now guess C or D and you lose (1/2) or win (1/2).
    Probability to win: 3/4 * 2/3 * 1/2 = 1/4.

    现在尝试别的东西：

    与启动电子，你输了（1/2），或留下了 AEF EGH （1/2 ）。
    现在，你知道该怎么猜赢。
    概率赢得：1/2

    Starting with E, you lose (1/2) or are left with AeF eGH (1/2).
    Now you know what to guess and win.
    Probability to win: 1/2.

    显然，该算法不是最优的。

    Clearly the proposed algorithm is not optimal.

    这篇关于优化算法制胜刽子手的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！