博弈论

公平组合游戏

公平组合游戏（ICG）需要满足以下条件

1. 有两名玩家
2. 两名玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面
3. 一个局面的合法操作，只取决于游戏局面本身且固定存在，与玩家次序或者任何其它因素无关
4. 无法操作者，即操作集合为空，输掉游戏，另一方获胜

SG函数

对于一个ICG，我们定义一个函数 $sg(x)$ ,$sg(x)=mex(\{ sg(y)|x->y \})$ 即一个状态下的sg函数值为这个状态所能转移到的所有状态的sg，再取mex
如果 $sg(x)=0$ 则状态x为必败态，反之为必胜态

对于多个ICG，我们有Sprague-Grundy定理：

设 $x_1,x_2,...,x_n$ 为ICG的状态，则：
$sg(x_1+x_2+...+x_n)=sg(x_1) \oplus sg(x_2) \oplus ... \oplus sg(x_n)$

常见博弈

Nim

即取石子游戏，有以下情况：

1. 可选步数为1~m的连续整数，则 $sg(x)=x$
2. 可选步数为任意步，则 $sg(x)=x$
3. 可选步数为一系列不连续的数，采用打表，预处理sg数组

阶梯博弈

k-Nim

k-nim是Nim的变形，即每次可以从不超过k个堆中取出任意个石子，不能取的一方为输。
首先我们把每个堆石子的数量表示为二进制，然后对所有的数逐位判断。如果有一位，所有的数这一位上为1的数量$\%(k+1)$不为0，则先手必胜。反之先手必输

anti-Nim

和一般的Nim差不多，不过变成了把最后的石子取完的一方为输。我们有SJ定理：

先手必胜，当且仅当：
（1）单一游戏中有一个SG大于1，且整个游戏SG不为0
（2）单一游戏中所有的SG小于等于1，且整个游戏SG为0

例题

P2148 [SDOI2009] E&D
首先打表找出sg函数的规律

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
int sg[21][21],vis[21][21];

const int n=20;

int dfs(int x,int y){
	if(vis[x][y]||vis[y][x]) return sg[x][y];
	if(x==1&&y==1) return 0;
	vector<int> v;
	//case1
	for(int i=1;i<x;i++){
		v.push_back(dfs(i,x-i));
	}
	//case2
	for(int i=1;i<y;i++){
		v.push_back(dfs(i,y-i));
	}
	sort(v.begin(),v.end());
	int p=0;
	for(int i:v){
		if(i<p) continue;
		if(i!=p){
			break;
		}
		p++;
	}
	vis[x][y]=vis[y][x]=true;
	sg[x][y]=sg[y][x]=p;
	return p;
}

得到下表

找到规律

实现sg函数

cpp
1
2
3
4
5
6
7
8
int getSG(int x,int y){
	if(x%2==1&&y%2==1){
		return 0;
	}
	if(y%2==0) swap(x,y);
	if(y%2==1) y++;
	return getSG(x/2,y/2)+1;
}

还可以检查一下

cpp
1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		if(getSG(i,j)==dfs(i,j)){
			cout<<"accept"<<endl;
		}else{
			cout<<"wa"<<endl;
		}
	}
}