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

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

科学



撰文|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]

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

戳这里提交新闻线索和高质量文章给我们。
相关阅读
骨懂圈的宝贝3-把古董实用了人教版教材画风引争议后,我赶紧翻开手边的数学教材... 也是惊呆了!纽约机场大乱,40%航班被取消!疏忽这1点,有人被困机场3天,有人被改签4次!俄乌战争微信朋友圈里争论方兴未艾最残暴上位史!LVMH和它背后的男人福特先生与福特汽车上热搜的数学教材,不光插画,内容能不能也改改.....机器学习时代,随机过程的数学知识还重要吗?当中年人迷上打羽毛球30岁开始护肤的我,迷上了买抗衰小样瞭望|“硅幕”背后的数字治理博弈一门备受争议却又曾风靡学术界的编程语言极度变态扭曲的小学数学教材插图背后的“那个势力”该不该被盘一下?【活动】风靡全球的飞盘游戏,波士顿留学生网给你“盘起来”啦!当年卖了几百万份的国产游戏,被玩家们送上了差评第一。学而思没做到的事,他全做到了!可汗新推的数学和逻辑,我太想和你分享,免费!Steam研究报告:95%新游戏是独立游戏,2A和3A游戏每年200款6个美国课堂的单词游戏,这样玩单词孩子根本忘不了!你当年上课偷玩的这个游戏,又成世界第一了。GDPR四周年 | 无法律边界的数据殖民时代结束了!三观碎一地!人教版数学书竟然这么辣眼睛?背后的原因太可怕!三国杀、狼人杀、剧本杀: “身份类”桌游风靡背后的时代症折磨了上百万人的游戏,有人用7分钟就给通关了?储户被“赋红码”事件追踪:许昌农商银行和它背后的神秘股东们现在的数学教材不好?以前的老教材更好?调查报告:7成俄罗斯家长允许孩子玩游戏,25%家长支持子女做游戏俄乌恩仇,这老爷子所言不虚呀!唐朝科举里的数学题,我赌你只能做1道出来!跟不上时代的老人为何说《杀手》不是潜行游戏,而是一款开放世界益智游戏?豆瓣7.7被嫌太低?比《风起陇西》更高级的,是它背后这条隐秘的顶级路线!万万没想到,有一天我会迷上白客作家王梆:没有人和人的近距离交往,你永远不知道改变世界的途径在哪|专访1天1集动画片,是我用过最简单有用的数学启蒙法(4部管够看)【活动】风靡全城的飞盘游戏,波士顿留学生网给你“盘起来”啦!
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。