博弈论

简介

两人在公平规则下进行有限的对决，胜负明确

类似有向无环图，由一个状态转移到下一个状态

对先手来说，存在两种状态，即必胜态和必败态

必胜态

当前状态的后续为必败态，当前状态即为必胜态

必败态

不存在后续，或是所有后续都必胜

DP 解决博弈

利用状态转移的关系，来解决简单的博弈问题

移棋子问题

$n \times m$ 的棋盘，$(1,1)$ 在左上角，$(n,m)$ 在右下角，每格标明黑白两色
上面有一个棋子，Alice 和 Bob 轮流移动这个棋子，Alice 先手移动，每次可以向上或向左移动一格，一旦移动到第一行或第一列游戏结束，执行最后一步移动的人，如果将棋子移动到黑格，就获胜，反之，则失败。
现在给这个棋子的起始位置，问最后获胜的玩家是谁，对于所有的 $(i,j)$ 满足 $2 \leq i,j \leq n$ 输出

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10010;

int dp[MAXN][MAXN],n,m;
string a,b;

int main(){
    cin>>n>>m>>a>>b;
    for(int i=0;i<=m-2;i++){
        dp[1][i+2]=(a[i]=='W');
    }
    for(int i=0;i<=n-2;i++){
        dp[i+2][1]=(b[i]=='W');
    }
    for(int i=2;i<=n;i++){
        for(int j=2;j<=m;j++){
            dp[i][j]=!(dp[i-1][j]&&dp[i][j-1]);
            if(dp[i][j])cout<<"A";
            else cout<<"B";
        }
        puts("");
    }
}

取石子游戏

有一堆石子，大小为 $x$，Alice 和 Bob 轮流操作，Alice 先手，Alice 每次可以取 $a[i]$ 个石子，Bob 可以取 $b[i]$ 个，谁不能操作就输。
问谁能获胜，对 $x = 1 \sim m$ 都输出

 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


#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int n1, n2, m, a[N], b[N], A[N], B[N];

int main(){
    cin >> n1 >> n2 >> m;
    for (int i = 1; i <= n1; i++){
        cin >> a[i];
    }
    for (int i = 1; i <= n2; i++){
        cin >> b[i];
    }
    for (int i = 1; i <= m; i++){
        for (int j = 1; j <= n1; j++){
            if(i >= a[j] && B[i-a[j]] == 0){
                A[i] = 1;
                break;
            }
        }
        for (int j = 1; j <= n2; j++){
            if(i >= b[j] && A[i-b[j]] == 0){
                B[i] = 1;
                break;
            }
        }
        puts(A[i] ? "Alice" : "Bob");
    }
    return 0;
}

带和局的情况

存在先手必败，胜
存在和，和
败

经典模型

巴什博弈

有 $n$ 个石子，每次取 $1 \sim m$ 个，Alice 先取，谁取最后一颗谁胜

$n % (m + 1) = 0$，先手必败
$n % (m + 1) \neq 0$，先手必胜

威佐夫博弈

有两堆石子，分别有 $a, b$ 颗，每次可以选一堆取 $x$ 个，也可以选两堆都取 $x$ 个
所以 $(a, b)$ 有三种转移，$(a-x, b)$, $(a, b-x)$, $(a-x, b-x)$;

打表找规律

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int dp[N][N];

int main(){
    for (int i = 0; i <= 100; i++){
        for (int j = 0; j <= 100; j++){
            for (int x = 1; x <= i; x++)
                if (dp[i - x][j] == 0) dp[i][j] = 1;
            for (int x = 1; x <= j; x++)
                if (dp[i][j - x] == 0) dp[i][j] = 1;
            for (int x = 1; x <= i && x <= j; x++)
                if (dp[i - x][j - x] == 0) dp[i][j] = 1;
            if (dp[i][j] == 0) printf("%d %d\n", i, j);
        } 
    }
    return 0;
}

