浅谈博弈论

sonny2011 · 2026-02-26 19:46:19 · 算法·理论

博弈论

概念

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

博弈论分类

1. 对称博弈/非对称博弈
   在 对称博弈 中，不同参与者在做出相同行为时获得的收益相同，收益与执行者的身份无关。否则称为 非对称博弈。
2. 零和博弈/非零和博弈
   在 零和博弈 中，无论各方采取何种行为，所有参与者的收益总和始终为零，即一方的收益必然是另一方的损失。非零和博弈 允许多方共赢或共输。
3. 同时博弈/序贯博弈
   在 同时博弈 中，所有参与者在不知道他人选择的前提下同时做出决策，例如剪刀石头布就是一个典型的 同时博弈。而在 序贯博弈 中，参与者依次行动，后行动者至少能够观察到先行动者的部分行为。
4. 完美/不完美信息博弈
   在 完美信息博弈 中，参与者在做出决策时，完全了解此前所有事件的发生情况。例如象棋、围棋等属于 完美信息博弈；而麻将、扑克等则不是，因为玩家无法获知他人的手牌。否则称为 不完美信息博弈。
5. 完全/不完全信息博弈
   在 完全信息博弈 中，所有参与者对博弈结构本身有完全了解，且这些信息为公共的。而在 不完全信息博弈 中，某些博弈要素对参与者来说是未知的，比如对方可以选择的决策集。

   组合博弈论

   特点

   在一个 组合博弈 游戏中，两个玩家轮流行动，双方都完全了解游戏的局面。所以组合博弈游戏是完全信息博弈和序贯博弈。 同时组合博弈游戏中没有随机因素

   公平组合游戏

   公平组合游戏 是一种 组合博弈。 在 公平组合游戏 中，一个状态(可以理解为局面)无法多次抵达，博弈在一个玩家无法行动时结束。 公平组合游戏 是对称博弈．

   Nim 游戏

   有 n 堆石子，第 i 堆石子有 a_i 个。两名玩家轮流在任意一堆石子中取若干个，但不能不取，取走最后一个石子的玩家获胜。

我们可以把每一个游戏局面记为一个状态。因为 Nim 游戏是一个公平博弈游戏，所以对于先手来说，每一个状态都是一个必胜状态或者必败状态。对于每一个可以由当前状态通过一步操作转移得来的状态，我们称其为当前状态的后继状态。由此我们可以得到一下推论：

1. 一个没有后继的状态是一个必败状态。
2. 一个状态是必胜状态，当且仅当它存在一个必败后继状态。
3. 一个状态是必败状态，当且仅当它的后继全部都是必胜状态。

对于每个推论，我们可以给出证明：

1. 如果一个状态没有后继状态，意味着玩家无法再进行操作，根据游戏定义，这个状态是必败状态。
2. 如果一个状态存在一个后继是必败状态，那么此时先手玩家可以选择通过一次操作使状态变为必败状态给对手，先手就能必胜。
3. 如果一个状态的所有后继都是必胜状态，那么不管先手玩家怎么操作，下一步对手一定会获得一个必胜状态，所以此时先手必败。

如果把每个状态看做一个节点，并向它的后继状态连边，我们就可以得到一个 DAG 。我们可以把 Nim 游戏 看做，在代表开始状态的节点上有一个棋子，双方轮流把棋子沿着 DAG 上的有向边向后移动到下一个节点，直到棋子被移动到代表边界情况的节点，即每堆石子的数量都为 0 。我们称这种在 DAG 为游戏的博弈图。这个博弈图是无环的，因为每次操作时，石子的数量都严格减少，无法重复到达一个局面。

可以证明，任何一个 公平组合游戏 都可以用一个博弈图描述。所以，任何一个 公平组合游戏 都可以暴力建出博弈图，然后爆搜求解。但是在 Nim 游戏中，状态的数量是 O(\prod\limits_{i=1}^{n}{a_i}) 的，特别大，所以我们还需要继续研究更好的求解方案。

