【老万】风靡全球的 Wordle 游戏：从入门到破解
老万约 11 分钟我喜欢这样的游戏：规则容易理解，精通非常困难。
比如俄罗斯方块（关于我和俄罗斯方块的故事，请读拙文）。又比如围棋，基本规则不到一天就可以掌握，但要成为高手，没有几十年的投入不成。（我不会下围棋，但是仰慕会下的人。）
今年风靡全球的纽约时报 wordle 就是这样的游戏。如果你还没有玩过它，大概是因为你需要科学翻墙。
Wordle 的规则一学就会：每天，纽约时报会选出一个长度为五个字母的英文单词让你猜。你有六次机会。每猜一次，游戏会告诉你：
哪些字母猜对了而且位置正确，
哪些字母猜对了但是位置错误。
比如答案是 TRASH，你猜的是 GREAT。系统就会提示你：
G：错，答案里没有这个字母。
R：猜对了！
E：错，没有这个字母。
A：有这个字母，但位置不对。
T：有这个字母，但位置不对。
根据系统的反馈，你可以逐步缩小范围，争取在六次之中猜出答案。
另外，只能猜字典上有的单词，不能耍赖生造一个，比如 AEIOU。
不少人玩 wordle 上瘾，每天盼着新的游戏开放，还在社交媒体上分享自己的战果。网上有不少攻略，教你首发用哪个单词好，如何制胜。
～～～～
我是程序员，在玩过几次之后，很快就不满足于人肉解决这个问题了。
凡能自动化的都要自动化，这是程序员活着的意义。
为了让自己的人生有意义，我决定写一个自动解 wordle 的程序。
这篇文章讲述了我从简单到高级迭代这个程序的过程，分析了每种算法的性能和改进思路，适合于对编程或者 wordle 感兴趣的朋友阅读。如果不耐烦，可以直接拉到结尾看结论，可能会出乎你的意料。
如果你只是想作弊，结尾有破解程序的源码链接。
～～～～
愚公曰：单词表长度有涯（这个游戏使用了 12974 个候选词），故每一步选择方式有涯，步数亦有涯（最多六步）。从理论上说我们可以暴力穷举所有的策略，从中选出一个成功率最高的。
然而，这种做法在现实中是难以行得通的，因为它需要的算力太高，即便是月入 3800 一顿三个肉包子的富人也难以负担。
所以，我决定先试一个简单的算法，看看效果如何再做计较。这也是程序员面试的基本修养：与其写不完一个精妙的算法，不如先写一个简单能用的，有时间再优化，起码可以拿到一半的分数。
我的想法是：
统计每个字母在候选单词表中出现的频度。如果一个字母在900个单词中出现过，它的频度就是900。
把候选词按总字母频度排序。如果一个词包含的高频字母多，就排在前面。
优先猜前排的单词，这样成功率比较高。
每次猜完后根据系统提示，把不满足所有提示条件的单词从候选词表中去掉。
从第三步起重复，直到游戏结束。
统计表明，字母 S 的频度最高，超过半数单词都包括它。字母 E 紧随其后。阿 Q 是垫底的，只在 113 个单词中出现过：
S: 6665E: 6662A: 5992O: 4439R: 4160I: 3759L: 3371T: 3295N: 2954U: 2512D: 2453Y: 2074C: 2028P: 2019M: 1976H: 1760G: 1644B: 1627K: 1506F: 1115W: 1039V: 694Z: 434J: 291X: 288Q: 113
拿到一个单词后，我们可以看一下它包含哪些字母，去掉重复字母后，把每个字母的频度加起来，就得到这个单词的总字母频度。比如，把这些单词按总字母频度排序后打印出来是这样的：
AROSE: 27918AEROS: 27918SOARE: 27918ARISE: 27238RAISE: 27238AESIR: 27238REAIS: 27238SERAI: 27238ALOES: 27129STOAE: 27053…JUGUM: 6423QAJAQ: 6396BUBBY: 6213FUZZY: 6135YUKKY: 6092IMMIX: 6023HYPHY: 5853GYPPY: 5737XYLYL: 5733FUFFY: 5701
是不是有很多都不认得？像 REAIS, QAJAQ 之类，要不是玩 wordle，八辈子都碰不到一回。
暴力检查了一下这个算法的效果。用它处理全部 12974 个单词，有 87.46% 的情况可以在六次之内猜出，显然还有很大改进空间。不过，考虑到它是如此简单，这已经超过了我的预期。
～～～～
接下来，我们想办法提升胜率。
细细一想，这个 1.0 算法过于急功近利了，一上来就急吼吼地要直扑答案，每一步想的都是“我现在就要赢！”
而且，它不考虑单词之间的配合，每次只看到眼前一步，执意选那个它觉得成功概率最大的。
不懂得布局是走不远的。wordle，人生，都如此。
其实，我们猜一个单词，目的不一定是马上赢，也可以是为了最大程度地获取信息，为接下来几步铺路。
如果说赢是求实利，探索型的猜测就是求势。
在游戏开局，应该尽力求势，最大化信息量。
到终局阶段，再利用早期积累的势，转化成实利，最大化成功概率。
没有积累就想成功，就像念完初小就退学创业。王思聪不比你条件好？人家也是在伦敦读了大学的。
好吧，如何求势？
我自己玩 wordle 的策略是首发 AUDIO 和 LEFTY 两个词，包括了全部元音字母 AEIOU 加一个半元音 Y，辅音字母 DFLT 在单词中的出现频率也不算低。这样，虽然 LEFTY 不一定是在所有剩余单词中最可能成功的，但它和 AUDIO 组合在一起，可以从系统那里套出不少信息，接下来就更好猜了。
把算法改成先猜这两个单词，再猜总字母频度高的词，果然有效，成功率到了90.62%。
看来，我的策略有一定的道理。
～～～～
如何再提升？
AUDIO 和 LEFTY 的组合，是我拍脑袋想出来的，虽然效果还可以，毕竟不能保证是最优。完全有可能其它两个单词首发有更高的胜率。
有了这个认识，下一步就清楚了：穷举所有两个单词的组合，看哪两个做首发可以给我们最大的总字母频度。
注意，一对单词的总字母频度不一定等于它们各自总字母频度的和，因为它们之间可能有重复字母，在计算总频度时是需要去重的。所以，一对单词的总字母频度一定是小于或等于单词1的总字母频度 + 单词2的总字母频度。
学过基本算法的同学知道，寻找最佳拍档的任务可以用嵌套循环解决：外圈选第一个单词，内圈选第二个单词，在循环体里计算这对词的总字母频度，取一个最优组合。
但是，我们一共有约13000个候选词，简单的嵌套就会循环大约 13000*13000 = 169000000（1亿6千9百万）次，还是有点慢的。
需要加一些小优化：
先把单词按总字母频度排序。每层循环从高频单词开始。
规定第二个单词必须在频度表上排在第一个单词后面，这样内层循环可以缩短，从一个正方形的循环变成三角形，减少一半工作。
因为一对单词的总字母频度肯定不会超过单词1的总字母频度 + 单词2的总字母频度，我们可以在内循环里先预判一下，如果两个单词各自的总字母频度之和不超过目前已知的最佳单词对的总字母频度，就没必要算下去了，直接退出内循环（因为循环是从高频到低频，后来的单词只会更差）。
最后一条，就是著名的 A* 剪枝搜索算法的核心思想。
优化后的代码很快出结果了。它推荐的首发对子是：
STARNLOUIE
我们看，这一对词同样覆盖了全部元音字母 AEIOU。有趣的是，它们不包括半元音字母 Y。辅音字母包括 LNRST，比 AUDIO + LEFTY 的 DFLT 有更高的字母频度（主要是字母 S 太高频了）。
用 STARN + LOUIE 首发，效果果然进步：成功率 91.12%。
这个增幅不大，说明 AUDIO + LEFTY 已经很优秀了。
～～～～
接下来怎么办？
既然两个单词配合效果好于单打独斗，何不尝试三个组合？
好吧，我们就整它个三重循环。
如果说，两重循环时那些优化是锦上添花，三重循环就完全仰仗优化了。不优化的结果是 13000*13000 *13000（大约2.2万亿）次循环，天长地久有时尽，此恨绵绵无绝期。
A* 剪枝搜索再立奇功，用了二十分钟搞定。它推荐了几组三个单词的组合，它们的得分相同。
我试了一下，LYRIC + UPSET + NOMAD （歌词惹恼浪子）的效果最好。有多好？成功率 95.23%。也就是说玩 20 次会失败一次。
这三个单词一共15个字母，没一个重复的，涵盖了全部五个元音字母和Y，还包括几个频率高的辅音字母。如果不借助电脑，人怕是很难想出这样的组合。
有人说二十分钟太慢了。不用怕，这二十分钟是用来确定首发阵容的，只需跑一次。定下来是 LYRIC + UPSET + NOMAD 首发后，就不需要每次都跑三重循环了。
一个好汉三个帮，三词协力不一样。
程咬金善使板斧。两军对峙，不管来将是谁，他上来就是劈脑门，挖眼仁，掏耳朵三下，虽然简单，却有效。
这个算法一样，不管系统反馈如何，前三招固定。虽然是固定开局，靠精心挑选的这三个词我们还是能获取很多信息，帮助后面三步的选择。
从三重循环需要的时间来看，我不打算试四重循环了。况且，一共只有六次猜的机会，不能在做势上花费太多的弹药。
～～～～
这个周末是国际父亲劳动节。在完成了做饭、割草、剪枝（真的剪树，不是 A* 算法那种）、购物等任务之后，我决定进一步挑战自己，完善 wordle 解决器。
在以前的算法中，我们假设这 13000 来个单词中每一个都可能是正确答案。其实，这个游戏是设计成不允许答案是生僻词的，否则大多数玩家会太不爽了，毕竟不是每个人都会为了玩 wordle 去背韦伯斯特大字典。
所以，我们只要在最后几步求实猜的时候把不可能是答案的生僻词剔掉，自然可以避免无效猜测，提高成功率。
怎么知道一个词算不算生僻呢？这个问题有一个简单的解决方法：看游戏的源代码。
Wordle 是用 Javascript 语言写的，要看源代码，只需一二三四：
打开游戏网页 https://www.nytimes.com/games/wordle/index.html，右击鼠标选择 “View Page Source”，看到当前页面的 HTML 源码。
找到一行 <script src="main.5d21d0d0.js"></script>，点这个 .js 文件名打开 Javascript 文件。
找到两个变量。第一个是 ko=["cigar","rebut","sissy",...]，所有可以做答案的五字母单词列表。
第二个是 wo=["aahed","aalii","aargh",...]，所有其它合法五字母单词。
我改进了程咬金算法，三板斧过后，只考虑合法答案表上的单词，不在错误的地方浪费机会。
效果惊人，一下子成功率飙升到 99.53%。在可能是答案的 2300 多个单词中，只有 10 个词不能被这种方法破解。
我估计这个成绩可以完胜大多数人类玩家了。要达到这个胜率，平均两百多局才能失手一次。因为 wordle 游戏每天只出一道新题，绝大多数人都没有玩过两百多局，连一百局都少见。
有人问这个算法的步数分布如何。我可以不负责任地讲，这个算法优化的目标是赢，不是尽快赢，所以平均步数不会很低。
阿尔法狗（AlphaGo）也一样。它的目标是赢，不是赢得多。它不在乎赢一目还是赢一百目。
和 AlphaGo 下棋经常让高手觉得憋屈。他们常常感觉自己跟狗的局面相去不远，还有赢面，岂不知一切都在 AlphaGo 的掌控之中，最后让你总是输那么一点点。
这看似一点点的差距，实际上永远难以追上。
～～～～
作为一名前谷歌程序员，即便 99.53% 的成功率也还是让我如鲠在喉如芒在背。究竟还有没有上升空间？
肯定是有的。关键是代价。
要用可以接受的代价提升成绩。毕竟我们不是人民币玩家。
我坐下来分析这个算法为什么有时会败。突然想到这是一个不思进取的算法。
你看，它不会从过去的失败中吸取教训，每次都是一张白纸从零开始。上一次犯的错，这一次还会错，不会发挥得差一点，也不会发挥得好一点，在哪里跌倒，就在哪里爬不起来。
我分析了全部十个失败案例：为什么最后三板斧没有致命？怎么做会更好？
针对每个案例，我用人脑选择的终局方案替换掉机器的方案。机器要做的是：一旦意识到前几步是通向那十座麦城中的一座，马上放弃思考，改用老万手工优化的方案。
当然，从理论上说，我可以写一个程序去穷举一切策略，为这十个残局分别找出一个最优解。可是，虽然残局的状态空间已经比从开局就进行搜索小了很多，还是一个巨大的数。如果有足够的耐心是可以等到结果的，但我没有足够的耐心。
所以我采取了一帮一，一对红的人机交互方式，手把手教会电脑如何面对困境，在绝望中寻找希望，机生终将辉煌。
结果怎么样呢？改进后的程咬金++算法会根据程咬金算法的教训避坑，彻底解决了 wordle 问题，实现了 100% 的成功率。
对的，你没看错。不管答案是什么，都可以在 6 步之内猜出。而且，前三步是固定的 LYRIC UPSET NOMAD，以不变应万变。
至此，wordle 游戏完全破解。
最后，还是回应一下很多朋友感兴趣的步数分布问题。用全部 2309 种可能的答案考验程咬金++，结果是：
一猜即中：一个单词（LYRIC）
两猜即中：一个单词（UPSET）
三猜即中：一个单词（NOMAD）
四猜即中：1475 个单词（63.88%）
五猜方中：746 个单词（32.31%）
六猜方中：85 个单词（3.68%）
也就是说大多数情况需要猜四次。
这篇文章介绍的全部算法代码开源在 https://github.com/zhanyong-wan/wordle-solver （点文末的“阅读原文”可以打开）。欢迎大家试用、改进。
～～～～
对了，大家一起干了这碗鸡汤：
不要急着一步到位。最好是好的敌人。先做出一个能用的，再迭代改进。
成功需要布局。先求势，再求实。势可以转化为实。
持之以恒，方向正确，人生终将辉煌。
学算法是有用的，不光是为了找工作。
～～～～～～～～～～
猜你会喜欢：
程序员护发秘籍 - 掌握这些工作技巧，包你不脱发
程序员的核心技能 - 以脱口秀的方式讲解程序员最重要的技能
程序员要学好语文 - 写作很重要，哪怕是写给自己看
如何做出保鲜十年的软件 - 老码农冒死披露行业内幕系列
2021老万故事汇 - 《老万故事会》2021全年文章汇总，供你按图索骥
～～～～～～～～～～
关注老万故事会公众号：
本公众号不开赞赏不放广告。如果喜欢这篇文章，欢迎订阅、转发、评论、点赞。谢谢！🙏