信息论如何拯救了我的文字游戏

# 无人知晓的数字 来源：https://motplot.app/helloworld 信息论 · 文字游戏 有时媒介与信息之间的关系比想象中更复杂。“B as in Bravo.” 你一定做过这件事：在嘈杂的电话线上拼写单词，越过字母去用整个单词来表达，因为*B*、*D*和*P*在电话线路出问题的一瞬间都变成了同一个模糊的声音。 这并非糟糕信号的小把戏。它是现代通信中最深刻的思想之一，由人类实时完成，与让航天器的信号在数百万公里的噪声中仍能清晰辨认的技巧如出一辙。马歇尔·麦克卢汉因“媒介即信息”而广受赞誉，但克劳德·香农在更早的几年已经提出了一个更冷酷的版本：对于传递你话语的机器而言，含义根本不重要；只有媒介重要，以及它的哪些信号能被区分开。*Bravo*和*Delta*能在坏线路上存活；*B*和*D*则不能。你凭耳朵就解决了这个问题，不假思索。把同样的本能推向极限（你能通过一个嘈杂信道强制传递多少信息，并且仍然以*完全*确定的方式被理解？），你就会直接陷入香农在1956年提出的一个问题。 我不是以数学家的身份到达那里的；我不是数学家。我完全是从另一个方向来的：我当时想构建一个使用演绎推理而非线索的文字游戏。我本以为这很简单。 让我告诉你，我发布过的最简单的东西，是如何竟然建立在最古老的未解决问题之上的。 ## “简单”的事情 这就是整个游戏。一个半完成的填字网格。一排等待放置的字母。给你一个字母，你点击它所属的单元格，然后继续，直到网格填满。 ## 一条规则 我想要的东西小到几乎不值得说出来：谜题永远不应该让你猜测。没有一个时刻是你已经做对了一切，逻辑却枯竭了，游戏只是让你选一个单元格然后碰运气。每一个字母都可以仅通过推理来放置。 我以为那是容易的部分：这是一个填字游戏，所以我认为最难的部分是构建一个好的词典并筛选填字。我希望能回去警告那个版本的我…… ## 那堵墙 词典花了几个月时间。当它终于做好时，我做了显而易见的事：我把生成器指向一个空文件夹，让它生成几千个棋盘供我筛选。用真实单词填满一个网格，隐藏一些，剩下的逐个还给玩家，只保留那些可以仅凭逻辑完成的棋盘。我会在晚上筛选收获。 它生成了大约四十个。然后它停滞了，一个接一个地生成棋盘又丢弃，因为几乎没有一个是可演绎的。在几个深夜之后，重写了生成器，重新思考了问题，它从未超过一百个。 这让我彻底停了下来。一个必须横向纵向拼出真实单词的五乘五网格是一片组合海洋。**可能棋盘的空间超出了人类的理解，但我的生成器找不到一个人类能解决的百个棋盘。** 这不是一个可以通过优化解决的速度问题。这是一堵墙，它问了一个我无法回答的问题：可演绎的棋盘真的如此*稀有*，只有稀少的几个可玩？我是否严重误判了配置，以至于我梦想中的游戏根本无法存在？有几个糟糕的日子，我相信这个项目已经死了——不是困难，也不是缓慢，而是*不可能*——我自己的生成器坚持认为我想象中的开阔田野不过是一堆死胡同。 让我看到一丝希望、刚好足够我继续前进的是，它丢弃的棋盘和它保留的棋盘之间区别如此之小。同一个网格，同一个给出的字母，只有一个未覆盖的单元格就是猜测和确定之间的全部距离。也许我对问题的看法才是问题。 给出“T” → 2个合法单元格。你会猜测。 给出“T” → 1个合法单元格。强制选择。 同一个棋盘，只差一个方格。**第一：** 给出的“T”适合两个空格：向下拼成TOWER，或沿底部向右拼成TRAM。你必须猜测。**第二：** 揭开一个方格，ASK中的K，则顶部的选项变成ATK向右。这不是一个单词，所以T被强制到了它唯一的合法位置。 ## 这不是一个错误 我花了数周像追踪一个错误一样追踪它：生成器的缺陷，词典太薄，剥离过程太贪婪。这些都不是。 它是本文开头那条坏电话线的事情（一个古老而著名的**通信**问题），而我之前深陷在网格和词典中，没能认出它的形状。一个谜题就是一个信道：我是发送者，玩家是解码者，我传输一个字母，他们必须恢复出我指的是哪个单元格。 普通填字游戏是*有噪声*的信道。解码者通常是对的，当他们错了时，他们只是耸耸肩，回溯，然后修正。一点混乱在这种游戏中是可以接受的；在每天的填字游戏中，它是一半的乐趣。但我承诺了比“通常正确”更严格的东西。我承诺了*从不犯错*，而“从不”不是同一个刻度盘上的更紧设置。这是另一台机器。 ## 混淆性 这就是我在黑暗中摸索的对象。为每一个空格画一个点；当两个单元格可以接受同一个给出的字母时，当它们*容易混淆*时，在两点之间画一条线。这个图有一个名字：**混淆图**。当一个谜题是演绎性的，恰好就是空格形成**独立集**时：这些点之间没有连线。没有混淆的对。没有硬币翻转。这就是我给自己设定的规则的确切形状，用一种我不知道存在过的语言画了出来。 000111——每个信号作为三比特的字符串是一个立方体的角；每一条边是一个翻转的比特，可能把一个信号变成它的邻居。安全的代码保持角点之间没有单次滑动可以连接：**000**和**111**相隔三次翻转。“B as in Bravo”是人类形式的相同思想，而历史的一个有趣巧合是，它源自的语音字母表于**1956年**最终确定，正是香农发表该问题的那一年。半个多世纪的数学已经在那里，等着我。我可以判断一个完成的棋盘是否可演绎；但我还不能有目的地构建一个这样的棋盘。要学习如何做到，我必须首先理解香农到底发现了什么。 ## 五胜于四 香农在几十年前就在最简单的案例中解决了这个形状。想象钟面上五个信号，每个信号离它的两个邻居如此之近，以至于线路可能把它们混在一起。一次发送一个，你只能安全地使用两个：挑一对不相邻的信号，你传输的任何东西都不会被误解为别的东西。五个中的两个。一个很小、整洁、令人失望的数字。 钟面上五个信号；连线连接那些容易混淆的信号；信号1和3被高亮为安全的一对。 钟面上五个信号；连线连接每一对容易混淆的（相邻的）信号；安全的、不相邻的一对被绿色点亮。一次传输安全地承载两个信号。香农注意到，如果你不再一次发送一个信号，而是把它们捆绑起来，把整个序列当作一条信息，效果会好得多。一次发送一个，两次传输给你2 × 2 = 4条永远无法混淆的信息。把一对捆绑起来并妥善选择，你可以承载五条。（第五条之所以能塞进去，是因为两个捆绑包可以在一个槽位上共享一个容易混淆的信号，只要它们在另一个槽位上保持清晰分离：一个单独使用风险太大的信号，有了伴侣就安全了。）而且收益会复合。十个信号一次发送一个，得到2的十次方，1024条安全信息；捆绑后，它们给出3125条。所以安全信息的数量每增加一个信号就乘以2.236，而不是乘以2。它的精确值是五的平方根（**√5 ≈ 2.236**）。 回到棋盘上。一个可演绎的谜题是一组没有混淆对的空格，而钟面上的安全信息是同样的结构：混淆图中的**独立集**。区别仅在于规模。我需要一个单独的棋盘是安全的；香农想要的是当捆绑包无限制增长时信道所能容纳的最佳乘数，他给它起了一个名字，**容量**。 ## 手电筒 每个标准应用都朝一个方向：你得到一个固定的图，要求找出其中的独立集，或限制它可能有多大。这是一个检测器，而一个更好的检测器对我没有帮助，因为我的生成器仍然在盲目地生成棋盘并扔掉几乎所有的棋盘。我不需要在已经陷入的棋盘里*找出*一个独立集。我需要*生长*一个独立集：构建棋盘，使得它的空格从一开始就是一个独立集，并拒绝放置任何会破坏它的字母。 生成器仍然在掷骰子；我从未找到一个纯粹确定性的方法来构建一个可演绎的棋盘。但每一次掷骰子都被加码了。每一步，它都会查看棋盘下正在成形的混淆图，并根据任何会添加一条边的动作权衡每一个选择：一个给出的字母有两个可能的位置，两个空格可以接受同一个方块。它揭开打破平局的那一个方格，偏好留下最少容易混淆对的填充，并放弃任何无法挽救的分支。香农的结构不再是一个最后运行的测试，而是从第一步开始就引导构建。 最终棋盘数以千计地出现了。仍然有一些紧张时刻，我不得不提高重试限制、放宽超时，或重新播种生成器，但它足够可靠地运行，以致于现在已经有一个超过9000个可玩谜题的库，大约相当于十年的每日谜题，已经排好了队。 ## 重新看待这个数字 我把这一切的标题搞反了。*无人知晓的数字*并不是数学前沿某个遥远的常数；它就在这里，在每个棋盘上，微缩版。游戏中的每一步都是一个小问题，有一个编号答案：这个字母属于哪个单元格？几乎总是周围的单词把它锁定，你无需思考就能回答。但是，如果两个单元格都适合给出的字母，都拼出真实单词，突然间就有了两个答案，而棋盘上没有东西可以在它们之间做出选择。在那一瞬间，正确的单元格确实是不可知的：不是难算或算得慢，而是单凭这个字母不可能算出来。一个无人知晓的数字。解决办法是通信中最古老的技巧，就是你在坏线路上拼写名字时已经使用的技巧：增加上下文。再多揭开一个方块，再确定一个交叉单词，不可知的东西就会弹回唯一强制的单元格。 阿尔弗雷德·诺斯·怀特海曾说：“追求简单，并怀疑它。”这个教训我似乎注定要无数次地重新学习。而你，则可以完全信任它：一个字母，一个单元格，从来不需要猜一次。 这是一个真实的游戏，Motplot（https://motplot.app/）。如果你感兴趣，不妨试试。