• 结论：先手必败，当且仅当 \bigoplus\limits_{i=1}^{n}{a_i}=0。下面证明为什么这个推论是成立的。
  考虑对所有的状态使用归纳法。
  1. 对于 \forall i,a_i=0，该状态没有后继状态，先手必败，且 \bigoplus\limits_{i=1}^{n}{a_i}=0，推论成立。
  2. 对于 \bigoplus\limits_{i=1}^{n}{a_i} \neq 0，我们需要证明此时先手必胜，也就是说，我们要构造一个移动，使得移动后 \bigoplus\limits_{i=1}^{n}{a_i}=0。设 k=\bigoplus\limits_{i=1}^{n}{a_i}，根据异或的性质，数组 a 中一定存在一个 i，使得 a_i \geq k，那么我们可以在这一堆石子中选取若干个石子使得 a_i \leftarrow a_i \oplus k，此时就有 \bigoplus\limits_{i=1}^{n}{a_i}=0 了。
  3. 对于 \bigoplus\limits_{i=1}^{n}{a_i}=0，我们需要证明此时先手必败，也就是说，我们需要证明此状态的所有后继状态都满足 \bigoplus\limits_{i=1}^{n}{a_i} \neq 0。很明显对于所有合法的移动，都会造成一个 a_i 发生改变, a_i^{'} \neq a_i，所以就有 a_i^{'} \oplus a_i \neq 0，就会造成整体异或和的改变。

由此，我们就可以在 O(n) 的时间内判断 Nim 游戏的胜负了。

巴什游戏

有一堆石子，共 n 个，两名玩家轮流取走 1 \sim m 个石子，取走最后一个石子的玩家获胜。

• 先手必败，当且仅当 n \equiv 0 \pmod {m+1}。

我们延续上面的思路，继续对此题进行归纳证明：

