第34章 解：（2）（1 / 2）

“且看相对简单的河图洛书，每个格子必属于九种状态之一，分别对应于数字1到9。而河图洛书的规则，实际上就是对有限种状态的约束。

第一种约束，是任意两个不同的格子，状态不同。

第二种约束，是任意三个直线相连的格子，状态组合必须属于以下八者其中之一：

(1,5,9),(1,6,8),(2,4,9),(2,5,8),(2,6,7),(3,4,8),(3,5,7),(4,5,6)。”

沈归尘似懂非懂地点点头。

“再看相对复杂的围棋，每个交叉点也只有三种可能的状态：【黑】、【白】、【空点】。只不过随着棋局的进展，每个交叉点的状态会动态地发生变化。

但无论怎样，围棋的几条规则，落子规则，提子规则，禁止自杀与打劫，其实都是关于棋盘总状态的约束。”

沈归尘觉得徐林说得对，但又不知道这有什么意义。

徐林总结道：“只涉及状态的赋值与状态间的逻辑约束，这实际上就是布尔代数问题。”

天元大陆土着听不懂思密达。

徐林所聊的，实际上就是围棋问题的抽象化。也即是拉普拉斯妖，又或者说AI们是如何处理这个问题的。

在简单的河图洛书问题中，拉斯会假定9个变量X_i，分别取值于数字1到9。

接下来她只需要找到一组合适的取值，使得以下的逻辑命题全部正确：

【对于?i≠j，X_i≠X_j】

【对于?{i,j,k}∈{{1,2,3},{4,5,6},{7,8,9},{1,4,7},{2,5,8},{3,6,9},{1,5,9},{3,5,7}}，

{X_i,X_j,X_k}∈{{1,5,9},{1,6,8},{2,4,9},{2,5,8},{2,6,7},{3,4,8},{3,5,7},{4,5,6}}】

这实际上就是Boolean可满足问题(SAT)，是计算机有能力解决的一大类典型问题。可以直接用SAT求解器计算出结果。

对于围棋，完全可以做类似的事，将每个交叉点编码成变量X_{i,t}，取值范围是{黑，白，空点}。因为围棋是动态过程的缘故，变量X不仅依赖于位置i，同样依赖于手数t。

与河图洛书的处理办法相似，围棋规则可以全数转化成关于X_{i,t}的逻辑约束，进而使得残局求活同样转化成一个寻找X_{i,t}赋值，使得关于规则的逻辑语句全部成真的计算问题。

徐林世界的AI围棋搜索就在隐含地处理类似的逻辑推理。只不过它们并非做显式查找，而是用神经网络近似。

无论河图洛书还是数独，其实都是一个人的游戏，故而获胜条件是“存在”一组状态，使得所有规则约束被满足。

也即是说，本质都是SAT问题。

可围棋却是双方玩家对弈的游戏，想要获胜就必须“存在”黑方第一手，对“任意”白方第二手，“存在”黑方第三手，对“任意”白方第四手……最后都有X_{i,t}满足所有规则约束（包括黑方获胜的一条额外约束）。

这种“存在”“任意”的量词交替模式，决定了围棋是比SAT更高阶的问题——QBF（量化布尔公式）。

QBF的复杂度与SAT相比如隔天堑。至少以徐林那个世界的计算力，完全无法将围棋问题彻底解决。

当然，用拉斯开挂全秒了。

关于计算问题的难度，其境界划分大致为：

第一境P境，可在多项式时间内求解，包括排序算法、素性判断。

第