2021-07-09

博弈论之SG函数

引入:
nim游戏,地上有 n 堆石子(每堆石子数量小于 10^4),每人每次可从任意一堆石子里取出任意多枚石子扔掉,可以取完,不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手,且告诉你这 n 堆石子的数量,他想知道是否存在先手必胜的策略。

定义:
luogu P2197 【模板】nim 游戏
Nim游戏是经典的公平组合游戏(ICG),对于ICG游戏我们有如下定义:

  • 两名选手
  • 两名选手轮流行动,每一次行动可以在有限合法操作集合中选择一个
  • 游戏的任何一种可能的局面(position),合法操作集合只取决于这个局面本身,不取决于轮到哪名选手操作、以前的任何操作、骰子的点数或者其它因素;局面的改变称为“移动”(move)
  • 如果轮到某名选手移动,且这个局面的合法的移动集合为空(也就是说此时无法进行移动),则这名选手输掉比赛

对于第三条,我们有更进一步的定义Position,我们将Position分为两类:

P-position:在当前的局面下,先手必败
N-position:在当前的局面下,先手必胜

它们有如下性质:

合法操作集合为空的局面是P-position
可以移动到P-position的局面是N-position
所有移动都只能到N-position的局面是P-position

我们对于此题,明显不可以用dfs,bfs等暴力模拟,So,引出我们的主题————

SG函数:

事实上,任何一个ICG游戏都可以通过把每个局面看成一个顶点,对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义SG(Sprague-Garundy)函数。

2021-07-09
先介绍 mex 运算,这是施加于一个集合的运算,表示最小的不属于(没出现过)这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

定义关于图的每个顶点的SG函数sg如下:sg(x)=mex{ sg(y1),sg(y2),sg(y3)… }(所有x出边所连的y)。也就是说,一个点的SG函数为在它所有后继中都未出现的最小的值。

ps:此处后继不为Splay中的后继,为所有x出边所连的y

对于一个sg(x)=0的顶点x,它的所有后继y都满足 sg(y)≠0。
对于一个sg(x)≠0的顶点,必定存在一个后继y满足sg(y)=0。

可以发现,顶点x所代表的postion是P-position当且仅当sg(x)=0,x点必先手败(跟P-positioin/N-position的定义是完全对应的)

如果如nim游戏,有 n 堆石子,我们只需将其拆成 n 个子游戏
So, sg(总体)=sg(子游戏1) ^ (子游戏2) ^ (子游戏3) ^ … ^ (子游戏n)

SG值的计算方法(重点)
可选步数为1~m的连续整数,直接取模即可,sg(x) = x % (m+1);
可选步数为任意步,sg(x) = x;
可选步数为一系列不连续的数,用"模板"计算。

又到了 喜闻乐见 的抄代码环节!
code:

int f[12],sg[1021];//f[]记录一次可取石子数
bool mex[1021];
void getSG(int n){//注意f[]要从小到大sort排序
	for (int i=1;i<=n;i++){
		for(int j=0;j<=n;j++)mex[j]=false;
		for (int j=1;f[j]<=i&&j<=m;j++)mex[sg[i-f[j]]]=1;//查后继的sg值
		for (int j=0;j<=n;j++)if(!mex[j]){sg[i]=j;break;}//查i的sg值
	}
}

ps:其实还有一种dfs的方法求sg,但博主是jrlqw(大蒟蒻),不会打…其实是觉得dfs不好,太复杂了

拓展:

51nod 3431 取石子游戏
题意:
A君和B君正在玩一个取石子游戏。 取石子游戏的规则是这样的,每个人每次可以从N堆中从一堆石子中取出若干个石子,每次取石子的个数有限制(会给出每次可取的个数,不同无规律),谁不能取石子时就会输掉游戏。 A君先进行操作,他想问你他是否有必胜策略,如果有,第一步如何取石子,在哪堆取几个?

输入文件的第一行为石子的堆数N,接下来N行,每行一个数Ai,表示每堆石子的个数。接下来一行为每次取石子个数的种类数M,接下来M行,每行一个数Bi,表示每次可以取的石子个数,输入保证这M个数按照递增顺序排列。

输出文件第一行为“YES”或者“NO”,表示小H是否有必胜策略。 若结果为“YES”,则第二行包含两个数,第一个数表示从哪堆石子取,第二个数表示取多少个石子,若有多种答案,取第一个数最小的答案,若仍有多种答案,取第二个数最小的答案。

数据规模和约定
数据编号 N范围 Ai范围 数据编号 N范围 Ai范围
1 N=2 Ai≤10 6 N≤10 Ai≤10
2 N=2 Ai≤1000 7 N≤10 Ai≤100
3 N=3 Ai≤100 8 N≤10 Ai≤1000
4 N≤10 Ai≤4 9 N≤10 Ai≤1000
5 N≤10 Ai≤7 10 N≤10 Ai≤1000
对于全部数据,M≤10,Bi≤10

样例
input:
4
7 6 9 3
2
1 2
output:
YES
1 1

tips:用sg值解,如果可行,先手必胜,第一步如何取石子,在哪堆取几个?如何判断呢?设在第 i 堆取第 j 中的个数个,N堆的sg值的xor和为all ,如果 all ^ sg[a[i]] ^ sg[a[i]-f[j]] == 0 则 可于 第 i 堆取 f[j] 个!(可用sg的意义&N、P局面来理解,从胜败角度判断)

最后,希望大家都可以从中学习到有用的知识,希望这篇文章对你有帮助

(反正博主觉得很有收获)

上一篇:webView 加载本地文件 - html/htm pdf docx tx


下一篇:博弈论-公平组合游戏