组合博弈

博弈论主要研究的是：在一个游戏中，进行游戏的多位玩家如何选择策略

算法竞赛中，最常见的博弈类型是组合博弈，大致分为公平组合游戏、非公平组合游戏、反常游戏

公平组合游戏

公平组合游戏（ICG）是最常见的博弈类型，特点如下：

• 在任意确定状态下，所有参与者可选择的行动完全相同，仅取决于当前状态，与身份无关
• 博弈中的同一个状态不可能多次抵达，博弈以参与者无法行动为结束，且博弈一定会在有限步后以非平局结束

博弈的双方对状态完全了解，且充分为自己打算，绝对理性

因此当局面确定，结果必然注定，且没有任何随机的部分，游戏中的每个状态，最终的结果也必然注定：必胜与必败

这一类博弈问题的结果没有任何意外

巴什博弈(Bash Game)

一共有n颗石子，两个人轮流拿，每次可以拿至少1颗，至多k颗棋子，取走最后一枚石子的玩家获胜

结论：先手必败，当且仅当

策略：若上式不成立，则先手先拿取n%(k+1)个石子，后手无论怎么拿，先手都可以拿取对应数量石子使得剩余石子维持上式，这样就能确保先手最后可以将石子全部拿完

尼姆博弈(Nim Game)

一共有n堆石头，两个人轮流进行游戏，在每个玩家的回合中，玩家需要选择任何一个非空石头堆，并从这堆石头中移除任意正数的石头数量，谁先拿走最后的石头就获胜

定义自然数的Nim和是

结论：先手处于必败态，当且仅当状态的Nim和为0

策略：若先手面对所有状态的Nim和不为0，则先手可以通过某个操作，使得后手面对Nim和为0的状态，后手进行操作，先手面对的一定是Nim和不为0的状态，如此往复，最终输的一方面对的是所有石头为0的状态，Nim和为0。

证明：

1. Nim和为0->Nim和不为0

   让所有堆的石子数按照高位到低位的二进制对齐排列，则Nim和为0的情况下，Nim和对应位也为0，证明前面对应位上有偶数个1

   从某一堆里拿若干石子，使得石子数量变小，一定会使得某一位的1会消失，就无法维持Nim和为0了

2. Nim和不为0->Nim和为0

​ 拿取某一堆上的石子，使得此时石子数更小，与其余堆石子的异或相等，使得总的Nim和为0

​ 拿哪一堆呢？

​ 找到从最高位总状态（总的Nim和）为1的第一位，则此时剩余堆的异或得到的数在该位上一定与要拿的那一堆状态该位不同，而往上往下都相同

​ 则我们选择这一位上对应的某堆是1的地方，让该堆的该位变成0，就能实现Nim和变为0

反尼姆博弈(反常游戏)

一共有n堆石头，两个人轮流进行游戏，在每个玩家的回合中，玩家需要选择任何一个非空石头堆，并从这堆石头中移除任意正数的石头数量，谁先拿走最后的石头就失败

分情况：

1. 若所有堆石头都只有一个，则奇数堆-后手赢，偶数堆-先手赢
2. 只有一堆大于一个，剩下的都小于等于一个，则先手一定赢
3. 若干堆大于一个，若干堆小于等于一个，只要此时Nim和不为0，那先手总能通过Nim博弈让自己进入2状态，从而获胜，否则后手赢

威佐夫博弈

有两堆石子，分别有 和 枚石子。两名玩家轮流从其中一堆或两堆中取石子，不能不取，但要求从两堆都取石子时，取走的石子数量必须相同。取走最后一枚石子的玩家获胜。

结论：

• **较小的一堆!=(较大的一堆-较小的一堆)*黄金分割比，先手获胜**
• 反之后手获胜

斐波那契博弈

有一堆石子，共计𝑛枚。两名玩家轮流取石子。第一个行动的玩家不限制取走的石子数目，但是不能取完石子；随后，每次取走的石子数目不得超过上次（指对手回合）取走的石子数目的二倍。每次取走的石子的数目不得为 0。取走最后一枚石子的玩家获胜。

结论：游戏开始时，先手必败，当且仅当石子数目n是斐波那契数。

Sprague–Grundy 理论

以上面的博弈游戏为例，我们让每个局面作为一个节点，则由某个局面可以通过一种行动，到达下一个局面，即可以连一条有向边，这就构成了一张游戏图

若当前行动由若干个，则后继节点就有若干个，最终必败局面被认为不再有后继节点

则公平组合游戏都可以对应成一张图

SG函数

每个局面的节点表示的状态，我们用sg函数值表示，sg函数值是所有后继节点的MEX（没出现过的局面）

