信息论找到了最佳 Wordle 起始词

在 COVID 疫情肆虐并限制我们休闲选择的过去几年里，您是如何度过的？软件开发者 Josh Wardle 和他的伴侣通过 《纽约时报》 的填字游戏打发时间。有一次，Wardle 想起了几年前他想到的一个类似游戏的想法。

他随后创建的这个名为 Wordle 的文字游戏，以他的姓氏命名，在 2022 年一炮而红。Twitter 时间线充斥着 Wordle 的结果。尽管这个游戏围绕着猜测一个每天都在变化的单词，但其背后有很多数学原理。

Wardle 在 2013 年提出了这个基本想法。您有六次尝试来正确确定一个五个字母的单词。您首先输入一个单词——例如，“start”——通过在五个空字段中输入字母。之后，这些字段会改变颜色。如果字母在答案词的完全相同的位置出现，则变为绿色；如果字母包含在答案词的不同位置，则变为黄色；如果字母不是答案词的一部分，则变为灰色。根据这些线索，您可以输入第二个单词并收集有关答案词字母的信息，直到您找到您正在寻找的答案。这个原理有点让人想起 20 世纪 70 年代流行的游戏 Mastermind。

支持科学新闻报道

如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关塑造我们今天世界的发现和想法的具有影响力的故事的未来。

[阅读更多关于数学游戏和谜题的内容]

您可以输入任何由五个字母组成的英文单词，大约有 10,000 个。然而，由于该列表也包含非常不常见的表达方式，例如 “aahed”（“aah” 的过去式），因此答案词是 一个更短的 2,309 个常用英语词汇列表 的一部分。目标是在尽可能少的尝试次数内找到答案词。更令人兴奋的是，您不能连续玩多次游戏。每天只有一个答案词——而且对于世界各地的所有玩家来说都是同一个词。这种变化赋予了游戏一种社交成分，这可能促成了它的流行。

意想不到的成功

但 Wardle 的目标根本不是全球性的广受欢迎。他在 2021 年初再次拾起他的 Wordle 想法，制作一个易于使用的游戏，以便和他的伴侣一起打发时间。有几个月，他们是仅有的两个用户。在某个时候，他们的家人听说了这个游戏，Wardle 在 2021 年 10 月决定 在他的个人网站 上免费提供它，并且没有广告。此后不久，Wordle 就火爆起来。2021 年 11 月 1 日，每天有 90 位用户玩 Wordle；到 2022 年 1 月 1 日，这个数字已经达到 30 万。又过了一周，这个游戏就有了 200 万用户。

2022 年 1 月，《纽约时报》宣布它 已收购 Wordle 的版权，价格为七位数美元的低端。这进一步扩大了游戏的覆盖范围。到 2022 年 3 月，全球 数千万人 至少玩过一次 Wordle。该游戏的一个特殊功能是，在玩完游戏后，您可以将游戏中的颜色代码（即彩色游戏字段）下载为表情符号，并在社交媒体上分享，以便与他人比较。 大多数人平均需要大约四次尝试 才能解决一个 Wordle。任何少于这个次数都被认为是成功。

如果您曾经尝试过 Wordle，那么您就会知道结果很大程度上取决于您选择的起始词。例如，“start” 不是一个非常明智的第一次尝试，因为它包含字母 T 两次。您浪费了五个位置中的一个，您本可以在这些位置收集有关其他字母的信息。当然，您可能会幸运，答案词也可能包含两个 T——但在所有其他情况下，您都不会获得任何信息。根据《纽约时报》的说法，最受欢迎的起始词 是 “adieu” 或 “audio”。由于这两个词都由许多元音组成，它们很快就能清楚地表明答案词中包含哪些字母。但这真的是最佳选择吗？

信息内容与命中率

也许最好从诸如 “Texas” 这样的词开始。如果答案词中包含像 X 这样的稀有字母，您将在第一步中清除 2,309 个可能的答案中的很大一部分。事实上，只有 37 个可能的单词包含 X。然而，X 不出现在答案词中的概率很高。在这些情况下，该信息几乎没有任何价值。如果一个人知道答案中没有 X，则可能性仅从 2,309 个减少到 2,272 个。因此，玩家必须问：“我重视尽可能多地获取信息吗？还是我宁愿有很高的正确猜测字母的概率？”

信息和概率相关的事实并不新鲜。数学家克劳德·香农，信息论的创始人，认识到这一点，并考虑到这种关系，定义了信息内容的度量。假设有一个包含可能事件的空间——在我们的例子中，是 Wordle 的 2,309 个答案词。那么，一条信息对应于将解空间减半的反馈，例如，如果答案词包含字母 S（例如，大约一半的答案至少包含一个 S）。

两条信息清除四分之三的答案——例如，当答案词包含 T 时。而有了三条信息，只剩下八分之一的单词。这意味着，一个字母包含在答案中的可能性越大，其信息内容就越小。

这个想法可以用数学方式表达。找到具有特定属性（例如字母 A）的单词的概率 (p) 可以通过将包含 A 的单词总数（表示为 M_A）除以所有单词的数量 (M) 来计算。所以 p = M_A / M。与此同时，信息 (I)，意思是“单词包含 A”，将所有可能性的空间 (M) 减少了 ½^I 倍。我们可以将其表示为 M_A = ½^I x M。

通过将两个方程式相互代入，可以得出一个结合了信息内容和概率的公式：p = ½^I x M / M，所以 p = ½^I。这也可以反过来求解 I：I = –log₂p。

