爆红的填词游戏「Wordle」的最优解

Wordle是前段时间在国外一个非常火的猜词游戏，玩家一共有六次机会来猜测一个由五个字母组成的单词。每进行一次猜词，都会根据猜测的单词和正确答案的匹配程度给予一些提示。对于每一个字母可能出现的提示有三种：灰色、黄色、绿色。灰色表示当前这个字母没有出现在最终答案之中；黄色表示当前字母出现在最终答案之中但是位置不对；绿色则表示当前字母出现在最终答案之中同时位置也是正确的。例如：最终答案是「snail」，猜测单词「sneak』，那么因为 s 和 n 都和答案的字母且位置相同，那么就会变成绿色，a 出现在答案之中，但是位置不正确就会呈现黄色，e 和 k 因为没有出现在答案中就会变成灰色。Wordle 游戏就是通过一次次的猜测后利用提示来缩小范围从而找到最终的答案。

其实这是一个再普通不过的猜词游戏了，能够让它爆火的第一个原因是因为游戏能够让你在成功猜出单词之后分享你的猜词图案，也就是上文所提到的每一次猜词的提示图案。第二个原因是游戏每天只能进行一次且全世界的人都猜同一个单词。成功猜出单词的人在社交媒体上分享自己的骄傲战绩，没有猜出的人会在下面询问正确答案，这就是分享给这个游戏带来社交属性。其实这和很多年前的微信上的「打飞机」小游戏是一样的，都是一个简单的小游戏加上了健康的社交属性就会让人疯狂。

相关阅读：

可能是学习编程时间久了的通病，我也在玩了几次Wordle之后就开始思考这个游戏有没有一个最优的算法，但是碍于自身的水平我也没有做太深入的研究。直到我在YouTube上看到3Blue1Brown关于Wordle的最优解的视频，在反复观看四五遍理解了所有的原理之后，也希望能给读者讲清楚是如何得到这个最优算法。

通过查看wordle的源码，得知了游戏一共提供了12972个单词作为可输入的单词，同时也查看到可能的正确答案是2315个，但是因为这个信息是查看到源码才得知，所以在进行算法设计的时候还是默认不知道这2315个单词，认为所有的12972个单词都有可能成为最终的正确答案。

算法要寻求的最优解其实是寻找一个最好的单词输入顺序，能够最快地筛选出正确答案。如何判断一个单词的好坏？简单来说如果单词能够帮助排除越多的可能性，也就说明这个单词越好。这只能说是大概的思路，为了找到最优的单词还是需要做到量化。

对于每一个单词，都对应可能有12972个正确答案，同时每一个单词一共会有三的五次方个可能会出现的图案(每一个字母栏位有三种可能性：灰色、黄色、绿色，一共有五个栏位)。

每一种图案对应了一个可能的正确答案单词表，那么这些可能出现的正确答案单词表所包含的单词个数除以单词总数就是每一种图案在当前输入单词下可能会出现的概率。

每一种图案出现的概率再乘以它给予的一个判断的好坏标准再求和就是一个单词的量化的好坏评分。这个判断标准就是当前这个单词能够带来的信息熵。

为了能够解释清楚，这里通过一个例子来简单解释下信息理论中「信息熵」以及「信息内容」两个概念。假设一个篮子里放有64个小球，甲乙两人进行猜球游戏，甲被事先告知64个小球中的一个，然后通过告诉乙信息来让乙能尽快找出目标小球。如果甲说：”目标球在篮子的左边部分“，那么这个信息帮助乙筛选掉了一半(32/64)的小球；如果甲说：”目标小球是左上角的那一个“，那么这个信息帮助乙筛选了63个小球。第二个信息帮助乙锁定到了64个球中的那一个球，根据「信息内容」公式得出这个信息的信息内容有6bit。其实也就是表示这个信息需要有6bit(2的6次方等于64)才能够存下来，因为需要找到64分之1的小球。同理第一个信息只帮助确定了所有小球一半，那么这个信息只包含1bit的信息内容。

每一个可能出现的图案的概率来乘以这个图案所传达的信息内容得到一个单词能带来的期望信息内容也就是信息熵，信息熵越高也就说明这个单词在各种情况下带来的信息内容越高。

有了判断单词的好坏标准，算法只需要算出12972个单词的信息熵，然后选择出信息熵最高的单词便可以作为起始单词了，在每一次输入之后，只需要根据游戏给出的提示再进行同样的步骤就可以让每一次输入都能够最大化信息熵。

那么这就是最优的算法了吗？答案是否定的，因为在每次输入单词之后，从可选列表里面选择最高信息熵的单词，但是却忽略了单词是否是常用的单词，可能有的单词的信息熵很高，但是单词本身不太可能成为最终的正确答案，或者当两个单词的信息熵是一样的时候，算法不能去选择更可能成为答案的那一个单词，而只能按照字母的排序顺序来选择。

为了能够让算法考虑到单词的常用性，算法需要考虑单词的词频，虽然有的单词都是比较常见的单词，但是因为出现的频次还是差别比较大，如果单纯依靠词频会让这两个单词的概率差1000倍，所以选择通过 sigmoid function 来让可能会成为答案的单词的概率接近1或者让不太常用的单词概率接近0。

在之后的算法中做出选择的时候就需要考虑单词的频率带来的可能性。每个单词还是和之前一样有一个信息熵，同时还有一个通过频次得到的可能成为正确答案的概率。算法的目的是为了能提升最后的成绩，也就是提升期望成绩。假设我们经过了三次输入之后，通过算法计算出了「words」可能成为最终的正确答案：「words」的信息熵是1.27 ，频次概率是0.58，这时算法需要去计算这个单词输入进去之后的期望成绩，频次概率告诉有58%的概率这个单词可能成为正确答案，也就是能在第四次成功，剩下的42%的概率会让最终结果至少在4次以上，也就是4加上一个可能的期望次数。

这个期望次数的计算需要根据当前单词能提供的信息以及当前游戏还剩下的信息进行综合判断。如果当前游戏还需要很大的信息量，也就是说还有很多的可能性，但是单词提供的信息不够多，那么这个期望次数会比较高，但是如果当前信息量和单词提供的信息量差不多，那么这个期望次数会很低。也就是游戏需要的信息和单词提供的信息之间的差和期望次数之间存在一个函数。这个函数通过模拟进行游戏后得到的数据建模得到，也就是看当信息差在多少的时候还需要进行多少次猜测。假设当前游戏还剩余的信息内容是1.44bit那么输入这个单词的最终的期望次数入下：

至此算法通过计算单词的信息熵和词频概率能够选择出最优的单词 「SALET」 来进行游戏。有人说做这个算法是毁了这个游戏，但是都看这了，你还觉得这是在讨论游戏吗？忘记最好的开始单词是什么，体验怎么去寻找信息内容，寻找信息熵，设计一个贪婪算法的过程才是这篇文章的意义所在，始于游戏，终于学习。（想要去体验这个算法的可以点击下方的Wordle Solver来体验）

相关阅读：