数据结构与算法学习笔记----博弈论

# 数据结构与算法学习笔记----博弈论

@@ author: 明月清了个风
@@ first publish time: 2025.2.6

ps⭐️包含了博弈论中的两种问题Nim游戏和SG函数，一共四道例题，给出了具体公式的证明过程。

Acwing 891. Nim游戏

[原题链接](891. Nim游戏 - AcWing题库)

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

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

输入格式

第一行包含整数$n$。

第二行包含$n$个数字，其中第$i$个数字表示第$i$个堆石子的数量。

输出格式

如果先手方必胜，则输出Yes。

否则，输出No。

数据范围

$1\le n\le 10^5$,

$1\le 每堆石子数\le 10^9$

思路

我们先介绍以下今天这道题目的背景——公平组合游戏ICG。这种游戏有以下几个特征：

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

因此，类似围棋那种棋类游戏都不算公平组合游戏。

接下来进入Nim游戏的讲解，首先明白两个概念——先手必胜状态和先手必败状态。其实很好理解：先手必胜状态意味着存在一种方法走到必败状态；而先手必败状态意味着无论怎么操作都不能走到一种先手必败状态。

然后我们就可以来看这个题目了，需要先介绍一个结论：

现在由$n$堆石子，每堆石子有$a_i$个，我们将所有的石子个数$a_1\oplus a_2\oplus \cdots \oplus a_n$异或起来，如果最后结果等于$0$，那就是先手必败状态，否则就是先手必胜状态。

接下来我们来证明为什么这个结论是正确的：

首先，当我们进行到最后一步时，也就是无法进行任何一步操作时的情况$0\oplus 0\oplus \cdots \oplus 0=0$，毫无疑问这是先手必败状态，符合上面的结论

第二种就是一般的情况，$a_1\oplus a_2\oplus \cdots \oplus a_n=x$，所有石子个数异或后不等于$0$，我们需要找到一种方式让其变成先手必败状态。我们需要的是找到$x$的二进制表示中的最高的一位$1$，假设其最高的一位$1$在第$k$位，那么一定存在一个$a_i$，其第$k$位是$1$，这时就有$a_i\oplus x<a_i$成立，这里举个例子解释一下：

ai     = 1 0 0 1 0 1 0 0
x  	   = 0 0 0 1 1 0 1 1
ai ^ x = 0 0 0 0 1 1 1 1

因为$x$的最高位位置一定小于等于$a_i$的最高位位置，因此上例子中我们所提到的第$k$位对于$a_i$来说是从左到右第$4$位，那么高于这个位置的所有数都会被异或成$0$，因此$a_i\oplus x<a_i$成立。

那么我们就可以从$a_i$这堆中拿走$a_i-(a_i\oplus x)$个石子，那么$a_i$这堆最后剩下$a_i-(a_i-(a_i\oplus x))=a_i\oplus x$个石子。

这时我们可以发现第二种一般的情况变成了
$$a_1\oplus a_2\cdots \oplus (a_i\oplus x)\cdots \oplus a_n=x\oplus x=0$$
回到了第一种情况，也就是一定存在一个方式使剩下的所有石子个数异或起来为$0$，那么为了说明我们上面蓝色结论正确，还有一步就是证明当所有石子个数异或起来为$0$时，无论怎么拿，剩下的所有石子数目异或值不为$0$。

