本帖最后由 dannie 于 2023-7-7 10:27 编辑
一个六岁孩子关于猜单词的简单问题变成了另一种分析的痴迷，使我最近玩了1500万场猜单词游戏。
早在 2007 年，我在从牛津到伦敦的火车上为一个人类猜测者写了一个猜单词游戏。我在伦敦地铁上花时间思考玩这个游戏的最佳策略，并在回程时为做猜词的计算机写了这个版本。它成功地猜出了我的测试词，我很满意，所以我把这两个版本提交给了 Wolfram 演示项目。三年后的今天，我的女儿已经长大了，可以玩了，但演示让她很恼火，因为它总是能猜到她的词。她问了一个显而易见的问题，当时我从来没有想过。"我能选择最难的词是什么，这样我就可以打败它？"
如果您不知道，猜单词的想法是，一个玩家想到一个词，并告诉另一个玩家它有多少个字母。第二位玩家反复猜测字母。如果猜中的字母在单词中，选词者必须说出该字母在单词中每一次出现的位置。如果不能，那么选词者就会很高兴地画出一个绞架的组件，上面挂着一个人。如果在单词被完全猜中之前，绞架和人就已经完成了，那么第二个玩家就输了。绞架和人的设计有很多种；我在上面这个有 13 个元素的绞架上学过，但我见过 10 到 13 之间的很多可能性，可能还有其他的。我把这些称为10局和13局。我的设计，即13局，对猜测者来说比较容易，因为他或她在输之前可以犯更多的错误。
为什么是刽子手？我不知道。据称，这个游戏可以追溯到维多利亚时代的英国，当时绞刑可能是对拼写不良的一种可接受的惩罚!
以下是我是如何创建这些游戏的。首先，让我描述一下我们正在攻击的算法。我的猜单词算法使用所有可用的信息来产生一个候选词的列表。起初，可用的信息只是单词的长度，但后来我们会知道一些字母和它们的位置，还有一些不在单词中的字母。所有这三点信息都可以很快地减少字典。接下来，游戏会对所有候选词中的字母进行频率分析（有多少候选词中至少包含一个 "a"，至少包含一个 "b"，以此类推）。我们避免猜错的最好机会（如果我们假设这个词是从字典中随机选择的）是选择一个经常出现的字母。
在这一点上，值得介绍一下博弈论中的纳什均衡（Nash equilibrium）。这是指当发现对立的策略时，即使对手的策略是已知的，任何一方都不能单方面改善他或她的结果。部分考虑到这一点，该算法并不选择最受欢迎的字母，而是根据频率加权选择任何一个可能的字母（例如，如果 1000 个候选词包含 "e"，13个包含 "x"，那么 "e "将以 1000：13 的比例被选中，而不是 "x"）。这是走向纳什均衡点的第一次迭代；没有它，我们的算法就完全是决定性的，因此，任何击败它的词都会每次都击败它。对手会通过每次都选择那个词来优化他或她的策略。该算法还使游戏更加有趣。我女儿的问题可以被认为是朝着纳什均衡的下一次迭代。知道了猜测者的算法，我们被要求优化如何从字典中选择单词的权重，而不是我所假设的同等权重。
(说点题外话：几年前在伦敦举行的第五届国际数学研讨会上，我有幸聆听了 John Nash- 纳什均衡的发明者，诺贝尔奖获得者，以及电影《美丽心灵》的主角，讲述了他对 Mathematica 的使用。每年的诺贝尔奖名单中通常至少有一位 Mathematica 用户，尽管遗憾的是，诺贝尔奖得主很少出现在好莱坞电影中)。
从概念上讲，回答我女儿的问题最简单的方法是对每一个可能的词进行粗暴的蒙特卡洛分析。我所做的第一件事是重构演示中的代码，使其更快。在我的演示中，筛选 90,000 个单词的字典并进行频率分析大约需要 0.2 秒--在互动游戏中是瞬时的。但是模拟整个游戏可能需要多达 26 个这样的选择，由于我想模拟 1500 万个游戏，我花了几分钟时间使用 Wolfram Workbench 中的 Profiler 来了解时间的去向，结果得到了一个快 10 倍的版本。如果要重复或改进我的分析,此实施位于帖子的底部。
然后我用 gridMathematica 并行运行了它。如果我能够使用 Wolfram-Alpha 的硬件，我将在几分钟内完成，但我只有几台闲置的办公电脑，所以我让它在周末运行。
我为字典中的每个词做了 50 个游戏的初始运行。足够收敛到真实结果的10% 以内，也足够做一个粗略的排序。然后我对更有希望的词进行了进一步的试验，在 1000 个最佳词的名单上共进行了 3000 场游戏。这足以让我对它们的排序有相当的把握。
为了使其他人不必消耗 CPU 周期，我在这里包括了 50MB 的生成数据。
现在我们有了这些数据，我们就可以开始分析了：
以下是我对 "困难 "一词得到的结果：
数据显示了 50 场比赛中每场的猜错次数。我们可以看到，"difficult"这个词并不难，平均需要 3.3 次错误的猜测--这还不足以让我的设计中开始画人。在50场比赛中，该算法从未在10场比赛中失败过，甚至在 13 场比赛中接近失败。尽管如果它下的是 8 局棋，它就会输一次。
让我们来看看算法在从字典中随机选择的一个词上的整体表现（最初的假设）。我们不能看平均失误率，因为一个猜错13个的游戏和一个猜错 20 个 的游戏同样是一个失败者。我们关心的是胜率，而这些胜率取决于游戏的大小。
例如，如果我们在 13 场比赛中选择 "猫"，那么我们将有 23% 的时间击败算法。
在 10 场比赛中，我们有 50% 的时间会击败它。
事实证明，对于 13 场比赛来说，我们只有 1% 的时间会击败随机选择的单词的算法。我明白为什么我的女儿会感到沮丧了。
10 局比赛上升到 5%：
如果算法根本没有使用频率分析，那么13局的胜率将是 10%，10 局的胜率将是 25%（在实验的第一次运行中，一个粗心的编码错误告诉了我）。
下面是游戏结果的分布。有一半的时间它的猜测是 4 个或更少的错误。
长单词和短单词哪个更好？当我和女儿玩的时候，我用的是短词，因为我以为短词更容易（对她来说当然更容易拼写），但我惊讶地发现，短词的平均错误率最高。原因似乎很简单，字母的变化越大，人就越不可能错过它们。在极端情况下，一个有 14 个不同字母的单词不可能在13局中获胜。只有 12个错误的字母。
因此，如果我们只记住一条规则，那就是使用 3 个字母的词。而绞架 (gallows) 的设计作品越多，情况就越是如此。
但我们感兴趣的是非常好的词，所以这里是每个词长中最好的词的得分：
通过仔细的选择，每个词的长度中最好的词都是比较平均的。
而且有趣的是，如果我们按胜率对这些词进行分类，最好的词比排名靠后几位的词有明显的优势。这里的每一行都是不同的游戏大小，从 9 到 13。排名靠后的单词的粗糙度是由于模拟数据不足，而不是算法中的真实现象。
好了，关于趋势就不多说了，下面是最好的词：
如您所料，像 "x "和 "z "这样的低频字母是一个很大的因素，但字母重复也是有用的，因为它们使较长的单词具有与较短的单词相似的不同字母数量。
因此，我们有了它。在所有游戏规模中，"jazz"赢得最多。尽管我们可以看到游戏大小的奇特差异。随着游戏大小的增加，"Jazzed "的表现逐渐变差，但 "faffed "的表现逐渐变好。了解这一点是另一个项目!
我们现在可以改进我们的选词算法。我们不应该随机选择一个词，而应该将我们的选择权重放在具有高胜率的词上。
当然，这只是朝着纳什均衡点又走了一步。如果猜测者更新算法以考虑到该策略，我们将不得不重复这整个实验，以获得一个更好的策略。最终，这两种算法很可能会收敛在一个点上，即每个词都有相同的胜率，而我们将知道最佳的游戏结果。
我怀疑这 13 局游戏基本上是可以解决的。有足够多的词是很容易猜到的，在这些词上冒更大的风险，去测试更难的词，会使猜测算法从 99% 的成功率提高到 100%。在这一点上，我们处于平衡状态--用 WOPR 的话说，"一个奇怪的游戏。唯一的胜利之举就是不玩。《战争游戏》的提法特别相关，因为纳什均衡被用作冷战时期相互确保破坏的核战略的理论基础，而影片的高潮基本上是这种模拟--增加了计算机的自我意识）。
对于 10 局，我只学到了足够的知识，看到最终的算法可能相当复杂，而且在这个简单的游戏中，有比我预期更丰富的内容。
如果您更想获得乐趣，那就从长词中挑选最好的。这里有一个表格，列出了10局中每个长度的最佳单词。它们的表现不如 3-5 个字母的单词好，但在娱乐方面，您无法击败 "powwowing"、"bowwowing "和 "huzzahing"!
这都是基于 Mathematica 内置的 90,000 词英语词典。对于更大的字典或其他语言，结果可能会有很大不同。
购买软件/免费试用
【13.2.1中英文 Wolfram 软件】请评论区留言申请
发表于 2023-7-7 10:25