谎言与幻梦的二周目初见杀第34章 解2

“且看相对简单的河图洛书每个格子必属于九种状态之一分别对应于数字1到9。

而河图洛书的规则实际上就是对有限种状态的约束。

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

第二种约束是任意三个直线相连的格子状态组合必须属于以下八者其中之一： (159)(168)(249)(258)(267)(348)(357)(456)。

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

“再看相对复杂的围棋每个交叉点也只有三种可能的状态：【黑】、【白】、【空点】。

只不过随着棋局的进展每个交叉点的状态会动态地发生变化。

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

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

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

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

徐林所聊的实际上就是围棋问题的抽象化。

也即是拉普拉斯妖又或者说AI们是如何处理这个问题的。

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

接下来她只需要找到一组合适的取值使得以下的逻辑命题全部正确： 【对于?i≠jX_i≠X_j】 【对于?{ijk}∈{{123}{456}{789}{147}{258}{369}{159}{357}} {X_iX_jX_k}∈{{159}{168}{249}{258}{267}{348}{357}{456}}】 这实际上就是Boolean可满足问题(SAT)是计算机有能力解决的一大类典型问题。

可以直接用SAT求解器计算出结果。

对于围棋完全可以做类似的事将每个交叉点编码成变量X_{it}取值范围是{黑白空点}。

因为围棋是动态过程的缘故变量X不仅依赖于位置i同样依赖于手数t。

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

徐林世界的AI围棋搜索就在隐含地处理类似的逻辑推理。

只不过它们并非做显式查找而是用神经网络近似。

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

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

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

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

QBF的复杂度与SAT相比如隔天堑。

至少以徐林那个世界的计算力完全无法将围棋问题彻底解决。

当然用拉斯开挂全秒了。

关于计算问题的难度其境界划分大致为： 第一境P境可在多项式时间内求解包括排序算法、素性判断。

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

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

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

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

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

但是众所周知尽管围棋死活题的复杂度达到PSPACE可一个人依旧是可以做的。

这个时候其实就用到一件事那就是枚举对方可能策略将一切可能性堵死。

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

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

至多只有黑方60手白方60手的相互交替。

那么就可以通过枚举白方60手的对策将QBF问题转化成低阶的SAT问题。

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

小主这个章节后面还有哦请点击下一页继续阅读后面更精彩！。

本文地址谎言与幻梦的二周目初见杀第34章 解2来源 http://www.dgszs.com