易坊好文馆

  1. 首页 > 玩科技 >

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


下面给出策梅洛定理的严格表述：在双人完全信息博弈下 ， 只有三种情况：要么先手具有必胜策略 ， 要么后手具有必胜策略 ， 要么双方的最优策略会导致平局 。比如前面所说的Chop游戏 ， 当m≠n时 ， 先手玩家具有必胜策略；如果m=n ， 后手玩家具有必胜策略 。Chop游戏没有平局 。策梅洛定理是一个结论很强的定理 ， 下面我们会发现 ， 它的证明非常简单 ， 不需要用到很高深的知识 。
策梅洛定理的证明
为了证明策梅洛定理 ， 我们需要引入一个小小的概念：游戏树 。在游戏的每一步 ， 玩家有很多种走法 ， 每一个走法都会产生新的分支 ， 把两位玩家的所有可能走法考虑进来 ， 就会得到一个树状结构 。这个树状结构穷尽了游戏过程的所有可能性 。下图是Chop游戏在1×4情况下的游戏树 。在本文 ， 我们用(1,0)表示先手获胜 ， (0,1)表示后手获胜 ， (0,0)表示平局 。
|什么？象棋和围棋都存在不败策略？
文章图片

文章图片

在游戏树上 ， 节点会标注上游戏状态 ， 比如上图中的方格 。有时候为了信息完全 ， 还会标注上在此节点轮到哪位玩家操作了 。因为我们把游戏循环往复的可能性排除了 ， 游戏状态转移图不会出现圈图 ， 所以必然是树图 。(对于象棋 ， 如果用A表示棋子状态 ， 加上了前文所述的其中一个规则后 ， 整个游戏状态将由(A, i)表示 ， 其中i表示已经连续i步双方都没有被吃掉棋子或者已经i次进入棋子状态A了 。在这样的表示下 ， 当i不等于j时 ， (A, i)和(A, j)哪怕棋子状态都是A ， 但是依然代表不同的游戏状态 。于是 ， 象棋的游戏转移也不会出现圈图 。)
接下来 ， 我们假设每一位玩家都是理智的 ， 当玩家处于游戏树的某个节点时 ， 她/他必然会选择对其最有利的走法 。假如现在游戏状态来到了倒数第二步 ， 再走一步游戏将结束了 ， 那么我们就会看到游戏树的末端 ， 大概是如下图这样的 ， 其中省略号表示未画出的末端节点
|什么？象棋和围棋都存在不败策略？
文章图片

文章图片

在上图的游戏树中 ， 如果在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的下一级节点的胜负最小值 。

推荐阅读


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

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