象棋和围棋都存在不败策略象棋和围棋都存在不败策略吗 _小知识

象棋和围棋都是中华文明的瑰宝，更是训练和测试思维能力的方式之一，那些在这两种棋类上取得成就的人们，其智商普遍得到公众认可。但是，我们是否想过，在这两种棋类上是否存在必胜或者平局的策略？答案是存在的，这是策梅洛关于双人完全信息博弈的一个定理的结论。本文将详细介绍这个定理的证明，并将其用于诸如五子棋的分析中。如无特殊说明，后文所提及的游戏都是双人游戏。

什么是最优策略
为了让大家对最优策略有一个直观的理解，这里举一个小游戏作为例子。这个小游戏叫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，但是依然代表不同的游戏状态。于是，象棋的游戏转移也不会出现圈图。)

象棋和围棋都存在不败策略 象棋和围棋都存在不败策略吗

象棋和围棋都存在不败策略象棋和围棋都存在不败策略吗