必胜策略，围棋之道-围棋的终极真理是否存在，上帝到底会怎样下棋

天马行空

2018年1月29日   棋艺探索

本文首发于知乎专栏——不一样的围棋，作者，不会功夫的潘达

在职业围棋圈，一部分棋手自称“求道派”。“道”者，终极真理是也。与“棋道”如影随形，“围棋上帝”、“围棋之神”也是棋手和棋迷常挂在嘴边的两个概念。在上一章节我们讲到，围棋之多变如恒河沙数，非人力所能及。思及此，棋迷朋友可能会诘问，围棋的终极真理是否存在，“围棋上帝”到底会怎样下棋。笔者将在本文解答这两个问题。（本文部分内容参考了笔者的其它回答）

1、小学生的游戏

围棋，终究还是个游戏。欲知围棋之道，我们可以先从研究一个简单的游戏入手。抢三十，一个酒桌上的小游戏，也是一道小学奥数题。它的规则是这样的：

甲和乙从1开始轮流报数，每次可以报1、2或3个数。比如甲报1,2；乙报3,4,5，甲报6，乙报7,8. 报出“30”这个数字的玩家获胜。

抢三十的诀窍，说来也不难，只需用到一点逆向思维。如果甲想抢到30，一定不能以29收尾，否则乙下回合可以直接抢到30。同理，甲也不能以28或27收尾，不然乙也能直接抢到30. 不过，若是甲以26收尾，则乙在下一回合必然抢不到30. 不仅如此，乙下一回合必然以27,28,29三者之一收尾。这样一来，轮到甲的时候，甲必然能抢到30. 因此，甲抢到26就可以保证获胜。同理，想要抢到26，甲必须抢到22、18、14、10、6、2. 我们以下图示意：

以红色的30为最终目标，橙色的26、22等数是兵家必争之地，而白色的27、28、29等数，只能过站，不可以停留。甲玩家只需一路占领2、6、10、14、18、22、26这一串等差数列，即可将胜利收入囊中。

小结一下。抢三十这个游戏，先手方（即先报数的甲玩家）有必胜策略，而且可以用数学语言精确地描述：先手方先报1,2；之后，若后手方报n个数（n=1,2或3），则先手方立即回以4-n个数。最终，先手方总能抢到30。

在博弈论（Game Theory）中，数学家把像22、26这些游戏中的“兵家必争之地”，称作必胜局面（Winning Position）。换句话说，抢到必胜局面的一方，即可稳操胜券。相应的，像27,28,29这样的节点，在此停留就会失败，被称为必败局面 （Losing Position）。

这个策略说来容易，却隐藏着许多变化。举个例子。甲报1,2，乙报3,4；这是一个回合。每一个回合，甲都会占领一个新的必胜节点。七个回合结束以后，甲才能抢到30. 每一个回合中，乙可以报一个、两个或三个数，各有三种选择。根据乘法原理，六个回合中，乙共有3*3*3*3*3*3*3=3^7=2187种策略的组合。只不过，乙的变化再多，也逃不出甲的手掌心。

那么，如果甲和乙抢的不是三十，而是每次可以报1-299个数字，报出1,000,000者为胜呢？依样画葫芦，我们仍可以为先手方找到必胜策略：先手方只需先报100。然后，若后手方报n个数（n=1,2,…,299），先手方立即回以300-n个数。先手方总能抢到100,400,700,1000,…999700,1000000这一串数，即“必胜节点”，从而获胜。

我们来看这一套必胜策略包含的变化。后手方每次有299种选择，先手方每次也只有一种回应。3330个回合之后，先手方就能获胜。因此，总变化数是299^3330。数字虽大，终究有限。因此，这个无聊的游戏，就算是上帝来和笔者玩，只要笔者拿到先手，就输不出去。这就是抢三十这类游戏的“终极真理”了。

2、完全信息游戏与策梅洛定理

