3775 字
19 分钟
博弈论算法详解：从CSP-S到IOI
2026-01-21
技术
算法
/
博弈论
/
SG函数
/
Nim
/
OI
/
CSP
/
IOI

博弈论算法详解：从CSP-S到IOI#

博弈论是组合数学和算法竞赛中的重要分支，在信息学奥赛中经常出现。本文将系统性地介绍从CSP-S到IOI级别的博弈论知识，帮助读者建立完整的博弈论知识体系。

一、博弈论基础#

1.1 基本概念#

在博弈论中,我们通常研究的是公平组合游戏（Impartial Combinatorial Games），其特点是：

  • 两个玩家轮流操作
  • 游戏状态对双方完全透明
  • 双方可以执行相同的操作
  • 不能操作的一方输掉游戏

1.2 必胜态与必败态#

  • 必胜态（N态/Winning Position）：当前玩家有策略必胜
  • 必败态（P态/Losing Position）：当前玩家必败（对手必胜）

核心定理：

  1. 无法进行任何操作的状态是必败态
  2. 能够转移到必败态的状态是必胜态
  3. 只能转移到必胜态的状态是必败态
// 判断状态的胜负性（记忆化搜索）
#include <bits/stdc++.h>
using namespace std;


map<int, int> memo; // 0: P态, 1: N态


// state: 当前状态
// getNextStates: 获取所有后继状态的函数
bool isWinning(int state, function<vector<int>(int)> getNextStates) {
    if (memo.count(state)) return memo[state];


    vector<int> nexts = getNextStates(state);


    // 无后继状态，为必败态
    if (nexts.empty()) {
        return memo[state] = 0;
    }


    // 有一个后继是必败态，则当前为必胜态
    for (int next : nexts) {
        if (!isWinning(next, getNextStates)) {
            return memo[state] = 1;
        }
    }


    // 所有后继都是必胜态，则当前为必败态
    return memo[state] = 0;
}

二、Nim游戏与SG函数#

2.1 经典Nim游戏#

有n堆石子，每堆有a[i]个。两人轮流操作，每次可以从任意一堆中取走任意个（至少1个）石子。取走最后一个石子的人获胜。

定理：当且仅当 a[1] ⊕ a[2] ⊕ ... ⊕ a[n] = 0 时，先手必败；否则先手必胜。（⊕表示异或）

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


int main() {
    int n;
    cin >> n;


    int xor_sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        xor_sum ^= a;
    }


    if (xor_sum == 0) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

2.2 SG函数（Sprague-Grundy Function）#

SG函数是博弈论的核心工具，用于求解任意公平组合游戏。

定义：对于状态x，设其所有后继状态为y1, y2, …, yk，则：

SG(x) = mex{SG(y1), SG(y2), ..., SG(yk)}

其中mex(S)表示不属于集合S的最小非负整数。

性质：

  • SG(x) = 0 当且仅当x是必败态
  • SG(x) ≠ 0 当且仅当x是必胜态
#include <bits/stdc++.h>
using namespace std;


const int MAXN = 1005;
int sg[MAXN];
bool vis[MAXN];


// 计算SG函数
// moves: 每次可以取走的石子数集合
int getSG(int n, const vector<int>& moves) {
    if (sg[n] != -1) return sg[n];


    memset(vis, 0, sizeof(vis));


    // 遍历所有可能的操作
    for (int move : moves) {
        if (n >= move) {
            vis[getSG(n - move, moves)] = true;
        }
    }


    // 计算mex
    for (int i = 0; ; i++) {
        if (!vis[i]) {
            return sg[n] = i;
        }
    }
}


int main() {
    int n, k;
    cin >> n >> k;


    vector<int> moves(k);
    for (int i = 0; i < k; i++) {
        cin >> moves[i];
    }


    memset(sg, -1, sizeof(sg));
    sg[0] = 0;


    if (getSG(n, moves) != 0) {
        cout << "先手必胜" << endl;
    } else {
        cout << "先手必败" << endl;
    }


    return 0;
}

2.3 多堆游戏的SG定理#

对于多个独立的游戏G1, G2, …, Gn，设它们的SG值分别为SG(G1), SG(G2), …, SG(Gn)，则：

组合游戏的SG值 = SG(G1) ⊕ SG(G2) ⊕ … ⊕ SG(Gn)

这就是著名的Sprague-Grundy定理。

三、经典博弈模型#

3.1 巴什博弈（Bash Game）#

规则：一堆n个石子，每次最多取m个，最少取1个，取走最后一个石子的人获胜。

结论：

  • 若 n % (m + 1) == 0，先手必败
  • 否则，先手必胜，且先手应取 n % (m + 1) 个
#include <bits/stdc++.h>
using namespace std;


