什么？象棋和围棋都存在不败策略？( 三 )
文章图片
文章图片
从下往上的胜负信息推导
如何确定谁才具有必胜策略：策略窃取
想必读者已经跃跃欲试了 ， 如果知道了象棋或者围棋的最优策略 ， 岂不是在棋坛上横着走？可惜的是 ， 虽然策梅洛定理的证明是构造性的 ， 但是构造过程需要我们先得到整个游戏树 ， 而像围棋这类棋 ， 游戏的路径(指从根节点到末端节点的一条路径)比宇宙的原子数目还要多 ， 要想通过整个游戏树来得到最优策略是不可能的了 。如此说来 ， 策梅洛定理仅仅给必胜或者平局策略提供了存在性 。不过 ， 借助策梅洛定理所提供的存在性 ， 我们可以利用被称为策略窃取的方法证明在某些游戏上后手不存在必胜策略 ， 换言之 ， 先手有不败策略 。
本文将以著名的五子棋为例介绍策略窃取是怎么一回事 。很明显 ， 五子棋满足策梅洛定理的条件 ， 于是有且仅有三种可能性：先手具有必胜策略、后手具有必胜策略、双方的最优策略会导致平局 。接下来我们使用反证法 。假如后手具有必胜策略 ， 我们把这个策略称为S 。这时候无论先手玩家怎么走 ， 后手玩家只要使用策略S ， 先手玩家必输 。
策略窃取的要点就是把对方的策略“窃取”过来 。先手玩家先在棋盘上随便放一个棋子 ， 位置记为P1 ， 然后假装这个棋子不存在 。这时候轮到后手玩家放子了 ， 由于假装P1上的棋子不存在 ， 后手玩家成了“先手” ， 而先手玩家成了“后手” ， 于是先手玩家可以使用必胜策略S 。根据这个策略的必胜性质 ， 无论对方怎么走 ， “后手”玩家(也就是先手玩家)都将获胜 。不过 ， 事情似乎没那么简单 。我们只是假装P1上的棋子不存在而已 ， 实际上这个棋子是存在的 。P1位置上的棋子会怎么影响到策略S的使用呢？假如走到了某一步 ， 策略S要求“后手”玩家将棋子放在P1位置 ， 这时候P1已经存在“后手”玩家的棋子了 ， 但是游戏要求玩家每一步都不能不下棋子 ， 此时“后手”玩家可以在这一步把棋子下在其他的任意位置 ， 记为P2 。这样的话P1和P2都占据了“后手”玩家的棋子 ， 这就等价于游戏一开始“后手”玩家将棋子下在了P2 ， 并且在目前这一轮“后手”玩家根据策略S的要求把棋子下在了P1位置 。如果接下来策略要求棋子下在P2 ， 那么“后手”玩家可以任意把棋子下在P3位置……如此类推 ， 先手玩家可以完美使用策略S ， 于是会必胜 。这和反证法的假设相矛盾 。于是 ， 五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局 。或者更简洁地表述为 ， 先手具有不败策略 。
回顾前述关于五子棋的讨论 ， 这个“五”字完全没有体现出来 ， 我们完全可以把相关结论推广到四子棋、六子棋等等 。特别地 ， 井字棋本质上是一种三子棋 ， 由于它的游戏树很简单 ， 我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略 。
文章图片
文章图片
在哪都能玩的井字棋
转载内容仅代表作者观点
不代表中科院物理所立场
来源：中科院理论物理研究所
黑龙江龙网_原标题：DoctorCurious 26: 什么？象棋和围棋都存在不败策略？
编辑：藏痴
【什么？象棋和围棋都存在不败策略？】来源：中科院物理所
推荐阅读
- 老公为什么会找丑的女人做女朋友？
- 一个女人，如果她什么都懂，那她一定恋爱过
- 吴婷和武庚的婚姻是否能够帮助他人的婚姻？
- 嫁给一个不爱自己的男人是什么感受？
- 女人主动加男生微信，这没什么不合适
- 为什么有些女人不肯承认老公还爱自己？
- 喜欢上一个人的时候，男方和女方各是如何说的
- 婚姻里，男人最害怕的事情是什么？
- 嫁对人和嫁错人，是完全不同的两种人生
- 为什么说三个月是分手魔咒？