风靡世界的猜词游戏,有人迷上了它背后的数学-资讯-知识分子

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

2022/05/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/

制版|小圭月
欢迎关注我们,投稿、授权等请联系

saixiansheng@zhishifenzi.com


参与讨论
0 条评论
评论
暂无评论内容
《赛先生》微信公众号创刊于2014年7月,创始人为饶毅、鲁白、谢宇三位学者,成为国内首个由知名科学家创办并担任主编的科学传播新媒体平台,共同致力于让科学文化在中国本土扎根。
订阅Newsletter

我们会定期将电子期刊发送到您的邮箱

GO