抢三十这一类游戏，我们能够运筹帷幄、立于不败之地的关键是，我们知道对手所有可能的选择，我们了解游戏中所有的信息。像这样的游戏，我们称之为完全信息游戏 (Perfect Information Game) 【反例：斗地主不是完全信息游戏，因为看不到对手的牌】。另一方面，抢三十也是一个有限游戏（Finite Game），即它总是在有限个回合内完成。对于所有的完全信息有限游戏，我们都可以画出它们的游戏树 （Game Tree）。就像图论中的树一样，一个完整的游戏树包含有一个起始节点，代表游戏中某一个局面，接着下一层的子节点是原来父节点局面下一步的各种可能性，以此类推。游戏树逐层扩展，直到游戏结束。

上图是抢三十游戏树的一部分。19这个节点只与20、21、22这三个节点连接，意味着若甲报出19，则乙只能报到20、21或22. 其它节点间的连接关系同理。

抢三十游戏相对简单，在于它只有一个终局局面，或者说游戏树的末端节点，也就是30。我们很容易从这唯一的最终节点逆推出必胜策略。但是对于拥有不止一个终局局面的游戏，推理最优策略就不那么容易。这时，就轮到游戏树出场亮相了。接下来，我们再介绍一个游戏为例。

井字棋 (Tic-Tac-Toe)，又称XO棋，是一种简单的棋。对局双方轮流在3×3的棋盘上落子，在横、竖或对角线方向上连成三个的一方获胜。如下图，是从空枰开始的井字棋游戏树。

如果能完整地画出一个游戏的游戏树，那么我们就像掌握了抢三十的秘笈一样，只需按图索骥。比如说，对于井字棋游戏的一个残局，下图的游戏树给出了双方所有的应对可能性。

此残局的初始局面，由画“X”一方先行。X方有三种选择，而每一种选择下，O方也有两种应对。标有蓝色分数的棋局是终局节点，+1表示X方获胜，-1表示O方获胜，0表示平局。很明显，X方不能选择棋盘右边的两个点，否则O方可以一击绝杀。因此，X方只能走在棋盘左边。这样一来，即使O方选择正确，X方也能保证平局。游戏树第二层和第三层的部分节点标有黑色数字。这些节点并非终局，但我们可以简单推理出双方都走对情况下的棋局结果，标上+1，-1或0。同理，我们可以逐层往上标记，直到残局的初始局面，也就是游戏树的起始节点。图中，起始节点的值是0，因此我们得到结论，此残局若双方应对无误，结果是平局；X方应走在棋盘左中的一点。

井字棋完整游戏树，来自Wikipedia

更进一步，如果我们画出井字棋的完整游戏树（如上图），我们就可以用同样的方法，逆推出游戏树中每一个节点最终会走向何种结果，最终推出双方的最优策略，以及在最优策略下谁胜谁负。事实上，如果从空枰开局，双方不犯错的情况下，井字棋会以平局收场。

所有的二人完全信息有限游戏，如果没有运气成分（例如飞行棋掷骰子），在理论上我们都可以用同样的方法，画出游戏树，从结果逆推到开局。数学家恩斯特·策梅洛（Ernst Zermelo）将这个结果总结为策梅洛定理（Zermelo's Theorem），表述如下：

若二人完全信息有限游戏不涉及随机成分，则要么先行方有必胜策略，要么后行方有必胜策略，要么双方均拥有必不败策略（即若双方都不犯错，游戏将会是平局）。

策梅洛定理的严格证明，其实和前文井字棋部分所述类似。在确定游戏树之后，从所有终局局面出发，可以推断出任意局面的胜负性（即此局面何方有必胜策略，或者双方均有不败策略），直至初始局面。在数学上，这种推理的方法，被称为反向数学归纳法（Backward Induction）。

策梅洛定理适用于大部分为人熟知的棋类游戏，比如国际象棋、五子棋、黑白棋、西洋跳棋等，但不适用于涉及运气成分的飞行棋，也不适用于多方混战的中国跳棋。

3、围棋，有限游戏？

