首页 > 博弈论(sg函数)
头像
Tiramisu`
发布于 2020-11-19 21:50
+ 关注

博弈论(sg函数)

巴什博弈

  • 只有一堆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)的倍数,就能最后获胜。


##威佐夫博弈

  • 有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

我们再用逆推归纳法分析。我们用(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。

若两堆物品的初始值为(a , b),且x < y,定义k=b-a;定义x = [ ( ( sqrt(5) + 1 ) / 2 ) * k ]
若x=a,则先手必败,否则先手必胜。


##Nim博弈

  • 有n堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

这里奇异局势变成了多堆(x1,x2,x3…),所以有一个结论就是把每堆Xi异或起来,结果为0则先手必败


##sg函数
在网上看过了很多介绍sg函数的文章,但是感觉还是不太明白,就像当初第一次知道dp的时候。。。。。所以,还是自己再进行以下,浅显的个人理解。
sg函数:SG(x)=mex{ SG(y) | x->y },mex(x)表示非x集合中最小的自然数
以下就是个人的浅显理解:
在解释之前,首先要知道sg值只需要关注0非0两种状态就行了

在看了mex函数之后,是不是感觉字面理解了,但是,啥意思呢?
首先,一个点的下一个状态,也就是子状态会有很多个,然后每个子状态又会有自己的子状态。当一个状态的子状态可以直接判断为必胜态或者必败态的时候,子状态返回自己的sg值,然后,用一个vis数组存下来,这里vis数组就相当于mex函数,然后当当前状态所有子状态都返回了自己的sg值,并用vis记录了下来,那么,vis从0开始,没有被标记过的第一个自然数则是当前状态的sg值。
当一个值被vis数组记录过,那么说明当前状态可以转换成对应sg值的状态,那么,如果0被标记了,那么说明当前状态可以转换成必败态,呢么当前状态的sg值一定是非0的,也就是必胜态。到这里,mex函数的意义是不是有点明白了,就是寻找第一个不能转换到的状态,那么,在看之前说的只需要关注0非0两种状态就行了,意思就是,当你通过mex函数也就是vis数组找到的当前点的sg值为0则说明,当前点没办法转换到必败态,那么,当前点就是必败态,所以sg值为0;反之,非0则说明可以转换到必败态,那么当前则是必胜态。

当所有点的sg值都推出来了,答案一般就是所求点的sg值异或,异或值为0则先手必败,否则先手必胜。

那么,之前求出来的sg值非0时会有相同的值,那想一下,一旦出现了两个相同的先手必胜态,先手走什么,后手模仿的话,那么肯定是先手输,所以sg值非0相同时,异或值也是0,这个应该比较好想。

以上就是个人的理解,如有错误,希望大家帮我指出,不胜感激。

全部评论

(2) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