象棋和围棋都是中华文明的瑰宝|什么？象棋和围棋都存在不败策略？
象棋和围棋都是中华文明的瑰宝 ， 更是训练和测试思维能力的方式之一 ， 那些在这两种棋类上取得成就的人们 ， 其智商普遍得到公众认可 。 但是 ， 我们是否想过 ， 在这两种棋类上是否存在必胜或者平局的策略？答案是存在的 ， 这是策梅洛关于双人完全信息博弈的一个定理的结论 。 本文将详细介绍这个定理的证明 ， 并将其用于诸如五子棋的分析中 。 如无特殊说明 ， 后文所提及的游戏都是双人游戏 。
什么是最优策略
为了让大家对最优策略有一个直观的理解 ， 这里举一个小游戏作为例子 。 这个小游戏叫Chop ， 在游戏的最开始有一个m×n的网格(下图是一个4×6网格示例) ， 游戏由两位玩家轮流操作 ， 每位玩家每轮可以沿着一整根竖网格线或者一整根横网格线将网格割掉一块 ， 割到只剩下一个小方格的玩家为胜者 。 注意 ， 不能沿着剩余网格的边界线做切割 ， 例如不能沿着下图的AB线切割 ， 但是沿着CD线或者EF线切割都是可以的 。 每次切割完之后网格会被分成两块 ， 由操作切割的玩家决定留下哪一块 。
文章图片
对于这类双人游戏 ， 一般会有最先进行操作的玩家 ， 我们将其称为先手 ， 另一位被称为后手 。 如果一开始的时候m和n其中一个数为1 ， 比如n=1 ， 先手玩家可以直接切割掉(m-1)个格子即可获得胜利 ， 这个策略就是先手玩家的最优策略 。 如果对于一般的m和n ， 先手或者后手怎样才能保证获胜呢？读者可以稍作思考 ， 再接着往下看 。
其实很简单 ， 如果m和n不相等 ， 那么先手的最优策略会导致必胜的结果：这时候先手玩家只要割掉其中一块使得剩下的网格是个长和宽相等的网格即可 。 这样 ， 无论后手切割哪条线 ， 都是在长和宽相等的基础上进行切割 ， 最后必然得到一个长宽不相等的网格 ， 也就不可能是单独一个网格 。 先手玩家只要每一步实行这个策略 ， 无论后手玩家怎么操作 ， 先手玩家都会获胜 。 这时候读者肯定明白了 ， 当m=n的时候 ， 无论先手玩家怎么操作 ， 后手玩家都可以借助前述一样的策略获胜 。
完全信息博弈和策梅洛定理
【象棋和围棋都是中华文明的瑰宝|什么？象棋和围棋都存在不败策略？】现在回到一般游戏的讨论上 。 策梅洛定理适用于被称为完全信息博弈的一类游戏 。 所谓完全信息博弈 ， 指的是游戏的所有信息都是公开的 ， 游戏双方都能清楚了解到目前游戏所处的状态信息 ， 并且游戏的每一步都不涉及概率因素 。 这个条件把扑克、飞行棋、暗棋和翻棋玩法下的军棋都排除掉了 。 然后 ， 我们还需要这个游戏能在有限步内结束 ， 并且 ， 游戏的结局要么是平局要么有一方是胜者 。 很明显 ， 围棋是属于完全信息博弈的 。 至于象棋 ， 有可能会进入循环状态从而整个游戏没完没了 。 为了避免这一点 ， 我们可以加入一些新规则使得象棋不会出现循环 ， 比如 ， 设定一个很大的数N ， 只要连续N步双方都没有被吃掉棋子就判为和棋 ， 或者不允许超过N次进入同一种棋子状态 ， 否则判为和棋 。 加入这些规则或者类似的规则之后 ， 象棋就满足要求了 。
下面给出策梅洛定理的严格表述：在双人完全信息博弈下 ， 只有三种情况：要么先手具有必胜策略 ， 要么后手具有必胜策略 ， 要么双方的最优策略会导致平局 。 比如前面所说的Chop游戏 ， 当m≠n时 ， 先手玩家具有必胜策略；如果m=n ， 后手玩家具有必胜策略 。 Chop游戏没有平局 。 策梅洛定理是一个结论很强的定理 ， 下面我们会发现 ， 它的证明非常简单 ， 不需要用到很高深的知识 。
相关经验推荐
- 正式服今天更新|王者荣耀正式服更新，新模式开启预热，吕布和娜可露露削弱
- CF美服的外挂有多猖狂？国服的笑脸兵根本没法和他们比
- 1月20日英雄联盟2022LCK春季赛DRX和T1的对决打响|Faker：之前的老队友在别的队！我会好好教训他
- 近日|王者荣耀：新英雄金蝉即将上线，2个徒弟孙悟空和猪八戒崛起
- 为期一个月的微博“游戏大赏”和“电竞大赏”日前相继收官。|在微博还原“大赏”的本质，体现社交媒体平台价值
- 骷髅：这个有点意思英雄联盟刚出来的时候|英雄联盟：当初的英雄模型，努努和放出来的一样，大龙：好丑啊！
- 做了20年的传说系列，和一款手游联动了？有玩家写出千字攻略点赞
- 王者荣耀主宰和暴君的区别是什么？玩王者荣耀怎样快速成为高手？
- 云顶：S6首个被移除的海克斯诞生，作用两极分化，和对手差距过大
- 后羿荣耀典藏泡汤，诸葛亮荣耀典藏除夕上线，特效融入钟表和星空元素