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

接下来，我们假设每一位玩家都是理智的，当玩家处于游戏树的某个节点时，她/他必然会选择对其最有利的走法。假如现在游戏状态来到了倒数第二步，再走一步游戏将结束了，那么我们就会看到游戏树的末端，大概是如下图这样的，其中省略号表示未画出的末端节点

文章插图
在上图的游戏树中，如果在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，于是会必胜。这和反证法的假设相矛盾。于是，五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局。或者更简洁地表述为，先手具有不败策略。

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

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