博弈论知识点

公平组合游戏ICG

若一个游戏满足：

  1. 由两名玩家交替行动；
  2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
  3. 不能行动的玩家判负；

则称该游戏为一个公平组合游戏。
NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

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

Mex运算

设S表示一个非负整数集合。定义mex(S)为求出不属于集合S的最小非负整数的运算，即：
mex(S) = min{x}, x属于自然数，且x不属于S

SG函数

在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1, y2, …, yk，定义SG(x)为x的后继节点y1, y2, …, yk 的SG函数值构成的集合再执行mex(S)运算的结果，即：
SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即SG(G) = SG(s)。

有向图游戏的和 —— 集合-Nim游戏

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：
SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理

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

Nim游戏

题意

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思考

必胜状态和必败状态
在解决这个问题之前，先来了解两个名词：

  1. 必胜状态，先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某 一个必败状态。
  2. 必败状态，先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

结论

假设n堆石子，石子数目分别是a1,a2,…,an，如果a1⊕a2⊕…⊕an≠0，先手必胜；否则先手必败。

证明

  • 操作到最后时, 每堆石子数都是 $0,0 \oplus 0 \oplus \ldots 0=0$

  • 在操作过程中, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=x \neq 0$ 。那么玩 家必然可以通过拿走某一堆若干个石子将异或结果变为 0 。

    证明: 不妨设x的二进制表示中最高一位1在第 $\mathrm{N}$ 位, 那么在 $a_{1}, a_{2}, \ldots, a_{n}$ 中, 必然有一个数 $a_{i}$, 它的第 $\mathrm{k}$ 为时 1 , 且$a_{i} \oplus x<a_{i}$, 那么从第 $i$ 堆石子中拿走 $\left(a_{i}-a_{i} \oplus x\right)$ 个石子,第 $i$ 堆石子还剩 $a_{i}-\left(a_{i}-a_{i} \oplus x\right)=a_{i} \oplus x$, 此时$a_{1} \oplus a_{2} \oplus \ldots \oplus a_{i} \oplus x \oplus \ldots \oplus a_{n}=x \oplus x=0$ 。

  • 在操作过程中, 如果 $a_{1} \oplus a_{2} \oplus \ldots \oplus a_{n}=0$, 那么无论玩 家怎么拿, 必然会导致最终异或结果不为 0 。
    反证法：假设玩家从第 $i$ 堆石子拿走若干个, 结果仍是 0 。不妨 设还剩下 $a^{\prime}$ 个, 因为不能不拿, 所以 $0 \leq a^{\prime}<a_{i}$, 且$a_{1} \oplus a_{2} \oplus \ldots \oplus a^{\prime} \oplus \ldots \oplus a_{n}=0$ 。那么$\left(a_{1} \oplus a_{2} \oplus \ldots \oplus a_{i} \oplus \ldots a_{n}\right) \oplus\left(a_{1} \oplus a_{2} \oplus \ldots \oplus a^{\prime} \oplus\right.$. 则 $a_{i}=a^{\prime}$, 与假设 $0 \leq a^{\prime}<a_{i}$ 矛盾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
using namespace std;
typedef long long LL;
int ans,n,x;
int main() {
    cin>>n;
    while(n--){
        scanf("%d",&x);
        ans^=x;
    }
    if(ans){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

台阶-Nim游戏

题意

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。

两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。

已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思考

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

证明：
先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
于是轮到后手：
①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0
因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。
（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
using namespace std;
typedef long long LL;
int ans,n,x;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(i%2) ans^=x;
    }
    if(ans){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

集合-Nim游戏（SG函数）

题意

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

思考

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include<vector>
#include<cstring>
#include<unordered_set>
using namespace std;
typedef long long LL;
int ans,n,k,s[105],f[10010];
int sg(int i){
    if(f[i]!=-1) return f[i];
    unordered_set<int> St;
    for(int j=0;j<k;j++){
         int sum = s[j];
        if (i >= sum) St.insert(sg(i - sum));
    }
    for(int j=0;;j++){
        if(!St.count(j))
            return f[i]=j;
    }
}
int main() {
    cin>>k;
    for(int i=0;i<k;i++){
        scanf("%d",&s[i]);
    }
    cin>>n;
    memset(f,-1,sizeof f);
    for(int i=0;i<n;i++){
        int x;
        scanf("%d",&x);
        ans^=sg(x);
    }

    if(ans){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

灭鼠先锋

题意

在 2 行 4 列的棋盘中，两人轮流操作，每次可选择在空位上放置 1 个棋子，或者在同一行连续的两个空位上放置棋子。最后使得棋盘放满的人输掉。

先手存在 4 种初始局面如下所示， O 表示空， X 表示已放置。每人均以最优策略放棋子。判断先手胜利（输出 V）还是后手胜利（输出 L）。

1
2
XOOO XXOO OXOO OXXO
OOOO OOOO OOOO OOOO

思考

直接搜索状态，可以用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
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const LL N=1010,mod=998244353;

int sg(string x){
    if(x=="0xxxxxxx"||x=="x0xxxxxx"||x=="xx0xxxxx"||x=="xxx0xxxx"||
    x=="xxxx0xxx"||x=="xxxxx0xx"||x=="xxxxxx0x"||x=="xxxxxxx0") return 0;
    if(x=="xxxxxxxx") return -1;

    unordered_set<int> st;
    for(int i=0;i<=7;i++){
        if(x[i]=='0'){
            x[i]='x';
            st.insert(sg(x));
            x[i]='0';
        }
    }
    for(int i=0;i<=6;i++){
        if(x[i]=='0'&&x[i+1]=='0'&&i!=3){
            x[i+1]=x[i]='x';
            st.insert(sg(x));
            x[i+1]=x[i]='0';
        }
    }
    for(int i=0;;i++){
        if(!st.count(i)) return i;
    }
}

int main(){
    cout<<sg("0000x000")<<endl;
    cout<<(sg("0000xx00"))<<endl;
    cout<<sg("00000x00")<<endl;
    cout<<sg("00000xx0")<<endl;
    return 0;
}

移棋子游戏

题意

给定一个有 N 个节点的有向无环图，图中某些节点上有棋子，两名玩家交替移动棋子。

玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，双方都会采取最优的行动，询问先手必胜还是先手必败。

思考

先对DAG上每个点求sg函数的值

考虑只有一个棋子，那么答案就取决于该棋子所在的点的SG值

多个棋子，相当于对多个相同的只有一个棋子的图进行操作，将所有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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include "cstring"
#include "vector"
#include "map"
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const LL N=1010,mod=998244353;

int n,m,k,x,y;
vector<int> mp[2010];
int f[2010];

void sg(int u){
    if(f[u]!=-1) return;
    map<int,int> cnt;
    for(int nx:mp[u]){
        sg(nx);
        cnt[f[nx]]++;
    }
    for(int i=0;;i++)
        if(cnt[i]==0){
            f[u]=i;
            return;
        }
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        mp[x].push_back(y);
    }
    memset(f,-1,sizeof f);
    for(int i=1;i<=n;i++){
        sg(i);
    }
    int res=0,nx;
    for(int i=1;i<=k;i++){
        cin>>nx;
        res^=f[nx];
    }

    if(!res){
        cout<<"lose";
    }else{
        cout<<"win";
    }
    return  0;
}