围棋与象棋不单是数量级的差别，它们是质上的差别

好蛋

围棋与象棋不单是数量级的差别，它们是质上的差别
作者：狩人甲

　　许多人用来说明围棋比象棋复杂时，都说指出围棋有19路，而象棋只有8路，所以有数量级的差别。
这个比法是肤浅的。
　　人家可以反驳说：“7路乃至5路围棋不就没什么变化了吗，象棋扩大到19路变化不就多了吗？”
　　要解释两者质上的差别，需要引入计算机的一些理论。
　　我拿算法复杂度来比例：我们知道，如果一个问题规模为n，计算出结果需要k*n个步骤，那么这叫做线形复杂度，如果需要n的k次方个步骤，那么这叫多项式复杂度，如果需要2的n次方个步骤，那么这叫指数复杂度。
　　当两个问题规模都很小的时候，解决实际问题时体现不出谁更复杂。只有当问题规模变大的时候，你才发现，线形复杂度永远也赶不上多项式复杂度，同理多项式复杂度也无法与指数复杂度相提并论。
　　我们假设现在问题是：把象棋和围棋的全部可能棋局都枚举一遍
　　那么象棋是多项式复杂度的，而围棋比指数复杂度还高一层，我不知道这个叫什么名称，但它是类似k1的(k2的n次方)次方这样的形式。
　　从算法复杂度上来说，围棋比象棋高两个档次。
　　另外，我想从图灵机角度来对比论证一下。
　　图灵在考虑可计算的机器的性质时，首先是设想一个人在计算，他把这个人的计算行为抽象成了这样一台机器：有一条无穷长的纸带子，一个有很多状态的机器在纸带上左右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带的内容。这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论上都是可以被图灵机模拟的。
　　判断这些东西的计算能力用的是这些机器所能接受的语言的概念。乔姆斯基把语言分成了0， 1，2 ， 3四个等级，0 级能力最强，3 级最差。这四个等级之间有着难以逾越的鸿沟。
　　这里的 3级语言也叫做正规语言，就是有穷自动机能听懂的， 2级语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就可以听懂了。1 级语言就是上下文相关的了，也就是说机器还得揣摩这话前后的意思。零级语言就是图灵机可以接受的语言了。
　　现在，我们考虑这样一个问题：象棋和围棋走子后棋局状态的变化，分别需要判断几个位置上的状况？
　　象棋当我落下一子时,只要考虑落子点的状态就可以了,如果这里有我自己的子,这步落子无效,如果这里有敌人的子,敌子被我吃掉,如果这里空白,那么仅仅是棋子的移位。象王车易位,吃过路兵等情况,我们可以把它看作可以遍历的特例而暂时不予考虑（充其量后面给它加半级）。
　　让我们回想一下乔姆斯基四级语言中的2级:上下文无关语言.当排除了特殊情况之后,我们可以认为,既然国际象棋棋局某格的状态变化与周围无关,那么,它应当是可以被能听懂2级语言的机器听懂的.我们可以把国际象棋理解成一个上下文无关语言。
　　回到围棋,当我们落下一子时,棋盘会变成什么样?如果周围全是敌子,有些敌子没了气,那敌子全部拿走,如果周围有自己的子,敌子没被拿走,自己的子反而没了气,那就是自填死。
　　听起来好象也很简单,但棋盘的变化是需要看周围的情况而决定的,如果只看落子点的状态,那我们什么结论也得不到.也就是说,围棋不能用上下文无关语言来等价,至少也得用上下文有关语言,就是会数很多数的1级语言。
　　在考虑围棋变化数的时候,劫可是不能不提.有人说"劫乃围棋精华",可对于1型语言来说,劫实在是要命的东西。1型语言的基本要求是它的语言产生式左边不长于右边,但对于劫来说,并非如此.有了劫,就意味着1型语言也接受不了围棋了.
　　更要命的还在后面。象三劫循环,四劫循环,长生劫等等,如果用"全局同型禁止再现",都可以从理论上解决。但是,全局同型禁止再现对于用图灵机模拟围棋,可以说是致命的一击.因为,这意味着这台图灵机得把以前的所有状态都存储起来,而具有无限种状态数的机器不是图灵机。
　　就算没有"全局同型禁止再现"这一规则,我们可以用图灵机来接受围棋,但判断每一步的好坏必须追溯到这一局棋的终点,这意味着这台图灵机要判断它不同情况下停机时的状态!而这是图灵机所无*能为力的。
　　从上面图灵机的角度来看，围棋比象棋高了2级半。
　　也许有的读者认真去看了，有个疑问：围棋的状态数怎么会是无限种呢？
　　这里的无限不是真无限，而是针对问题规模的准无限。现实中下棋，当然下不了那么多手，因为你不是机器，你不会那么去下。
　　但是对于计算机来说，它要考虑全部可能情况，还真就能走出无穷状态的棋局来，为便于理解，你可以尝试在二路棋盘上走走看，如果不禁止全局同型，你发现它不是通常意义的劫，但是永远走不完；如果禁全局同型，你会发现要把所有点循环一遍后才出现同型。
　　这仅仅只有4个点，终局需要走到第二十四手，你想想按照超越指数方式的膨胀，361个点会导致多少手？
　　从上面两个方面，都能看出来，围棋复杂性高出象棋不止一个档次，而且这个复杂性是内在的，与棋盘大小无关。