香农在 1948 年 发现了概率和信息内容之间这种惊人的联系。根据 1971 年 发表在《大众科学》 上的一篇文章，香农说：“我最关心的是如何称呼 [这个新量 I]。我曾想称它为 ‘信息’，但这个词用得太滥了，所以我决定称它为 ‘不确定性’。当我与 [计算机科学家、物理学家和数学家] 约翰·冯·诺依曼讨论时，他有一个更好的主意。冯·诺依曼告诉我，‘你应该称它为熵，有两个原因。首先，你的不确定性函数已经在统计力学中以这个名称使用，所以它已经有一个名称了。其次，也是更重要的，没有人真正知道熵是什么，所以在辩论中你将永远占据优势。’”

从那时起，上面定义的量 I 就被称为熵。

回到 Wordle。熵可以帮助我们找到合适的起始词。一个词的熵越高，信息增益就越高。然而，高熵总是伴随着低命中率，因此您应该找到这两个因素的平衡，以选择最佳的起始词。

您可以计算所有可能输入的熵期望值，正如数学家 Grant Sanderson 在他的 YouTube 频道 3Blue1Brown 中所做的那样。为了做到这一点，Sanderson 采取了以下步骤：首先，对于大约 10,000 个输入词中的每一个，他计算了基于 2,309 个答案词可能出现的颜色模式的频率。

例如，五个灰色方块（所有字母都不正确）可能会出现 250 次。另一方面，一个绿色方块后跟四个灰色方块（第一个字母正确且位置正确）可能只出现 15 次，等等。颜色模式出现的频率越高，在输入一个单词后遇到它的概率就越高。与此同时，颜色代码提供了可以用熵来衡量的信息。由于一些答案词被排除在外，因此解空间减少了。

为了找出您从起始词中平均会获得多少信息，您可以计算每个可能的关联颜色代码的熵，并用其出现的概率对其进行加权。换句话说，您可以计算期望值。事实证明，单词 “soare”（一种幼鹰的过时术语）表现最佳，期望值为 5.89 比特。这意味着，如果您从这个词开始，可能的答案词空间将平均缩小到 2^–5.89，或可能性的 1.7%。因此，平均而言，仍然可能有大约 22 个答案词。

从 “Soare” 开始，表现良好

Wordle 不仅包含一次猜测尝试，而是多次。通过选择两个连续单词的合适组合，与从 soare 开始相比，可能会更有效地限制可能的答案数量。

Sanderson 也遵循了这种方法。他按如下步骤进行：假设在输入 soare 后，您得到五个灰色方块。所以您只知道字母 S、O、A、R 和 E 不是答案词的一部分。由此，Sanderson 检查了对于所有可能的后续输入，哪个第二颜色模式可能会出现，从而计算出第二个输入词的熵的期望值。如果在起始词 soare 之后，所有字段都是灰色的，则第二个输入的最佳选择是 “clint”。（顺便说一下，clint 是一种坚硬的岩石。）

现在您可以搜索对于在您输入 soare 后可能出现的其他颜色模式，最合适的第二个单词是什么。例如，对于一个绿色方块后跟四个灰色方块，“thilk”（另一个过时的术语，意思是 “that” 或 “this”）给出了最佳结果。如果我们现在用相应的概率对第二个单词的熵进行加权，我们得到的值为 4.11。这意味着，使用起始词 soare，我们平均获得 5.89 比特的信息，而使用最佳的第二个单词，我们又获得 4.11 比特。如果一个人完美地玩 Wordle，那么在两次尝试后，他将平均获得 10 比特的信息——也就是说，解空间将减少 2^–10 倍，平均留下 2.25 个答案词。

“Slane” 作为更佳策略

如果您查看两个词的最佳组合，另一个选择被证明更强大：“slane”（一种用于挖掘泥炭的特殊铲子）。这个起始词平均仅提供 5.77 比特的信息，但使用最佳的第二个输入，您平均会收到另外 4.27 比特。这使总数达到 10.04 比特，并将 2,309 个可能性减少到平均 2.19 个单词。

如果您想 设计一个尽可能精通的 Wordle 算法，考虑第二个单词的选择非常重要。但对于人类玩家来说，这种策略可能并不重要。毕竟，不可能记住对于 slane 之后出现的每种颜色模式，哪个后续单词最合适。因此，无论您使用 soare 还是 slane 开始游戏，应该没有太大区别。

然而，在玩 Wordle 时考虑信息论还是非常有用的，正如《量子杂志》令人印象深刻地说明的那样。假设您使用 “bloat” 开始游戏，并得到灰色、灰色、灰色、黄色、黄色。那么您就知道答案词包含 A 和 T（但在不同的位置），并且不包含 B、L 或 O。其次，您尝试用 “watch” 碰碰运气，您几乎就要成功了：第一个字段是灰色的；其他四个是绿色的。所以第一个字母是错误的，但所有其他字母都是正确的。您接下来该怎么做？

您现在可以简单地猜测，例如，“match”。但是——假设您正在玩常规 Wordle，而不是困难模式——从信息论的角度来看，您应该输入 “chimp”。

当然，chimp 不可能是答案。但它有助于缩小选择范围。在输入 watch 之后，仍然有四个词浮现在脑海：catch、hatch、match 和 patch。如果您一个接一个地输入这些词，您仍然可以赢得游戏，但您可能会表现不佳。另一方面，输入 chimp 会揭示哪个起始字母（C、H、M 或 P）是正确的。因此，您在四次尝试后赢得了游戏。如果您喜欢冒险，您当然可以碰碰运气，并希望在第三次尝试中猜对正确的答案。

无论如何，我将来会使用 soare 作为我的起始词。让我们看看我下一次 Wordle 需要多少次尝试。在我居住的德国，每位玩家的平均尝试次数为 4.01 次。在美国，这个数字是 3.92 次。也许借助信息论，我们将在未来几个月内设法击败记录保持者瑞典（平均：3.72 次尝试）。

本文最初发表在《明镜周刊·科学》，经许可转载。