围棋有没有必胜策略?
的有关信息介绍如下:
简单回答:存在必胜策略,可以证明存在必胜策略;但是人类现在没有找到必胜策略,在可以看到的将来也很可能找不到必胜策略。
解释:
“围棋是否存在必胜策略”这一问题其实是一个并不复杂的数学问题,不过其中有一个难点。
我们首先需要以下这个重要定理:
以上是策梅洛定理的非正式陈述。严格的陈述涉及博弈论的一些术语,稍微复杂,不过在这里非正式陈述就足够了。注意到,和国际象棋一样,围棋也是“二人、完全资讯、不涉及运气因素”的回合制游戏。
这里唯一有可能产生争议的地方是围棋是否为“有限游戏”,即一盘围棋是否总会在有限步之内结束。这个小问题涉及到围棋规则。目前围棋界有中国规则、日本规则、韩国规则、应氏规则等主流规则,也有美国规则、新西兰规则等改进版。这些规则中,除了数目和数子的差异之外,另一个主要差异在于“禁全同”,即是否“禁止全局同形再现”。而围棋规则研究者、数学家和计算机科学家一般公认采用“禁全同”的中国规则和类似规则(美国、新西兰)为逻辑自洽的规则,而日本、韩国规则有逻辑上的缺陷。
以上即所谓“禁全同”规则。关于“禁全同”可能造成的所谓“悖论”,请移步
。
严格采取“禁全同”的中国规则下,三劫循环不判和,而等效于打一个单劫。包括长生、双提二子等特殊棋形类似。这样一来,与3又3/4子的贴子(贴目)一起,和棋(无胜负)就不可能出现了。(当然现有中国规则在执行中仍然将三劫循环判为无胜负,这只是一个暂时的妥协。)
同时,围棋就变成了一个妥妥的有限游戏。事实上,计算机科学家已经给出了一个(19路)围棋所有可能局面的上界:2.08*10^170 (
)。
那么我们已经解决了采用策梅洛定理的所有小前提。根据策梅洛定理,在02版中国规则(黑贴3又3/4子,严格禁全同)下,对于19路围棋,以下两者之一有且只有一个成立:
1、黑方(先行者)有必胜策略;
2、白方(后行者)有必胜策略;
注意到,因为贴目(3.75子/7.5目)为非整数,和棋不存在,所以必不败策略等价于必胜策略。
那么到底是1还是2成立呢?我们不知道,也许我们很久以后也不能知道。
要证明其中之一成立,需要对围棋的游戏树进行穷举。然而10^170仅仅是局面(position)的数量而已,游戏树(棋局总数)是对所有局面的排列,不知道大到哪里去了,穷举谈何容易!在计算机产生革命性的变化之前恐怕是不用想了。
然而,我们可以做出这样一个大胆的猜测:
存在一个非负整数X, 使得:
1、当贴目小于X时,黑方有必胜策略;
2、当贴目大于X时,白方有必胜策略;
3、当贴目等于X时,双方最佳应对,结果是和棋。
直观上这很可能是对的,不过我不会证。
-----------------------------更新割----------------------------------
我尝试证明一下,不知道对不对。第一遍阅读以下部分可以直接跳过,哈哈
事实1:贴目为-361目(即白贴黑361目)时黑棋不败;
事实2:贴目为361目时白棋不败;
定理(策梅洛):当贴目值为Y时(Y为任意整数),以下三者有且只有一个成立:
a)黑棋有必胜策略;b)白棋有必胜策略;c)黑白双方均有不败策略,即最佳应对下双方为和棋。
引理1:假设贴目为X时黑棋有不败策略(X为任意整数),那么贴目为X-1时黑棋有必胜策略;
同样地,假设贴目为X时白棋有不败策略,那么贴目为X+1时白棋有必胜策略。
证明:假设贴目为X时黑棋有不败策略,即存在一个黑方策略,使得(无论白棋怎么下),黑方至少盘面X目;那么黑棋在贴目为X-1时采取同样策略即可获胜。
推论1:假设贴目为X时双方均有不败策略,那么贴目小于X时黑方有必胜策略,贴目大于X时白方有不败策略。
证明:数学归纳法
引理2:假设贴目为X时黑棋有必胜策略,那么贴目为X+1时以下两者有且只有一个成立:
a)黑棋有必胜策略;b)黑白双方均有不败策略;
证明: 假设贴X目黑必胜。那么对于黑棋,存在一种策略,使得不管白方怎么应对,黑方在终局时都能够至少盘面X+1目(否则贴X目黑棋不是必胜)。那么在贴X+1目的情况下,黑棋只需采取相同的策略就可以至少保住和棋,即白方不能必胜。
定理:存在一个整数X(-361<X<361), 使得:
1、当贴目小于X时,黑方有必胜策略;
2、当贴目大于X时,白方有必胜策略;
3、当贴目等于X时,双方最佳应对,结果是和棋。
证明:假设不存在这样的X。根据事实1和引理2,可以得出当贴目Y满足(-361<Y<361)时,黑方均有必胜策略(否则根据引理2,存在某一个Y,黑白双方均有不败策略,再根据引理1,该Y就是所求的X)。即贴目为360时黑方必胜,贴目为361时白方必胜。这又与引理2矛盾。故假设不成立,证毕。
这里只能证明X是一个整数,而不是正整数。虽然直观上看X几乎一定是个自然数,但是想要证明黑棋在不贴目的情况下有不败策略好像也很难(还是不可能?)。注意模仿棋可以被轻易破解。
-----------------------------------------------------------------------------
从现在棋手胜率的统计来看,这个X很可能就在7-8左右。
“柯洁认为贴6目半都多了。。仅供参考”
然而我们已经确定的是什么呢?
19路不知道谁赢,小棋盘总知道谁赢吧。
从1*1到5*5的棋盘,包括一些长方形的(5*6,2*10, 等等)棋盘,学者已经通过穷举找到了上述的X值,都在以上链接里。不管怎么样,这也是一个进步吧。有关于小棋盘上围棋的拆解,可以移步一下答案。
----------------------------------------更新割---------------------------------
插播一篇文学作品。刘慈欣《诗云》节选



