风靡世界的猜词游戏，有人迷上了它背后的数学

2022-05-05 10:05

撰文｜antares

编辑｜马修

前段时间，以黄绿色块矩阵图为交互界面的猜词游戏Wordle风靡社交网络，随后又诞生了各种变体游戏，比如中文成语变种、英语四词变种。如今风潮退去，让我们一起来看看“留在沙滩上的贝壳”。

Wordle游戏的规则非常简单，它要求玩家在6次之内猜出一个由5个字母组成的单词。每次输入单词时，如果输入的字母在目标单词中，但是位置不对，那么格子会显示成黄色；如果输入的字母在目标单词中，且位置正确，那么格子会显示成绿色；如果都不对，则会显示成灰色。玩家需要根据每次猜词后的反馈来调整自己的猜词策略，最终猜出单词。

虽然玩Wordle的大多数人都是自己乖乖猜词，但心思活络的人很自然就会想到：有没有可能借助计算机，弄出一个神奇的算法帮自己猜词呢？

玩Wordle时，一般人会先使用一两个固定的词打底，然后再猜符合之前提示的词，不断缩小范围直到猜出正确答案。通常情况下，这种思路行得通。但是，如果你遇到过下图中的情况，就会发现这种单纯的策略并不合适。

下图这种局面，在第4次猜测的时候，不能像图中这样，更换首字母来猜测，而是应该把所有可能的首字母列出来，找一两个词涵盖最多的首字母可能性，然后根据反馈尽可能多地排除掉不可能的首字母，确认出首字母后，才能保证第6次有可能猜中。

一次开局惊艳、结果失败的Wordle游戏

我们需要更高级的策略。在讨论算法之前，我们先来看一下手头可以使用的素材。

Wordle所使用的单词表，可以在它的json代码里直接看到。单词表有两个，一个是从游戏上线第1天开始之后的2000多天，全部正确答案的列表；另一个，是这些正确答案以外可以合法猜测的单词列表，共10000多个。

两个词表加起来的12972个单词，正好就是CSW19（Collins Scrabble Words，2019）中所有的五字母单词。“Collins Scrabble Words”是英语国家中Scrabble锦标赛（猜词比赛）普遍使用的词表，在英文的单词类游戏里相当权威。当然，在我们讨论Wordle猜词策略的时候，是不能使用正确答案列表的，否则就可以根据日期直接翻出答案了。以下的讨论，都应当基于我们手上只有CSW19词表的假设来进行。

有了词表之后，初等的想法就是根据字母频率来选择单词。字母在词表里出现的次数越多，确定或排除之后就越好缩小范围。如果你在网上搜索一下，绝大多数讲Wordle猜词策略的文章，都是按照这个思路推荐的。所以，元音或常见字母多的adieu或是aisle就是很好的第一猜测。当然，这个算法相当简陋，但不需要电脑就可以做。

接下来，让我们用数学化一点的思维，继续对这个想法进行分析。

从直觉上讲，猜一个词之后，颜色的提示根据黄绿灰3种颜色的不同，会有3^5=243种可能的组合。那么剩余的词表，也会按照上一个词的颜色提示拆成243个更小的词表。要是这些拆分后的小词表里，有一个包含的单词数量特别大，万一正确答案就在这个词表里，那么接下来就会很难猜。反之，拆分得越均匀，就说明不管正确答案在哪个词表里，都会相对好猜，这个第一次猜测的词也就越有效。

那么，怎样算是“拆分得均匀”呢？数学上的做法是使用信息熵，其定义是：每个事件发生概率的对数的期望值，单位为比特。信息熵满足可加性，对一个猜测来说，“出现243种反馈的哪一种”这一随机事件的信息熵越大，“正解位于剩余词表中哪一个”的期望信息熵越小。而当信息熵等于0的时候，就表明词表只剩下一个词，答案可以完全确定了。因此，每一步都应当寻找让“出现243种反馈的哪一种”这一随机事件的信息熵最大的猜测词。这一算法的细节，可以参考3blue1brown关于wordle的视频，他以这套思路为算法策略，模拟出的平均猜测次数是4.124。

但是，这个策略是不是最优的呢？事实上，它所考虑的仅仅是每一步的局部最优策略，而局部最优的组合不一定是整体最优——就如同磨刀不误砍柴工的道理。它甚至不能先验地回答这样的问题：该策略能否保证在6次之内猜出任何Wordle的答案？滑铁卢大学的前研究助理教授Laurent Poirrier在他的博客（blog）上对此进行了一系列的讨论。我们下面展开讲讲。

嗯？稍等一下。什么叫“保证在6次之内猜出任何答案”？

我们可以先设想一下如何描述一个“解Wordle的策略”。如果有人声称自己有Wordle的必胜法，该怎么要求他证明？

甲：我有一套Wordle的必胜法。

乙：那你把每一步该猜什么词写下来吧。

甲：但根据反馈不同，每步猜的词也不同啊。

乙：第一个词总是要在什么信息都没有的情况下猜的，你把第一个词写下来吧。

甲：好，我写了。

乙：第一个词输入以后有243种可能的反馈。对于每种可能的反馈，你的第二个词分别是什么，写下来吧。

甲：好，我写。啊，不过有些反馈（比如绿绿绿绿绿）这个游戏就结束了，还有些反馈（比如第一个词猜apple，反馈是绿绿绿绿黑）根本没词可以满足，那些就不写了。

乙：没问题。在每种可能性下你猜完了第二个词，然后你又有243种可能的反馈，对于每种反馈，你第三个词会猜什么？

