网站备案核验单,无锡哪里有做网站的,蓝色风格的网站,网站项目注#xff1a;下列游戏都建立在双方都有最优策略的情况下#xff0c;若未加以说明#xff0c;则每人每次至少取一个石子。
例1#xff1a;取石子游戏之一
有两个游戏者#xff1a;A和B。有n颗石子。 约定#xff1a;两人轮流取走石子#xff0c;每次可取1、2或3颗。A先…注下列游戏都建立在双方都有最优策略的情况下若未加以说明则每人每次至少取一个石子。
例1取石子游戏之一
有两个游戏者A和B。有n颗石子。 约定两人轮流取走石子每次可取1、2或3颗。A先取取走最后一颗石子的人获胜。 问题A有没有必胜的策略
分析这是小学必备奥数题之一我们可以很容易的知道当n为0,4,8,12……时A必定会输因为不论A取多少B只要和A共同取走4即可当n不为0,4,8,12……时A只需要将n取成4的倍数这样就变成了B先取B一定会输所以A一定会赢。
经过我们的分析发现对这个游戏而言0,4,8,12……这些状态是对于先手的必败状态而其他状态是对于先手的必胜状态因此我们现在介绍一下有关博弈的一些名词和概念
1、平等组合游戏
两人游戏。两人轮流走步。有一个状态集而且通常是有限的。有一个终止状态到达终止状态后游戏结束。游戏可以在有限的步数内结束。规定好了哪些状态转移是合法的。所有规定对于两人是一样的。
因此我们的例1提到的游戏即为一个平等组合游戏但是我们生活中常见的棋类游戏如象棋、围棋等均不属于平等组合游戏因为双方可以移动的棋子不同不满足最后一个条件而我们后续提到的游戏以及博弈中的其他游戏基本属于平等组合游戏
2、N状态必胜状态P状态必败状态
像例1的分析一样0,4,8,12……等状态就是对于先手的P状态必败状态其他的则是对于先手的N状态必胜状态。
那么我们定义两个状态之间的转换
所有的终止状态都为P状态对于任意的N状态存在至少一条路径可以转移到P状态对于任意的P状态只能转移到N状态
证明过于简单这里不再赘述我们只需要明白一点每个人都会选择最策略即可。
当然这里所说的都是最后走步的人获胜的游戏至于那些走到最后失败的游戏我们在最后做了一个简单的讲解Anti Nim。
例2取石子游戏之二
将例1的游戏扩展一下我们定义一个集合Sp1,p2,...,pk(k∈Z∗)Sp1,p2,...,pk(k∈Z∗)S{p1,p2,...,pk}(k∈Z∗)S{p1,p2,...,pk}(k∈Z∗)S{p1,p2,...,pk}(k∈Z∗) S\{{p_{1},p_{2},...,p_{k}}\}(k \in Z^*)Sp1,p2,...,pk(k∈Z∗)Sp1,p2,...,pk(k∈Z∗)S{p1,p2,...,pk}(k∈Z∗)aak,bbk那么取走
