用户投稿
象棋和围棋都是古老的棋类游戏，它们都有复杂的变化和策略，但说“存在不败策略”并不准确。
对于象棋来说，历史上并没有找到绝对的不败策略。虽然有一些开局和中局策略被认为是非常有利的，但对手可以通过调整策略来应对。象棋的复杂性在于，棋盘上的局势每一步都在不断变化，且双方的策略也会互相影响。
围棋的情况也类似。围棋的规则相对简单，但棋盘上的变化极其复杂，每一子落定都可能引发整个棋局的变革。虽然有一些被认为是优势的开局，但这些优势并不是绝对的不败，因为对手可以通过不同的应对策略来抵消这些优势。
总的来说，象棋和围棋都存在很多策略和技巧，但说它们有绝对的不败策略是不准确的。这两种棋类游戏的高深之处在于其无穷的变化和策略多样性。
相关内容：
象棋和围棋都是中华文明的瑰宝，更是训练和测试思维能力的方式之一，那些在这两种棋类上取得成就的人们，其智商普遍得到公众认可。但是，我们是否想过，在这两种棋类上是否存在必胜或者平局的策略？答案是存在的，这是策梅洛关于双人完全信息博弈的一个定理的结论。本文将详细介绍这个定理的证明，并将其用于诸如五子棋的分析中。如无特殊说明，后文所提及的游戏都是双人游戏。
什么是最优策略为了让大家对最优策略有一个直观的理解，这里举一个小游戏作为例子。这个小游戏叫Chop，在游戏的最开始有一个m×n的网格(下图是一个4×6网格示例)，游戏由两位玩家轮流操作，每位玩家每轮可以沿着一整根竖网格线或者一整根横网格线将网格割掉一块，割到只剩下一个小方格的玩家为胜者。注意，不能沿着剩余网格的边界线做切割，例如不能沿着下图的AB线切割，但是沿着CD线或者EF线切割都是可以的。每次切割完之后网格会被分成两块，由操作切割的玩家决定留下哪一块。
其实很简单，如果m和n不相等，那么先手的最优策略会导致必胜的结果：这时候先手玩家只要割掉其中一块使得剩下的网格是个长和宽相等的网格即可。这样，无论后手切割哪条线，都是在长和宽相等的基础上进行切割，最后必然得到一个长宽不相等的网格，也就不可能是单独一个网格。先手玩家只要每一步实行这个策略，无论后手玩家怎么操作，先手玩家都会获胜。这时候读者肯定明白了，当m=n的时候，无论先手玩家怎么操作，后手玩家都可以借助前述一样的策略获胜。完全信息博弈和策梅洛定理现在回到一般游戏的讨论上。策梅洛定理适用于被称为完全信息博弈的一类游戏。所谓完全信息博弈，指的是游戏的所有信息都是公开的，游戏双方都能清楚了解到目前游戏所处的状态信息，并且游戏的每一步都不涉及概率因素。这个条件把扑克、飞行棋、暗棋和翻棋玩法下的军棋都排除掉了。然后，我们还需要这个游戏能在有限步内结束，并且，游戏的结局要么是平局要么有一方是胜者。很明显，围棋是属于完全信息博弈的。至于象棋，有可能会进入循环状态从而整个游戏没完没了。为了避免这一点，我们可以加入一些新规则使得象棋不会出现循环，比如，设定一个很大的数N，只要连续N步双方都没有被吃掉棋子就判为和棋，或者不允许超过N次进入同一种棋子状态，否则判为和棋。加入这些规则或者类似的规则之后，象棋就满足要求了。下面给出策梅洛定理的严格表述：在双人完全信息博弈下，只有三种情况：要么先手具有必胜策略，要么后手具有必胜策略，要么双方的最优策略会导致平局。比如前面所说的Chop游戏，当m≠n时，先手玩家具有必胜策略；如果m=n，后手玩家具有必胜策略。Chop游戏没有平局。策梅洛定理是一个结论很强的定理，下面我们会发现，它的证明非常简单，不需要用到很高深的知识。策梅洛定理的证明为了证明策梅洛定理，我们需要引入一个小小的概念：游戏树。在游戏的每一步，玩家有很多种走法，每一个走法都会产生新的分支，把两位玩家的所有可能走法考虑进来，就会得到一个树状结构。这个树状结构穷尽了游戏过程的所有可能性。下图是Chop游戏在1×4情况下的游戏树。在本文，我们用(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，于是会必胜。这和反证法的假设相矛盾。于是，五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局。或者更简洁地表述为，先手具有不败策略。回顾前述关于五子棋的讨论，这个“五”字完全没有体现出来，我们完全可以把相关结论推广到四子棋、六子棋等等。特别地，井字棋本质上是一种三子棋，由于它的游戏树很简单，我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略。转载内容仅代表作者观点
什么是最优策略为了让大家对最优策略有一个直观的理解，这里举一个小游戏作为例子。这个小游戏叫Chop，在游戏的最开始有一个m×n的网格(下图是一个4×6网格示例)，游戏由两位玩家轮流操作，每位玩家每轮可以沿着一整根竖网格线或者一整根横网格线将网格割掉一块，割到只剩下一个小方格的玩家为胜者。注意，不能沿着剩余网格的边界线做切割，例如不能沿着下图的AB线切割，但是沿着CD线或者EF线切割都是可以的。每次切割完之后网格会被分成两块，由操作切割的玩家决定留下哪一块。
其实很简单，如果m和n不相等，那么先手的最优策略会导致必胜的结果：这时候先手玩家只要割掉其中一块使得剩下的网格是个长和宽相等的网格即可。这样，无论后手切割哪条线，都是在长和宽相等的基础上进行切割，最后必然得到一个长宽不相等的网格，也就不可能是单独一个网格。先手玩家只要每一步实行这个策略，无论后手玩家怎么操作，先手玩家都会获胜。这时候读者肯定明白了，当m=n的时候，无论先手玩家怎么操作，后手玩家都可以借助前述一样的策略获胜。完全信息博弈和策梅洛定理现在回到一般游戏的讨论上。策梅洛定理适用于被称为完全信息博弈的一类游戏。所谓完全信息博弈，指的是游戏的所有信息都是公开的，游戏双方都能清楚了解到目前游戏所处的状态信息，并且游戏的每一步都不涉及概率因素。这个条件把扑克、飞行棋、暗棋和翻棋玩法下的军棋都排除掉了。然后，我们还需要这个游戏能在有限步内结束，并且，游戏的结局要么是平局要么有一方是胜者。很明显，围棋是属于完全信息博弈的。至于象棋，有可能会进入循环状态从而整个游戏没完没了。为了避免这一点，我们可以加入一些新规则使得象棋不会出现循环，比如，设定一个很大的数N，只要连续N步双方都没有被吃掉棋子就判为和棋，或者不允许超过N次进入同一种棋子状态，否则判为和棋。加入这些规则或者类似的规则之后，象棋就满足要求了。下面给出策梅洛定理的严格表述：在双人完全信息博弈下，只有三种情况：要么先手具有必胜策略，要么后手具有必胜策略，要么双方的最优策略会导致平局。比如前面所说的Chop游戏，当m≠n时，先手玩家具有必胜策略；如果m=n，后手玩家具有必胜策略。Chop游戏没有平局。策梅洛定理是一个结论很强的定理，下面我们会发现，它的证明非常简单，不需要用到很高深的知识。策梅洛定理的证明为了证明策梅洛定理，我们需要引入一个小小的概念：游戏树。在游戏的每一步，玩家有很多种走法，每一个走法都会产生新的分支，把两位玩家的所有可能走法考虑进来，就会得到一个树状结构。这个树状结构穷尽了游戏过程的所有可能性。下图是Chop游戏在1×4情况下的游戏树。在本文，我们用(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，于是会必胜。这和反证法的假设相矛盾。于是，五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局。或者更简洁地表述为，先手具有不败策略。回顾前述关于五子棋的讨论，这个“五”字完全没有体现出来，我们完全可以把相关结论推广到四子棋、六子棋等等。特别地，井字棋本质上是一种三子棋，由于它的游戏树很简单，我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略。
微信扫一扫打赏
支付宝扫一扫打赏
