logo标签列表

赢得Hangman游戏的最佳算法

algorithmprobabilitygreedygame-theory
21
在游戏“Hangman”中，贪婪的字母频率算法是否等同于最大获胜概率的算法？
是否有情况值得为了更好猜对答案而牺牲剩余生命保值？
问题的进一步说明：
- 要猜的单词从已知的词典中获取。 - 您有N个生命，因此必须使猜测单词中的所有字母的概率最大，而不会犯N个错误（即您可以拥有无限次的正确猜测）。 - 对于本练习，词典中的每个单词具有相等的概率（即单词是随机选择的） - 针对一个恶意、全知的选词器提出一个策略将是更困难的练习（我没有在这里提出）
动机：这个问题受到了http://www.datagenetics.com/blog/april12012/index.html上有趣讨论的启发。
他们提出了一种优化解决“Hangman”文字游戏的算法。
他们的策略可以概括如下（为了澄清而编辑）：
- 我们可以假设该单词来自特定的词典 - 我们知道单词中字母的数量 - 消除所有在词典中没有正确字母数的单词。 - 选择未被猜测的字母，在剩余词典子集中出现最多的单词中。 - 如果该字母出现，则知道它的位置。 - 如果该字母未出现，则知道该字母不存在于单词中。 - 消除不完全符合正确模式的词典子集中的所有单词，并重复此步骤。 - 如果有2个或更多字母出现同样频繁，则算法可以对位置进行更深入的分析，以确定哪一个更好（如果这是合理的）。

在每个阶段，我们猜测出现在剩余可能单词中最多的字母（未曾猜测过的）。

这种算法有一些优点 - 我们始终是最不可能失去生命的。

但是，我认为这并不一定是最佳解决方案：如果我们试图猜测单词（在一定数量的生命内），并不总是最常出现的字母对于区分剩余可用单词最有用。

虽然我不确定，但似乎尽可能避免失去生命是合适的。是否会存在最佳策略可以让我们为了更好的获胜机会而牺牲一个生命？

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

最好能够提供一个字典和游戏示例来证明。

1
你所说的“最有可能获胜算法”是指什么？ - Iulius Curt
按照“Hangman”的标准规则，如果你在不失去N条生命（即猜错N个字母）的情况下完成单词，则赢得游戏。最有可能获胜的算法是一种理论算法，它可以让你在词典中获胜的最大可能百分比上获胜。 - Ronald
为了这个问题，您可以假设单词选择是随机的，而不是由全知对手选择的。 - Ronald
9个回答
11
假设以下字典: 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。
显然，上述算法不是最佳的。
这只是一个特殊字典的示例，它只有一种生命。 - knivil
1
@knivil；是的，正是所要求的：一个示例展示所提出的策略有时不是最优的。 - Reinstate Monica
没有一种方法是适用于所有情况的最佳选择。如果列表已排序，则冒泡排序优于其他排序策略。你的答案是正确和有效的，但你并没有获得任何知识。 - knivil
1
@knivil：嗯，我确实获得了一些知识，即所提出的算法并非在所有情况下都是最优的。但是很明显存在着一个最优算法（即找到最佳移动的算法）。因此，我不理解你的评论。（所有排序算法都可以将列表排序，因此从这个意义上讲，所有排序算法都是最优的。） - Reinstate Monica
是的，如果对于这个玩具示例来说不是最优的，那么继续假设它可能对英语最优的人就必须承担起证明的责任。也许是，也许不是；但在这个答案所包含的玩具证明之后，“也许”是行不通的。 - JamesTheAwesomeDude
8
你需要做出一些关键性的假设，才能玩“Hangman”游戏。
  • 你只需要猜一个单词，还是需要猜一个短语？
  • 有些单词比其他单词更有可能吗？