如此类推。对图论熟悉的读者立刻可以看出来，这样写下来的词会构成一个图论里叫做树的结构，也就是所谓“决策树”。每一个“猜测”都相当于是沿着决策树往下走一层，这会缩小可能的词表，直到可能词表只剩下一个为止。

决策树原本是一个运筹学分类算法里的概念，用来描述决策的流程，在机器学习中它则是分类算法的一种模型。在Wordle猜词游戏这个场景里，我们的目的，是通过确定每个节点所猜的词，来构造一个“深度”尽可能少的决策树。

Wordle决策树图源：https://www.poirrier.ca/notes/wordle/#decision-trees

可以看出来，决策树的最大层数（“深度”）表明了最差情况下的猜测次数。倘若存在一个深度5的决策树，就说明按照这套策略，在6次猜测之内（第1次猜测叫做深度0）一定可以猜中答案。同时，对于任何答案，也都可以“按图索骥”地计算出，这个答案需要几次可以被猜中。倘若需要求算“平均次数”是多少，也可以用这种方法算出来。

如何确定这种决策树存在或是证明其不存在呢？当然是靠试错和枚举。

具体说来，第一层有一个词，这个词有12972种可能性。第一个词确定之后，第二层的词有最多243个词表，每一个词表又有12971种可能性……如果枚举完前5层所有可能的情况，就能找到一棵完整的树，那就说明一定有一个可行策略可以保证6次内猜中，如果没有，那就说明6次不够。

当然，5层的决策树，每层243个分支的话，最多会有243^5条分支，再考虑到每个分支下所猜测的词最多有12972种可能性，计算量就会爆表了。不过，在适当的“剪枝”和调整试错优先级的做法之下，所需要的时间可以大幅减少。

直觉上，我们会认为，倘若一个猜测能在最差的反馈下尽量减少可能词表的大小，那这个猜测就会更有效率。滑铁卢大学的Laurent Poirrier采用了243种情况下剩余词表的平方和作为这个衡量标准，平方和越小的选项就越会优先枚举。

按照这一策略，Laurent Poirrier成功花了50个CPU小时的时间找到了一个5层的决策树，第一个词是spaer。也就是说，Wordle确实可以保证在6次之内猜中（12972个词中的）所有可能的答案。进一步的分析，帮助Laurent Poirrier找到了平均（假设词表中所有单词以同样概率为正解）猜测次数意义下的最优算法，平均猜测是4.07771次，最多6次猜中。

之后，Laurent Poirrier试图用同样的方法，寻找4层的决策树或证明其不存在，也就是说想看看5次猜测能否保证猜对。结果，他把自己在亚马逊云上的计算时长烧空了也没算出来。

在寻找可行的解法时，只要找到一个正解算法就可以停了——例如，在寻找6次保证能猜中的算法时，他将搜索空间分成了10组同时进行，编号为9的那组的第一个词就是发现有一个可行解的spaer，之后的词也就不用试了。反之，如果烧了非常多的计算时长也没有找到，就说明枚举了非常多的决策树，但没有一个可行的。换句话说，5次保证猜对的算法很可能不存在——当然了，这并不是一个严谨的证明。

那么有没有什么办法，可以不需要枚举所有可能性就证明这种算法不存在呢？山重水复疑无路，柳暗花明又一村。没过两天，就有名叫Alex Peattie的另一个人，换了个角度进行尝试。他在自己的Blog上简洁而灵巧地证明了5次猜测是不够的。

这套证明的核心是基于这样一点：找词表中有19个结尾是ills，只有首字母不同的单词：

bills, cills, dills, fills, gills, hills, jills, kills, lills, mills,

nills, pills, rills, sills, tills, vills, wills, yills, zills

换言之，几乎所有的辅音字母都可以配上-ills形成一个英语单词。问题在于，即使预先就告诉你正确答案在这19个词当中，5次猜测仍然不够用。

事实上，想要保证在第5次猜中的话，前4次的猜测就必须包含19个可能首字母中的18个，根据简单分析，每个单词只有5个字母，4个单词20个字母，这样减去18，只有2个字母的余地，那么我们可以知道，至少有两个词要完全由这19个首字母之中的五个组成，并且还不能有相同字母。

由于这19个首字母中并不包含“a e i o u”五个元音字母，y也只能用一次，因此，只有两组词符合这些条件。

另人非常意外的是，竟然真的有两组存在——谁能想到竟然真的有crwth这种单词呢？确定之后，再去遍历尝试，能否用两次猜测排除掉剩余9个字母中的8个，答案是不行，因此就可以证明5次猜测不能保证猜中正确答案。

关于Wordle还有一些其他的进阶讨论。例如，倘若已知正解在那个2000多的词表里，则是最多5次猜中。在困难模式下，也就是每次猜的词，必须符合此前的所有提示的模式下，则需要7次才能保证猜中，平均需要4.52629次。对于词表甚至字母表都不同的变体（比如中文成语版本），找出多少步能保证猜中则是一个NP问题（Non-deterministic Polynomial，即多项式复杂程度的非确定性问题）。

游戏快乐，烧脑快乐。

参考文献：

【1】https://www.poirrier.ca/notes/wordle-optimal/#computational-complexity

【2】https://alexpeattie.com/blog/establishing-minimum-guesses-wordle/

制版｜小圭月

欢迎关注我们，投稿、授权等请联系

[email protected]

微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。

来源: qq

点击查看作者最近其他文章