1. 当 n=0 时，根据游戏定义有先手必胜。
2. 当 n \not\equiv 0 \pmod {m+1} 时，我们要证明此状态先手必胜，也就是说，我们要构造一种方案，使得在操作之后有 n \equiv 0 \pmod {m+1}。根据取余的定义，此时有 1 \le n \pmod {m+1} \le m，那么我们就可以通过取走 n \mod {m+1} 个石子使得 n - (n \mod {m+1}) \equiv 0 \pmod {m+1}。
3. 当 n \equiv 0 \pmod {m+1} 时，我们要证明此状态先手必败，也就是说，不管此时先手怎么操作，都会使得 n^{'} \not\equiv 0 \pmod {m+1}。假设我们这一步取走了 k 个石子，那么 n^{'} \equiv 0-k \equiv {m+1}-k \pmod {m+1}。由于 1 \le k \le m，所以一定有 m+1-k \neq 0，所以 n^{'} 不会再成为 m 的倍数。

其实，这个题也可以通过 O(nm) 建出博弈图，然后在图上 dfs 求解。但这种做法仅限用于 m 较小的情况。

阶梯 Nim 游戏

有 n 堆石子，第 i 堆石子有 a_i 个，两名玩家轮流进行操作，每次操作要么取走第 1 堆石子中的若干个石子，要么选择一个 i (1<i \le n)，将第 i 堆中的若干个石子移动到第 i-1 堆中，取走最后一个石子的玩家获胜。

这个游戏和 Nim 游戏很类似，但把直接移走的操作变为了向前移的操作。但是我们也可以发现，对于偶数堆，当一个玩家把一些石子向前移动一堆，下一步的玩家可以把这些石子再次向前移，这样偶数堆的石子对答案就没有影响了。让我们打开思路，把偶数堆当做垃圾桶，那么奇数堆的石子可以在一次操作中移动到偶数堆，就相当于直接拿走了，那么此时游戏转化为了一个 Nim 游戏。

• 结论：先手必败，当且仅当所有奇数堆个数的异或和为 0 ，即 \bigoplus\limits_{i=1}^{\lfloor \frac{n}{2} \rfloor} a_{2 \times i+1}=0 。

Fibonacci Nim 游戏

有一堆石子，共 n 个，两名玩家轮流取石子，第一次行动不限制数量，但不能取完，随后的每一次行动取走的石子数量都不能超过上一次的两倍，取走最后一个石子的玩家获胜。

• 结论：先手必败，当且仅当 n 是 Fibonacci 数。

考虑证明上面的推论。
首先我们对题意进行一个转化。每一次操作最多取 k 个，初始时 k=n-1，每一次操作后把 k 变成上一次操作取走的数量的两倍。
Fibonacci 数有一个这样的性质：任意正整数可以被拆分成若干个不相邻的 Fibonacci 数的和。那么我们考虑这个拆分，如果 k 大于这个拆分中的最小的数时，先手必胜。因为此时我们要么移走全部石子，要么移走拆分中最小的数的个数个石子，此时有次小的数严格大于最小的数的两倍，所以下一步对手无法取走次小的数，此时先手仍然处于必胜状态中。
反过来，如果我们处于必败状态，那么取完后的 Fibonacci 拆分中的最小数一定严格大于取走的数量，那么这个局面一定处于必胜状态。

例题

P7864

题目大意

给定一棵有根树，两个玩家轮流选择若干个叶子节点删除，不能不摘，删除根节点的玩家获胜，求最终胜者。

Solution

神秘人类智慧题。

只有一个点的情况，明显是先手必胜。
菊花图。两个节点时，先手只能删掉唯一一个叶子，然后后手删掉根，先手必败。否则，先手把叶子删到只剩一个，然后就转化为了先手必败的情况扔给对手，先手必胜。
链。双方只能轮流删最下面的节点，所以当点数为奇数时先手必胜，否则先手必败。

接下来考虑向之前的情况中添加节点。设新添加的节点为 x，它的父节点是 fa。
如果 fa 原来不是叶子结点，并且之前的情况是必胜的，那么可以在第一次把新节点删掉。
如果之前的情况是必败的，那么就可以在第一步只删掉 x，把必败情况留给对手。
于是，我们就发现了，如果有一个叶子结点的父节点有大于等于两个儿子，那么这个状态一定必胜。
再考虑一下新节点是原来的叶子结点的情况。考虑从这个点向上找到的第一个儿子数 \ge 2 的节点出断开，那么我们就得到了一条链。手玩发现当这个链的长度为偶数时，我们可以通过一直断开叶子结点得到上面考虑的这个必胜情况。
归纳一下上面的思路，我们发现可以对于每个叶子节点，统计到它最近的儿子数 \ge 2 的节点到它的距离。只要对于所有叶子结点，这个距离都是奇数，就可以得到先手必胜。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
int fa[N],son[N];
vector<int> g[N];
int p[N];
void dfs(int x)
{
    if(son[x]>=2)p[x]=0;
    else p[x]=p[fa[x]]+1;
    for(int y:g[x])dfs(y);
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        g[i].clear();
        son[i]=p[i]=0;
    }
    for(int i=2,a;i<=n;++i)
    {
        cin>>a;
        fa[i]=a;
        son[a]++;
        g[a].push_back(i);
    }
    dfs(1);
    bool flag=0;
    for(int i=2;i<=n;++i)
        if(son[i]==0&&(p[i]&1))flag=1;
    cout<<flag<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

P8347

题目大意

给定一棵树，两个玩家轮流在这棵树上进行操作。每次操作先选择一个节点，删除这个节点和这个节点相连的边，再选择一个联通快，删除其他联通块。操作完之后使这棵树只剩下一个节点的玩家输。

Solution

首先考虑最简单的情况。
两个点只可能是一条长为二的链，此时先手玩家不管删掉哪一个点都只剩下一个节点，先手必败。
三个点只可能是一条长为三的链，此时先手删去边上的一个节点就变成了上面的情况，所以先手必胜。
四个点的情况可能是一条长为四的链或一个菊花图。是链的情况可以删掉中间的一个节点然后保留长为二的链，此时先手必胜。是菊花图的情况由于删中心点一定只能保留一个点，所以中心点是不能删的，只能删叶子结点，然而此时叶子结点数量是三，所以先手必败。

由此推广到 n 个点的菊花图，我们只能删掉 n-1 个叶子结点，所以若 n 是奇数则先手必胜，否则先手必败。
再考虑两个点数为四的菊花图连接中间节点形成的图，手玩可以发现此时先手必败。仔细观察可以发现，在这个图中，每一个点的度数都是奇数，于是我们大胆猜测，先手必败，当且仅当所有点的度数都是奇数。

继续沿用归纳法的思路，对这个推论进行归纳：

1. 当这个图为点数为偶数的菊花图时，先手必败。
2. 当这个图中有偶度数点时，先手必胜，也就是说当这个图中有偶度数点时，玩家可以通过一步操作，使得这个图中所有点的度数都是奇数。构造此方案，我们可以选择一个离其它偶度数点最远的点(可以感性理解一下)，断掉它和其它偶度数点相连的点，我们就构造出了一个所有点都是奇度数的图。
3. 当这个图全部都是奇度数点时，先手必败，也就是说，不管此时先手怎么操作，都会使得图中产生一个偶度数点。我们可以发现，断掉一个点的同时，剩余的图中会有一个点的度数减一，由于它原来是奇度数点，那么现在就产生了一个偶度数点。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,d[N];
void solve()
{
    cin>>n;
    for(int i=1;i<=n;++i)d[i]=0;
    for(int i=1,u,v;i<n;++i)
    {
        cin>>u>>v;
        d[u]++,d[v]++;
    }
    bool flag=1;
    for(int i=1;i<=n;++i)
        if((d[i]&1)==0)flag=0;
    cout<<(flag==0?"Hifuu\n":"Luna\n");
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

P2148

题目大意

给定 n 组游戏，每组游戏中有两堆石子，两个玩家轮流选择一组游戏进行操作，每次操作玩家可以选择删掉其中一堆所有石子，将另一堆石子分成两堆放到原来的位置，要保证操作时未删掉的那堆石子要有至少两个石子，第一个不能操作的玩家输。

Solution

首先这个题是 n 组游戏的组合，所以无法避免的要使用 SG 函数。下面来介绍一下 SG 函数。

在一个公平组合游戏中，我们定义一个局面的 SG 函数值为它所有后继状态 SG 函数的 \operatorname{mex}，其中 \operatorname{mex} 函数指一个集合中最小的没有出现的自然数。特别地，定义一个没有后继状态的状态的 SG 值为 0。

SG 函数建立在 SG 理论之上。SG 理论指出，所有公平组合游戏都等价于单堆 Nim 游戏，而一个 n 个石子的单堆 Nim 游戏，它的 SG 函数值就是 n。
此处引入游戏的和的概念：游戏的和，可以理解为由多个同时进行且互不干扰的子游戏组成的游戏，玩家在每一步选择其中一个子游戏移动一步，且游戏在所有子游戏都无法移动时结束。此时，我们称这个由多个子游戏组成的游戏为这些子游戏的和。容易发现，游戏的和满足结合律和交换律。比如 Nim 游戏就是多个单堆 Nim 游戏的和。而对于一个由多个子游戏组成的游戏，我们定义它的 SG 函数为它所有子游戏 SG 函数的异或和。

那么 SG 函数有什么用呢？这里给出一个定理：一个公平组合游戏中的一个状态 x 是必胜状态，当且仅当 \operatorname{SG}(x)\neq 0。利用 SG 函数，我们就可以快速判断一个局面是必胜局面还是必败局面。

回到此题，因为石子被两两分组了，所以我们只需依次求出每组石子的 SG 函数值，然后全异或起来就可以了。
定义 S_x=\{\operatorname{SG}(a,b)|a+b=x\}，即一个状态所有后继状态 SG 函数的集合。 把一堆石子拿掉，另一堆任意拆成两堆，等于说由状态 (a,b) 可以转移到 {(c,d),c+d=a或c+d=b}，即 \operatorname{SG(x,y)}=\operatorname{mex}\{S_x\cup S_y\}。特别地，\operatorname{SG}(1,1)=0。
然后打表 \operatorname{SG} 函数，发现 S_x 就是 x 的二进制中 1 的下标的集合，随后我们就可以发现一些奇妙的性质：

4. 若 a 是偶 b 是奇数，\operatorname{SG}(a,b)=\operatorname{SG}(a,b+1)

然后我们就可以用这个和更正减损术差不多的算法用 O(\log V) 复杂度算出一个二元组的 \operatorname{sg} 函数了。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,sg,a,b;
int get(int a,int b)
{
    int res=0;
    while(1)
    {
        if((a&1)&&(b&1))return res;
        if(a&1)++a;
        else if(b&1)++b;
        else
        {
            a>>=1,b>>=1;
            ++res;
        }
    }
}
void solve()
{
    sg=0;
    cin>>n;
    n/=2;
    for(int i=1;i<=n;++i)
    {
        cin>>a>>b;
        sg^=get(a,b);
    }
    cout<<(sg?"YES\n":"NO\n");
}
int main()
{
    std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}

P3179

题目大意

有一个长度为 n 的数组，有一些格子是白的，有一些是黑的，每次操作选择一个白色的格子，下标为 x。接着选择一个大小在 1\ldots \lfloor\dfrac{n}{x}\rfloor 之间的整数 k，将下标为 x,2\times x,\ldots ,k\times x 的格子都进行颜色翻转。不能操作的人输。 每次给定数组的初始状态，求出是否有必胜策略。

Solution

本题即为经典的翻棋子问题。
我们假设现在只有 x 是白色。于是，我们可以选择翻 x,2x,\cdots,kx。翻完之后 x 会变黑，其他的会变白。
如果只翻 x，那么翻完后没有任何棋子是白色，无法继续操作，故此后继状态 SG 值为 0。如果翻 x 和 2x，那么翻完后只有 2x 是白色，这个后继状态的 SG 值是 \operatorname(2x)。以此类推，其他后继状态的 SG 值分别为 \operatorname{SG}(2x),\operatorname{SG}(2x) \oplus \operatorname{SG}(3x),\cdots,\bigoplus\limits_{i=1}^{k} \operatorname{SG}(i \cdot x)。
故我们得到当前的 S_x=\{\operatorname{SG}(2x),\operatorname{SG}(2x) \oplus \operatorname{SG}(3x),\cdots,\bigoplus\limits_{i=1}^{k} \operatorname{SG}(i \cdot x)\}。
如果暴力枚举每一个下标 x 对应的 S 集合并求出 SG 函数值，时间复杂度是 O(n\cdot \sum\limits_{i=1}^{n}{\lfloor\frac{n}{i}\rfloor})=O(n\log n)，需要优化。

考虑到数据范围是 n \leq 10^9，连 O(n) 都过不了，又没有什么 \log 做法，于是想到根号做法整除分块。下面证明对于 \lfloor \dfrac{n}{x} \rfloor 相同的 x 都有 \operatorname{SG}(x) 相同。

我们知道 S_x=\{\operatorname{SG}(2x),\operatorname{SG}(2x) \oplus \operatorname{SG}(3x),\cdots,\bigoplus_{i=1}^{k} \operatorname{SG}(i \cdot x)\}。对于 \lfloor \dfrac{n}{x} \rfloor=\lfloor \dfrac{n}{y} \rfloor 的 x,y，容易发现 S_x 与 S_y 的大小均为 \lfloor \dfrac{n}{x} \rfloor。对于 S_x 与 S_y 中的每个元素 tx 和 ty，有 \lfloor \dfrac{n}{tx} \rfloor=\lfloor \dfrac{\lfloor\frac{n}{x}\rfloor}{t}\rfloor=\lfloor \dfrac{\lfloor\frac{n}{y}\rfloor}{t}\rfloor=\lfloor \dfrac{n}{ty} \rfloor。所以 S_x 和 S_y 完全相同。故 \operatorname{mex}\{S_x\}=\operatorname{mex}\{S_x\}，即 \operatorname{SG}(x)=\operatorname{SG}(y)。
所以对于每一个 i ,集合 \{n|\lfloor \frac{n}{x} \rfloor=i\} 内的 n 所对应的 S 集合和 SG 函数值都是相同的。所以我们可以用整除分块在 O(\sqrt{n}) 的时间复杂度内求出每种 S 集合以及对应的 SG 函数值。

然而整除分块后每个集合的内部结构也无法暴力求出，于是考虑在每个集合内再进行一次整除分块。
考虑在一个下标 x 对应的集合 x,2x,3x,\cdots,kx 中取两个元素 t_1 x 和 t_2 x。这两个元素可能满足 \lfloor\dfrac{n}{t_1 x}\rfloor=\lfloor\dfrac{n}{t_2 x}\rfloor，所以再次进行整除分块。设对于在范围 l_i\le t\le r_i 内的 t 有 \lfloor\dfrac{n}{tx}\rfloor 相同，则我们只需将这个状态的 SG 函数值与当前维护的前缀异或和异或得到的结果标记入 S_x ，然后判断区间长度的奇偶性，奇数则将前缀异或和异或上此状态的 SG 值，否则前缀异或和不变。
只需预处理出所有的 SG 函数值，就可以 O(1) 查询所有下标的 SG 函数值，每次查询只需将 m 个下标的 SG 函数值异或起来就可以得到最终结果了。 考虑计算时间复杂度，当 x>\sqrt{n} 时，\lfloor\dfrac{n}{x}\rfloor 只有 O(\sqrt{n}) 种取值，而 \sqrt{\frac{n}{x}}<O(n^{\frac{1}{4}})，所以时间复杂度 O(\sqrt{n}\times n^{\frac{1}{4}})=O(n^{\frac{3}{4}})。当 x\leq\sqrt{n} 时，复杂度为 O(\sqrt{n}+\sum\limits_{x=1}^{\sqrt{n}} \sqrt{\frac{n}{x}})=O(n^{\frac{3}{4}})，那么程序的时间复杂度为 O(n^{\frac{3}{4}})，n\leq 10^9 的时候刚好通过。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k,limit;
int s[N][2];
int cnt,pos[N];
int mex[N*24];
int sg(int x)
{
    if(x>limit)return s[n/x][0];
    else return s[x][1];
}
void init()
{
    for(int i=1,j;i<=n;i=j+1)
    {
        j=n/(n/i);
        pos[++cnt]=j;
    }
    for(int t=cnt;t>=1;t--)
    {
        int res=0,p=pos[t];
        mex[res]=t;
        for(int i=p*2,j;i<=n;i=j+p)
        {
            j=n/(n/i)/p*p;
            mex[res^sg(i)]=t;
            if(((j-i)/p+1)&1)res^=sg(i);
        }
        int ans=0;
        while(mex[ans]==t)ans++;
        if(p>sqrt(n))s[n/p][0]=ans;
        else s[p][1]=ans;
    }
}
int main()
{
    cin>>n>>k;
    limit=sqrt(n);
    init();
    while(k--)
    {
        int m,res=0;
        cin>>m;
        while(m--)
        {
            int a;
            cin>>a;
            res^=sg(a);
        }
        cout<<(res?"Yes\n":"No\n");
    }
    return 0;
}