用信息论玩猜数字
看到3b1b用信息论玩Wordle，这里写一个玩猜数字的简化版本.用信息论玩猜数字信息论中衡量一个事件的信息是否丰富是从概率出发，在信息论中，1bit的信息量对应着−log212\displaystyle -\log_{2}\frac{1}{2}−log221，意味着，这个事情发生的概率是12\displaystyle \frac{1}{2}21，且发生之后将能够帮助我们筛选掉一半的搜索空
看到3b1b用信息论玩Wordle，这里写一个玩猜数字的简化版本.
用信息论玩猜数字
信息论中衡量一个事件的信息是否丰富是从概率出发，在信息论中，1bit的信息量对应着 − log 2 1 2 \displaystyle -\log_{2}\frac{1}{2} −log221，意味着，这个事情发生的概率是 1 2 \displaystyle \frac{1}{2} 21，且发生之后将能够帮助我们筛选掉一半的搜索空间。
直观来看，如果一个事件发生的概率越小，那么发生之后提供的信息就越多，而如果一个事件是常常发生的，那么其发生之后带来的信息也是不多的。
举个例子，一个猜数字游戏，在1-10中随机选择一个数字，然后每次会告诉你是否猜对，如果没猜对则告诉你比它大还是比它小。假设我们一开始猜5，然后告诉我们比5大，于是这个数字一定是[6,7,8,9,10]之中的一个，因此该事件发生的概率是 5 10 \displaystyle \frac{5}{10} 105，而该事件蕴含的信息量就是1bit！它成功将空间减少了一半。
那如果比5小呢？意味着数字一定是[1,2,3,4]中的一个，概率是 4 10 \displaystyle \frac{4}{10} 104，其信息量是 − log 2 4 10 = 1.321928 b i t \displaystyle -\log_{2}\frac{4}{10} =1.321928\ bit −log2104=1.321928 bit，可以发现这个事件缩减的搜索空间更多，因此提供的信息量更大！
最后，如果结果是5猜对了，那么概率是 1 10 \displaystyle \frac{1}{10} 101，信息量是 − log 2 1 10 = 3.321928 b i t \displaystyle -\log_{2}\frac{1}{10} =3.321928\ bit −log2101=3.321928 bit，是信息量最大的情况，这也是显然的，因为这个事件将搜索空间降低到了只有1个。
所以，就猜5而言，比它小跟比它大又或者猜对了所提供的信息量是不同的，那么这个策略能给我们的平均信息量是多少呢？显然将所有可能根据其发生的概率平均起来，就得到平均的信息量：
− 1 2 log 2 1 2 − 4 10 log 2 4 10 − 1 10 log 2 1 10 = 1.360964 b i t -\frac{1}{2}\log_{2}\frac{1}{2} -\frac{4}{10}\log_{2}\frac{4}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.360964\ bit −21log221−104log2104−101log2101=1.360964 bit
而这个就是熵的定义了！
这时候如果我们需要判断，猜哪个数字的决策最好？是不是相当于问，猜哪个数字，将搜索空间平均减少的最多，也就是猜哪个数据的平均信息量（熵）是最大的！因此，用类似的方法，我把所有的猜的数字的熵计算一下，可以得到如下表：
| 猜哪个数字 | 熵 |
|---|---|
| 1 | − 1 10 log 2 1 10 − 9 10 log 2 9 10 = 0.4689956 -\frac{1}{10}\log_{2}\frac{1}{10} -\frac{9}{10}\log_{2}\frac{9}{10} =0.4689956 −101log2101−109log2109=0.4689956 |
| 2 | − 1 10 log 2 1 10 − 8 10 log 2 8 10 − 1 10 log 2 1 10 = 0.9219281 -\frac{1}{10}\log_{2}\frac{1}{10} -\frac{8}{10}\log_{2}\frac{8}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =0.9219281 −101log2101−108log2108−101log2101=0.9219281 |
| 3 | − 2 10 log 2 2 10 − 7 10 log 2 7 10 − 1 10 log 2 1 10 = 1.15678 -\frac{2}{10}\log_{2}\frac{2}{10} -\frac{7}{10}\log_{2}\frac{7}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.15678 −102log2102−107log2107−101log2101=1.15678 |
| 4 | − 3 10 log 2 3 10 − 6 10 log 2 6 10 − 1 10 log 2 1 10 = 1.295462 -\frac{3}{10}\log_{2}\frac{3}{10} -\frac{6}{10}\log_{2}\frac{6}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.295462 −103log2103−106log2106−101log2101=1.295462 |
| 5 | − 4 10 log 2 4 10 − 5 10 log 2 5 10 − 1 10 log 2 1 10 = 1.360964 -\frac{4}{10}\log_{2}\frac{4}{10} -\frac{5}{10}\log_{2}\frac{5}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.360964 −104log2104−105log2105−101log2101=1.360964 |
| 6 | − 5 10 log 2 5 10 − 4 10 log 2 4 10 − 1 10 log 2 1 10 = 1.360964 -\frac{5}{10}\log_{2}\frac{5}{10} -\frac{4}{10}\log_{2}\frac{4}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.360964 −105log2105−104log2104−101log2101=1.360964 |
| 7 | − 6 10 log 2 6 10 − 3 10 log 2 3 10 − 1 10 log 2 1 10 = 1.295462 -\frac{6}{10}\log_{2}\frac{6}{10} -\frac{3}{10}\log_{2}\frac{3}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.295462 −106log2106−103log2103−101log2101=1.295462 |
| 8 | − 7 10 log 2 7 10 − 2 10 log 2 2 10 − 1 10 log 2 1 10 = 1.15678 -\frac{7}{10}\log_{2}\frac{7}{10} -\frac{2}{10}\log_{2}\frac{2}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =1.15678 −107log2107−102log2102−101log2101=1.15678 |
| 9 | − 8 10 log 2 8 10 − 1 10 log 2 1 10 − 1 10 log 2 1 10 = 0.9219281 -\frac{8}{10}\log_{2}\frac{8}{10} -\frac{1}{10}\log_{2}\frac{1}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =0.9219281 −108log2108−101log2101−101log2101=0.9219281 |
| 10 | − 9 10 log 2 9 10 − 1 10 log 2 1 10 = 0.4689956 -\frac{9}{10}\log_{2}\frac{9}{10} -\frac{1}{10}\log_{2}\frac{1}{10} =0.4689956 −109log2109−101log2101=0.4689956 |
从这个表中，我们发现，猜5和6的熵是最高的，与我们直觉相符。如果游戏进入下一轮，我们完全可以使用上述的方法，从剩余的搜索空间计算不同猜测的熵，然后选择熵最大的作为我们的决策。
信息论的好处在于，这个问题的随意变种都是可解的，比如每个数字的选择不再是随机的，而是服从某种分布，此时，我们也只需要根据不同数字的概率来计算出每个决策所可能出现的结果及其熵就能找到最优的决策了。
参考资料
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
1
0- 0
已为社区贡献22条内容
所有评论(0)