胜出的Hang子手优化算法

 

在Hangman游戏中，贪婪的字母频率算法是否相当于最佳获胜算法？

为了更好地猜测正确的答案，是否曾经有过这样的情况值得牺牲你的剩余生命的保存？

进一步澄清问题：

  • 被选中的单词是从已知的词典中提取的。
  • 你被赋予了N条生命，因此必须最大化猜测单词中所有字母的概率，而不会犯N个错误（也就是说，你可能有无限数量的正确猜测）。
  • 词典中的每个词都具有相等的概率，为了这个练习（即词是随机选择的）
  • 一个更难的练习就是制定一个针对恶意的，无所不知的单词选择器的策略（我不是在这里问）

    • 动机：这个问题受到了http://www.datagenetics.com/blog/april12012/index.html上有趣的讨论的启发

    他们提出了一种算法来优化地解决文字游戏“Hang子手”。

    他们的战略可以总结如下（编辑澄清）：

  • 我们可以假设这个词是从一个特定的词典中提取的
  • 我们知道单词中的字母数量
  • 消除字典中没有正确字母数目的所有单词。
  • 选择字典中剩余子集中的最大单词数量出现的尚未猜出的字母。
  • 如果这封信发生，我们知道它的位置。
  • 如果这封信没有发生，我们知道它不会出现在这个词中。
  • 消除字典子集中所有不符合此正确模式的单词，然后重复。
  • 如果有两个（或更多）字母经常出现，则该算法可以对位置进行更深入的分析以确定哪一个是首选的（如果这是合理的）？

    • 在每个阶段，我们都在猜测发生在剩余可能字数最多的字母（以前未猜到）。

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

    但是，这让我觉得这不一定是最好的解决方案：如果我们试图猜测这个词（在一定数量的生命中），并不总是这样，最频繁出现的字母是最有用的字母区分剩余的可用单词。

    尽管如此，我不确定，因为尽可能避免失去生命似乎很合适。 是否会出现这样的情况，即最优策略允许我们为了获得更好的机会而牺牲生命？

    问题：这种贪婪算法是否等于最佳机会获胜算法？ 你能证明吗？

    一个示例字典+游戏将是理想的显示一个disproof。

    假设以下字典： ABC ABD AEF EGH 。 （我会利用未经审查的信件。）
    假设你只有一次生命（让证明变得容易得多......）。

    上面提出的算法：

    从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。

    显然，所提出的算法不是最优的。

    关于“Hang子手”的游戏，你必须做出一些关键的假设。

  • 你只需要猜一个词，或者你需要猜测一个词组？
  • 有些词比其他词更可能吗？

    • 有一点要记住的是，如果你选择一个正确的信件，你不会猜测。

    我将提供一个解决方案，用于一个字 - 同样可能的情况。 通过创建一个等于当前字典的笛卡尔乘积的新字典等，可以推广两个字的情况。比较可能的情况可以通过一些概率来推广。

    在我们定义我们的算法之前，我们定义了减少的概念。 如果我们在ONCE上猜测字母L1，L2，L3，... LN，那么我们会将字典缩小为一个较小的字典：一些字将被消除，另外一些字母也可能被删除。 例如，如果我们有字典{dog, cat, rat}并且我们猜到a ，如果猜测是真的，我们将消除{d，g}，或者如果它是假a ，我们也会消除{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]条目，那么在等概率世界中“Hang子手”游戏几乎是不可能的（除非字典受到高度限制），所以你必须在不平等 -概率世界。 在这个世界上，不是最大化你所消除的消除量，而是最大化“预期的惊喜”（也称为熵）。 每个单词都与先前的概率相关联（例如，假设该单词有'0.00001'的机会，而该单词为'hang子手'的概率为0.002）。 令人惊讶的是等于机会，以比特为单位（机会的负对数）。 一个猜测的答案将不会产生任何字母，单个字母或多个字母（很多可能性）。 从而：

  • 对于每个可能的猜测，考虑猜测会有的效果
  • 对于猜测的每个可能结果，考虑该结果的可能性。 例如，如果您猜测'A'是一个3个字母的单词，那么您必须考虑集合{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=='___') ; 如果这是无限的，没有什么可以丢失的，我们会自动选择它。

    • 所以要回答你的问题：

    >在Hangman游戏中，贪婪的字母频率算法是否相当于最佳获胜算法？

    显然不是：如果字典是 

    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的大小， 8的机会将您的字典缩小到3/8的大小，成本为1.这是更好的选择。

    编辑：我想用一个英文字典的例子（上面）来演示这不是人为的，并且假设人们可以从这个例子中推断出来，而不会被非严格的平等所挂断。 但是，这里有一个明确无误的反例：你有2000个单词。 1000个单词首先包含字母A 另外1000字包含其他地方嵌入的B的独特组合。 例如， ?B??? ， ??B?? ， ???B? ， ????B ， ?BB?? ， ?B?B? 等等? s表示随机选择的字符。 除了一个单词（其中？是'A'）之外，第一个没有A ，因此A s的频率严格大于B s的频率。 所提出的算法猜想A这将导致{50％：choices_halved，50％：choices_halved＆lose_one_life}，而该算法将决定选择B这导致{50％：YOU_WIN，50％：choices_halved＆lose_one_life}。 百分比已经被略微调整。 （不，双字母词不会对'频率'贡献两次，但即使它是在疯狂的定义下做的，也可以通过让这些词以AAA...A开头来修饰这个例子）。

    （关于评论：在这个例子中抱怨严格的平等是不合理的，例如“999/2000”，因为你可以使概率任意相近）。

    （其中指出了一个有趣的方面：​​如果字典足够大以至于不可能使hang子手变得不可能，那么一个策略应该抛弃猜测，它不能猜测，例如，如果它只剩下2个棋子，它应该做出最高概率的假设，它可以消除超过2次移动的子树，值得惊喜。）

    我写了一个脚本，可以最佳地解决hangman [github]。

    我的基本策略是这样的：

  • 对于诸如..e ..这样的模式，尝试使用字母：e，s，t
  • 检查只有n个数字的单词（在本例中为5）
  • 创建一个可能的单词列表
  • 从提供的信息创建一个正则表达式
  • 在这种情况下，它将是[^est][^est]e[^est][^est]
  • 解析匹配此正则表达式的单词的单词列表
  • 循环查看每个单词，计算每个字母出现的次数
  • 你最佳的下一个猜测是最可能的字母
    • 链接地址: http://www.djcxy.com/p/40217.html

    上一篇: Optimal Algorithm for Winning Hangman

    下一篇: How can I figure out which tiles move and merge in my implementation of 2048?