“且看相对简单的河图洛书，每个格子必属于九种状态之一，分别对应于数字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境，可在多项式时间内求解，包括排序算法、素性判断。

第二境Np境，不可在多项式时间内求解，却可以在多项式时间内验证一个答案是否正确，就比如SAt。

第三境pSpAcE境，可在多项式空间内求解，比如围棋、象棋各种棋，还有方才的qbF。

第四境ExptImE境，可在指数时间内求解，比如各种广义游戏是否有必胜策略。

再往上的境界，已是不知天地为何物，恐怕只有神才知道。

qbF相比SAt，横跨一个大境界，一般情形下根本无法同台较量。

但是众所周知，尽管围棋死活题的复杂度达到pSpAcE，可一个人依旧是可以做的。这个时候其实就用到一件事，那就是枚举对方可能策略，将一切可能性堵死。

qbF问题也是如此，完全可以通过枚举去掉逻辑语句中的“任意”，将他们全部改成存在。

徐林事先声明自己将在120手内取胜，看似提高围棋残局的难度，可实际上却简化了qbF求解，将搜索范围极大的缩小。

至多只有黑方60手，白方60手的相互交替。那么就可以通过枚举白方60手的对策，将qbF问题转化成低阶的SAt问题。

说起来简单，可是因为SAt与qbF间横隔一个大境界差距，此过程无法在多项式时间内处理。

至少在围棋AI研究的早期，地球人尝试这条道路完全走不通。

好在拉斯有力大飞砖的超绝计算力，能帮徐林将这个转化变作现实。

徐林让拉斯做的第一件事就是这个：将珍珑棋局转为SAt问题，无论在难度还是形式上，都比原本更加简单。

想要零知识证明珍珑棋局，只需要零知识证明其相对应的SAt问题。

SAt虽只是Np之境，却也是Np巅峰大圆满，人称Np完全境。

SAt足以降维打击一切Np境以内的敌人。所