int main() {
    long long n, m;
    cin >> n >> m;


    if (n % (m + 1) == 0) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜，先取 " << n % (m + 1) << " 个" << endl;
    }


    return 0;
}

3.2 威佐夫博弈（Wythoff Game）#

规则：两堆石子，数量分别为a和b。每次可以：

  1. 从一堆中取任意个
  2. 从两堆中取相同数量

结论：设较小值为mn = min(a, b)，较大值为mx = max(a, b)，定义：

k = mx - mn

当且仅当 mn == floor(k * φ) 时为必败态（φ = (1 + √5) / 2，黄金分割比）

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


int main() {
    long long a, b;
    cin >> a >> b;


    if (a > b) swap(a, b);


    long long k = b - a;
    double phi = (1.0 + sqrt(5.0)) / 2.0;
    long long expected = (long long)(k * phi);


    if (a == expected) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

3.3 斐波那契博弈#

规则：一堆n个石子，先手第一次不能全部取完，之后每次取的数量不能超过对手刚取数量的2倍。

结论：当且仅当n是斐波那契数时，先手必败。

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


int main() {
    long long n;
    cin >> n;


    // 生成斐波那契数列
    set<long long> fib;
    long long a = 1, b = 2;
    fib.insert(a);
    fib.insert(b);


    while (b <= n) {
        long long c = a + b;
        fib.insert(c);
        a = b;
        b = c;
    }


    if (fib.count(n)) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

3.4 阶梯Nim游戏#

规则：n个阶梯，每个阶梯上有若干石子。每次可以将某个阶梯上的若干石子移到下一层。最后一层的石子不能移动。将最后一个石子移到地面的人获胜。

结论：只考虑奇数层的石子，异或和为0则先手必败，否则先手必胜。

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


int main() {
    int n;
    cin >> n;


    int xor_sum = 0;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        if (i % 2 == 1) { // 只考虑奇数层
            xor_sum ^= a;
        }
    }


    if (xor_sum == 0) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

四、Multi-SG游戏#

4.1 Multi-SG理论#

在经典SG游戏中，每个局面只能转移一次。而在Multi-SG游戏中，每个局面可以转移多次（转移k次）。

定义：

  • SG(x, k) 表示在状态x下还可以进行k次转移的SG值
  • 终止状态：SG(x, 0) = x

计算方法：

int getMultiSG(int x, int k, const vector<int>& moves) {
    if (k == 0) return x;


    set<int> vis;
    for (int move : moves) {
        if (x >= move) {
            vis.insert(getMultiSG(x - move, k - 1, moves));
        }
    }


    // 计算mex
    for (int i = 0; ; i++) {
        if (!vis.count(i)) return i;
    }
}

五、博弈树与Alpha-Beta剪枝#

5.1 博弈树搜索#

对于复杂的博弈问题，可以使用博弈树进行搜索。

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


const int INF = 1e9;


struct State {
    // 定义游戏状态
    int value;


    vector<State> getNextStates() {
        // 返回所有后继状态
        vector<State> result;
        // ... 生成后继状态
        return result;
    }


    bool isTerminal() {
        // 判断是否为终止状态
        return false;
    }


    int evaluate() {
        // 评估函数
        return value;
    }
};


// Minimax算法
int minimax(State state, int depth, bool isMax) {
    if (depth == 0 || state.isTerminal()) {
        return state.evaluate();
    }


    if (isMax) {
        int maxEval = -INF;
        for (State next : state.getNextStates()) {
            int eval = minimax(next, depth - 1, false);
            maxEval = max(maxEval, eval);
        }
        return maxEval;
    } else {
        int minEval = INF;
        for (State next : state.getNextStates()) {
            int eval = minimax(next, depth - 1, true);
            minEval = min(minEval, eval);
        }
        return minEval;
    }
}

5.2 Alpha-Beta剪枝#

Alpha-Beta剪枝可以大幅减少博弈树的搜索节点数。

int alphaBeta(State state, int depth, int alpha, int beta, bool isMax) {
    if (depth == 0 || state.isTerminal()) {
        return state.evaluate();
    }


    if (isMax) {
        int maxEval = -INF;
        for (State next : state.getNextStates()) {
            int eval = alphaBeta(next, depth - 1, alpha, beta, false);
            maxEval = max(maxEval, eval);
            alpha = max(alpha, eval);
            if (beta <= alpha) {
                break; // Beta剪枝
            }
        }
        return maxEval;
    } else {
        int minEval = INF;
        for (State next : state.getNextStates()) {
            int eval = alphaBeta(next, depth - 1, alpha, beta, true);
            minEval = min(minEval, eval);
            beta = min(beta, eval);
            if (beta <= alpha) {
                break; // Alpha剪枝
            }
        }
        return minEval;
    }
}

六、动态博弈与组合游戏#

6.1 DAG上的博弈#

有向无环图（DAG）上的博弈是一类重要的博弈模型。

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


const int MAXN = 1005;
vector<int> graph[MAXN];
int sg[MAXN];
bool vis[MAXN];


int getSG_DAG(int u) {
    if (sg[u] != -1) return sg[u];


    memset(vis, 0, sizeof(vis));


    for (int v : graph[u]) {
        vis[getSG_DAG(v)] = true;
    }


    for (int i = 0; ; i++) {
        if (!vis[i]) {
            return sg[u] = i;
        }
    }
}


int main() {
    int n, m;
    cin >> n >> m;


    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
    }


    memset(sg, -1, sizeof(sg));


    // 计算所有节点的SG值
    for (int i = 1; i <= n; i++) {
        getSG_DAG(i);
    }


    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        int xor_sum = 0;
        for (int i = 0; i < k; i++) {
            int pos;
            cin >> pos;
            xor_sum ^= sg[pos];
        }


        if (xor_sum == 0) {
            cout << "先手必败" << endl;
        } else {
            cout << "先手必胜" << endl;
        }
    }


    return 0;
}

