有一种很有意思的游戏,就是有物体若干堆,可以是火柴棍或是围棋子等等均可。两个
人轮流从堆中取物体若干,规定最后取光物体者取胜。这是我国民间很古老的一个游戏
,别看这游戏极其简单,却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够
取胜。
(一)巴什博奕(Bash Game):只有一堆n个物品,两个人轮流从这堆物品中取物,规
定每次至少取一个,最多取m个。最后取光者得胜。
显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,
后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果
n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走
k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的
取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
这个游戏还可以有一种变相的玩法:两个人轮流报数,每次至少报一个,最多报十
个,谁能报到100者胜。
(二)威佐夫博奕(Wythoff Game):有两堆各若干个物品,两个人轮流从某一堆或同
时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况下是颇为复杂的。我们用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示
两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们
称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,
10)、(8,13)、(9,15)、(11,18)、(12,20)。
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k,奇异局势有
如下三条性质:
1。任何自然数都包含在一个且仅有一个奇异局势中。
由于ak是未在前面出现过的最小自然数,所以有ak > ak-1 ,而 bk= ak + k > ak
-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
2。任意操作都可将奇异局势变为非奇异局势。
事实上,若只改变奇异局势(ak,bk)的某一个分量,那么另一个分量不可能在其
他奇异局势中,所以必然是非奇异局势。如果使(ak,bk)的两个分量同时减少,则由
于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
3。采用适当的方法,可以将非奇异局势变为奇异局势。
假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了
奇异局势(0,0);如果a = ak ,b > bk,那么,取走b - bk个物体,即变为奇异局
势;如果 a = ak , b < bk ,则同时从两堆中拿走 ak - ab - ak个物体,变为奇异局
势( ab - ak , ab - ak+ b - ak);如果a > ak ,b= ak + k,则从第一堆中拿走多余
的数量a - ak 即可;如果a < ak ,b= ak + k,分两种情况,第一种,a=aj (j < k)
,从第二堆里面拿走 b - bj 即可;第二种,a=bj (j < k),从第二堆里面拿走 b - a
j 即可。
从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜
;反之,则后拿者取胜。
那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?我们有如下公式:
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数(1+√5)/2 = 1。618...,因此,由ak,bk组成的矩形近
似为黄金矩形,由于2/(1+√5)=(√5-1)/2,可以先求出j=[a(√5-1)/2],若a=[
j(1+√5)/2],那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1
+ j + 1,若都不是,那么就不是奇异局势。然后再按照上述法则进行,一定会遇到奇异
局势。
(三)尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的
物品,规定每次至少取一个,多者不限,最后取光者得胜。
这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首
先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是
(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一
下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情
形。
计算机算法里面有一种叫做按位模2加,也叫做异或的运算,我们用符号(+)表示
这种运算。这种运算和一般加法不同的一点是1+1=0。先看(1,2,3)的按位模2加的结
果:
1 =二进制01
2 =二进制10
3 =二进制11 (+)
———————
0 =二进制00 (注意不进位)
对于奇异局势(0,n,n)也一样,结果也是0。
任何奇异局势(a,b,c)都有a(+)b(+)c =0。
如果我们面对的是一个非奇异局势(a,b,c),要如何变为奇异局势呢?假设 a < b
< c,我们只要将 c 变为 a(+)b,即可,因为有如下的运算结果: a(+)b(+)(a(+)
b)=(a(+)a)(+)(b(+)b)=0(+)0=0。要将c 变为a(+)b,只要从 c中减去 c-(
a(+)b)即可。
例1。(14,21,39),14(+)21=27,39-27=12,所以从39中拿走12个物体即可达
到奇异局势(14,21,27)。
例2。(55,81,121),55(+)81=102,121-102=19,所以从121中拿走19个物品
就形成了奇异局势(55,81,102)。
例3。(29,45,58),29(+)45=48,58-48=10,从58中拿走10个,变为(29,4
5,48)。
例4。我们来实际进行一盘比赛看看:
甲:(7,8,9)->(1,8,9)奇异局势
乙:(1,8,9)->(1,8,4)
甲:(1,8,4)->(1,5,4)奇异局势
乙:(1,5,4)->(1,4,4)
甲:(1,4,4)->(0,4,4)奇异局势
乙:(0,4,4)->(0,4,2)
甲:(0.4,2)->(0,2,2)奇异局势
乙:(0,2,2)->(0,2,1)
甲:(0,2,1)->(0,1,1)奇异局势
乙:(0,1,1)->(0,1,0)
甲:(0,1,0)->(0,0,0)奇异局势
甲胜。
分享到:
相关推荐
博弈论的几个经典模型 博弈论是研究互动决策的理论,它研究的是各行动方(即局中人)的决策是相互影响的,每个人在决策的时候必须将他人的决策纳入自己的决策考虑之中。博弈论的应用领域非常广泛,在经济学、政治...
在博弈论中,我们通常涉及以下几个核心概念: 1. **参与者(Players)**:在博弈中,每个有独立决策能力的个体称为参与者,他们根据自身的目标和策略进行决策。 2. **策略(Strategies)**:每个参与者可以选择的...
博弈论的几个经典模型 博弈论是研究互动决策的理论,旨在...博弈论的几个经典模型展示了博弈论的应用于解决实际问题的能力。这些模型都是研究互动决策和策略选择的重要工具,可以帮助我们更好地理解和解决实际问题。
设计一个人机对弈的智能系统,通常需要考虑以下几个关键组成部分: 1. **状态表示**:为了使计算机能够理解当前棋局的状态,需要设计一种有效的方式表示棋盘上的情况。例如,在五子棋中,可以通过一个二维数组来...
几个博弈案例.pdf
在这样的市场结构中,少数几个大公司占据了市场的大部分份额,它们的决策不仅受到自身利益的影响,还必须考虑到竞争对手的反应。这种决策过程就构成了博弈分析的基础,每个公司都在尝试找到最优策略以最大化自己的...
在MATLAB中实现演化博弈,通常涉及以下几个步骤: 1. **定义支付矩阵**:支付矩阵描述了不同策略组合下的收益情况。比如在著名的“囚徒困境”博弈中,合作与背叛的策略组合会产生不同的结果。 2. **选择初始策略...
"sujiyanhua.zip"压缩包中的代码很可能包含了实现随机演化博弈的算法,这些算法可能包括以下几个关键部分: 1. **策略选择**:每个个体可能有一组可选策略,代码会根据随机性或某种规则决定个体选择的策略。 2. **...
解决不平等博弈问题的关键是计算 Alice 能比 Bob 多走几步。如果这个值大于 0,那么 Alice 必胜。如果这个值小于 0,那么 Bob 必胜。否则后手必胜。 在 OI 中,超现实数和不平等博弈问题是非常重要的一部分。OI 中...
接下来,文章介绍了几种经典的博弈模型。巴什博奕(Bash Game)是一个简单的物品分割游戏,威佐夫博弈(Wythoff's Game)涉及两个玩家交替移除数字,尼姆博弈(Nim Game)则是在一堆或多堆物品中移除物品,目标是让...
除了纳什均衡,还有其他几种重要的均衡概念,如子博弈完美纳什均衡,用于处理动态博弈,考虑了博弈过程中可能出现的中间阶段。另外,还有合作博弈论,研究如何通过协议或联盟达到更好的结果。 在实际应用中,博弈论...
一个博弈通常由几个关键元素构成:参与者(玩家)、策略集、收益函数和信息结构。玩家是博弈中的决策主体,他们可以选择不同的策略;策略集则是玩家可选的所有可能行动;收益函数则定义了每个策略组合下的结果;信息...
在“基于Matlab绘制演化博弈主体的演化轨迹”这一任务中,我们主要关注以下几个关键知识点: 1. **演化博弈理论**:演化博弈理论源自生物学的自然选择概念,由John Maynard Smith和George R. Price引入到博弈论中。...
讲义中可能涵盖了以下几个关键知识点: 1. **基本概念**:博弈论的基本元素包括参与者(玩家)、策略集、支付函数和博弈结构。每个参与者都有自己的目标,通过选择不同的策略来追求最大化利益。 2. **零和博弈与非...
在Matlab中实现复杂网络囚徒困境博弈,需要以下几个关键步骤: 1. **网络生成**:首先,需要构建复杂网络,这可能涉及到随机规则网络或无标度网络的生成算法,如Erdős-Rényi模型、Barabási-Albert模型等。 2. *...
2. **纳什均衡**:由约翰·纳什提出的纳什均衡是博弈论中的关键概念,指在一个博弈中,每个玩家的策略都是对其他玩家策略的最佳响应,且没有玩家有单方面改变策略的动机。它是分析静态博弈的标准工具。 3. **零和...