这里用反证法，假设我们可以从某一堆$a_i$中拿走一定数量的石子使其变成$a_i^{\prime }$并且所有石子个数异或起来仍然为$0$，则有方程组
$$\{\begin{array}{l}{a}_1\oplus a_2\cdots \oplus a_i\oplus a_n=0\\ a_1\oplus a_2\cdots \oplus a_i^{\prime }\oplus a_n=0\end{array}$$
将两个方程左右两边分别异或起来有
$$a_i\oplus a_i^{\prime }=0$$
该等式成立的条件为$a_i=a_i^{\prime }$，但是我们的假设是拿走了一定数量的石子，因此$a_i^{\prime }\ne a_i$，因此矛盾。

到这就可以写代码了，其实代码很短。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;

int main()
{
    cin >> n;
    
    int res= 0 ;
    
    
    while(n --)
    {
        int x;
        cin >> x;
        res ^= x;
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

Acwing 892. 台阶-Nim游戏

[原题链接](892. 台阶-Nim游戏 - AcWing题库)

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

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

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

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

输入格式

第一行包含整数$n$。

第二行包含$n$个数字，其中第$i$个数字表示第$i$个级台阶上的石子数$q_i$。

输出格式

如果先手方必胜，则输出Yes。

否则，输出No。

数据范围

$1\le n\le 10^5$,

$1\le a_i\le 10^9$

思路

其实这题是上一题的稍微进阶版本，有了上一题的经验我们也知道这一题一定也存在所谓的先手必胜状态和先手必败状态。

题目中有一关键信息“每次都必须拿，已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。”，那么我们对台阶进行编号，地面为第$0$级，以此类推。

其实可以观察一下，对于偶数级台阶上的石子，假设只有三级$0,1,2$，那么对于台阶$2$上的石子一人拿了$x$个到台阶$1$后，另一人就可以将这$x$个拿到台阶$0$，而台阶$1$上数量不变，也就是说偶数台阶上的石子操作不会影响大局。

而对于奇数台阶上的石子$a_1,a_3,\cdots ,a_{2n+1}$，我们就可以看做是第一题中经典的Nim游戏了。

也就是$a_1\oplus a_3\cdots \oplus a_{2n+1}=x\ne 0$时，先手必胜，否则先手必败。

同样我们分两种情况来看：

第一种情况$x\ne 0$:

1. 那么一定存在一种方式使某一堆$a_i$变成$a_i\oplus x$，从而所有奇数台阶石子异或值为$0$，那么先手将$a_i\oplus x$个石子往下拿之后，第二人有两种选择：

   • 一种是从偶数堆拿，那么不管它拿多少，我们都将他拿的数量再往下放，这样就不会打破奇数台阶的格局
   • 第二种是从奇数堆拿，那么就一定会打破奇数台阶的格局，我们继续像上面一样找到使所有奇数台阶数量异或为$0$的拿法即可。

   也就是说，不管第二人怎么拿，我们都有石子拿，而第二人永远只能打破格局或者从偶数堆拿，最终没有石子拿的局面一定会被对手遇到，因此先手必胜。

那么对于第二种情况$x=0$，我们根据上述分析已经可以得出结论了，这是先手必败的状态。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

int n;

int main()
{
    cin >> n;
    
    int res = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        if(i % 2) res ^= x;
    }
    
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

Acwing 893. 集合-Nim游戏

[原题链接](893. 集合-Nim游戏 - AcWing题库)

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

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

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

输入格式

第一行包含整数$k$，表示数字集合$S$中数字的个数。

第二行包含$k$个整数，其中第$i$个整数表示数字集合$S$中的第$i$个数$s_i$。

第三行包含整数$n$。

第四行包含$n$个整数，其中第$i$个整数表示第$i$堆石子的数量$h_i$。

输出格式

如果先手方必胜，则输出Yes。

否则，输出No。

数据范围

$1\le n,k\le 100$,

$1\le s_i,h_i\le 10000$，

思路

从这一题开始我们介绍新一类博弈论题目，使用到了SG函数

首先我们先定义一个运算——Mex运算：找到一个集合中最小的不属于这个集合的自然数（最小非负整数）。比如有个集合$S=1，2，3$，则有$Mex(S)=0$。

然后我们就可以引入SG函数了

对于游戏中的某个状态$G$，其SG函数值$SG(G)$定义为
$$SG(G)=mex(SG(G^{\prime })|G^{\prime }是G的后继状态)$$

他有两个关键性质：

1. 终止状态的SG值为$0$。
2. 如果$SG(G)=0$，当前玩家处于必败态，否则为必胜态。

这里画一张图帮助理解，其实可以每种状态（或者说局面）可以看成一个结点，那么游戏中的所有局面可以看成一张有向图，如下图所示，每一个节点对应一种局面，每种局面与其能到达的后继局面之间由有向边连接。节点上的值为其SG值，如$SG=3$的绿色节点，其能到达的局面有$0,1,2$，因此其值为$3$，其余节点以此类推，没有后继节点的局面SG值为$0$。其实到这应该有一点头绪了，SG为$0$的节点不能到达别的任何局面，也就是无法进行操作，因此是必败局面；而不为$0$的节点一定可以到达某一个SG为$0$的局面，因此为必胜局面。

那这里其实会有一个问题：必败定义为$0$，必胜定义成$1$不就行了嘛？为什么还有弄一个$mex$操作呢？

在讲这个问题之前，我们需要知道如果有多个子游戏，先手胜负状态的计算方法为$S{G}_{总}=S{G}_1\oplus S{G}_2\oplus \cdots \oplus S{G}_n$，同样的，当$S{G}_{总}\ne 0$时表示先手必胜，否则表示先手必败，证明的方法和第一题Nim游戏相同，只要将上面的石子数量$a_i$改成$S{G}_i$即可，大家可以回顾一下上面第一题

然后，我们确定简单定义为$0$和$1$是可行的，但是只在一些简单的问题中可行，这样的做法会有局限性——无法区分不同状态的复杂性：在简单定义中，所有必胜态都被定义为1，所有必败态都被定义为0。但是很明显，这样会丢失一些信息，比如上图中的例子里，$SG=3$的节点可以为我们提供一个信息——他有多个后继节点，如果我们将其简单标记为1，则无法获得这一信息。

上图描述的一个游戏的情况，当我们需要考虑多个子游戏的时候，情况还会更加复杂，对于多个子游戏来说，我们最终的状态可以通过$S{G}_{总}=S{G}_1\oplus S{G}_2\oplus \cdots \oplus S{G}_n$得到。我们很容易就可以举出一个例子，比如两个游戏，如果其$SG$值都简单记为1，那么异或值为0;如果一个为1，而另一个为2，异或值为3；很明显，虽然两个子游戏在两种标记方法中都满足$SG\ne 0$，但是计算的结果却不同。

了解了这些就可以开始写代码了，比较复杂的地方是$SG$函数的实现，其实类似于一个递归搜索的过程，至于最小的不存在的整数，可以使用集合来实现，具体的看代码吧

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 10010;

int n, m;
int f[N], s[N];

int sg(int x)
{
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S;
    for(int i = 0; i < n; i ++)
    {
        int sum = s[i];
        if(x >= s[i]) S.insert(sg(x - sum));
    }
    
    for(int i = 0;; i ++)
    {
        if(!S.count(i))
        {
            return f[x] = i;
        }
    }
}

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i ++) cin >> s[i];
    
    memset(f, -1, sizeof f);
    
    cin >> m;
    
    int res = 0;
    for(int i = 0; i < m; i ++)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
    
}

Acwing 894. 拆分-Nim游戏

[原题链接](894. 拆分-Nim游戏 - AcWing题库)

给定$n$堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子(新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。)

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

输入格式

第一行包含整数$n$。

第二行包含$n$个整数，其中第$i$个整数表示第$i$堆石子的数量$a_i$。

输出格式

如果先手方必胜，则输出Yes。

否则，输出No。

数据范围

$1\le n,a_i\le 100$

思路

其实有了上面一题的经验，这题应该会简单一点了，首先要明确的就是这个游戏何时会结束：每次进行操作的时候虽然都会将一堆变为两堆，但是数值一定会减少，也就是说最后一定会有一堆操作完后变成了两堆0无法继续操作，这就是结束局面。

同样的，对于每一堆石子我们都可以计算$SG$值，假设有一堆石子$a_i$分为两堆$(b_1,b_2)$，那么其分解后的$SG$值$SG(b_1,b_2)=SG(b_1)\oplus SG(b_2)$；不过我们需要注意的是可能会有多种操作方法，也就是说$a_i$也可以分为两堆为$(c_1,c_2)$，只要满足题意即可，同样的会有$SG(C_1,C_2)=SG(c_1)\oplus SG(c_2)$，那么对于$a_i$来说，其$SG$值$SG(a_i)=SG(b_1,b_2)\oplus SG(c_1,c_2)\oplus \cdots$。

代码其实改一下上一题的就行了，不会很复杂。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110;

int n ;
int f[N];

int sg(int x)
{
    if(f[x] != -1) return f[x];
    
    unordered_set<int> S;
    for(int i = 0; i < x; i ++)
        for(int j = 0; j <= i; j ++)
            S.insert(sg(i) ^ sg(j));
            
    for(int i = 0; ; i ++)
        if(!S.count(i))
            return f[x] = i;
}

int main()
{
    cin >> n;
    
    memset(f, -1, sizeof f);
    int res = 0;
    
    for(int i = 0; i < n; i ++)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}