象棋和围棋都是中华文明的瑰宝，更是训练和测试思维能力的方式之一，那些在这两种棋类上取得成就的人们，其智商普遍得到公众认可。但是，我们是否想过，在这两种棋类上是否存在必胜或者平局的策略？答案是存在的，这是策梅洛关于双人完全信息博弈的一个定理的结论。本文将详细介绍这个定理的证明，并将其用于诸如五子棋的分析中。如无特殊说明，后文所提及的游戏都是双人游戏。
什么是最优策略
为了让大家对最优策略有一个直观的理解，这里举一个小游戏作为例子。这个小游戏叫Chop，在游戏的最开始有一个m×n的网格(下图是一个4×6网格示例)，游戏由两位玩家轮流操作，每位玩家每轮可以沿着一整根竖网格线或者一整根横网格线将网格割掉一块，割到只剩下一个小方格的玩家为胜者。注意，不能沿着剩余网格的边界线做切割，例如不能沿着下图的AB线切割，但是沿着CD线或者EF线切割都是可以的。每次切割完之后网格会被分成两块，由操作切割的玩家决定留下哪一块。
对于这类双人游戏，一般会有最先进行操作的玩家，我们将其称为先手，另一位被称为后手。如果一开始的时候m和n其中一个数为1，比如n=1，先手玩家可以直接切割掉(m-1)个格子即可获得胜利，这个策略就是先手玩家的最优策略。如果对于一般的m和n，先手或者后手怎样才能保证获胜呢？读者可以稍作思考，再接着往下看。
其实很简单，如果m和n不相等，那么先手的最优策略会导致必胜的结果：这时候先手玩家只要割掉其中一块使得剩下的网格是个长和宽相等的网格即可。这样，无论后手切割哪条线，都是在长和宽相等的基础上进行切割，最后必然得到一个长宽不相等的网格，也就不可能是单独一个网格。先手玩家只要每一步实行这个策略，无论后手玩家怎么操作，先手玩家都会获胜。这时候读者肯定明白了，当m=n的时候，无论先手玩家怎么操作，后手玩家都可以借助前述一样的策略获胜。
完全信息博弈和策梅洛定理
现在回到一般游戏的讨论上。策梅洛定理适用于被称为完全信息博弈的一类游戏。所谓完全信息博弈，指的是游戏的所有信息都是公开的，游戏双方都能清楚了解到目前游戏所处的状态信息，并且游戏的每一步都不涉及概率因素。这个条件把扑克、飞行棋、暗棋和翻棋玩法下的军棋都排除掉了。然后，我们还需要这个游戏能在有限步内结束，并且，游戏的结局要么是平局要么有一方是胜者。很明显，围棋是属于完全信息博弈的。至于象棋，有可能会进入循环状态从而整个游戏没完没了。为了避免这一点，我们可以加入一些新规则使得象棋不会出现循环，比如，设定一个很大的数N，只要连续N步双方都没有被吃掉棋子就判为和棋，或者不允许超过N次进入同一种棋子状态，否则判为和棋。加入这些规则或者类似的规则之后，象棋就满足要求了。
下面给出策梅洛定理的严格表述：在双人完全信息博弈下，只有三种情况：要么先手具有必胜策略，要么后手具有必胜策略，要么双方的最优策略会导致平局。比如前面所说的Chop游戏，当m≠n时，先手玩家具有必胜策略；如果m=n，后手玩家具有必胜策略。Chop游戏没有平局。策梅洛定理是一个结论很强的定理，下面我们会发现，它的证明非常简单，不需要用到很高深的知识。
策梅洛定理的证明
为了证明策梅洛定理，我们需要引入一个小小的概念：游戏树。在游戏的每一步，玩家有很多种走法，每一个走法都会产生新的分支，把两位玩家的所有可能走法考虑进来，就会得到一个树状结构。这个树状结构穷尽了游戏过程的所有可能性。下图是Chop游戏在1×4情况下的游戏树。在本文，我们用(1,0)表示先手获胜，(0,1)表示后手获胜，(0,0)表示平局。
在游戏树上，节点会标注上游戏状态，比如上图中的方格。有时候为了信息完全，还会标注上在此节点轮到哪位玩家操作了。因为我们把游戏循环往复的可能性排除了，游戏状态转移图不会出现圈图，所以必然是树图。(对于象棋，如果用A表示棋子状态，加上了前文所述的其中一个规则后，整个游戏状态将由(A, i)表示，其中i表示已经连续i步双方都没有被吃掉棋子或者已经i次进入棋子状态A了。在这样的表示下，当i不等于j时，(A, i)和(A, j)哪怕棋子状态都是A，但是依然代表不同的游戏状态。于是，象棋的游戏转移也不会出现圈图。)
接下来，我们假设每一位玩家都是理智的，当玩家处于游戏树的某个节点时，她/他必然会选择对其最有利的走法。假如现在游戏状态来到了倒数第二步，再走一步游戏将结束了，那么我们就会看到游戏树的末端，大概是如下图这样的，其中省略号表示未画出的末端节点
在上图的游戏树中，如果在A处轮到先手玩家操作了，那么她/他必然会选择走向B。走向C和D对先手玩家来说都不是最优走法。于是，A虽然不是末端节点，但是它依然可以带有胜负信息(1,0)，这个胜负信息表示先手方在A处只要按最优策略走就会获胜。当然，上图只是一个例子，有可能末端节点都不是(1,0)状态的，这时候对先手玩家来说最优策略就是走到平局状态(如果有平局末端的话)，这样A节点将会带有(0,0)的胜负信息。如果是最坏情况，节点A下的所有末端节点都对应(0,1)的胜负，那么在A处无论先手玩家怎么走都必输，于是节点A带有的胜负信息是(0,1)。假如我们给胜负引入大小关系：(1,0)>(0,0)>(0,1)，那么前述得到A的胜负信息的分析可以总结为：轮到先手方操作，A节点的胜负=A的下一级节点的胜负最大值。另一方面，如果在A处轮到后手玩家操作了，我们也可以通过类似的分析得到A处的胜负信息，只不过最大值要换成最小值：轮到后手方操作，A节点的胜负=A的下一级节点的胜负最小值。
得到了A处的胜负信息之后，我们就可以忽略A下面的所有节点了，这时候A就成了一个末端节点，它带有相应的胜负信息，这个胜负信息表示从该节点出发，两位玩家都使用最优策略后会导致的胜负结局。这个操作可以继续进行下去，不断得到上一级节点的胜负信息，然后忽略掉旧的末端节点。如此往复，因为树是有限高的，最终我们会得到游戏一开始那个节点(术语叫根节点)的胜负信息。如果根节点的胜负信息是(1,0)，那么意味着先手玩家只要按最优策略走下去就会必胜；如果根节点的胜负信息是(0,1)，那么意味着后手玩家具有必胜策略；如果根节点的胜负信息是(0,0)，那么意味着双方的最优策略会导致平局。至此，策梅洛定理证明完毕。
从下往上的胜负信息推导
如何确定谁才具有必胜策略：策略窃取
想必读者已经跃跃欲试了，如果知道了象棋或者围棋的最优策略，岂不是在棋坛上横着走？可惜的是，虽然策梅洛定理的证明是构造性的，但是构造过程需要我们先得到整个游戏树，而像围棋这类棋，游戏的路径(指从根节点到末端节点的一条路径)比宇宙的原子数目还要多，要想通过整个游戏树来得到最优策略是不可能的了。如此说来，策梅洛定理仅仅给必胜或者平局策略提供了存在性。不过，借助策梅洛定理所提供的存在性，我们可以利用被称为策略窃取的方法证明在某些游戏上后手不存在必胜策略，换言之，先手有不败策略。
本文将以著名的五子棋为例介绍策略窃取是怎么一回事。很明显，五子棋满足策梅洛定理的条件，于是有且仅有三种可能性：先手具有必胜策略、后手具有必胜策略、双方的最优策略会导致平局。接下来我们使用反证法。假如后手具有必胜策略，我们把这个策略称为S。这时候无论先手玩家怎么走，后手玩家只要使用策略S，先手玩家必输。
策略窃取的要点就是把对方的策略“窃取”过来。先手玩家先在棋盘上随便放一个棋子，位置记为P1，然后假装这个棋子不存在。这时候轮到后手玩家放子了，由于假装P1上的棋子不存在，后手玩家成了“先手”，而先手玩家成了“后手”，于是先手玩家可以使用必胜策略S。根据这个策略的必胜性质，无论对方怎么走，“后手”玩家(也就是先手玩家)都将获胜。不过，事情似乎没那么简单。我们只是假装P1上的棋子不存在而已，实际上这个棋子是存在的。P1位置上的棋子会怎么影响到策略S的使用呢？假如走到了某一步，策略S要求“后手”玩家将棋子放在P1位置，这时候P1已经存在“后手”玩家的棋子了，但是游戏要求玩家每一步都不能不下棋子，此时“后手”玩家可以在这一步把棋子下在其他的任意位置，记为P2。这样的话P1和P2都占据了“后手”玩家的棋子，这就等价于游戏一开始“后手”玩家将棋子下在了P2，并且在目前这一轮“后手”玩家根据策略S的要求把棋子下在了P1位置。如果接下来策略要求棋子下在P2，那么“后手”玩家可以任意把棋子下在P3位置……如此类推，先手玩家可以完美使用策略S，于是会必胜。这和反证法的假设相矛盾。于是，五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局。或者更简洁地表述为，先手具有不败策略。
回顾前述关于五子棋的讨论，这个“五”字完全没有体现出来，我们完全可以把相关结论推广到四子棋、六子棋等等。特别地，井字棋本质上是一种三子棋，由于它的游戏树很简单，我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略。
在哪都能玩的井字棋
转载内容仅代表作者观点
不代表中科院物理所立场
来源：中科院理论物理研究所
原标题：DoctorCurious 26: 什么？象棋和围棋都存在不败策略？
编辑：藏痴