请记住，如果你猜对了一个字母，你不会失去机会。
我将为你提供一个解决单词等概率情况的方案。两个单词的情况可以通过创建一个新的字典，该字典等于您当前字典的笛卡尔积来推广。比其他情况更可能的情况可以通过一些概率来推广。
在定义算法之前，我们定义了一个缩减的概念。如果我们要同时猜测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)的字母...请注意，如果所有单词都有某个字母，这可能是无限的，如果是这样，请继续猜测，因为没有惩罚。
  • 进行猜测，获取更新的游戏状态
  • 消除所有因新板而失效的单词
当然，如果你的词典条目超过2^[最大猜测次数]，在等概率世界中“Hangman”游戏几乎是不可能的（除非词典受到高度限制），因此你必须在不等概率的世界中工作。在这个世界里，你不是最大化你所做的消除量，而是最大化“预期惊异”（也称为熵）。每个单词都有一个先验概率（例如，假设单词“putrescent”的概率为0.00001，“hangman”的概率为0.002）。惊异等于概率，以比特为单位衡量（概率的负对数）。猜测的答案将产生没有字母、一个字母或多个字母的回答（许多可能性）。因此：
  • 对于每个可能的猜测，考虑该猜测的影响
  • 对于猜测的每种可能结果，考虑该结果的概率。例如，如果你为一个三个字母的单词猜测“A”，你必须考虑集合{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的概率以1的代价将词典大小减小至3/8。你需要选择能够揭示最多信息的字母。在这种情况下，你应该猜测S，因为它有4/8的概率免费将词典减小至4/8，1/8的概率将词典免费减小至1/8，还有3/8的概率以1的代价将词典减小至3/8。这是更好的选择。
编辑: 我想使用一个英语词典的例子来说明这不是人工制造的，并假设人们可以从例子中推断出来，而不会卡在非严格相等上。然而，这里有一个明确的反例：你有2000个单词。1000个单词在第一个位置包含字母A。另外1000个单词包含嵌入在别处的唯一组合的B。例如，?B???, ??B??, ???B?, ????B, ?BB??, ?B?B？等。'?'代表随机选择的字符。除了一个单词（其中'?'是'A'）之外，第一个位置中没有A，因此A的频率严格大于B的频率。建议的算法会猜测A，这将导致{50%：choices_halved，50%：choices_halved & lose_one_life}的结果，而此算法将指定选择B，这将导致{50%：YOU_WIN，50%：choices_halved & lose_one_life}的结果。百分比略微近似四舍五入。(不，一个有双字母的单词不会对'频率'产生两倍的贡献，但即使在一个疯狂的定义下它真的这样做了，你也可以轻松地修改这个例子，使单词以AAA...A开头。)
(关于评论: 在这个例子中抱怨严格相等是不合理的，例如"999/2000"，因为你可以使概率彼此任意接近。)
(这指出了一个有趣的侧面注释: 如果字典足够大，有时可能无法进行hangman游戏，一种策略应该放弃它不希望能够猜到的单词。例如，如果它只剩下2个动作，它应该进行最高可能性的假设，消除了超过2个动作位的惊喜。)
1
我不认为这样做更好：1）假设单词是“cATs”（其中一个以“s”结尾的单词），并且1a）你猜测“s”，那么你就猜对了，接下来两次猜测可以是AT，将你的选择减少到{c，b，r，v}。这与1b）相同，如果你已经猜过A或T，那么显然s具有最高频率，你只剩下{c，b，r，v}的选择（在这两种情况下你都没有失去生命）。2）单词是“role”，2a）你猜测“s”然后你失去了一条生命，你应该猜测“o”或“l”，你是正确的，只剩下{m，v，r}而不是[cont] - Attila
1
2b) 猜测 A 或 T，你会失去一条生命，猜测 'o'、'l' 或 'e'，你会回到 {m,v,r}。3) 这个单词是 gATe（请参见我的先前评论）3a) 你猜测 's'，失去一条生命，猜测 o 或 l，失去 => 找到单词或2b) 猜测 A 或 T，不失去，猜测 's'，失去 -> 找到单词。在3a)中，你失去了2条生命，在3b)中，你在找到单词之前失去了1条生命。 - Attila
您目前拥有相等频率的 'A'、'T' 和 'S'，因此贪心算法不排除选择 'S'。 - Ronald
1
@ninjagecko 您的A/B计数反例是错误的。 如果A是正确的，那么我可以“免费”选择B（我知道我不会失去生命）。 如果我选择A而它是错误的-那么我除了999个选项之外都被排除了。如果我选择B并且它是正确的，那很好（和如果我选择A然后B一样）。 如果我选择B并且它是错误的-那么我排除了所有但1000个选项（比我选择A更糟）。 - Ronald
不知道原帖是否还在，但我不明白"(frac words with L#words without L + frac words without L#words with L)/(# words without L/# words total)"的意思，您能使用另一种形式来表示吗？ - KTibow
显示剩余6条评论
4

