2017年7月10日 棋艺探索
【潘达】围棋真的存在先／后手必胜么？-目前也可以认为，白方必胜的可能性大于黑方必胜。
本文来源：知乎，作者：不会功夫的潘达
围棋真的存在先手必胜／后手必胜的情况么？
本来这题只需要五个字（策梅洛定理）就可以解决，参见此答案《围棋有没有必胜策略？ – 知乎》。
但是这类问题在知乎上反复出现，我有必要针对题主的问题说明添加一些补充。
题主的疑问是，围棋双方每一步棋都有几百种合法的选择，一盘棋又有几百个回合，排列组合一下以后是天文数字。一个必胜策略，能够包含这些天文数字吗？
1、“抢三十”
我们先来看一个小学生都能理解的游戏： （来源：资优网）
小聪与小明在抢30。两个人从1 开始，轮流往下报数，每次至少报一个数，至多报三个数，谁报到30 就胜了。“1，2”，小聪开始报数。“3，4，5”，小明接着往下报。“6”。“7，8”。结果，小聪报到30，小明输了。
接连报了几次，总是小聪胜。“怎么老输？我的运气真不好。”“这不是运气。胜有胜的道理，垐有输的原因。换个玩法，你就明白了。”小聪取出一副扑克，说：“我们轮流取牌，每次至少取一张，至多取三张。这回取最后一张的算输。”
玩了几次，还是小明输。
“老是你赢，把诀窍告诉我吧。”
“诀窍很简单，把问题倒过来想。假设是你报30，那么，在这之前的一次，你应当报到多少呢？” “不能报到29，也不能报到28 或者27。要是我报到27，28，29，你就可以报30。所以，我应该报到26。要是我报到26，那么，不管你怎么报，我都能报到30 了。”
“对。要抢30，先抢26。那要抢26，先抢什么呢？”
“先抢22。”
“对。这样，我们就得到了一串取胜的数——30，26，22，18，14，10，6，2。这样，第一个人应当报到2，他就可以陆续报到6，10，14，18，22，26，30。”
“这么说来，总是第一个报数的人胜了。”
“是这样的。不过，要是他不知道诀窍，让第二个人抢去一个取胜的数，胜利就可能易手了。”
这个问题，我想对于在座各位都是很清楚的。“抢三十”，先手方有必胜策略，而且可以精确地描述：先手方先报1,2；之后，若后手方报n个数（n=1,2或3），则先手方立即回以4-n个数。最终，先手方总能抢到30。
这个具体的必胜策略，包含了多少种不同的变化呢？后手方每次有3种选择，先手方每次只有一种回应。6个回合之后，先手方就能抢到30. 因此，总变化数是3^6=729种。
那么，如果小明和小聪抢的不是三十，而是每次可以报1-299个数字，报出1,000,000者为胜呢？类似于刚才的分析，我们照样可以为先手方找到必胜策略：先手方只需先报100。然后，若后手方报n个数（n=1,2,…,299），先手方立即回以300-n个数。先手方总能抢到100,400,700,1000,…999700,1000000这一串数，从而获胜。
我们来看这一套必胜策略包含的变化。后手方每次有299种选择，先手方每次也只有一种回应。3330个回合之后，先手方就能获胜。因此，总变化数是299^3330, 不管这数多大，反正肯定比围棋的总变化数（游戏树复杂度，限定棋局在400手以内完成）要多。然而，这个数字终究是有限的. 因此，这个无聊的游戏，就算是上帝来跟我玩，只要我先手，我稳操胜券。相信各位能够理解其中的逻辑。
2、有限游戏
由此，我们引出策梅洛定理（维基百科）
定理表示在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当一必有一方有必胜/必不败的策略。
这条定理虽然是用自然语言描述，但其中的概念都很直观，没有定义上的争议。重点在于“有限”二字。上面讲的“抢一百万”游戏，虽然变化巨多，但终究有限。在2002版（最新）中国围棋规则的限定条件下，围棋也是有限游戏。
中国围棋竞赛规则（2002年版）
第一章 总则
第6条 禁止全局同形
着子后不得使对方重复面临曾出现过的局面。
这一条防止了一盘围棋无限进行下去。需要说明的是（尽管我已经说明了N次，若我不再重复，一定会有人挑刺。请了解禁全同规则的朋友原谅我的啰嗦。），“三劫循环”、“长生”等特殊棋型，在中国规则下严格说不构成循环，参见陈祖源老师的研究。现在部分比赛中将三劫循环判和棋/无胜负，是一种权宜之计，或者对局双方对规则不了解的情况下达成的协议，或者采用的是日本/韩国规则。
综上所述，围棋是个有限游戏。因此，取决于贴先数（贴子、贴目）的不同，黑方或白方之一必然有必胜/不败的策略。
围棋尽管变化繁多，但实际变化总数仍然不敌“抢一百万”这个无脑游戏。因此，围棋有一个包罗万象的必胜策略并不是什么奇怪的事。
（注：行文简洁起见，下文可能出现“黑/白方必胜（不败）”等表述，其含义为，在此局面下，黑/白方有一个必胜（不败）策略。）
3、非构造性证明
也许有些思维活跃的读者还有疑问。“抢一百万”这个游戏变化虽多，但掌握规律以后没有任何难度，因为我们有一个简单易行的必胜策略。但是围棋呢？你找得出一个具体的必胜策略吗？吴清源不能，柯洁不能，甚至AlphaGo也不能。就算是棋艺已臻化境的AlphaGo，距离围棋之神还远得很。你找不出具体的必胜策略，怎么敢打包票说要么先手必胜，要么后手必胜？
数学上，能够证明存在，而构造不出一个具体例子的概念，海了去了。我们把这样的证明叫作“非构造性证明”。
我们还是以游戏举例（来自维基百科）
A、B两人进行这样一个数学游戏：在黑板上轮流写下1到2000中的任意一个整数（含边界，A先写），但不能写下任何黑板上已存在的数的因子。问：谁有必胜策略？证明：
考虑一种新的游戏：A'、B'在黑板上轮流写下2到2000中的任意一个整数（含边界，A'先写），但不能写下任何黑板上已存在的数的因子。在这个游戏中谁有必胜策略？
如果A'有必胜策略，那么A在原游戏中也采用这个策略。注意，1在以后的过程中再也不能写上了（因为它是任何数的因子）。由于在新游戏中A'有必胜策略，所以在原游戏中，A有必胜策略。
如果B'有必胜策略，那么A在原游戏中先写上1。这就相当于构建了上述新游戏，B是新游戏中的A'，A是新游戏中的B'。由于在新游戏中B'有必胜策略，所以在原游戏中，A有必胜策略。
综上所述，A有必胜策略。
上述证明过程中并没有找出具体的必胜策略，但是仍然证明了A有必胜策略。
这个游戏没有刚才的“抢一百万”那么无脑，找出一个具体的必胜策略很有难度。但是，我们通过逻辑推理，仍然能够证明先手方必胜，不必找一个具体的策略。
同理，我们可以证明，围棋在贴先为零的情况下，执黑一方有必不败策略。
预备知识：
中国围棋竞赛规则（2002年版）
第一章 总则
第7条 终局
1、棋局下到双方一致确认着子完毕时，为终局。
2、对局中有一方中途认输时，为终局。
3、双方连续使用虚着，为终局。
第9条 计算胜负
着子完毕的棋局，采用数子法计算胜负。将双方死子清理出盘外后，对任意一方的活棋和活棋围住的点以子为单位进行计数。
双方活棋之间的空点各得一半。
棋盘总点数的一半180.5点为归本数。一方总得点数超过此数为胜，等于此数为和，小于此数为负。
证明：假设白方有必胜策略，将此策略记为S。则黑方可以在第一手选择虚手（即停一招）。现在棋盘为空枰，轮白方落子，相当于双方交换了先手。即白方变为先手方，黑方变为后手方。若白方在棋盘任意位置落子，则黑方可以模仿前文假设后手方存在的必胜策略S，获得胜利，黑胜。若白方同样选择虚手，则双方连续虚着。按照规则第7条第3款，棋局终止，计算胜负。按规则第9条，双方各得空枰的一半，平局。综上，白方不存在必胜策略，因此黑方不败。
注意：这不是模仿棋。
如果你认为黑先模仿棋必胜，你对围棋的认识还有欠缺。请来知乎 Live – 全新的实时问答 学习围棋基础知识。全套仅售299哦~
4、有贴先的围棋
当然，无贴先的围棋并不公平，只在历史上存在。现行中国规则，黑棋须贴先3.75子，以平衡先手优势。小数部分是0.75的贴先杜绝了和棋的可能。在排除和棋之后，黑白双方有且只有一方存在必胜策略。AlphaGo最新公布的自战50局，白方赢得其中38局，胜率76%。《现行围棋的合理贴目 – 知乎专栏 @湿猫》 一文中，提到3.75子的贴先规则下，职业棋手的对局，白方胜率约为53%。由此，我们可以认为，现行中国规则，对于职业棋手，白方稍优。虽然不能下确定的结论，我们也可以认为，白方必胜的可能性大于黑方必胜。因此，中国规则或许有必要引入收后还子、细化贴先，以便允许贴先数等同于日本韩国规则的6.5目。若此问题得到解决，中国规则可以说接近完美，围棋规则统一指日可待。 | 