读到这里，性急的读者可能已经脱口而出，“那么，围棋当然也适用策梅洛定理，一定存在某一方的必胜策略嘛”。且慢。围棋确实符合“二人”、“完全信息”、“无随机因素”这三个特点，但“有限”这个性质，我们暂时还得打个问号。

有记载的职业棋局，最长手数记录是414手（林修平VS陈禧一），超过了围棋盘交叉点的总数361个。但这并不是一局围棋长度的上限。能够无限进行下去的棋局，其实在职业比赛中已经出现过多次。比如下图，古力和李世乭在2012年三星杯32强双败淘汰赛首轮的一局。

由于棋盘右方罕见的四劫循环，本局被判“无胜负”，双方重赛。注意，本局的结果是“无胜负”，而不是和棋（平局）。“无胜负”隐含的意思是，这盘棋可以无限进行下去。在规则没有禁止的情况下，黑白双方将反复提四个劫，循环往复。

对应到围棋的游戏树中，多劫循环是一种循环(loop)结构。

比如，在上图中，节点1-2-5和节点2-3-4-5分别构成循环。循环使得策梅洛定理中的反向归纳法失效，不适用于有循环的游戏。

好在，现行中国围棋规则在原则上禁止多劫循环，也包括长生等其他特殊的循环棋型。

.中国围棋竞赛规则（2002年版）

.第一章 总则

.第6条 禁止全局同形

.着子后不得使对方重复面临曾出现过的局面。

本条规则有时简称“禁全同（SuperKo）”或“禁同形”。在部分比赛中，禁全同规则并未得到严格执行。本章节剩余的部分，我们仍基于严格的禁全同规则来讨论。在严格禁同的情况下，循环不复存在。即使局面再多，一盘棋也不能无限进行下去。

综上所述，禁全同的围棋是有限游戏，适用策梅洛定理。取决于贴先的不同，黑方或白方之一肯定有必胜或不败的策略。现行中国规则，黑贴3又3/4子，杜绝了和棋的可能性。因此，黑方或白方之一肯定有必胜策略。如果采用旧时的不贴目规则，允许和棋，则要么黑方有必胜策略，要么白方有必胜策略，要么双方均有必不败策略。

4、存在而不可知的必胜策略

也许思维活跃的读者还有疑问。黑白双方之一有必胜策略，这个回答并不令人满意。想必读者更关心的问题是，到底是黑棋必胜，还是白棋必胜。前文介绍的抢三十，变化不少，但掌握规律以后没有任何难度，因为先手方有一个简单易行的必胜策略。无禁手的五子棋倒是很复杂，但资深爱好者大多也知道花月局加蒲月局可以保证黑方必胜。

图注：五子棋花月开局。其后变化虽复杂，但黑方总有确定获胜的路线。

但是围棋呢？我们在前一章节介绍了围棋变化总数之多。既然如此，找出一个具体的必胜策略，可行吗？事实上，吴清源不能，柯洁不能，甚至AlphaGo也不能。就算是棋艺已臻化境的AlphaGo，距离围棋之神还远得很。如果找不出具体的必胜策略，怎么敢打包票说要么先手必胜，要么后手必胜？

数学上，能够证明存在，而构造不出一个具体例子的概念，实在太多太多。我们把这样的证明叫作“非构造性证明（Non-constructive Proof）”。接下来，我们将介绍一个数学游戏，并以此进一步展示非构造性证明。

A、B两人进行这样一个数学游戏：在黑板上轮流写下1到2000中的任意一个整数（含边界，A先写），但不能写下任何黑板上已存在的数的因子。

因为一共只有两千个数可以写，所以这个游戏不会无限进行下去，符合策梅洛定理的应用条件。换句话说，要么A有必胜策略，要么B有必胜策略。问题来了，谁有必胜策略呢？

答案是先手方，A有必胜策略。

证明：

考虑一种新的游戏：A'、B'在黑板上轮流写下2到2000中的任意一个整数（含边界，A'先写），但不能写下任何黑板上已存在的数的因子。在这个游戏中谁有必胜策略？

