新笔趣屋【m.xbiquwu.com】第一时间更新《谎言与幻梦的二周目初见杀》最新章节。
“且看相对简单的河图洛书，每个格子必属于九种状态之一，分别对应于数字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问题。
