摘要:

策梅洛定理的证明?策梅洛定理证明?象棋和围棋是中华文明的瑰宝，也是训练和检验思维能力的方式之一。在这两种棋上有所成就的人，智商一般都是大众公认的。但是，我们有没有想过，这两种棋，到底有没有胜或平的策略？答案是存在的，这是泽梅洛定理对两人完全信息博弈的结论。本文将详细介

象棋和围棋是中华文明的瑰宝，也是训练和检验思维能力的方式之一。在这两种棋上有所成就的人，智商一般都是大众公认的。但是，我们有没有想过，这两种棋，到底有没有胜或平的策略？答案是存在的，这是泽梅洛定理对两人完全信息博弈的结论。本文将详细介绍这一定理的证明，并以五子棋分析为例加以应用。除非特别说明，以下段落提到的游戏都是双人游戏。

最优策略是什么？

为了让你对最优策略有一个直观的认识，这里以一个小游戏为例。这个小游戏叫Chop。游戏开始时有一个mn的格子(下图是一个46的格子的例子)。游戏由两个玩家轮流操作。每个玩家可以在每一轮中沿着一条完整的垂直网格线或一条完整的水平网格线切下一块网格，只切下一块小网格的玩家获胜。注意不能沿着剩余网格的边界线切割，比如不能沿着下图的AB线切割，但是可以沿着CD线或者EF线切割。每次切割后，格子会被分成两块，操作切割的玩家会决定留下哪一块。

对于这种双人游戏，通常会有第一个玩家来操作，我们称之为第一个玩家，另一个玩家称为第二个玩家。如果一开始M和N中有一个是1，比如n=1，那么先手玩家可以直接切掉(m-1)个方块获胜。这个策略对于第一手玩家来说是最佳策略。如果平均M和N，第一手或者第二手怎么保证胜利？读者可以思考片刻，然后继续阅读。

其实很简单。如果M和N不相等，那么第一手牌的最佳策略会导致一个获胜的结果：此时，第一手牌的玩家只需要砍掉其中的一个，使得剩下的格子是一个长宽相等的格子。这样，无论哪一行被后继者切割，都是在长宽相等的基础上切割，最后必然得到一个长宽不相等的网格，所以不可能是单个网格。只要第一个玩家每一步都执行这个策略，不管第二个玩家怎么操作，第一个玩家都会赢。这时，读者必须明白，当m=n时，无论第一个玩家如何操作，第二个玩家都可以通过与上述相同的策略获胜。

完全信息博弈与策梅洛定理

现在我们回到一般游戏的讨论。泽梅洛定理适用于一类叫做完全信息博弈的博弈。所谓完全信息博弈，就是博弈的所有信息都是公开的，博弈双方都可以清楚地知道博弈的当前状态信息，博弈的每一步都不涉及概率因素。这个条件排除了扑克、飞行棋、暗棋、翻转棋下的军棋。然后，我们还需要游戏在有限的几步内结束，游戏的结局要么是平局，要么是赢家。很明显，围棋属于完全信息博弈。至于象棋，有可能会进入循环状态，整个游戏没完没了。为了避免这种情况，我们可以增加一些新的规则，这样象棋就不会出现循环。比如设置一个大数n，只要连续n步双方都没有被吃掉就判定为和局，或者不允许进入同一个棋局状态超过n次，否则判定为和局。加入这些规则或类似的规则后，象棋就符合要求了。

以下是泽梅洛定理的严格表述：在两人完全信息博弈中，只有三种情况：要么第一人有赢的策略，要么第二人有赢的策略，要么双方的最优策略会导致平局。比如上面说的剁手游戏，当mn时，第一个玩家有获胜策略；如果m=n，后继玩家有一个获胜策略。砍人游戏没有平局。泽梅洛定理是一个结论性很强的定理。下面我们会发现，它的证明非常简单，不需要用到非常高深的知识。

策梅洛定理的证明

为了证明泽尔梅洛定理，我们需要引入一个小概念：博弈树。在游戏的每一步，玩家都有很多招式，每一个招式都会产生一个新的分支。把两个玩家所有可能的移动都考虑进去，你会得到一个树形结构。这种树形结构穷尽了游戏过程的所有可能性。下图是14的情况下，砍游戏的游戏树。在本文中，我们用(1，0)表示第一手赢，(0，1)表示第二手赢，(0，0)表示和棋。

在游戏树上，节点会标有游戏状态，比如上图中的方块。有时候为了完成信息，会标注轮到哪个玩家在这个节点操作。因为我们排除了游戏循环的可能性，游戏状态转移图不会出现圆图，所以一定是树形图。(对于国际象棋来说，如果用A来表示棋子状态，加上上面提到的规则中的一个，整个博弈状态就用(A，I)来表示，其中I表示双方连续I步没有吃棋子或者已经I次进入棋子状态A。在这个表示法中，当I不等于J时，即使棋子是A，(A，I)和(A，J)仍然代表不同的博弈状态，因此，在国际象棋的博弈转移中不会出现圆图。)

接下来，我们假设每个玩家都是理性的。当一个玩家处于博弈树的某个节点时，她/他必然会选择对他/她最有利的方式。如果现在游戏状态到了倒数第二步，再走一步游戏就结束了，那么我们就会看到游戏树的结尾，就像下图，其中省略号表示未显示的结束节点。

在上面的博弈树中，如果是第一个轮到玩家在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，那么他就赢了。这与反证法的假设相矛盾。所以五子棋只能存在两种情况：第一个棋手有赢的策略，双方的最优策略会导致和棋。或者更简洁的说，先手有不败的策略。

回顾之前关于五子棋的讨论，根本没有体现“五”字。我们完全可以把相关结论推广到五子棋、五子棋等等。特别是井字游戏，本质上是一种三人象棋。因为它的博弈树非常简单，我们甚至可以用穷举法证明井字第一个玩家有不败策略。

哪里都可以玩井字游戏。

转载内容仅代表作者观点。

不，我代表中国科学院物理研究所

资料来源：中国科学院理论物理研究所

原标题：好奇博士26:什么？象棋和围棋都有不败的策略？

编辑：藏傻逼