如果A'有必胜策略，那么A在原游戏中也采用这个策略。注意，1在以后的过程中再也不能写上了（因为它是任何数的因子）。由于在新游戏中A'有必胜策略，所以在原游戏中，A有必胜策略。

如果B'有必胜策略，那么A在原游戏中先写上1。这就相当于构建了上述新游戏，B是新游戏中的A'，A是新游戏中的B'。由于在新游戏中B'有必胜策略，所以在原游戏中，A有必胜策略。

综上所述，A有必胜策略。

上述证明过程中并没有找出具体的必胜策略，但是仍然证明了A有必胜策略，乃是非构造性证明的一个良好范例。注意到，“如果B'有必胜策略”一段，假设了一个后手方的必胜策略，然后再交给原游戏中的先手方A使用。这种证明方法，在博弈论中被称为“策略复制论证（Strategy-stealing argument）”。对于具有对称性的游戏，策略复制论证总能证明先手方不败。

用相似的思路，我们可以证明，无贴目的围棋，执黑一方有必不败策略。不过，我们需要特别小心，无贴目围棋的对称性非常微妙。为此，我们需要引用部分中国围棋规则的条文作为预备知识：

中国围棋竞赛规则（2002年版）

第一章 总则

第7条 终局

1、棋局下到双方一致确认着子完毕时，为终局。

2、对局中有一方中途认输时，为终局。

3、双方连续使用虚着，为终局。

第9条 计算胜负

着子完毕的棋局，采用数子法计算胜负。将双方死子清理出盘外后，对任意一方的活棋和活棋围住的点以子为单位进行计数。

双方活棋之间的空点各得一半。

棋盘总点数的一半180.5点为归本数。一方总得点数超过此数为胜，等于此数为和，小于此数为负。

现在我们可以正式开始证明了。

根据策梅洛定理，无贴目的围棋，要么黑方有保证不败的策略，要么白方有必胜策略。假设白方有必胜策略的，将此策略记为S。

对此，黑方可以在第一手使用虚着（即停一招）。现在棋盘为空枰，轮白方落子，相当于双方交换了先手。即白方变为先手方，黑方变为后手方。

若白方在棋盘任意位置落子，则黑方可以复制前文假设后手方存在的必胜策略S，获得胜利，黑胜。

若白方同样选择虚手，则双方连续虚着。按照规则第7条第3款，棋局终止，计算胜负。按规则第9条，双方各得空枰的一半，平局。

综上，假设的后手方必胜策略S不存在，因此先手方（黑方）不败。

注意：这不是模仿棋。

5、最优贴目值

当然，即使没有数学证明，不贴目的围棋不公平，也是显而易见的。在近代日本，黑棋属于下手，用来平衡与上手的实力差距。现行中国规则，黑棋须贴先3又3/4子，以平衡先手优势。贴先小数部分的3/4子杜绝了和棋的可能。在排除和棋之后，黑白双方有且只有一方存在必胜策略。额外的贴先破坏了对称性，策略复制论证法不再成立。因此，仅从数学上，我们无从得知黑方必胜还是白方必胜。我们可以确定无误的是，存在一个最优贴目值（Game Theory Value），记作X，满足以下性质：

1.X是一个非负整数（脚注：此处的贴目值按数目法定义，如X=7目。如果用中国规则的贴子，则X的小数部分可以是1/2，比如X=3又1/2子。）；

2.贴目值为X时，先后手双方均存在不败策略；即双方都不犯错，结果是和棋；

3.贴目值大于X时，后手方有必胜策略；

4.贴目值小于X时，先手方有必胜策略。

这几条性质非常直观，证明起来也不困难，我们交给读者思考。

在小棋盘上，最优贴目值并不难确定。比如，对于二路(2×2)棋盘，X=0.

