微信号:bigdatalab

介绍:宽客俱乐部旗下美国大数据实验室,大数据研究应用.

围棋有没有必胜策略?

2016-01-26 08:53 大数据实验室

先手贴目从上古时代的零一直增加到现在的七目半,是否说明了正在向必胜策略逼近,未来贴目是否还会继续增加?


简单回答:存在必胜策略,可以证明存在必胜策略;但是人类现在没有找到必胜策略,在可以看到的将来也很可能找不到必胜策略。


解释:

“围棋是否存在必胜策略”这一问题其实是一个并不复杂的数学问题,不过其中有一个难点。
我们首先需要以下这个重要定理


策梅洛定理(英语:Zermelo's theorem)是博弈論的一條定理,以恩斯特·策梅洛命名。定理表示在二人的有限遊戲中,如果雙方皆擁有完全的資訊,並且運氣因素並不牽涉在遊戲中,那先行或後行者當一必有一方有必勝/必不敗的策略。若運用至國際象棋,則策梅洛定理表示“要麼黑方有必勝之策略、要麼白方有必勝之策略、要麼雙方也有必不敗之策略”。


以上是策梅洛定理的非正式陈述。严格的陈述涉及博弈论的一些术语,稍微复杂,不过在这里非正式陈述就足够了。注意到,和国际象棋一样,围棋也是“二人、完全资讯、不涉及运气因素”的回合制游戏。


这里唯一有可能产生争议的地方是围棋是否为“有限游戏”,即一盘围棋是否总会在有限步之内结束。这个小问题涉及到围棋规则。目前围棋界有中国规则、日本规则、韩国规则、应氏规则等主流规则,也有美国规则、新西兰规则等改进版。这些规则中,除了数目和数子的差异之外,另一个主要差异在于“禁全同”,即是否“禁止全局同形再现”。而围棋规则研究者、数学家和计算机科学家一般公认采用“禁全同”的中国规则和类似规则(美国、新西兰)为逻辑自洽的规则,而日本、韩国规则有逻辑上的缺陷。


2002中国现行围棋规则
-------------------
第一章 总则
第6条 禁止全局同形
着子后不得使对方重复面临曾出现过的局面


以上即所谓“禁全同”规则。


严格采取“禁全同”的中国规则下,三劫循环不判和,而等效于打一个单劫。包括长生、双提二子等特殊棋形类似。这样一来,与3又3/4子的贴子(贴目)一起,和棋(无胜负)就不可能出现了。(当然现有中国规则在执行中仍然将三劫循环判为无胜负,这只是一个暂时的妥协。)


同时,围棋就变成了一个妥妥的有限游戏。事实上,计算机科学家已经给出了一个(19路)围棋所有可能局面的上界:2.08*10^170 (Counting Legal Positions in Go)。


那么我们已经解决了采用策梅洛定理的所有小前提。根据策梅洛定理,在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目半都多了。。仅供参考”
然而我们已经确定的是什么呢?


First player scores MxN Go


19路不知道谁赢,小棋盘总知道谁赢吧。
从1*1到5*5的棋盘,包括一些长方形的(5*6,2*10, 等等)棋盘,学者已经通过穷举找到了上述的X值,都在以上链接里。不管怎么样,这也是一个进步吧。


来源:专吃刘小羊(知乎)







招聘启事


某投资公司因拓展业务需要,现招聘以下人员,欢迎发送简历至邮箱,简历中请注明应聘职位名称、期望薪金。

1.量化投资经理

2.新三板项目经理
3.金融行业人力资源顾问
4.网站微信编辑(财经/金融/投资)
5.活动策划与执行专员


工作地点:上海浦东

简历发送邮箱:5424567@qq.com


招聘详情请点击下面”阅读原文“


 
大数据实验室 更多文章 用户画像数据建模方法 李光斗:警方是如何利用大数据抓到王全安的 降楼价,新加坡居然靠的是无人驾驶! 小数法则和经验主义 什么性格的人适合 Quant 这个职位?能否描述一下 Quant 一天的生活是怎样的?
猜您喜欢 iOS移动开发周报-第1期 你们关心的一些问题 智能城市方案:OpenStack合力K8s打造IoT平台 深度学习与推荐系统 深入浅出 RecyclerView