博弈论二

ACM

复杂博弈论


推荐的论文
硬币翻转博弈

SG函数

推荐的学习博客
谈谈我的理解：
SG函数非常的像多堆的Nim博弈，唯一的区别就是SG函数还可以向后面的状态跳，但是这是没有什么意义的，因为对手不论怎样都可以返回原来的亦或为0的状态。
求SG的两种姿势：

以递推的形式进行打表

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
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int sg[maxn];
int f[maxn];
bool vis[maxn];
void solve(int n){
    for(int i=1; i<=n; i++){
        memset(vis, 0, sizeof(vis));
        for(int j=0; f[j]<=i&&j<3; j++){
            vis[sg[i-f[j]]] = true;
        }
        for(int j=0; j<=i; j++){
            if(!vis[j]){
                sg[i] = j;
                break;
            }
        }
    }
    for(int i=1; i<=n; i++){
        cout<<i<<" "<<sg[i]<<endl;
    }
}
int main(){
    f[0] = 1, f[1] = 2, f[2] = 4;
    solve(15);
    return 0;
}

以dfs来进行打表

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
30
31
32
33
34
35
36
37
38
39
40
41
42
//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int sg[maxn];
int n, m;
int s[maxn];
int dfs(int x){
    if(sg[x]!=-1) return sg[x];
    bool vis[maxn];
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<m; i++){
        if(x>=s[i]){
            dfs(x-s[i]);
            vis[sg[x-s[i]]] = true;//记住一定要使sg[y]的状态
        }
    }
    int ans = -1;
    for(int i=0; i<=x; i++){
        if(!vis[i]){
            ans = i;
            break;
        }
    }
    return sg[x] = ans;
}
int main(){
    s[0] = 1, s[1] = 2, s[2] = 4;
    memset(sg, -1, sizeof(sg));
    m = 3;
    n = 10;
    for(int i=1; i<=n; i++){
        dfs(i);
    }
    for(int i=1; i<=n; i++){
        cout<<i<<" "<<sg[i]<<endl;
    }
    return 0;
}

dfs打表

骑士有6种移动的方式，注意状态空间的转移

AC code

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int sg[maxn][maxn];
int n, t;
int dx[6] = {-1, 1, -1, -2, -2, -3};
int dy[6] = {-3, -2, -2, -1, 1, -1};
bool judge(int x, int y){
    if(x<0) return false;
    if(y<0) return false;
    return true;
}
int dfs(int x, int y){
    if(sg[x][y]!=-1) return sg[x][y];
    bool vis[maxn];
    memset(vis, 0, sizeof(vis));
    for(int i=0; i<6; i++){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(judge(nx, ny)){
            vis[dfs(nx, ny)] = true;
        }
    }
    for(int i=0; i<maxn; i++){
        if(!vis[i]){
            return sg[x][y] = i;
        }
    }
}
int main(){
    scanf("%d", &t);
    int kase = 1;
    memset(sg, -1, sizeof(sg));
    while(t--){
        scanf("%d", &n);
        int x, y;
        int ans = 0;
        for(int i=0; i<n; i++){
            scanf("%d%d", &x, &y);
            ans^=dfs(x, y);
        }
        if(ans){
            printf("Case %d: Alice\n", kase++);
        }
        else{
            printf("Case %d: Bob\n", kase++);
        }
    }
    return 0;
}

取石子游戏

游戏的规则是每一次只能取一堆石子个数的一半，向下取整。
不能取的人失败
先对单堆的石子求SG函数，发现以下的规律：

  1. 当n是偶数的时候， SG(n) = n/2;
  2. 当n是奇数的时候， SG(n) = SG(n/2);这里的是向下取整

递归的计算奇数堆的SG值就可以了

