易坊好文馆

  1. 首页 > 玩科技 >

|什么？象棋和围棋都存在不败策略？( 三 )


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

推荐阅读


上一篇：xyg|XYG让三追四失败，TES顺利报了虐泉之仇，网友：败人品的行为少做

下一篇：|lpl官方解说米勒评分，rng是17支队伍中唯一的s级队伍