我写了一个脚本，最优地解决了hangman问题 [github]。

我的基本策略是：

  • 对于像..e..这样的模式，已尝试的字母为：e，s，t
  • 检查只有n个数字的单词（在这种情况下是5）
  • 创建可能单词的列表
    • 从提供的信息创建正则表达式
    • 在本例中，它将是[^est][^est]e[^est][^est]
    • 解析您的单词列表以匹配此正则表达式的单词
  • 循环遍历每个单词，计算每个字母出现的次数
  • 您的最佳下一步猜测是最有可能的字母
哇，喜欢那个！我在考虑建议一个“Hangman编程比赛” :) 但可能Hangman太容易解决了。 - Ronald
1
@Ronald，我本来想指责你过度思考了，但显然这个点已经过去了。我计划稍后对各种方法进行一些分析，也许最终会发现根本没有这样的词！ - fredley
1
@RonaldStewart 如果你还感兴趣：http://www.tommedley.com/372/hangman-overkill/ - fredley
2
对于您的“最有可能字母”评分功能，我会优先考虑每个字母出现的单词数量，其次是每个单词中出现的次数（作为第二排序指数）。这样，如果两个字母在相同数量的单词中出现，但一个字母在单词内重复出现的次数更多，您会更喜欢具有更多重复次数的那个字母。主要排序指数最小化了猜测错误的可能性，而次要指数最大化了可能被揭示的字母数量。 - Carl
注意: tommedly.com链接已不可用。 - Prune
显示剩余3条评论
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

注意：我们当然应该使用标准化权重，例如 频率 / 单词数 来获得准确的权重测量。
注意：这个算法可以和应该根据对手进行调整：
- 在与人类对战时，更常见的单词权重更高。 - 在与AI对战时，取决于难度级别： - 在简单级别上，瞄准常见单词。 - 在困难级别上，瞄准不寻常的单词。
你的字典很有用。我认为R比E更可能，因为它出现在同样数量的单词中（3个），如果你是对的，你可以获得关于R位置的额外信息。（如果R出现在第二个位置，你已经知道答案是FROST） - Ronald
哎呀，我忽略了那个 R :) 不过，基本的想法是你可以利用一些外部信息（语言用法）来提高选择。 - Iulius Curt
0

在可能单词池中选择最常见的字母策略可以最大化在特定回合猜测字母正确的概率。然而，这种策略并不能最大化整体获胜概率。@Reinstate Monica的答案证明了这一事实（适用于不仅仅是hangman游戏）。

例如，考虑以下两个选项：玩7局每局有90%获胜概率的游戏，或者玩1局50%的概率。起初，似乎最大化获胜概率是最优解，但是0.9⁷<0.5（因为0.9⁷=47.8%）。

尽管如此，从速度、简单性和获胜率来看，它仍然是一个非常好的算法。我为葡萄牙语（我的母语）编写了它，并且似乎可以保证在标准的5次错误或更少的情况下获得97%的获胜概率。

0

不，这个贪心算法并不是最好的，我可以通过给出更好的解决方案来证明：