AC code

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//#include <bits/stdc++.h>
//using namespace std;
//const int mod = 1e9+7;
//const int maxn = 1e3;
//typedef long long ll;
//int vis[maxn];
//int sg[maxn];
//ll dfs(int x){
//    if(x%2 == 0) return x/2;
//    else return dfs(x/2);
//
//}
//
//
//int main(){
//    memset(vis, 0, sizeof(vis));
//    memset(sg, -1, sizeof(sg));
//    sg[1] = 0;
//    sg[0] = 0;
//    for(int i=1; i<=100; i++){
//        memset(vis, 0, sizeof(vis));
//        for(int j=1; 2*j<=i; j++){//注意不能取0个石子
//            vis[sg[i-j]] = 1;
//        }
//        for(int j=0; j<=i; j++){
//            if(!vis[j]){
//                sg[i] = j;
//                break;
//            }
//        }
//    }
//    for(int i=1; i<=100; i++){
//        if(i%2 == 1)cout<<i<<" "<<sg[i]<<endl;
//    }
//    return 0;
//}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dfs(int x){
    if(x%2 == 0) return x/2;
    else return dfs(x/2);
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    scanf("%d", &t);
    int kase = 1;
    while(t--){
        int n;
        scanf("%d", &n);
        int ans = 0;
        int temp;
        for(int i=0; i<n; i++){
            scanf("%d", &temp);
            ans ^= dfs(temp);
        }
        if(ans){
            printf("Case %d: Alice\n", kase++);
        }
        else{
            printf("Case %d: Bob\n", kase++);
        }
    }
    return 0;
}

E 取石子游戏2

知识的参考博客
有若干堆石子，但是最后取走石子的人为负，问先手必胜还是先手必败。
这是Nimm game的第二种形式
这里有关于充裕堆的定义：

定义：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。

下面定义几种状态：

  1. T:石子的各堆的个数亦或和为0。(利他态)
  2. S:各堆的石子的个数亦或和不为0.(利己态)

1.1: \(T_2\): 充裕堆的个数大于等于2.
1.2: \(T_0\): 充裕堆的个数为0.
ps:这里不存在\(T_1\):充裕堆的个数为1，是因为，各堆的石子的个数亦或和为0.不可能存在

2.1: \(S_0\): 仅有奇数个孤单堆
2.2: \(S_1\): 仅有一个充裕堆， 若干个孤单堆
2.3: \(S_2\): 大于等于两个充裕堆，若干个孤单堆，总之亦或和不为0

下面给出若干个性质：

  1. \(S_2\)无法转移到\(T_0\), 结论很显然
  2. \(S_0\)为必败态，也是很显而易见的。
  3. \(T_0\)为必胜态，相当于有偶数个1.
  4. \(S_1\)为必胜态，因为先手可以调节充裕堆的个数：当有奇数个1时，将充裕堆中的石子全部取走，变成了\(S_0\),先手胜；或者当有偶数个1时，充裕堆只剩下一个石子。
  5. \(T_2\)为必败态：\(T_2\)只能转移到\(S_2 or S_1\), \(S_2只能转移到T_2\)
  6. \(S_2\)为必胜态： \(S_2\)只能转移到\(T_2\),\(T_2\)是必败态

综上：\(T_2, S_0是必败态，S_2, S_1, T_0是必胜态\)

AC代码

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
30
31
32
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int num[maxn];
int n;
int main(){
    int t;
    ios::sync_with_stdio(false);
    cin>>t;
    int kase = 1;
    while(t--){
        cin>>n;
        int tot = 0;
        int Xor = 0;
        int single = 0;
        for(int i=0; i<n; i++){
            cin>>num[i];
            if(num[i] == 1) single++;
            Xor ^= num[i];
        }
        //T2或者是S0态是必败态，其他的状态是必胜态
        if((single<=n-2&&Xor==0)||(Xor!=0&&(single == n)&&single%2)){
            printf("Case %d: Bob\n", kase++);
        }
        else {
            printf("Case %d: Alice\n", kase++);
        }
    }
    return 0;
}

拆分石子游戏

