获胜Hangman的优化算法

Question

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

为了更好地猜测正确的答案,有没有值得牺牲保留你的剩余生命的情况？

进一步澄清问题:

• 要猜测的所选单词取自已知字典.
• 你有N个生命,因此必须最大化猜测单词中所有字母而不犯N 错误的概率(即你可能有无限数量的正确猜测).
• 为了这个练习,词典中的每个单词具有相同的概率(即单词是随机选择的)
  • 一个更难的练习就是提出一个针对恶意的,无所不知的词选择策略(我不是在这里问)

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

他们提出了一种最佳地解决单词游戏"Hangman"的算法.

他们的策略可以这样概括(编辑以供澄清):

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

在每一个阶段,我们都在猜测最大数量的剩余可能单词中出现的字母(以前没有猜到).

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

但是,令我感到震惊的是,这不一定是最好的解决方案:如果我们试图猜测这个词(在一定数量的生命中),那么最常见的字母是最有用的字母并不一定总是这样.区分剩余的可用单词.

不过,我不确定,因为尽可能避免失去生命似乎是恰当的.最佳策略是否会让我们牺牲生命以获得更好的获胜机会？

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

一个示例字典+游戏将是理想的显示反证.

Answer 1

假设以下字典: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.

显然,所提出的算法不是最优的.

Answer 2

对于"刽子手"的游戏,你必须做出一些批判性的假设.

• 你只需要猜一个字,或者你需要猜一个短语吗？
• 有些单词比其他单词更有可能吗？

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

我将为单字 - 并且 - 同样可能的情况提供解决方案.双字案例可以通过创建一个等于当前字典的笛卡尔积的新字典等来推广.可能性比其他情况更具概率.

在我们定义算法之前,我们定义了约简的概念.如果我们在ONCE上猜测字母L1,L2,L3,...... LN,那么我们会将字典缩小为较小的字典:某些字会被删除,另外一些字母也可能被删除.例如,如果我们有字典{dog, cat, rat}并且我们猜到了a,如果猜测为真,我们将消除{d,g},或者如果它是假的则消除{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]条目,那么"Hangman"游戏在等概率世界中几乎是不可能的(除非字典受到高度约束),因此您必须在不等概率世界中工作.在这个世界中,你不是最大化你所做的消除量,而是最大化"预期的惊人"(也称为熵).您将每个单词与先前概率相关联(例如,假设该单词为'putrescent'的概率为0.00001,该单词为'hangman'的概率为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大小免费,并且3 /将你的字典缩小到3/8尺寸的成本为1的几率.这绝对是更好的.

编辑:我想使用一个英语字典示例(上图)来演示这不是人为的,并假设人们可以从示例中推断而不会挂在非严格的相等上.但是,这里有一个明确的反例:你有2000个单词.A首字母包含1000个单词.其他1000个单词包含B嵌入其他地方的独特组合.例如,?B???,??B??,???B?,????B,?BB??,?B?B?,等.?s为随机选择的字符.A第一个？中没有s,除了一个单词(其中？是'A'),因此As 的频率严格大于Bs 的频率.建议的算法会猜测A哪个会导致{50%:choices_halved,50%:choices_halved&lose_one_life},而这个算法将决定B导致{50%:YOU_WIN,50%:choices_halved&lose_one_life}的选择.百分比略有下降.(不,带有双字母的单词对'频率'没有贡献两倍,但即使它是在一个疯狂的定义下做的,你也可以通过使单词开头来简单地修改这个例子AAA...A.)

(关于评论:在这个例子中抱怨严格的平等是不合理的,例如"999/2000",因为你可以使概率任意地彼此接近.)

(这指出了一个有趣的旁注:如果字典足够大,有时候无法使刽子手变得不可能,那么策略应该抛弃那些预期无法猜测的猜测.例如,如果它只剩下2个动作,它应该做出最高概率的假设,它可以消除超过2个动作的意外消息.)