首先发现 $(a, b)$ 和 $(b, a)$，状态相同，即同为必败态或必胜态
再对 $a < b$ 的情况分析，发现 $a$ 是从 $1$ 到 $n$ 的，$b - a$ 逐渐递增，依次为 $1, 2, 3, 4, 5, …$

Nim 模型

有 $n$ 堆石子，每堆有 $a[i]$ 个石子，Alice 和 Bob 轮流取，Alice 先取，每次可以从选一堆任取 $x$ 个石子，可以拿光，但不能不拿，谁最后把所有的拿光谁获胜

先打表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int dp[N][N];

int main(){
    for (int i = 0; i <= 100; i++){
        for (int j = 0; j <= 100; j++){
            for (int x = 1; x <= i; x++)
                if (dp[i - x][j] == 0) dp[i][j] = 1;
            for (int x = 1; x <= j; x++)
                if (dp[i][j - x] == 0) dp[i][j] = 1;
            // for (int x = 1; x <= i && x <= j; x++)
            //     if (dp[i - x][j - x] == 0) dp[i][j] = 1;
            if (dp[i][j] == 0) printf("%d %d\n", i, j);
        } 
    }
    return 0;
}

发现 $i == j$，经推广更多维，可以总结出必败态：$A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_n = 0$
要证明此结论，可从三个定理入手
1：没有后续状态的状态是必败态
2：对于 $A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_n \neq 0$ 的局面一定存在某种移动使 $A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_n = 0$
3：对于 $A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_n = 0$，不存在一种移动使 $A_1 \oplus A_2 \oplus A_3 \oplus … \oplus A_n = 0$

例题练习

石子游戏 2

有 $n$ 堆石子，每堆有 $a[i]$ 个石子，Alice 和 Bob 轮流操作，每次可以把一堆个数为奇数的石子分为两堆，两堆都不能为空，或把两堆为偶数的石子和为一堆

可以注意到两种操作都是对堆数改变，那么堆数的奇偶性就是突破点，同时根据操作的实质，可以发现只有 $1$ 个石子的堆是无法继续操作的，最后石堆将变成全是 $1$ 或者 $1$ 个偶数剩下的全是 $1$

所以结论就是：如果石堆全是 $1$，则先手必败，如果不是全为 $1$ 那么就检测结束时堆数的奇偶性是否改变

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int n, odd, one;
int x;

int main(){
    cin >> n;
    for (int i = 1;i <= n; i++){
        cin >> x;
        if (x % 2 == 1) odd++;
        if (x == 1) one++;
    }
    if (one != n) odd++;
    if ((odd + n) % 2 != 0)cout << "Alice\n";
    else cout << "Bob";
    return 0;
}

石子游戏 3

有 $n$ 堆石子，每堆有 $a[i]$ 个石子，Alice 和 Bob 轮流操作，选择 $n/2$ 堆非空石子，每堆移除掉正数个(可以不同)的石子，从 Alice 开始。

倒推：
必败：超过 $n/2$ 个堆已经为 $0$
必胜：有 $1 \sim n/2$ 个堆为 $0$
必败：有 $> n/2$ 个堆石子数量为 $1$
必胜：有 $1 \sim n/2$ 个堆的数量为 $1$
必败：有 $> n/2$ 个堆的数量为 $2$
……
有大于 $n/2$ 个堆的数量 = min，必败

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <bits/stdc++.h>
using namespace std;
const int N = 10010;

int n, mx = 1e9, cnt;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if (x < mx) mx = x, cnt = 0;
        if (x == mx) cnt++;
    }
    if (cnt > n/2) cout << "Alice\n";
    else cout << "Bob\n";
    return 0;
}

SG 板子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <bits/stdc++.h>
using namespace std;

int sg[1010];

int main() {
    int n, p;
    cin >> n >> p;
    for (int i = 1; i <= n; i++) {
        set<int> s;
        for (int j = 1; j <= i; j *= p) {
            s.insert(sg[i - j]);
        }
        while (s.count(sg[i])) sg[i]++;
        printf("%d %d\n", i, sg[i]);
    }
    return 0;
}