今天学了一下博弈论基础的一些东西

【算法学习笔记】01 博弈论

公平组合游戏

Nim

n 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取，取走最后一个物品的人获胜。

如果Nim游戏中的规则变成每次最多只能取K个
则将每堆石子数mod (k+1).

概念

必胜态：先手必胜的状态
必败态：先手必败的状态

定理

没有后继状态的是必败态
一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

Nim和

SG函数

在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。

定义mex函数：
值位不属于集合S中的最小非负整数

Nim转化为有向图游戏

Nim枚举每一种状况
这样转化成一个有向图（图见例2），求出每个SG的值

例题

首先是基础课的：

1. 台阶-Nim游戏

https://www.acwing.com/problem/content/894/

分析：（来自评论区大佬）

因为第一阶拿到地面要拿一次，第二阶拿两次，第三阶拿三次…所以可以看成第二阶有两堆石子，第三阶有三堆….
因为偶数阶石子为偶数堆，所以异或为0，
奇数阶异或后就是原本石子数目，
所以可以把原本所有奇数阶的石子进行异或，得到的就是答案

易得Code:

#include <bits/stdc++.h>

using namespace std;

int main () {
    int ans = 0, n;
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        if (i & 1)  ans ^= x;
    }
    if (ans)    cout << "Yes\n";
    else    cout << "No\n";
}

2. 集合-Nim游戏

https://www.acwing.com/problem/content/895/

分析：

根据样例可画出这样一个有向图
每一堆石子都可以表示出这样一个状态图

得出SG的值

故可用记忆化搜索保存每一种状态

#include<bits/stdc++.h>

using namespace std;
const int N = 105, M = 10005;

int n, m, x, ans = 0;
int s[N], f[M];

int sg(int x){
	if(f[x] != -1)
		return f[x];

	set<int> S;
	for(int i = 0; i < m; i ++){
		int sum = s[i];
		if(x >= sum)    S.insert(sg(x - sum));
	}

    //mex
	for(int i = 0; ; i ++)
		if(!S.count(i))     return f[x] = i; 
}

int main() {
	cin >> m ;
	for(int i = 0; i < m; i ++)
		cin >> s[i];
	cin >> n;
	memset(f, -1, sizeof f);

	for(int i = 0; i < n; i ++){
		cin >> x;
		ans ^= sg(x);//同NIM
	}

	if(ans)     cout << "Yes";
	else    cout << "No";
}

3. 拆分-Nim游戏

https://www.acwing.com/problem/content/896/

分析：最大值在减少，故游戏一定能结束

对于每一堆求SG。关键在于怎么求SG：
由SG函数理论，多个独立局面的SG值，等于这些局面SG值的异或和。故一堆拆成两堆后，只需把局部异或起来即可得总体值。

Code:

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int f[N];

int SG (int x) {
    if (f[x] != -1)     return f[x];

    set <int> s;
    for (int i = 0; i < x; i ++)
        for (int j = 0; j <= i; j ++) {
            s.insert (SG(i) + SG(j));
        }

    for (int i = 0; ; i ++)
        if (!s.count (i))   return f[x] = i;
}

int main () {
    int n, ans = 0;
    cin >> n;
    memset (f, -1, sizeof f);
    while (n --) {
        int x;
        cin >> x;
        ans ^= SG(x);
    }
    if (ans)    cout << "Yes\n";
    else    cout << "No\n";
}

提高课的博弈论：

4. 移棋子游戏

https://www.acwing.com/problem/content/1321/

算是SG函数的模板题，由纯理论导出，直接求每个棋子的SG值异或和即可

#include <bits/stdc++.h>

using namespace std;
const int N = 2005, M = 6005;
int f[N], n, m, k, ans;
int h[N], e[M], ne[M], idx;

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int SG (int x) {
    if (f[x] != -1)     return f[x];

    set <int> s;
    for (int i = h[x]; ~i; i = ne[i])
        s.insert (SG(e[i]));

    for (int i = 0; ; i ++)
        if (!s.count (i))   return f[x] = i;
}

int main () {
    memset (h, -1, sizeof h);
    memset (f, -1, sizeof f);
    cin >> n >> m >> k;
    while (m --) {
        int x, y;
        cin >> x >> y;
        add (x, y);
    }
    while (k --) {
        int x;
        cin >> x;
        ans ^= SG(x);
    }
    if (ans)    cout << "win\n";
    else    cout << "lose\n";
}

5. 取石子

https://www.acwing.com/problem/content/1323/

==结论：（简单情况——所有堆的石子个数>1）设b=堆数+石子总数-1，则 先手必胜等价于b是奇数==

奇数一定存在一个偶数后继：

堆数>1, 合并两堆
堆数=1，取一个石子

偶数的所有后继必然是奇数：

合并
取一子

均可得证

终止状态：1堆1个的情况

懒得做笔记了，戳这里

6. 取石子游戏

https://www.acwing.com/problem/content/1324/

碎碎念

学到后面感觉一些比较复杂的题目还是离不开dp
果然dp真的很重要啊。。。
我还是先补补基础dp好了，要不然真是寸步难行TAT

以及，目前关于Nim和定理之类的，现有的资料都只提到了如何证明其必要性，而没有说明是怎么推导的。
问了大佬，大佬也表示暂时没找到答案。
希望某一天能知道是怎么来的吧

暂时先到这里啦

拓展学习：
https://www.cnblogs.com/candy99/p/6548836.html
https://zhuanlan.zhihu.com/p/257013159
https://zhuanlan.zhihu.com/p/359334008