博弈论(Bash博弈、Nim博弈、SG函数、组合博弈)

组合博弈入门

一、博弈论三条性质：

• 终结点为P点

• P点只能到N点

• N点至少有一种途径到P点

N：必胜态 P：必败态

  

1、引导题

1846 Brave Game

题目大意：
n个石子两人轮流取1~m个，最后取空的胜利


n：23  m：2
0：P      //终结点
1：N
2：N
3：P
4：N
5：N
6：P

结论： x % (m + 1) == 0 则为P点
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include 
#include 

using namespace std;

int main() {
    int t, n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        cout << (n % (m + 1) ? "first" : "second") << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

2、引导题

1847 Good Luck in CET-4 Everybody!

题目大意：
n张纸牌两人轮流取2的幂次(1, 2, 4, 8, 16……),最后取空的胜利

同理上一题取石子
0 1 2 3 4 5 6 7 8 9 10 11 12 13
P N N P N N P N N P N  N  P  N
结论： n % 3 == 0 则为P点
1
2
3
4
5
6
7

#include 
#include 

using namespace std;

int main() {
    int n;
    while (cin >> n) {
        cout << ((n % 3) ? "Kiki" : "Cici") << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

  

  

二、NIM博弈

定理： 如果先手必胜，则有$A_{1}xor{A}_{2}xor...A_n\ne 0$

  就是控0，所有堆都为空时异或为0。只要还剩石子，并且异或为0，那么至少还有两堆，或者说一次必取不完局面。就把这种局面一直扔给对手，使自己保证永远不败状态，此时无论对手怎么取，异或都不为0。

27:	  11011  num[0]  
8:    01000  num[1]
20:   10100  num[2]
13:   01101  num[3]
      ---- ^
10:   01010  sum

nim[i] > (nim[i] ^ sum) 为可选方案  注意：运算符优先级
nim[i] = nim[i] ^ sum 为具体调整方案
1
2
3
4
5
6
7
8
9

  

1、先手状态判定

1849 Rabbit and Grass

题目大意：
n堆石子，两人轮流选一堆取走任意个，最后取空的胜利，问先手必赢还是必输

解题思路：NIM博弈
1
2
3
4

#include 
#include 

using namespace std;

int main() {
    int n;
    while (cin >> n && n) {
        int Xor = 0, x;
        while (n--) {
            cin >> x;
            Xor ^= x;
        }
        cout << (Xor ? "Rabbit Win!" : "Grass Win!") << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  

2、先手必胜第一手方案数

1850 Being a Good Boy in Spring Festival

题目大意：
nim博弈如果先手必胜的话，那么输出第一步用多少种选择。反之先手必败输出0
1
2

#include 
#include 

using namespace std;

#define N 100

int nim[N +  10];

int main() {
    int n;
    while (scanf("%d", &n) && n) {
        int sum = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%d", nim + i);
            sum ^= nim[i];
        }
        for (int i = 0; i < n; ++i) {
            if (nim[i] > (nim[i] ^ sum))  ++ans;
            //nim[i] = nim[i] ^ sum 为具体调整方案
        }
        printf("%d\n", ans);
    }
    return 0;
}
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

  

  

  

三、SG函数

有向图游戏

​ 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
​ **任何一个公平组合游戏都可以转化为有向图游戏。**具体方法是,把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

​ 设 $S$​​​ 表示一个非负整数集合。定义 $Mex(S)$​ 为求出不属于集合 $S$​ 的最小非负整数的运算。

SG函数

​ 在有向图游戏中，对于每个节点 $x$ , 设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1,y_2,...,y_k$，定义$SG(x)$为 $x$ 的后继节点 $y_1,y_2,...,y_k$ 的 $SG$函数值构成的集合再执行$Mex\ $运算的结果，即$SG(x)=Mex({SG(y_1),SG(y_2),…,SG(y_k)})$​

​ 特别的，整个有向图游戏 $G$​​​ 的 $SG$ 函数值被定义为有向图游戏起点 $s$ 的 $SG$ 函数值，即 $SG(G)=SG(s)$​

​ 有向图游戏的和：设$G_1,G2,...,G_m$​是 $m$​ 个有向图游戏。定义有向图游戏 $G$​，它的行动规则是任选某个有向图游戏$G_i$​，并在 $G_i$​上行动一步。$G$​ 被称为有向图游戏$G_1,G_2,\dots ,G_m$​ 的和

​ 有向图游戏的和的$SG$​​函数值等于它包含的各个子游戏$SG$​函数值的异或和，即:$SG(G)=SG(G_1)xorSG(G_2)xor...xorSG(G_m)$​

​ 定理

​ 有向图游戏的某个局面必胜，当且仅当该局面对应节点的$SG$​​函数值大于$0$

​ 有向图游戏的某个局面必败，当且仅当该局面对应节点的$SG$​函数值等于$0$​

​ 我们不再详细证明该定理。读者可以这样理解:
​ 在一个没有出边的节点上，棋子不能移动，它的$SG$​​​​​​值为$0$​​​​​​，对应必败局面。若一个节点的某个后继节点$SG$​​​​​​值为$0$​​​​​​，在$\ Mex\ $运算后，该节点的$SG$​​​​​​值大于$0$​​​​​​.这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。
​ 若一个节点的后继节点$SG$​​​​值均不为$0$​​​，在$\ Mex\ $运算后，该节点的$SG$​值为$0$。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。
  

1、多堆取石子

1848 Fibonacci again and again

题目大意：
三堆石子，两人轮流取f个，最后取空的胜利
f[1] = 1, f[2] = 2, f[3] = 3, f[4] = 5, ... , f[n] = f[n - 1] + f[n - 2]

解题思路：SG函数
1
2
3
4
5

#include 
#include 
#include 

using namespace std;

#define N 1000

int SG[N + 10], flag[N + 10], fib[N];

void Get_Fib() {
    fib[1] = 1;
    fib[2] = 2;
    for (int i = 3; fib[i - 1] < N; ++i)  fib[i] = fib[i - 1] + fib[i - 2];
    return ;
}

void Get_SG() {
    for (int i = 1; i <= N; ++i) {
        memset(flag, 0, sizeof(flag));
        for (int j = 1; i - fib[j] >= 0; ++j)  flag[SG[i - fib[j]]] = 1;
        int ind = 0;
        while (flag[ind])  ++ind;
        SG[i] = ind;
    }
    return ;
}

int main() {
    Get_Fib();
    Get_SG();
    int m, n, p;
    while(scanf("%d%d%d", &m, &n, &p) && m && n && p) {
        printf("%s\n", SG[m] ^ SG[n] ^ SG[p] ? "Fibo" : "Nacci");
    }
    return 0;
}
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

  

2、拍卖会

2149 Public Sale

题目大意：
底价为0，轮流加价1~m，率先加到不小于n的胜利。依次输出先手必胜的情况第一次可以叫的价钱，如果先手必败输出none

解题思路：
以终点n作为博弈起点，倒序求SG值
SG yyds！
1
2
3
4
5
6

#include 
#include 
#include 

using namespace std;

#define N 1100

int SG[N + 10], flag[N + 10];

void Get_SG(int n, int m) {
    for (int i = n; i > 0; --i) {
        memset(flag, 0, sizeof(flag));
        for (int j = 1; j <= m && i + j <= n; ++j) {
            flag[SG[i + j]] = 1;
        }
        for (int j = 0; ; ++j) {
            if (flag[j] == 0) {
                SG[i] = j;
                break;
            }
        }
    }
    return ;
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        if (m >= n) {
            for (int i = n; i <= m; ++i) {
                if (i - n)  putchar(' ');
                printf("%d", i);
            }
            putchar('\n');
            continue;
        }
        Get_SG(n, m);
        bool is = true;
        for (int i = 1; i <= m; ++i) {
            if (SG[i])  continue;
            if (!is)  putchar(' ');
            printf("%d", i);
            is = false;
        }
        if (is)  printf("none\n");
        else  putchar('\n');
    }
    return 0;
}
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

  

3、志愿者选拔

2188 悼念512汶川大地震遇难同胞——选拔志愿者

题目大意：
低价为0，轮流加价1~m，率先加到不小于n的胜利。先手必胜输出Grass，反之Rabbit
1
2

#include 
#include 
#include 

using namespace std;

#define N 10000
#define M 10        //注意这里可以节约空间花销，m<=10,一个点最多十个后继，SG值不可能大于等于10

int SG[N + 10], flag[M + 10];

void Get_SG(int n, int m) {
    for (int i = n; i > 0; --i) {
        memset(flag, 0, sizeof(flag));
        for (int j = 1; j <= m && i + j <= n; ++j) {
            flag[SG[i + j]] = 1;
        }
        for (int j = 0; ; ++j) {
            if (flag[j])  continue;
            SG[i] = j;
            break;
        }
    }
    return ;
}

int main() {
    int t, n, m;
    cin >> t;
    while (t--) {
        scanf("%d%d", &n, &m);
        if (m >= n)  printf("Grass\n");
        else {
            Get_SG(n, m);
            bool is = 0;
            for (int i = 1; i <= m; ++i) {
                if (SG[i])  continue;
                is = 1;
                break;
            }
            printf("%s\n", is ? "Grass" : "Rabbit");
        }
    }
    return 0;
}
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

  

4、组合博弈

1536 S-Nim

1944 S-Nim

题目大意：
5 1 2 3 4 5   //5种取子规则
3             //3次询问
2 5 12        //第一次 2堆石子 分别5和12块石子
3 2 4 7		  //第二次
4 2 3 7 12    //第三次
0			  //输入0结束

记忆化搜索SG值，只计算用到的SG值，没有用到的SG值不计算，减少了部分时间开销
1
2
3
4
5
6
7
8
9

#include 
#include 
#include 
#include 

using namespace std;

#define N 10000
#define M 100

int vis[M + 5], SG[N + 5];   //vis取子规则 

int Get_SG(int x, int &k) {
    if (~SG[x])  return SG[x];
    int flag[M + 5] = {0};
    for (int i = 1; i <= k && x - vis[i] >= 0; ++i) {
        flag[Get_SG(x - vis[i], k)] = 1;
    }
    int ind = 0;
    while (flag[ind])  ++ind;
    return SG[x] = ind;
}

int main() {
    int k, t;
    while (scanf("%d", &k) && k) {
        memset(SG, -1, sizeof(SG));
        SG[0] = 0;
        for (int i = 1; i <= k; ++i)  scanf("%d", vis + i);
        sort(vis + 1, vis + k + 1);    //取子规则需提前排序
        scanf("%d", &t);
        while (t--) {
            int n, Xor = 0;
            scanf("%d", &n);
            for (int i = 1, x; i <= n; ++i) {
                scanf("%d", &x);
                Xor ^= Get_SG(x, k);
            }
            printf("%c", Xor ? 'W' : 'L');
        }
        putchar('\n');
    }
    return 0;
}
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