19

在游戏 Hangman 中，贪心字母频率算法是否等同于最佳获胜机会算法？

为了更好地猜测正确答案，是否有值得牺牲剩余生命的保护？

进一步澄清问题：

  • 要猜测的选定单词已从已知字典中获取。
  • 你有 N 条生命，因此必须最大限度地猜测单词中的所有字母而不犯 N错误（即你可能有无限数量的正确猜测）。
  • 为了这个练习，字典中的每个单词都有相等的概率（即随机选择单词）
    • 一个更难的练习是想出一个对抗恶意的、无所不知的选词者的策略（我不是在这里问这个）

动机：这个问题的灵感来自于http://www.datagenetics.com/blog/april12012/index.html上的有趣讨论

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

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

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

在每个阶段，我们都在猜测出现在剩余可能单词中的最大数量的字母（之前没有猜到）。

喜欢这个算法有一些动机——我们总是极不可能失去生命。

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

不过，我不确定，因为尽可能避免失去生命似乎是合适的。最优策略是否会允许我们牺牲生命以获得更好的获胜机会？

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

一个示例字典+游戏将是展示反证的理想选择。

4

8 回答 8

10

假设以下字典：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。

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

于 2012-03-30T21:36:50.633 回答
8

关于什么是“刽子手”游戏，您必须做出一些关键假设。

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

要记住的一件事是，如果你选择了一个正确的字母，你就不会失去猜测。

我将为一个单词和同样可能的情况提供一个解决方案。可以通过创建一个与当前字典的笛卡尔积相等的新字典来概括两个词的情况。比其他情况更有可能的情况可以用一点概率来概括。

在我们定义我们的算法之前，我们先定义一个归约的概念。如果我们将字母 L1,L2,L3,...LN 都猜一次，那么我们会将字典缩减为更小的字典：一些单词会被淘汰，另外一些字母也可能会被淘汰。例如，如果我们有字典{dog, cat, rat}并且我们猜测a，如果猜测为真，我们将消除 {d,g}，如果猜测为假，我们将消除 {c,r,t}。

