经验啦

  1. 首页 > 生活杂烩 > 游戏 > >

象棋和围棋都是中华文明的瑰宝|什么？象棋和围棋都存在不败策略？( 二 )


策梅洛定理的证明
为了证明策梅洛定理 ， 我们需要引入一个小小的概念：游戏树 。 在游戏的每一步 ， 玩家有很多种走法 ， 每一个走法都会产生新的分支 ， 把两位玩家的所有可能走法考虑进来 ， 就会得到一个树状结构 。 这个树状结构穷尽了游戏过程的所有可能性 。 下图是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的下一级节点的胜负最小值 。
得到了A处的胜负信息之后 ， 我们就可以忽略A下面的所有节点了 ， 这时候A就成了一个末端节点 ， 它带有相应的胜负信息 ， 这个胜负信息表示从该节点出发 ， 两位玩家都使用最优策略后会导致的胜负结局 。 这个操作可以继续进行下去 ， 不断得到上一级节点的胜负信息 ， 然后忽略掉旧的末端节点 。 如此往复 ， 因为树是有限高的 ， 最终我们会得到游戏一开始那个节点(术语叫根节点)的胜负信息 。 如果根节点的胜负信息是(1,0) ， 那么意味着先手玩家只要按最优策略走下去就会必胜；如果根节点的胜负信息是(0,1) ， 那么意味着后手玩家具有必胜策略；如果根节点的胜负信息是(0,0) ， 那么意味着双方的最优策略会导致平局 。 至此 ， 策梅洛定理证明完毕 。
象棋和围棋都是中华文明的瑰宝|什么？象棋和围棋都存在不败策略？
文章图片

相关经验推荐


上一篇：LOL：侯爷官宣加入WBG，Doinb打脸评级主播，自嘲进季后赛都困难

下一篇：英雄联盟高清壁纸，动漫人物，希望大家喜欢