|
根据统计，大多数人类玩家需要猜测 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 游戏上，一次猜测获得的信息量可以用每种可能情况的概率与对应信息量相乘，再把结果相加来计算，也就是求数学期望。Rythm可以让用户在Discord服务器上播放来自YouTube视频的音乐。 以猜测 weary 为例，计算出获得的信息量为 4.9 比特代表这则信息消除的不确定性比扔 5 个硬币的不确定性少一点 算法思路有了，接下来就可以交给程序，计算出所有 12972 个单词的能消除的信息熵。 用同样的方法，可以再计算第二步，第三步猜测能消除的信息熵。 根据这些计算结果，程序就可以在每一次猜测时，选择所有可能单词里能消除信息熵最多的那个。 比如第一次猜 slate 获得一次反馈，此时还剩下 578 个单词可选，其中选 ramin 能消除最多的信息熵，这样一步一步猜直到猜出正确答案。 接下来，拿这个程序在所有 2135 种可能的答案上跑一遍，平均用了 4.124 步猜出正确答案。 3Blue1Brown 觉得这个成绩还不够好，至少没有超过普通人类玩家水平，还需要继续优化。 最终成绩逼近理论极限 成绩不够好的一个问题出在每个单词作为答案的可能性其实并不相同像 aahed aalii aargh 这种偏门单词虽然在允许猜测的总单词列表里，但并不在答案列表的 2315 个单词里找一个典型的例子，当遇到 abbas和 abyss二选一时，如果程序能知道 abyss 是常用词，就可以省下一步 下一步改进方向就是引入词频统计数据，这样的数据集可以从 Wolfram 上找到。 这里还遇到一个问题，比如 which 和 braid 的出现频率相差 1000 倍，但都可以算是常见单词，出现在答案列表里的可能性相差不大。 解决办法就是用 Sigmoid 函数做处理，让更多数据靠近 0 或 1。 将处理后的词频数据与前面的信息量计算结果相结合，得到优化后的信息量计算方法。谷歌以侵犯版权为由，在几周前首先关闭了Groovy机器人，现在，它也要迫使Rythm下线。 在实际游戏中，也把信息量与词频结合考虑，就能让程序更倾向于选择常见单词比如在下面的情况中，words 和 dorms 的信息量并不是最高的，但因为词频较高所以优先考虑 优化后的成绩到了 3.601，平均节省了半步如果加大计算量，每次根据两步搜索的结果选择单词可以进一步提高成绩 而且根据两步搜索的计算结果，3Blue1Brown 认为能获得最大信息量的开局单词是 crane此外还可以让程序知道具体哪 2315 个单词真的是在答案列表里的，用上所有这些技巧后，成绩再次提升到 3.438 实际上这个成绩的理论极限就不可能低于 32315 种答案意味着有 11.17 比特的不确定性，而暴力搜索后，前两步能获得的最大信息量在 10.01 比特，还剩下 1.16也就是说第三步的难度比二选一还要难一点，没有算法能保证每次都正确 不过 3Blue1Brown 还是找到了新办法进一步提升成绩让程序记住每个正确答案，并在下一局中把猜过的单词排除出去，最终成绩到达 3.138，逼近了理论极限 看完整个视频后，有网友表示学到的信息论知识比上课学到的还多也有很多人对到底哪个单词才是最佳开局展开了讨论虽然两步搜索的结果是 crane，不过 3Blue1Brown 也不确定对于人类玩家来说是不是最佳开局单词毕竟实际游戏中人类很难像程序一样算出第二步的情况对于人类来说，soare 和 tares 都是很好的开局 还能挑战变态模式 程序写好后，3Blue1Brown 还做了更多尝试，比如原版 Wordle 的困难难度，成绩是 3.562，还有一个 Wordle 变态版 Absurdle，这个版本不再限制尝试次数，但变态之处在于游戏 AI 会与玩家对抗玩家猜测一次后正确答案就会变化，在所有反馈可能性中挑选信息熵最大的那个，就像是在躲避玩家的猜测 如果你看到这里也想挑战这个变态版试试，可以复制下方链接。 视频传送门: 原版游戏地址: 变态版游戏地址: 。 |
声明：以上内容为本网站转自其它媒体，相关信息仅为传递更多企业信息之目的，不代表本网观点，亦不代表本网站赞同其观点或证实其内容的真实性。投资有风险，需谨慎。