每一步我们都知道字母的数量和一些字母。我们从单词集合中选择所有包含给定位置上的给定字母并且长度与所询问的单词相匹配的单词。我们从所选单词的子集中选择出现频率最高的字母并猜测该字母。对于每个猜测，猜测的字母将被标记为已猜测，它们将来不会再被猜测。这样，你比在你问题中描述的贪心算法中有更好的生存机会。

编辑：

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

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

在这种情况下，这个猜测的置信率是y/n，比任何其他字母的置信率都要高，从而增加了生存的机会。因此，这样的步骤是最优的。如果您只包含这种精神的一系列步骤，那么这些步骤的序列也将是最优的，因此该算法是最优的。
但是，如果我们有任何额外的信息（例如单词的描述或知道在短时间内两次拥有相同单词的概率），则可以根据额外的信息增强此算法，所有单词集合中的单词都将具有适应值（基于额外信息的概率），并且单词中的所有字母类型将根据适应分数进行加权。
好吧，我猜测“鉴于这个字母出现/未出现在单词中”包括在内。 - Iulius Curt
这是对第一个答案的改进，但下面的答案进一步改进了它。 - DRVic
@Ronald，在这种情况下，你的算法看起来是最优的，除非你有其他信息。 - Lajos Arpad
有证据会更好，但还是谢谢你的帮助。 - Ronald
1
证明一个算法是所有算法中最好的解决方案是困难的，因为同一个问题可能有许多可能的算法，你必须证明所有现有的算法都比你的更差或相等，同时还必须证明更好的想法是不可能的。 - Lajos Arpad
显示剩余4条评论
0

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

如果我们假设所有单词在与计算机对手玩游戏时出现的概率相等。在4个字母，6条命的情况下，如果你有查看第二个最流行字母的选项，你获胜的概率将从55.2%增加到58.2%，如果你愿意再检查一个字母，那么它将增加到59.1%。

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

使用ENABLE1（拥有172820个单词的Scrabble字典）进行完整分析，包括2到6个字母，0到10条命以及1-greedy到4-greedy的情况，得到以下结果。当然，在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%
...
-1
选择一个字母，将剩余的有效单词分成两个大小相近的集合。如果有位置信息，则可能会有超过2个集合。重复此过程，直到您的集合大小为1。这是最好的方法。证明留作练习。
1
它在每一步中尽量减少剩余单词的数量。 - knivil
1
@knivil：想象一下，你有16个词和2条命。 你的第一次猜测让你找到了8个词，第二次猜测找到了4个词，第三次猜测找到了2个词，而第四次猜测将让你获胜。然而，由于你只有2条命，在第四次猜测之前你可能已经被吊死了-实际上，你可能给自己赢得胜利的机会为0。在这种情况下，二分搜索似乎比其他选项表现要差？ - Ronald
4
不，它并不会。因为当你选择最常见的字母时，如果它恰好是匹配的，你就不会失去任何东西，所以消除多少单词都是免费的，而如果不匹配，那么你希望两组不平衡，因为你只保留较小的那一组。 - Iulius Curt
1
如果使用位置信息，那么我的第一个猜测可能会带出超过2个集合。因此，我会选择最小化所有剩余集合中最大值的字母。而16个单词的例子只是一个例子，对于n个生命和未知长度的m个单词的一般策略怎么样呢...现在清楚了，证明是不可能的：前提条件没有清晰地表述。 - knivil
3
“证明留作练习。” 当某事难以或不可能被证明时，人们常说这句话。 - Lajos Arpad
显示剩余6条评论
-1
一个关于编程的例子表明这不是最优解; 假设模式为KE??, 你已经消除了所有可能性，除了KELL, KELP, KEMB, KEMP, KEWL, 而你还剩一条命。然而，虽然L 是贪婪的选择，但它可能导致失败，而P则是必胜之选。
这并没有回答问题。一旦您拥有足够的声望，您将能够评论任何帖子；相反，提供不需要询问者澄清的答案。- 来自审核 - MD. RAKIB HASAN
在这个例子中，L实际上是最佳选择。如果P输掉60%的比赛，为什么它会被保证呢？ - ordptt
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接