一.巴什博奕(BashGame):
首先我们来玩一个比较古老的报数游戏。A和B一起报数,每个人每次最少报一个,最多报4个。轮流报数,看谁先报到30.
如果不知道巴什博弈的可能会觉得这个是个有运气成分的问题,但是如果知道的人一定知道怎样一定可以赢。
比如A先报数的话,那么B一定可以赢(这里假定B知道怎么正确的报数)
B可以这样报数,每次报5-k(A)个数,其中k(A)是A报数的个数这样的话没一次
两人报完数之后会变成51015202530这样是不是B一定会赢呢?是不是有一种被欺骗的感觉呢?好吧下面我们来看看这个原理。我们先看下一个一眼就能看出答案的例子比如说我们报到5(4+1),每次报最多报4个,最少报1个.那么是不是后者一定可以赢呢?答案是肯定的。好了到这巴什博弈的精髓基本就OK了。
那么如果我们要报到n+1,每次最多报n个,最少报1个的话,后者一定能够赢。
现在我们需要报数到n,而每次最多报数m个,最少报数1个.我们可以化成这样
n=k*(1+m)+r(0<=r<=m)这样的话如果r不等于0那么先手一定会赢,为什么呢?首先先手报r个,那么剩下k倍(1+m)个数,那么我们每次报数1+m-k(B)个数就一定能保证最后剩下1+m个,那么就到了上面我们说的那个了,先手就一定会赢,如果r=0那么后手一定会赢,道理一样的。
到这巴什博弈也就介绍完了,知道这个道理之后我们也可以去骗小朋友了。-_-//
代码如下:
二.威佐夫博奕(WythoffGame):
这种博弈比前面一种要稍微复杂一点。我们来看下下面这个游戏。
有两堆火柴棍,每次可以从某一堆取至少1根火柴棍(无上限),或者从两堆取相同的火柴棍数。最后取完的是胜利者。好了,如果你不知道这个博弈定理,对于小数目的火柴棍数,可能还能推出来,但是如果火柴棍数一多,就不行了。看了下面的这个介绍,你也会有一种被骗的感觉。
首先我们知道两堆火柴是没有差别的,也就是说第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一样的结果。
我们用一个二维的状态(a,b)来记录当前剩下的火柴数,表示第一堆剩下a根火柴,第二堆剩下b根火柴。同样我们假设两个人的编号是A和B,且A先取。
那么如果某个人遇到了这样的状态(0,0)那么也就是说这个人输了。这样的状态我们叫做奇异状态,也可以叫做失败态。
那么接下来的几个失败态为(1,2),(3,5),(4,7),(6,10),(8,13)……
我们用a[i]表示失败态中的第一个,b[i]表示失败态中的第二个.(i从0开始).
那么我们可以看到b[i]=a[i]+i;(i>=0),a[i]是前面的失败态中没有出现过的最小的整数
下面我们可以得到三个基本的结论。
1.每个数仅包含在一个失败态中
首先我们知道a[k]是不可能和前面的失败态中的a[i],b[i]重复的(这点由a[i]的得到可以知道)
b[k]=a[k]+k>a[k-1]+k>a[k-1]+k-1+1>a[k-1]+(k-1)=b[k-1]>a[k-1]这样我们知道每个数仅在一个失败态中。
2.每个失败态可以转到非失败态。
加入当前的失败态为(a,b),那么如果我们只在一堆中取的话,肯定会变成非失败态(这点由第一点可以保证),如果从两堆同时取的话,由于每个失败态的差是不一样的,所以也不可能得到一个失败态。也就是说一个失败态不管你怎么取,都会得到一个非失败态。
3.每个非失败态都可以转到一个失败态
对于这个结论,首先我们要知到每个状态(a,b)要么a=a[i],要么b=b[i].(每个数都出现在一个失败态中),下面我们分两种情况来讨论
I.a=a[i].如果b=a的话那么一次取完就变成了(0,0).如果b>b[i]的话,那么我们从第二堆中取走b-b[i]就变成了一个失败态。如果b<b[i].那么我们从两堆中同时取走a-a[b-a[i]]这样得到失败态(a[b-a[i]],a[b-a[i]]+b-a[i])(a[i]=a)
II.b=b[i].如果a>a[i]那么我们从第一堆中取走a-a[i]根火柴.
如果a<a[i].这里又分两种情况。第一是a=a[k](k<i)
那么我们从第二堆取走b-b[k]就行了。
第二是a=b[k]这样的话由于两堆火柴是没有区别的,所以我们把b变成a[k]就行了,也即是从第二堆火柴中取走b-a[k]就变成了失败态
至于怎么判断一个状态是否是失败态.我们可以用下面的方法来判断(本人暂时还不会证明)
a[i]=[i*(1+√5)/2](这里的中括号表示向下取整)b[i]=a[i]+i;
那么这就是一个失败态
代码如下:
三.尼姆博奕(NimmGame):
指的是这样的一个博弈游戏,目前有任意堆石子,每堆石子个数也是任意的,双方轮流从中取出石子,规则如下:
1)每一步应取走至少一枚石子;每一步只能从某一堆中取走部分或全部石子;
2)如果谁取到最后一枚石子就胜。
也就是尼姆博弈(Nimm Game)。
必败局面:也叫奇异局势。无论做出何出操作,最终结果都是输的局面。必败局面经过2次操作后,可以达到另一个必败局面。
必胜局面:经过1次操作后可以达到必败局面。
即当前局面不是必败局面就是必胜局面,而必胜局面可以一步转变成必败局面。
最终状态:
(1)最后剩下一堆石子;(必胜局面)
(2)剩下两堆,每堆一个;(必败局面)
(3)当石子剩下两堆,其中一堆只剩下1颗,另一堆剩下多于n颗石子时,当前取的人只需将多于1颗的那一堆取出n-1颗,则局面变为刚才提到的必败局面。(必胜局面)
判断当前局势是否为必胜(必败)局势:
1)把所有堆的石子数目用二进制数表示出来,当全部这些数按位异或结果为0时当前局面为必败局面,否则为必胜局面;
2)在必胜局面下,因为所有数按位异或的结果是大于零的,那么通过一次取,将这个(大于其它所有数按位异或的结果的)数下降到其它所有数按位异或的结果,这时局面就变为必败局面了。
定理:一组自然数中必然存在一个数,它大于等于其它所有数按位异或的结果。
证明:原命题等价于,设a1^a2^... ^an=p,p≠0时,必存在k,使得ak^p<ak(当p=0时,对于任意的k,有ak^p=ak)。
设p的最高位是第q位,则至少存在一个k,使得ak的第q位也是1,而ak^p的第q位为0,所以ak^p<ak
补缀一点,(a^b)^b=a^(b^b)=a^0=a,所以ak^p相当于“其它所有数按位异或的结果”。
例1:2 45 45
45^45=0,45和45的异或等于0。
例 2:3 3 6 9
局势(3,6,9)因为3^6^9不等于0,所以这是一个必胜局势。
3 011
^6 110
5 101
即从第3堆中的9个中取走9-5=4个,则(3,6,9)->(3,6,5),3^6^5=0,故(3,6,5)为奇异局势,即从必胜局势转变成必败局势。
代码如下:
分享到:
相关推荐
博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈论,几个案例博弈...
身边的博弈论:博弈论与信息经济学浅说 对于许多非数学专业和经济学专业的人们来说,博弈论可能是一个极为陌生的概念。但在国外,博弈论作为现代经济学的前沿领域,已成为占据主流的基本分析工具。1994年诺贝尔经济...
博弈论及其应用,matlab源码
博弈论分析,演化博弈图形
20世纪80年代至今是博弈论的完善和应用期。博弈论广泛 应用到经济学、社会学、生物学等。并于1994年直接获奖, 成功应用博弈论而于1996年获奖的最优税制及二级价格拍卖, 001年获奖的信息经济学。
优秀的博弈论课件最好的博弈论课件最好的博弈论课件
元宝自动机 元宝自动机 博弈论 博弈论 matlab源代码 matlab源代码 matlab源代码
博弈论试题及答案.pdf
不错的博弈论例子哦,有兴趣的和我一起看看吧。。。。 郑重声明:该资源仅供学习交流使用。
博弈论(Game Theory) 第一章 引论 第二章 基本概念 第三章 完全信息静态博弈 第四章 完全信息动态博弈 第五章 不完全信息静态博弈 第六章 不完全信息动态博弈 第七章 合作博弈 第八章 演化博弈
目前,大多数 DRL 模型事实上还停留在传统的博弈论层面,例如**纳什均衡或零和游戏**等。但随着DRL的发展,传统博弈论方法已经逐渐呈现出不足之处,而同时则有一些新的博弈论方法被纳入到人工智能的程序当中。雷锋网...
《经济博弈论》期末考试复习题及参考答案.pdf
博弈论,我们每个人都应该懂的 道理。
很好的关于微分博弈的入门材料,浙大博士论文
张维迎的博弈论与信息经济学部分答案答案...................
AnyLogic博弈论程序和视频,用户、企业价格的博弈,包括用户、企业、政府三个智能体
博弈论试题集,博弈论试题集,博弈论试题集,博弈论试题集
基于演化博弈的模拟仿真,特别是对于双方博弈过程中的演化趋势进行分析
运用博弈论思想,研究了雷达对抗中干扰效果的动态评估问题。把干扰效果作为博弈盈利函数,从时间、空间、 频率、能量四个方面对干扰效果进行了定量描述,给出了干扰效果的综合评估算法,从而建立了电子对抗博弈策略...