信息论初步：从猜词游戏开始

· · 算法·理论

0 前言

给我去看 3Blue1Brown。

没了。

1 问题引入

如 WC2022 的 T3 一样，你需要玩一个经典的游戏：猜词。

交互库先在给定的库里面选择一个单词，每次你可以向交互库询问一个库中有的单词，交互库会返回你字母猜对且位置猜对的字母，以及仅字母猜对的字母。

（在 CF753C 中，返回的是数量，不过并不影响分析）

2 解法

接下来的所有测试结果都是在真实的 wordle 上面测试得到的。

Link : Wordle Game。

机制是与那道题目是一样的，不同的是我们可以询问 6 次，而且词库数量扩大到了 12000+，但是真正可能成为答案的只有 2000+。

2.1 算法 1

首先有一个暴力的想法，每次找到第一个满足之前所有询问的单词并询问，不断重复直到只剩下一个单词。

这样暴力跑出来的效果比预想的要好：在八次随机测试中，全部都跑出了解，部分甚至跑出了 2 次的神秘成绩。平均次数是 4.5。

2.2 算法 2

显然这样做并不是最优的，很显然，在某些情况下，某些单词能够让我们得到更多的信息，当然了，由于我们并不知道询问这个单词能够得到的回答是什么，所以我们应当求得到信息的期望。然后我们选择期望最大的那个单词进行询问，即为一个非常好的策略。

把对于询问 x 的期望写出来：

E[x] = \sum_{i \in \text{All possible responses}} p(i) \cdot w(i)

接下来我们要做的是设计 w(i) 函数。这个 w(i) 即为上文所说的对于某种回答能够得到的信息量。

这里不妨先引入一些信息的概念。

2.3.1 基本概念

我们衡量一个信息的基本单位是比特（bit）。如果一个回答能够让我们的合法可能答案缩小一半，那么我们就说这个回答给了我们 1 比特的信息。而如果一个回答让我们的合法可能答案缩小至 \dfrac 14，那么我们就说这个回答给了我们 2 比特的信息。类比下去，如果一个回答让我们的合法可能答案缩小至 \dfrac 1{2^k}，那么我们就说这个回答给了我们 k 比特信息。

此时信息的公式已经很显然了：

(\frac 12)^I = p \Leftrightarrow I = - \log_2 (p)

其中 p 表示概率。表示什么概率？我们将我们的合法可能答案叫做概率空间。你可以理解为这个空间里面的每一个词都可以出现在正确答案里面，为什么要这么命名呢？

我们发现，一个观测得到的结果使得概率空间缩小的倍数与这个结果能够给我们的信息是互相关联的，而在这个例子中，使得概率空间缩小的倍数与这个观测得到这个结果的概率又是等价的。

所以我们说 p 表示这个结果出现的概率，这个表述是没有问题的。

那么，如果概率和信息是通过一个函数互相关联的，为什么我们还要这么麻烦去定义一个新的量呢？

答案就是，对数有一些很好的性质能够非常好的简化我们的表达，我们知道，由于 a^b \cdot a^c = a^{b + c}，所以 \log_ab + \log_ac = \log_abc。所以对于连续的多个观测，假设每次观测得到的信息是 I_1, I_2, \dots , I_n，那么我们得到的总的观测量就是 \sum_{i = 1}^n I_i。

顺便说一句，这个概率空间中的每一个词作为最终答案的可能性可以相等，也可以不相等。

接下来我们先考虑出现概率相同的情况。

回到原来的问题，上述式子变为了

E[I] = \sum_{i \in \text{All possible responses}} - p(i) \cdot \log_2(p(i))

注意到这里我们不使用 E[x] 这种不准确的写法了，我们使用 E[I] 表示信息量的期望。

那么，这个 E[I] 总该有一个名字吧。确实，E[x] 的名字就叫做熵（Entropy）。

关于熵这个概念，我们发现，它通常代表了对于一种有多少可能性的度量。举个例子吧，对于询问 x，假设 p(i) 是一组非常不均匀的数，而计算出的熵 E[I] = 6（本文剩下的所有关于信息量的部分均省略单位 bit），那么无论 p(i) 具体怎么表现，其等价于有 64 种情况，\forall 1 \leq i \leq 64, p(i) = \dfrac 1{64} 一样。