最优算法如下：

  • 考虑博弈树
  • 查看 [#guesses left == 1] 的所有节点
  • 如果没有节点，游戏是不可能的；如果有一个节点，那就是你的答案

当然，这就是您解决任何游戏的方式，并且在大多数情况下，由于指数大小的要求，它是难以处理的。除非您完美地复制这一点，否则您无法达到最佳状态，而且我严重怀疑一个不“看”两个或更多移动的策略能否希望复制这一点。但是，您可以尝试如下近似最优策略。

在每个步骤重复以下操作：

  • 考虑每个字母：选择将最大化每个预期惩罚的预期字典减少的字母：也就是说，选择将最大化 ( frac words with L#words without L+frac words without L#words with L )/( # words without L/ # words total) 的字母 L...请注意，如果所有这些都可能是无限的单词有一个特定的字母，在这种情况下继续猜测它，因为没有惩罚。
  • 猜一猜，获取更新的棋盘状态
  • 消除所有被新板作废的字

当然，如果你的字典有多个2^[max number of guesses]词条，“刽子手”游戏在等概率世界中几乎是不可能的（除非字典受到高度限制），所以你必须在不等概率世界中工作。在这个世界上，不是最大化你所做的消除量，而是最大化“预期的惊喜”（也称为熵）。您关联的每个单词都有一个先验概率（例如，假设单词“putrescent”的可能性为 0.00001，单词“hangman”的可能性为 0.002）。惊喜等于机会，以比特为单位（机会的负对数）。一个猜测的答案要么不产生字母，要么产生一个字母，要么产生一个以上的字母（许多可能性）。因此：

  • 对于每个可能的猜测，考虑猜测会产生的影响
  • 对于猜测的每个可能结果，请考虑该结果的概率。例如，如果您猜 'A' 是 3 个字母的单词，则必须考虑 set 中的每个可能结果{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

您的算法会猜测aor t，它有 5/8 的机会免费将您的字典减小到 5/8 大小，并且有 3/8 的机会将您的字典减小到 3/8 大小而成本为 1。您想选择透露最多信息的信件。在这种情况下，您应该猜到 S，因为它有 4/8 的机会免费将您的字典缩小到 4/8 大小，有 1/8 的机会免费将您的字典缩小到 1/8 大小，以及 3/ 8 机会以 1 的成本将字典缩小到 3/8 大小。这绝对更好。

编辑：我想使用一个英语词典示例（上图）来演示这不是人为的，并假设人们可以从示例中推断出来而不会被非严格相等所困扰。然而，这里有一个明确的反例：你有 2000 个单词。1000 个单词A首先包含该字母。其他 1000 个单词包含B嵌入其他地方的 s 的独特组合。例如，?B???, ??B??, ???B?, ????B, ?BB??,?B?B?等。?s 代表随机选择的字符。第一个 ?中没有As，除了一个单词（其 ? 是“A”），因此As 的频率严格大于Bs 的频率。所提出的算法会猜测A这将导致{50%：choices_halved，50%：choices_halved & lost_one_life}，而此算法将指示B导致{50%：YOU_WIN，50%：choices_halved & lost_one_life}的选择。百分比已略微四舍五入。（不，带有双字母的单词不会对“频率”产生两倍的影响，但即使它在一个疯狂的定义下确实如此，您也可以通过使单词以 . 开头来简单地修改这个示例AAA...A。）

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

（这指出了一个有趣的旁注：如果字典足够大以至于有时无法执行刽子手，那么策略应该丢弃它不希望能够猜测的猜测。例如，如果它只剩下 2 步，它应该做出尽可能高的概率假设，以消除具有超过 2 步的惊喜的子树。）

于 2012-03-30T14:30:41.943 回答
3

关于您尝试猜测单词而不是尝试猜测字母的想法，确实可能存在一些孤立的情况，您从第一次尝试就猜测单词或类似的情况，但这并不能使该算法在平均情况下更好. 这是关于预期概率的。

可以对该算法进行的一些改进（在 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以获得准确的重量测量。

注意：这个算法可以而且应该适应对手：

  • 在与人类比赛时，更常用的词会得到更高的权重
  • 与AI对战时，取决于难度级别：
    • 在简单的水平上瞄准常用词
    • 在硬水平上瞄准不寻常的单词
于 2012-03-30T13:22:29.510 回答
3

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

我的基本策略是这样的：

  • 对于诸如 ..e.. 之类的模式，带有尝试过的字母：e,s,t
  • 检查只有 n 位数的单词（在本例中为 5）
  • 创建一个可能的单词列表
    • 从提供的信息创建一个正则表达式
    • 在这种情况下，它将是[^est][^est]e[^est][^est]
    • 解析您的单词列表以查找与此正则表达式匹配的单词
  • 循环遍历每个单词，计算每个字母出现的次数
  • 您的最佳下一个猜测是最有可能的字母
于 2012-03-31T19:53:15.057 回答
0

不，这个贪心算法根本不是最好的，我可以通过提供更好的解决方案来证明这一点：

在每一步中，我们都知道字母的数量，并且我们知道一些字母。我们从一组单词中选择在给定位置具有给定字母并且它们的长度与所讨论单词的长度匹配的所有单词。我们从选定的单词子集中选择最常见的字母并猜测给定的字母。对于每一次猜测，猜测的字母将被标记为已猜测，并且将来不会再次被猜测。这样，与问题中描述的贪心算法相比，您的生存机会要大得多。

编辑：

在澄清了问题并制定了进一步的规范后，我得出的结论是该算法是最优的。

如果我们有 n 个具有给定长度的单词，包含所有正确的猜测（“好字母”）并且不包含任何错误的猜测（“坏字母”），x 存在，我们可以查看字母在仍然可能的单词中的频率并选择频率最高的字母，假设 y 个单词包含该字母。

在这种情况下，这个猜测的置信度是 y/n，它比任何其他字母的置信度都大，从而提供了更高的生存机会。因此，这样的步骤是最佳的。如果你按照这种精神制作一系列只包含步骤的步骤，那么这一系列的步骤也会是最优的，所以这个算法是最优的。

但是，如果我们有任何额外的信息（比如单词的描述，或者知道在短时间内出现两次同一个单词的概率），这个算法可以基于额外的信息来增强，集合中的所有单词of words 将具有适应度值（基于额外信息的概率），并且单词中的所有字母类型将根据适应度得分进行加权。

于 2012-03-30T12:46:04.703 回答
0

答案清楚地说明了为什么贪心算法不是最好的，但没有回答如果我们偏离贪心路径，我们能得到多少更好。

如果我们假设所有单词的可能性相同，以防您与计算机对手对战。在 4 个字母的情况下，6 个生命的情况下，如果您可以选择仅查看第二受欢迎的字母，您获胜的概率会从 55.2% 增加到 58.2%，如果您愿意再检查一个字母，则它会增加到 59.1%。

代码：https ://gist.github.com/anitasv/c9b7cedba324ec852e470c3011187dfc

使用 2 到 6 个字母、0 到 10 条生命、1-贪婪到 4-贪婪的 ENABLE1（具有 172820 个单词的拼字游戏词典）进行全面分析，得出以下结果。当然，在 25 条生命时，每个策略都相当于 100% 的胜率，所以不要超过 10 条生命。超过 4-greedy 只是略微提高了概率。

letters, lives, 1-greedy, 2-greedy, 3-greedy, 4-greedy


2 letters 0 lives   3.1%    3.1%    3.1%    3.1%
2 letters 1 lives   7.2%    7.2%    7.2%    8.3%
2 letters 2 lives   13.5%   13.5%   13.5%   14.5%
2 letters 3 lives   21.8%   21.8%   22.9%   22.9%
2 letters 4 lives   32.2%   33.3%   33.3%   33.3%
2 letters 5 lives   45.8%   45.8%   45.8%   45.8%
2 letters 6 lives   57.2%   57.2%   57.2%   57.2%
2 letters 7 lives   67.7%   67.7%   67.7%   67.7%
2 letters 8 lives   76%     76%     76%     76%
2 letters 9 lives   84.3%   84.3%   84.3%   84.3%
2 letters 10 lives  90.6%   91.6%   91.6%   91.6%


3 letters 0 lives   0.9%    1.1%    1.1%    1.1%
3 letters 1 lives   3.4%    3.8%    3.9%    3.9%
3 letters 2 lives   7.6%    8.4%    8.6%    8.8%
3 letters 3 lives   13.7%   15%     15.1%   15.2%
3 letters 4 lives   21.6%   22.8%   23.3%   23.5%
3 letters 5 lives   30.3%   32.3%   32.8%   32.8%
3 letters 6 lives   40.5%   42%     42.3%   42.5%
3 letters 7 lives   50.2%   51.4%   51.8%   51.9%
3 letters 8 lives   59.6%   60.9%   61.1%   61.3%
3 letters 9 lives   68.7%   69.8%   70.4%   70.5%
3 letters 10 lives  77%     78.3%   78.9%   79.2%


4 letters 0 lives   0.8%    1%      1.1%    1.1%
4 letters 1 lives   3.7%    4.3%    4.4%    4.5%
4 letters 2 lives   9.1%    10.2%   10.6%   10.7%
4 letters 3 lives   18%     19.4%   20.1%   20.3%
4 letters 4 lives   29.6%   31.3%   32.1%   32.3%
4 letters 5 lives   42.2%   44.8%   45.6%   45.7%
4 letters 6 lives   55.2%   58.2%   59.1%   59.2%
4 letters 7 lives   68%     70.4%   71.1%   71.2%
4 letters 8 lives   78%     80.2%   81%     81.1%
4 letters 9 lives   85.9%   87.8%   88.4%   88.7%
4 letters 10 lives  92.1%   93.3%   93.8%   93.9%


5 letters 0 lives   1.5%    1.8%    1.9%    1.9%
5 letters 1 lives   6.1%    7.5%    7.9%    8%
5 letters 2 lives   15.9%   18.3%   18.9%   19.2%
5 letters 3 lives   30.1%   34.1%   34.8%   34.9%
5 letters 4 lives   47.7%   51.5%   52.3%   52.5%
5 letters 5 lives   64.3%   67.4%   68.3%   68.5%
5 letters 6 lives   77.6%   80.2%   80.6%   80.8%
5 letters 7 lives   86.9%   88.6%   89.2%   89.4%
5 letters 8 lives   92.8%   94.1%   94.4%   94.5%
5 letters 9 lives   96.4%   97.1%   97.3%   97.3%
5 letters 10 lives  98.2%   98.6%   98.8%   98.8%


6 letters 0 lives   3.2%    3.7%    3.9%    3.9%
6 letters 1 lives   12.6%   14.3%   14.9%   15%
6 letters 2 lives   29.2%   32.2%   32.8%   33%
6 letters 3 lives   50.1%   53.4%   54.2%   54.4%
6 letters 4 lives   69.2%   72.4%   73.1%   73.2%
6 letters 5 lives   83.1%   85.5%   85.9%   86.1%
6 letters 6 lives   91.5%   92.9%   93.2%   93.2%
6 letters 7 lives   95.8%   96.5%   96.7%   96.8%
6 letters 8 lives   97.9%   98.3%   98.4%   98.5%
...
于 2020-01-03T12:26:18.540 回答
0

证明这不是最佳的英语示例；假设模式是 KE??，你已经排除了除了KELL、KELP、KEMB、KEMP、KEWL之外的所有可能性，你只剩下一条生命。那么尽管L是贪婪的选择，但它可能会导致失败，而P是保证获胜。

于 2022-01-01T21:40:04.897 回答
-1

选择一个字母，将剩余的有效单词分成两组几乎相等的大小。位置信息可能超过 2 组。重复直到你的集合大小为 1。这是最好的方法。证明留作练习。

于 2012-03-30T12:55:22.760 回答