• 最终必败点是A，则sg(A) = 0
• 若状态点是B，则sg(B) = MEX(B的后继节点)
  • 若sg(B)!=0，那么B为必胜态
  • 若sg(B)==0，那么B为必败态

例如：我们举一个巴什博弈的例子，n=8,m=3

SG定理

若一个ICG游戏由若干独立的ICG子游戏构成，则sg(总)=sg(1)^sg(2)^....

如：巴什博弈

设sg[i]表示还剩i颗石子时，sg值是多少，则可以根据m来决定后继状态分别为多少，即sg[i]可以转移到sg[i-1], sg[i-2], ..., sg[i-m]的局面，通过转移找对应状态的MEX

e.g. 使用sg定理表示巴什博弈

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

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> sg(n+1);
  vector<int> vis(m+1, 0);
  for (int i = 1; i<=n; i++)
  {
    vis.assign(n+1,0);
    for (int j = 1; j<=m&&i-j>=0; j++)
    {
      vis[sg[i-j]] = 1;
    }
    for (int j = 0; j<=m; j++)
    {
      if (!vis[j])
      {
        sg[i] = j;
        break;
      }
    }
  }
  cout << (sg[n]!=0?"1":"0");
}

可以打印出sg表来发现规律

e.g. 使用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

void solve() {
  int n;
  cin >> n;
  vector<int> arr(n+1);
  int maxn = -1;
  for (int i = 1; i<=n; i++)
  {
    cin >> arr[i];
    maxn = max(maxn, arr[i]);
  }
  vector<int> sg(maxn+1);
  vector<int> vis(maxn+1);
  // 打sg表，从0到maxn，取arr的值在表中的sg值，异或起来
  for (int i = 1; i<=maxn; i++)
  {
    vis.assign(maxn+1, 0);
    // 已经遍历过的sg值
    for (int j = 0; j<i; j++) vis[j] = 1;
    // 计算每种情况的sg值
    for (int j = 0; j<=maxn; j++)
    {
      if (!vis[j])
      {
        sg[i] = j;
        break;
      }
    }
  }
  int xxor = 0;
  for (int i = 1; i<=n;i++)
  {
    xxor^=sg[arr[i]];
  }
  cout << (xxor?"Yes":"No")<<endl;
}

通过sg表发现规律

e.g. P2148

该题的数据规模达到了，靠打sg表并异或求肯定无法获得结果，因此我们需要用sg值来总结规律

我们打一个小规模的sg表，同时，因为题目需求，我们需要开一个二位sg表，来存储题目所需

如sg[5][7]，的下一个状态可以是移走7，将5分为4,1 3,2 2,3等等，求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

vector<vector<int>> dp(N, vector<int>(N, -1));
int sg(int a, int b)
{
  if (a==1&&b==1) return 0;
  if (dp[a][b]!=-1) return dp[a][b];
  vector<int> vis(max(a,b)+1,0);
  if (a>1) // 去掉b拆a
  {
    for (int l = 1, r = a-1; l<a; l++, r--) vis[sg(l,r)] = 1;
  }
  if (b>1) // 去掉a拆b
  {
    for (int l = 1, r = b-1; l<b; l++, r--) vis[sg(l,r)] = 1;
  }
  int ans = 0;
  for (int i = 0; i<=max(a,b); i++)
  {
    if (!vis[i])
    {
      ans = i;
      break;
    }
  }
  return ans;
}
void solve() {
  for (int i = 0; i<=9; i++)
  {
    for (int j = i; j<=9; j++)
    {
      cout << i<<"-"<<j<<": "<<sg(i,j)<<endl;
    }
  }
  
}

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

0-0: 0
0-1: 0
0-2: 1
0-3: 0
0-4: 2
0-5: 0
0-6: 1
0-7: 0
0-8: 3
0-9: 0
1-1: 0
1-2: 1
1-3: 0
1-4: 2
1-5: 0
1-6: 1
1-7: 0
1-8: 3
1-9: 0
2-2: 1
2-3: 2
2-4: 2
2-5: 1
2-6: 1
2-7: 3
2-8: 3
2-9: 1
3-3: 0
...

我们发现，最终结果是a,b石子数-1后进行或运算，最低位0所在位置

很神秘，但是就是打表找到的这个规律，于是代码变为

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

void solve() {
  int n;
  cin >> n;
  int sg = 0;
  for (int i = 1; i<=n; i+=2)
  {
    int a, b;
    cin >> a >> b;
    int num = ((a-1)|(b-1));
    int cnt = 0;
    while(num)
    {
      if ((num&1)==0)
      {
        break;
      }
      num>>=1;
      cnt++;
    }
    sg^=cnt;
  }
  cout <<(sg?"YES":"NO")<<endl;
}