熵也可以表示对一种不确定性的度量，这个与热力学上的熵是有一定联系的。仍然举个例子，假设我们在玩猜词游戏，猜到一半，此时仍然有很多的合法的可能答案。此时最终答案在所有可能答案上分布的熵（下简称答案熵）就是对一种不确定性的度量。假如说我们有 100 个可能答案，那么熵即为 6.64（上文强调过只考虑出现概率相同的情况）。而如果我们只剩下了 10 个可能答案，那么熵就仅为 3.32 了。

由于信息的优雅性质，假设一次观测的信息量是 2.32，那么答案熵就可以很好的计算出来：3.32 - 2.32 = 1。此时我们就知道只剩下两个答案了。

接下来我们就可以写出这个程序的第一代版本了：我们每次操作完之后，对所有词库内单词算出当前情况下的熵，然后选择最大的一个。

由于时间复杂度飙升到 O(Tn^2)，所以在第一次猜测的时候时间复杂度变得难以承受。我们预处理发现 tares 是最优的答案之一。

所以开局我们直接选择 tares，待到答案熵降低到一定水平的时候再开始跑分析（如果没有降低到一定水平按照算法 1 输出）。

而当问题的不确定熵降到 0 之后，我们便直接输出可行库中的剩余答案。

为此，我写了一个比较长的测试程序，一共有两个版本，一个是模拟 wordle，一个是 wordle 机器人，代码均放在剪切板中。

https://www.luogu.com.cn/paste/3e2ifkju

这八次的随机测试就没有之前那么幸运了。但是平均值仍然达到了比较理想的 3.75。

那么，我们能不能优化程序呢？答案是可以的！

我们发现，假设只存在两个或者几个答案，那么与其去尝试一些虽然能够带来更多信息的词，不如去直接尝试找到答案。

而在词库数量仍然非常大的时候，在几乎相同的信息熵期望下，选择一个在答案词库里面的词可能比选择一个不在答案词库里面的词更加优秀。

假设现在我们已经知道了熵和期望概率 E[I],p(x)，那么我们应当如何去衡量这两者之间的权重呢？

比较靠谱的想法是，我选择了这个词的期望步数是多少，然后根据这个进行从小到大的排序。

根据期望公式，我们可以写出估价函数：

g(x) = p(x) \times curstep + (1 - p(x))(curstep + f(P - E[I]))

其中，curstep 指代当前步数，而 f(x) 则代表如果不确定熵是 x，期望还要再走 f(x) 步才能得到答案。

接下来摆在我们面前的是一个新问题：f(x) 怎么求？

在 3Blue1Brown 的视频里，他采用了一个暴算 + 拟合期望函数的方法。

我就直接强行猜测这个函数了，反正词库也差不多，我搞了一个差不多的。

f(x) = \log_2(x+2)

按照上面的优化编写程序。代码同样放在剪切板里。

https://www.luogu.com.cn/paste/mzf1rif3

发现八次随机测试平均值也是 3.75！事实上，这个优化相较于之前讨论的优化影响不是很大。第一点，在单词库比较大的时候，实际上排序与之前没有什么差别。第二点，在数据规模比较小的时候，程序仍然比较保守，推荐的词汇大多还是熵比较高的单词，然而太激进也会导致试错的情况，所以到这个地步已经非常不错了。

在 3Blue1Brown 的视频中引入了词频这一说法辅以 Sigmond 函数（旷野大计算.jpg）以及使用一个 possible answer list。但是在 WC 的题目中，我们并没有找到类似的描述，也就不能使用这个做法了。但是 WC 的题目中给出了一个首字母。对于 WC 这道题目，只需要对首字母进行预处理，再玄学调参 + 常数优化应该就可以过了。

3 后记

这篇文章耗费了我几天的时间，虽然代码本身不难但是由于是第一次写比较大规模的代码加上这个知识点还是比较新的，所以如此。

如果有对代码的优化，以及错误的指出，或者是对这篇文章有建设性的建议，亦或是询问代码的使用方法，欢迎评论或者私信！

就这样。