数学科普人士攻克火爆猜字游戏 Wordle
发布时间：2022-02-09 15:29:53 所属栏目：动态 来源：互联网
导读：免费猜字小游戏 Wordle 正在席卷全球，火到以数百万美元的价格被收购，全球玩家数量也突破了 200 万。如果你在微博、微信等地方看到这些神神秘秘的方块，那就是 Wordle 玩家在分享自己当日的战绩了。 根据统计，大多数人类玩家需要猜测 4 次或以上才能取得
|
免费猜字小游戏 Wordle 正在席卷全球，火到以数百万美元的价格被收购，全球玩家数量也突破了 200 万。如果你在微博、微信等地方看到这些神神秘秘的方块，那就是 Wordle 玩家在分享自己当日的战绩了。 根据统计，大多数人类玩家需要猜测 4 次或以上才能取得胜利。比如，2 月 5 日的题目在当天 30 多万份晒出战绩的玩家中，只有 27% 能在三次以内猜中。这个游戏自然也成了程序员们的新竞技场，他们写出各种算法来比拼谁用的步数最少。这其中，百万粉数学科普人士 3Blue1Brown 的玩法更为硬核 —— 他不光写出了求解算法，还用数学知识一步步优化至逼近理论极限，最终成绩平均 3.138 次猜测就能获胜。并且他用统计办法找出了与人类常见策略不同的最佳开局单词 crane。 他像往常一样把这个过程整理成视频分享出来，不仅展示了算法，还把其中涉及的信息论、统计学知识讲得明明白白。视频发布一天之内就有上百万播放，围观的网友也纷纷在评论区表达了赞叹。 为了游戏点进来，为了精彩的信息论知识留下，太酷了！ 他用了什么样的算法，理论极限又是怎么算出来的？下面一起来看看。 从每一次猜测中获得最多信息 Wordle 的游戏规则很简单，玩家需要猜出程序每天指定的一个 5 位英语单词谜底。玩家可以随意提交一个英语单词，但必须是字典里有的，不能胡乱拼写。如果字母在谜底中出现且位置对了就显示绿色，字母出现了但位置不对就显示黄色，字母在答案的单词中没出现就显示灰色。根据反馈信息再进行下一轮猜测，在 6 次尝试之内猜出就算赢。 如何让步数尽量少？ 3Blue1Brown 的总体思路是尽量从每一次猜测中获得最多的信息。他先是找来了 26 个字母在英语文本中出现频率的统计数据，尝试在前两次尝试中覆盖最多高频字母。比如 other+nails 的组合，就可以覆盖出现频率最高的 11 个字母中的 10 个，如果运气好就能确定下来一些字母。即使这些字母都没出现依然是一种信息量很大的反馈，10 个常用字母都没出现的单词数量就大大减少了，让下一步猜测更简单。 不过在尝试过程中，又出现了新的问题。同样用 nails 这几个字母，也可以拼成 snail ，这两种拼写顺序之间的差异，仅依据字母频率数据是无法衡量的。 下面需要一种新的计算方法。 如何计算信息量？ 原版 Wordle 游戏里有一个数量 12972 的总单词列表，都能作为猜测词使用。另外有一个 2315 个单词的列表，只有这些单词会出现在答案里 (据说是游戏作者的女朋友挑选的)。因为游戏是用 Javascript 写的，数据都在客户端，这些数据直接可以从源码里找到。不过 3Blue1Brown 觉得让程序利用答案列表的话有点像作弊了，他果断给自己加大难度，只考虑总单词列表。游戏中，每一次猜测都能从 12972 个单词中排除一些结果。比如猜测 weary，如果 W 位置正确同时 A 出现了，那么剩下的可选单词只剩 58 个。 这样对同一个猜测，从 5 个字母全没出现到 5 个字母全对的各种反馈的概率都可以计算出来。 这样，问题就变成了如何评估各种反馈情况包含的信息量。 3Blue1Brown 选择的办法，就是利用信息论祖师爷香农提出的信息熵概念。信息熵描述的是事件的不确定性，单位就是大家知道的比特。理解起来也不难，可以用扔硬币来解释。 扔 1 枚硬币只会出现正、反两种结果，而且概率相等。扔 2 枚硬币就有正正、正反、反正、反反这 4 种结果，扔 3 枚有 8 种情况等等，也就是扔 n 次有 2 的 n 次方种结果。 当一个事件有两种结果且概率都是 1/2，其不确定性相当于扔 1 枚硬币，此时信息熵定义为 1 比特。如果一个事件有 8 种结果且概率都是 1/8，就相当于扔 3 枚硬币，此时信息熵就是 3 比特。 信息量和信息熵的数量相等、意义相反，相当于衡量一则信息能消除多少不确定性。设每种结果的概率为 p，信息量为 I，有如下等式。 回到 Wordle 游戏上，一次猜测获得的信息量可以用每种可能情况的概率与对应信息量相乘、再把结果相加来计算，也就是求数学期望。 以猜测 weary 为例，计算出获得的信息量为 4.9 比特。代表这则信息消除的不确定性比扔 5 个硬币的不确定性少一点。 算法思路有了，接下来就可以交给程序，计算出所有 12972 个单词的能消除的信息熵。 3Blue1Brown 觉得这个成绩还不够好，至少没有超过普通人类玩家水平，还需要继续优化。 最终成绩逼近理论极限 成绩不够好的一个问题出在每个单词作为答案的可能性其实并不相同。像 aahed aalii aargh 这种偏门单词虽然在允许猜测的总单词列表里，但并不在答案列表的 2315 个单词里。找一个典型的例子，当遇到 abbas（人名，阿巴斯）和 abyss（深渊）二选一时，如果程序能知道 abyss 是常用词，就可以省下一步。 下一步改进方向就是引入词频统计数据，这样的数据集可以从 Wolfram 上找到。 这里还遇到一个问题，比如 which 和 braid 的出现频率相差 1000 倍，但都可以算是常见单词，出现在答案列表里的可能性相差不大。 而且根据两步搜索的计算结果，3Blue1Brown 认为能获得最大信息量的开局单词是 crane。此外还可以让程序知道具体哪 2315 个单词真的是在答案列表里的，用上所有这些技巧后，成绩再次提升到 3.438。 实际上这个成绩的理论极限就不可能低于 3。2315 种答案意味着有 11.17 比特的不确定性，而暴力搜索后，前两步能获得的最大信息量在 10.01 比特，还剩下 1.16。也就是说第三步的难度比二选一还要难一点，没有算法能保证每次都正确。 不过 3Blue1Brown 还是找到了新办法进一步提升成绩。让程序记住每个正确答案，并在下一局中把猜过的单词排除出去，最终成绩到达 3.138，逼近了理论极限。 看完整个视频后，有网友表示学到的信息论知识比上课学到的还多。也有很多人对到底哪个单词才是最佳开局展开了讨论。虽然两步搜索的结果是 crane，不过 3Blue1Brown 也不确定对于人类玩家来说是不是最佳开局单词。毕竟实际游戏中人类很难像程序一样算出第二步的情况。对于人类来说，soare 和 tares 都是很好的开局。 还能挑战变态模式 程序写好后，3Blue1Brown 还做了更多尝试，比如原版 Wordle 的困难难度，成绩是 3.562，还有一个 Wordle 变态版 Absurdle，这个版本不再限制尝试次数，但变态之处在于游戏 AI 会与玩家对抗。玩家猜测一次后正确答案就会变化，在所有反馈可能性中挑选信息熵最大的那个，就像是在躲避玩家的猜测。 Absurdle 的作者之前还开发过一个变态版俄罗斯方块，每次都给你最不需要的方块。对于这个变态版 Wordle，结果 3Blue1Brown 的程序也挑战成功。 （编辑：开发网_开封站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330459号