梦晨 发自 凹非寺
免费猜字小游戏Wordle正在席卷全球，火到以数百万美元的价格被收购，全球玩家数量也突破了200万。
比如，1月31日的题目在当天30多万份晒出战绩的玩家中，只有27%能在三次以内猜中。
这个游戏自然也成了程序员们的新竞技场，他们写出各种算法来比拼谁用的步数最少。
这其中，百万粉数学科普大神3Blue1Brown的玩法更为硬核——
他不光写出了求解算法，还用数学知识一步步优化至逼近理论*限，最终成绩平均3.138次猜测就能获胜。
并且他用统计办法找出了与人类常见策略不同的**开*单词crane。
为了游戏点进来，为了精彩的信息论知识留下，太酷了！
从每一次猜测中获得最多信息
Wordle的游戏规则很简单，玩家需要猜出程序每天指定的一个5位英语单词谜底。
玩家可以随意提交一个英语单词，但必须是字典里有的，不能胡乱拼写。
如果字母在谜底中出现且位置对了就显示绿色，字母出现了但位置不对就显示**，字母在答案的单词中没出现就显示灰色。
在6次尝试之内猜出就算赢。
3Blue1Brown的总体思路是尽量从每一次猜测中获得最多的信息。
尝试在前两次尝试中覆盖最多高频字母。
比如other+nails的组合，就可以覆盖出现频率**的11个字母中的10个，如果运气好就能确定下来一些字母。
10个常用字母都没出现的单词数量就大大减少了，让下一步猜测更简单。
同样用nails这几个字母，也可以拼成snail ，这两种拼写顺序之间的差异，
下面需要一种新的计算方法。
如何计算信息量？
原版Wordle游戏里有一个数量12972的总单词列表，都能作为猜测词使用。
不过3Blue1Brown觉得让程序利用答案列表的话有点像作弊了，他果断给自己加大难度，只考虑总单词列表。
游戏中，每一次猜测都能从12972个单词中排除一些结果。
比如猜测weary，如果W位置正确同时A出现了，那么剩下的可选单词只剩58个。
3Blue1Brown选择的办法，就是利用信息论祖师爷香农提出的信息熵概念。
信息熵描述的是**的不确定*，单位就是大家知道的比特。
理解起来也不难，可以用扔硬币来解释。
扔1枚硬币只会出现正、反两种结果，而且概率相等。
扔2枚硬币就有正正、正反、反正、反反这4种结果，扔3枚有8种情况等等，也就是扔n次有2的n次方种结果。
当一个**有两种结果且概率都是1/2，其不确定*相当于扔1枚硬币，此时信息熵定义为1比特。
如果一个**有8种结果且概率都是1/8，就相当于扔3枚硬币，此时信息熵就是3比特。
信息量和信息熵的数量相等、意义相反，相当于衡量一则信息能消除多少不确定*。
设每种结果的概率为p，信息量为I，有如下等式。
以猜测weary为例，计算出获得的信息量为4.9比特。
代表这则信息消除的不确定*比扔5个硬币的不确定*少一点。
此时还剩下578个单词可选，其中选ramin能消除最多的信息熵，这样一步一步猜直到猜出正确答案。
最终成绩逼近理论*限
成绩不够好的一个问题出在每个单词作为答案的可能*其实并不相同。
像aahed aalii aargh这种偏门单词虽然在允许猜测的总单词列表里，但并不在答案列表的2315个单词里。
找一个典型的例子，当遇到abbas（人名，阿巴斯）和abyss（深渊）二选一时，如果程序能知道abyss是常用词，就可以省下一步。
比如在下面的情况中，words和dorms的信息量并不是**的，但因为词频较高所以优先考虑。
此外还可以让程序知道具体哪2315个单词真的是在答案列表里的，用上所有这些技巧后，成绩再次提升到3.438。
2315种答案意味着有11.17比特的不确定*，而**搜索后，前两步能获得的**信息量在10.01比特，还剩下1.16。
也就是说第三步的难度比二选一还要难一点，没有算法能保证每次都正确。
让程序记住每个正确答案，并在下一*中把猜过的单词排除出去，最终成绩到达3.138，逼近了理论*限。
虽然两步搜索的结果是crane，不过3Blue1Brown也不确定对于人类玩家来说是不是**开*单词。
毕竟实际游戏中人类很难像程序一样算出第二步的情况。
对于人类来说，soare和tares都是很好的开*。
程序写好后，3Blue1Brown还做了更多尝试，比如原版Wordle的困难难度，成绩是3.562，
还有一个Wordle变态版Absurdle，这个版本不再限制尝试次数，但变态之处在于游戏AI会与玩家对抗。
玩家猜测一次后正确答案就会变化，就像是在躲避玩家的猜测。
结果3Blue1Brown的程序也挑战成功。
原版游戏地址：
变态版游戏地址：
求解算法成绩逼近理论*限，连信息论都用上了》
发表评论