6.2 翻硬币游戏#

n枚硬币排成一行，每次可以翻转一枚正面向上的硬币及其左边的所有硬币。最后一个翻硬币的人获胜。

解法：将正面向上的硬币位置看作Nim游戏的石子堆，异或和为0则先手必败。

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


int main() {
    int n;
    cin >> n;


    int xor_sum = 0;
    for (int i = 0; i < n; i++) {
        int coin;
        cin >> coin;
        if (coin == 1) {
            xor_sum ^= i;
        }
    }


    if (xor_sum == 0) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

七、IOI级别博弈题目#

7.1 删数游戏#

问题：给定一个序列，两人轮流删除一个数（有限制条件），最后无法操作的人输。

解法思路：

  1. 建模成博弈问题
  2. 使用SG函数或者动态规划
  3. 注意状态压缩和优化
#include <bits/stdc++.h>
using namespace std;


const int MAXN = 20;
int a[MAXN];
int n;
map<int, int> sg; // 状态 -> SG值


int getSG(int state) {
    if (sg.count(state)) return sg[state];


    set<int> vis;


    // 枚举删除哪个数
    for (int i = 0; i < n; i++) {
        if (state & (1 << i)) {
            // 检查是否可以删除
            bool canRemove = true;
            // ... 根据题目条件判断


            if (canRemove) {
                int nextState = state ^ (1 << i);
                vis.insert(getSG(nextState));
            }
        }
    }


    for (int i = 0; ; i++) {
        if (!vis.count(i)) {
            return sg[state] = i;
        }
    }
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }


    int initState = (1 << n) - 1;


    if (getSG(initState) != 0) {
        cout << "先手必胜" << endl;
    } else {
        cout << "先手必败" << endl;
    }


    return 0;
}

7.2 分裂游戏#

问题：一个数n，每次可以将其分裂成若干个较小的数，最后无法操作的人输。

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


map<int, int> sg;


int getSG(int n) {
    if (n == 0) return 0;
    if (sg.count(n)) return sg[n];


    set<int> vis;


    // 枚举所有分裂方案
    for (int i = 1; i <= n/2; i++) {
        // 分裂成 i 和 n-i
        int xor_sum = getSG(i) ^ getSG(n - i);
        vis.insert(xor_sum);
    }


    for (int i = 0; ; i++) {
        if (!vis.count(i)) {
            return sg[n] = i;
        }
    }
}


int main() {
    int n;
    cin >> n;


    if (getSG(n) != 0) {
        cout << "先手必胜" << endl;
    } else {
        cout << "先手必败" << endl;
    }


    return 0;
}

7.3 反Nim游戏#

问题：与经典Nim游戏相反，取走最后一个石子的人输。

结论：

  • 如果所有堆石子数都为1，且堆数为奇数，先手必败
  • 如果存在一堆石子数大于1，当异或和为0时先手必败
  • 其他情况先手必胜
#include <bits/stdc++.h>
using namespace std;


int main() {
    int n;
    cin >> n;


    vector<int> a(n);
    int xor_sum = 0;
    bool allOne = true;


    for (int i = 0; i < n; i++) {
        cin >> a[i];
        xor_sum ^= a[i];
        if (a[i] > 1) allOne = false;
    }


    bool firstLose = false;
    if (allOne) {
        firstLose = (n % 2 == 1);
    } else {
        firstLose = (xor_sum == 0);
    }


    if (firstLose) {
        cout << "先手必败" << endl;
    } else {
        cout << "先手必胜" << endl;
    }


    return 0;
}

八、解题技巧总结#