对于五路及以下的小棋盘，计算机穷举即可证明最优贴目值。但七路及以上的围棋，变化已经极多，超过了计算机目前的穷举能力。七路棋盘，围棋手有比较深入的研究。上世纪八十年代，日本的一些围棋爱好者与工藤纪夫等职业棋手合作，完成了七路棋盘最优解的研究。2015年，李喆等职业棋手也独立完成了相似的研究。他们的结论完全一致——七路盘，9目是最优贴目值。

（图注：七路盘最优解一变）

基于围棋知识的研究虽然没有穷举所有变化，但也足够有说服力。换句话说，知道了最优贴目值，等价于知道了空枰开局时双方的最优策略。这在博弈论中被称为弱解构（Weak solution）. 对应地，强解构（Strong solution）需要知道从任何局面开局时双方的最优策略。而像十九路盘上无贴目的棋局，我们只知道何方有不败策略，而不知怎么走棋才能不败，这种情况被称为超弱解构（Ultra-we ak solution）。

小棋盘的最优解，棋手的研究也就到此为止了。即使是被普遍视作小朋友入门用的九路围棋，其变化之多也远远超出了职业棋手的研究能力；当然，更是远远超出计算机的穷举能力。在前面章节提过，十九路围棋的变化数相比于九路围棋，何止几何级增长。从而，寻找最优策略是一件遥不可及的任务。换句话说，我们也无从得知最优贴目值是多少。贴3又3/4子规则下，我们连何方有必胜策略都不知道，也就是连超弱解构都做不到。

唯一的安慰是，人类发明的人工智能，为我们掀开了真理的一角。AlphaGo在2017年5月公布的自战50局，白方赢得其中38局，胜率76%。因为AlphaGo的水平极高，我们可以据此认为，贴3又3/4子的棋局对白方有利。这和近年来职业棋手在大贴目对局下的感受、实际胜负统计相符。笔者在此下一个模糊的结论：十九路围棋，最优贴目值X很可能小于7目半（3又3/4子）。

6、围棋之道

本章写到这里，没有讨论任何围棋的技术，围棋之道却已呼之欲出。

道，即为终极真理，就是掌握一切。

在抢三十游戏中，终极真理就是先抢到26,22等一系列关键数字。对于七路围棋，职业棋手对于种种变化详尽的研究，基本上揭示了七路围棋的终极真理。

十九路围棋的终极问题是，最优贴目值是多少。解决最优贴目值问题，意味着了解空枰开局时双方的最优策略。用我们刚刚提到的术语，叫做弱解构围棋。

如果要求更高一点，希望知道所有奇形怪状局面下的最优策略，即强解构围棋，这是围棋上帝干的活。

这就是棋道了。

十九路围棋之道，和七路围棋之道，看上去只是复杂程度的区别。不过，其变化总数跨度之大，量变引发了质变。我们已经掌握了七路围棋的几乎所有变化，却永远不可能掌握十九路围棋的所有变化。

前文提到，十九路围棋盘的所有合法局面数，10的170次方。比较一下，西洋跳棋的合法局面数，10的20次方，在近年被弱解构。国际象棋的合法局面数，约10的50次方，弱解构遥遥无期。目前最牛的超级计算机，中国的神威·太湖之光，每秒运算次数10的17次方。通过穷举的方式破解围棋，我们一台需要每秒运算次数10的165次方的计算机。

10的165次方，这不是人类的领域。这是神祇，或者外星人的领域。

“棋道一百，我只知其七。”藤泽秀行名誉棋圣之言，曾被认为是自谦。然而，人类已经了解的围棋，从比例上来看，远远不及变化总数的百分之七，诚为沧海一粟。

即使如此，人类也从未放弃对棋道的追求。从围棋十诀到AlphaGo，我们集跬步而成千里。也许有一天，刘慈欣《诗云》中无所不能的李白文明，带着量子存贮器中收集的《真·围棋10的170次方变化大全》来和地球人对弈，人类的ZetaGo也能胜天半子。就像祁同伟，哦不，《天局》中的浑沌那样。

本文首发于知乎专栏——不一样的围棋，专栏地址——https://zhuanlan.zhihu.com/godifferent