有n堆石子，每一次只能将一堆石子分成数量不等的两堆。
注意用set来存状态，用vis[]数组会爆空间

AC code

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int sg[maxn];
int dfs(int x){
    if(sg[x]!=-1) return sg[x];
    int mid;
    set<int> s;//用set来计算mex， 用vis数组记录的开销太大了！！
    s.clear();
//    memset(vis, 0, sizeof(vis));
    if(x%2==0){
        mid = x/2-1;
    }
    else{
        mid = x/2;
    }
    for(int i=1; i<=mid; i++){
        s.insert(dfs(x-i)^dfs(i));//注意是两个子游戏的亦或！
    }
    for(int i=0; i<=x; i++){
        if(s.count(i) == 0){
            return sg[x] = i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    int kase = 1;
    memset(sg, -1, sizeof(sg));
    while(t--){
        int n;
        cin>>n;
        int temp;
        int ans = 0;
        for(int i=0; i<n; i++){
            cin>>temp;
            ans^=dfs(temp);
        }
        if(ans){
            printf("Case %d: Alice\n", kase++);
        }
        else{
            printf("Case %d: Bob\n", kase++);
        }
    }
    return 0;
}

树上博弈


我们可以得到下面的结论，一棵子树的根节点的SG值为各子子树根节点的SG值加1的亦或和
注意：
当对树的边权进行赋值的时候，前面的树形结构相当于边权为1。后面我们将会看到树带有边权的树上博弈

无向图上面的博弈要先进行相应的缩点，然后再进行树上博弈

有边权的树上博弈

每一次一个人将树上面的边权-1，当边权为0的时候，整棵子树都会被删除

题解

下面的解释我还不太会证明。先记住结论吧
SG定理，对于当前节点u，每次考虑字节点v，u-v边的长度为l

当l为1时：sg(u) ^= (sg(v) + 1)

当l为奇数时： 需要判断sg(v)奇偶性，奇数-1，偶数+1；

当l为偶数时：sg(u) ^= sg(v)

AC代码

1
2

棋盘上面的移动石子

通过相应的转换，然后转化为Nim博弈
假设(i, j)坐标上面有石子，如果(i+j)的奇偶性和(n+m)的奇偶性相同，那么后手可以仿照先手的步骤，那么剩下的棋盘的石子就是Nim博弈了

AC code

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
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d", &t);
    int kase = 1;
    while(t--){
        int r, c;
        scanf("%d%d", &r, &c);
        int ans = 0;
        int temp;
        for(int i=1; i<=r; i++){
            for(int j=1; j<=c; j++){
                scanf("%d", &temp);
                if((r+c-i-j)%2 == 0){
                    continue;
                }
                else{
                    ans ^= temp;
                }
            }
        }
        if(ans==0){
            printf("Case %d: lose\n", kase++);
        }
        else{
            printf("Case %d: win\n", kase++);
        }
    }
    return 0;
}

需要补充的题目

christmas game

未解决的问题

本文标题:博弈论二

文章作者:Babydragon

发布时间:2018-05-22, 19:26:48

最后更新:2018-05-26, 22:29:14

原始链接:http://baolintian.github.io/2018/05/22/博弈论二/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. SG函数
    1. 1.1. 以递推的形式进行打表
    2. 1.2. 以dfs来进行打表
  2. 2. dfs打表
    1. 2.1. AC code
  3. 3. 取石子游戏
    1. 3.1. AC code
  4. 4. E 取石子游戏2
    1. 4.1. AC代码
  5. 5. 拆分石子游戏
    1. 5.1. AC code
  6. 6. 树上博弈
    1. 6.1. 有边权的树上博弈
      1. 6.1.1. 题解
      2. 6.1.2. AC代码
  7. 7. 棋盘上面的移动石子
    1. 7.1. AC code
  8. 8. 需要补充的题目
  9. 9. 未解决的问题
{{ live2d() }}