象棋和围棋都是中华文明的瑰宝|什么？象棋和围棋都存在不败策略？( 三 )
从下往上的胜负信息推导
如何确定谁才具有必胜策略：策略窃取
想必读者已经跃跃欲试了 ， 如果知道了象棋或者围棋的最优策略 ， 岂不是在棋坛上横着走？可惜的是 ， 虽然策梅洛定理的证明是构造性的 ， 但是构造过程需要我们先得到整个游戏树 ， 而像围棋这类棋 ， 游戏的路径(指从根节点到末端节点的一条路径)比宇宙的原子数目还要多 ， 要想通过整个游戏树来得到最优策略是不可能的了 。 如此说来 ， 策梅洛定理仅仅给必胜或者平局策略提供了存在性 。 不过 ， 借助策梅洛定理所提供的存在性 ， 我们可以利用被称为策略窃取的方法证明在某些游戏上后手不存在必胜策略 ， 换言之 ， 先手有不败策略 。
本文将以著名的五子棋为例介绍策略窃取是怎么一回事 。 很明显 ， 五子棋满足策梅洛定理的条件 ， 于是有且仅有三种可能性：先手具有必胜策略、后手具有必胜策略、双方的最优策略会导致平局 。 接下来我们使用反证法 。 假如后手具有必胜策略 ， 我们把这个策略称为S 。 这时候无论先手玩家怎么走 ， 后手玩家只要使用策略S ， 先手玩家必输 。
策略窃取的要点就是把对方的策略“窃取”过来 。 先手玩家先在棋盘上随便放一个棋子 ， 位置记为P1 ， 然后假装这个棋子不存在 。 这时候轮到后手玩家放子了 ， 由于假装P1上的棋子不存在 ， 后手玩家成了“先手” ， 而先手玩家成了“后手” ， 于是先手玩家可以使用必胜策略S 。 根据这个策略的必胜性质 ， 无论对方怎么走 ， “后手”玩家(也就是先手玩家)都将获胜 。 不过 ， 事情似乎没那么简单 。 我们只是假装P1上的棋子不存在而已 ， 实际上这个棋子是存在的 。 P1位置上的棋子会怎么影响到策略S的使用呢？假如走到了某一步 ， 策略S要求“后手”玩家将棋子放在P1位置 ， 这时候P1已经存在“后手”玩家的棋子了 ， 但是游戏要求玩家每一步都不能不下棋子 ， 此时“后手”玩家可以在这一步把棋子下在其他的任意位置 ， 记为P2 。 这样的话P1和P2都占据了“后手”玩家的棋子 ， 这就等价于游戏一开始“后手”玩家将棋子下在了P2 ， 并且在目前这一轮“后手”玩家根据策略S的要求把棋子下在了P1位置 。 如果接下来策略要求棋子下在P2 ， 那么“后手”玩家可以任意把棋子下在P3位置……如此类推 ， 先手玩家可以完美使用策略S ， 于是会必胜 。 这和反证法的假设相矛盾 。 于是 ， 五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局 。 或者更简洁地表述为 ， 先手具有不败策略 。
回顾前述关于五子棋的讨论 ， 这个“五”字完全没有体现出来 ， 我们完全可以把相关结论推广到四子棋、六子棋等等 。 特别地 ， 井字棋本质上是一种三子棋 ， 由于它的游戏树很简单 ， 我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略 。
文章图片
在哪都能玩的井字棋
转载内容仅代表作者观点
不代表中科院物理所立场
来源：中科院理论物理研究所
原标题：DoctorCurious26:什么？象棋和围棋都存在不败策略？
编辑：藏痴
来源：中科院物理所
相关经验推荐
- 正式服今天更新|王者荣耀正式服更新，新模式开启预热，吕布和娜可露露削弱
- CF美服的外挂有多猖狂？国服的笑脸兵根本没法和他们比
- 1月20日英雄联盟2022LCK春季赛DRX和T1的对决打响|Faker：之前的老队友在别的队！我会好好教训他
- 近日|王者荣耀：新英雄金蝉即将上线，2个徒弟孙悟空和猪八戒崛起
- 为期一个月的微博“游戏大赏”和“电竞大赏”日前相继收官。|在微博还原“大赏”的本质，体现社交媒体平台价值
- 骷髅：这个有点意思英雄联盟刚出来的时候|英雄联盟：当初的英雄模型，努努和放出来的一样，大龙：好丑啊！
- 做了20年的传说系列，和一款手游联动了？有玩家写出千字攻略点赞
- 王者荣耀主宰和暴君的区别是什么？玩王者荣耀怎样快速成为高手？
- 云顶：S6首个被移除的海克斯诞生，作用两极分化，和对手差距过大
- 后羿荣耀典藏泡汤，诸葛亮荣耀典藏除夕上线，特效融入钟表和星空元素