8.1 识别博弈类型#

  1. 单堆取石子 → 巴什博弈或SG函数
  2. 多堆取石子 → Nim游戏
  3. 两堆特殊操作 → 威佐夫博弈
  4. 阶梯状态 → 阶梯Nim
  5. 图上移动 → DAG博弈

8.2 通用解题步骤#

  1. 确定游戏类型：公平组合游戏还是其他
  2. 定义状态：明确状态表示和终止状态
  3. 找出操作：列出所有可能的操作
  4. 计算SG值：使用记忆化搜索或动态规划
  5. 判断胜负：SG值为0则必败，否则必胜

8.3 优化技巧#

  • 使用记忆化避免重复计算
  • 状态压缩减少空间复杂度
  • 找规律简化SG函数计算
  • 对于周期性SG值，只需预处理一个周期

8.4 博弈论与其他算法的结合#

博弈论经常与其他算法知识点结合出题：

  1. 博弈 + 图论：在图上进行博弈，结合最短路、拓扑排序等
  2. 博弈 + 数论：质因数分解、约数等与博弈结合
  3. 博弈 + 动态规划：状态转移与博弈结合
  4. 博弈 + 组合数学：排列组合与博弈结合

九、经典习题推荐#

9.1 入门题目#

  1. 洛谷 P2197 - Nim游戏（入门）
  2. 洛谷 P2580 - 于是他错误的点名开始了（基础）
  3. 洛谷 P1247 - 取火柴游戏（巴什博弈）

9.2 进阶题目#

  1. 洛谷 P1288 - 取数游戏（SG函数）
  2. 洛谷 P2148 - 移动游戏（威佐夫博弈）
  3. 洛谷 P2578 - 威佐夫博弈（Wythoff Game）
  4. 洛谷 P4279 - 小凸想跑步（组合博弈）

9.3 高级题目#

  1. CF1033D - Divisors（数论+博弈）
  2. CF975D - Ghosts（图论+博弈）
  3. IOI2001 - Game（经典IOI题）
  4. NOI2005 - 智慧珠游戏（复杂博弈）

9.4 专题训练#

建议按以下顺序练习：

  1. 先做10道Nim游戏相关题目，熟悉异或运算
  2. 再做10道SG函数题目，掌握mex运算
  3. 每种经典模型至少做3道题
  4. 最后挑战组合博弈和IOI题目

十、总结#

博弈论是算法竞赛中的重要专题，从基础的Nim游戏到复杂的SG函数，从经典模型到IOI级难题，都需要扎实的理论基础和大量的练习。

关键要点#

  1. 理解必胜态和必败态的递推关系
  2. 掌握SG函数的定义和计算方法
  3. 熟记经典模型的结论和证明
  4. 灵活运用SG定理解决组合博弈
  5. 多做题积累经验和直觉

学习路径建议#

初学者（CSP-J/S水平）：

  • 掌握必胜态必败态概念
  • 熟练Nim游戏
  • 掌握巴什博弈等简单模型

中级（省选水平）：

  • 深入理解SG函数
  • 掌握所有经典模型
  • 能够解决Multi-SG问题

高级（NOI/IOI水平）：

  • 博弈与其他算法结合
  • 复杂状态空间的博弈
  • 博弈树搜索与剪枝

常见错误提醒#

  1. 忘记判断边界条件：空状态是必败态
  2. SG函数计算错误：mex运算要正确
  3. 异或运算理解偏差：多个游戏要异或SG值
  4. 经典模型记忆混淆：多做题加深记忆
  5. 状态表示不当：选择合适的状态表示方式

希望本文能帮助大家建立完整的博弈论知识体系，在算法竞赛中游刃有余！记住，博弈论不仅是数学工具，更是一种思维方式。通过大量练习，你会逐渐培养出博弈直觉，在面对新问题时能够快速找到解决方案。

继续加油，祝大家在OI道路上越走越远！

博弈论算法详解：从CSP-S到IOI
https://myblog-590.pages.dev/posts/algorithm-game-theory/
作者
谢星宇
发布于
2026-01-21
许可协议
CC BY-NC-SA 4.0

相关文章

1

网络流与二分图匹配：从CSP-S到IOI

网络流算法完整教程，涵盖最大流、最小费用流、二分图匹配等核心内容

技术 2026年1月21日
2

数论算法详解：从CSP-S到IOI

数论算法完整教程，涵盖质数、GCD、快速幂、逆元、欧拉函数等核心内容

技术 2026年1月21日
3

字符串算法详解：从CSP-S到IOI

字符串算法完整教程，包含KMP、字典树、AC自动机、后缀数组等核心算法

技术 2026年1月21日
网络流与二分图匹配：从CSP-S到IOI
数论算法详解：从CSP-S到IOI
© 2026 谢星宇. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari