前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >博弈 个人 见解

博弈 个人 见解

作者头像
全栈程序员站长
发布2022-07-12 18:06:43
2670
发布2022-07-12 18:06:43
举报

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

由于周測被虐,做了好久的博弈题,找了好多关于博弈的相关资料,感觉自己,似乎还是动了那么一点点。临睡前,就小小的总结一下,希望以后看到的时候,可以有所感悟吧!!

接下来是正题。

讲到博弈, 事实上也就是找规律,可是知道一般的博弈类型能够高速便捷的解决这个问题。

博弈的类型大致有下面几种:巴什博弈,威佐夫博奕,尼姆博弈。除此之外还有斐波那契博弈,sg模板等

巴什博弈:(摘自百度文库)

巴什博奕(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者胜。

巴什博弈主要内容是:n%(m+1)是否为零。 要是为零的话,就是先手输,否则,先手赢

威佐夫博奕:(以下关于定义的语句,为了保持说明的完整性·准确性,均摘自网络百度文库,以下就不在说明)

威佐夫博奕(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 – aj 就可以。 从如上性质可知,两个人假设都採用正确操作,那么面对非神秘局势,先拿者必胜;反之,则后拿者取胜。 那么任给一个局势(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,若都不是,那么就不是神秘局势。然后再依照上述法则进行,一定会遇到神秘 局势。

威佐夫博奕的思想就是那个公式:推断等号两边是否相等a(a是较小的数)==floor((b-a)*((sqrt(5.0)+1)/2))

要是相等的话就是先手输,否则先手赢

尼姆博弈:

尼姆博弈基本思想:

两人从n堆物品中取随意个,先取完者胜。

即将n堆物品的数量异或,得到的值假设为0,则先手败,反之先手胜。

假设要求先手在胜的条件下,到神秘局势的方法数,则推断异或的值与每一堆原值异或后(结果应该表示该堆没有參加异或时的异或值)与原值比較大小,

假设小于,则方法数加一。且相应的方法后,该堆的数目应变为异或的值与每一堆原值异或的值。

尼姆博弈的主要内容就是:对每堆的数量进行异或运算

Fibonacci’s Game(斐波那契博弈) 斐波那契博弈模型,大致上是这种: 有一堆个数为 n 的石子,游戏两方轮流取石子,满足: 1. 先手不能在第一次把全部的石子取完; 2. 之后每次能够取的石子数介于1到对手刚取的石子数的2倍之间(包括1和对手刚取的石子数的2倍)。 约定取走最后一个石子的人为赢家,求必败态。

(转)分析: n = 2时输出second; n = 3时也是输出second; n = 4时,第一个人想获胜就必须先拿1个,这时剩余的石子数为3,此时不管第二个人怎样取,第一个人都能赢,输出first; n = 5时,first不可能获胜,由于他取2时,second直接取掉剩下的3个就会获胜,当他取1时,这样就变成了n为4的情形,所以输出的是second; n = 6时,first仅仅要去掉1个,就能够让局势变成n为5的情形,所以输出的是first; n = 7时,first取掉2个,局势变成n为5的情形,故first赢,所以输出的是first; n = 8时,当first取1的时候,局势变为7的情形,第二个人可赢,first取2的时候,局势变成n为6得到情形,也是第二个人赢,取3的时候,second直接取掉剩下的5个,所以n = 8时,输出的是second; ………… 从上面的分析能够看出,n为2、3、5、8时,这些都是输出second,即必败点,细致的人会发现这些满足斐波那契数的规律,能够判断13也是一个必败点。 借助“Zeckendorf定理”(齐肯多夫定理):不论什么正整数能够表示为若干个不连续的Fibonacci数之和。n=12时,仅仅要谁能使石子剩下8且此次取子没超过3就能获胜。因此能够把12看成8+4,把8看成一个站,等价与对4进行”气喘操作”。又如13,13=8+5,5本来就是必败态,得出13也是必败态。也就是说,仅仅要是斐波那契数,都是必败点。 所以我们能够利用斐波那契数的公式:fib[i] = fib[i-1] + fib[i-2],仅仅要n是斐波那契数就输出No。

经常使用的博弈类型,基本就是这些。以后碰见很多其它的再来补充。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/118491.html原文链接:https://javaforall.cn

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021年12月,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档