【算法基础篇】（五十九）巴什博弈 (Bash Game) 超详解：从原理到实战，搞定经典取石子问题

前言

在算法竞赛的博弈论领域，巴什博弈（Bash Game）是最基础、最经典的公平组合游戏模型，也是入门博弈论的必经之路。它以简单的规则为载体，蕴含着博弈论的核心思想 ——必胜态与必败态的推导，掌握巴什博弈的解题思路，能为后续学习 Nim 博弈、SG 函数等复杂博弈模型打下坚实的基础。本文将从巴什博弈的定义出发，深入推导其核心结论，结合多个经典例题讲解实战用法，同时附上完整的 C++ 代码实现，让你彻底吃透巴什博弈的精髓。下面就让我们正式开始吧！

一、博弈论基础铺垫

在正式讲解巴什博弈之前，我们先快速梳理博弈论中几个核心概念，这是理解所有博弈模型的前提，尤其是公平组合游戏（ICG） 的定义，巴什博弈正是典型的公平组合游戏。

1.1 公平组合游戏 (ICG)

公平组合游戏是博弈论中最核心的分类之一，满足以下三个关键条件：

1. 游戏由两名玩家轮流进行决策，双方都知晓游戏的全部信息（无隐藏规则）；
2. 任意玩家在某一确定游戏状态下，能做出的决策集合只与当前状态有关，与玩家身份无关（双方规则对等）；
3. 游戏以玩家无法行动为判负条件，且游戏一定会在有限步内结束，不存在平局。

简单来说，公平组合游戏的核心是规则公平、结果确定，不存在运气成分，且两名玩家的操作空间完全由当前游戏状态决定。

1.2 必胜态与必败态

在公平组合游戏中，由于玩家都是绝顶聪明的（会选择对自己最有利的最优策略），因此游戏的每一个状态都有唯一的结果，分为两种：

• 必胜态：当前状态下，行动的玩家（先手）存在至少一种策略，使得无论对方如何操作，自己最终都能获胜；
• 必败态：当前状态下，行动的玩家（先手）无论采取何种策略，对方都能找到应对方法，最终自己一定会失败。

博弈论的核心解题思路，就是推导游戏初始状态是必胜态还是必败态，而推导的关键依据是两个核心性质：

1. 必胜态的后继状态中，至少存在一个必败态（先手可以通过操作让对方陷入必败态）；
2. 必败态的后继状态中，全部都是必胜态（无论先手怎么操作，都会让对方进入必胜态）。

这两个性质是所有博弈模型推导的底层逻辑，巴什博弈的结论也正是基于此推导而来。

1.3 非公平组合游戏与反常游戏

与公平组合游戏相对的是非公平组合游戏，其核心区别是：玩家在确定状态下的决策集合与玩家身份有关，比如中国象棋、围棋、国际象棋（双方不能使用对方的棋子），这类游戏的解题思路比公平组合游戏复杂得多。

反常游戏则是规则与经典游戏一致，但胜负判定相反的游戏，比如经典 Nim 游戏是取走最后一颗石子获胜，而反常 Nim 游戏是取走最后一颗石子判负。巴什博弈也存在反常版本，本文重点讲解经典巴什博弈，后续会简单提及反常版本的思路。

二、巴什博弈 (Bash Game) 核心原理

2.1 巴什博弈的经典问题描述

巴什博弈的经典场景是取石子游戏，规则如下：

一共有n颗石子，两名玩家轮流从石子堆中取石子，每次至少取 1 颗，最多取k颗；拿到最后一颗石子的玩家获胜。 问：先手玩家是否存在必胜策略？

这是最标准的巴什博弈模型，所有巴什博弈的变种问题都是基于此规则延伸而来。我们的目标就是通过数学推导，找到n和k之间的关系，直接判断先手的胜负。

2.2 核心结论推导

结合前文提到的必胜态与必败态的核心性质，我们从最简单的情况开始推导，逐步找到规律。

步骤 1：定义基础状态

首先定义必败态的基准：当石子数n=0时，当前玩家无石子可取，判负，因此n=0是必败态。

步骤 2：分析小数值的状态规律

假设每次最多取k=3颗石子（方便举例），我们分析n从 1 到 10 的状态：

• n=1：先手取 1 颗，直接获胜 → 必胜态；
• n=2：先手取 2 颗，直接获胜 → 必胜态；
• n=3：先手取 3 颗，直接获胜 → 必胜态；
• n=4：先手无论取 1/2/3 颗，后手都能取走剩下的所有石子（比如先手取 1，后手取 3；先手取 2，后手取 2；先手取 3，后手取 1），后手获胜 → 必败态；
• n=5：先手取 1 颗，剩下 4 颗（必败态）交给后手 → 必胜态；
• n=6：先手取 2 颗，剩下 4 颗（必败态）交给后手 → 必胜态；
• n=7：先手取 3 颗，剩下 4 颗（必败态）交给后手 → 必胜态；
• n=8：先手无论取 1/2/3 颗，后手都能取走对应数量，让剩下的石子数为 4 颗 → 必败态；

从这个例子中，我们能清晰看到规律：当 n 是 k+1 的倍数时，当前状态为必败态；否则为必胜态。

对应上面的例子，k+1=4，n=4、8是 4 的倍数，均为必败态，其余为必胜态。

步骤 3：通用结论严格证明

通过例子找到的规律需要严格证明，我们结合必胜态和必败态的核心性质，证明巴什博弈的通用结论：

巴什博弈核心结论：对于 n 颗石子、每次取 1~k 颗的取石子游戏，

1. 若n % (k + 1) == 0，则先手必败；
2. 若n % (k + 1) != 0，则先手必胜。

证明过程：设m = k + 1，分两种情况讨论：

情况 1：n 是 m 的倍数（n = t * m，t 为正整数）

当前玩家（先手）无论取x颗石子（1 ≤ x ≤ k），剩下的石子数为n - x = t*m - x。此时后手玩家只需取m - x颗石子（由于1 ≤ x ≤ k，则1 ≤ m - x ≤ k，符合规则），剩下的石子数为(t-1)*m，依旧是 m 的倍数。

如此反复，后手玩家总能让每次操作后剩下的石子数保持为 m 的倍数，最终先手玩家会面对n=m的状态，无论先手取多少，后手都能取走最后一颗石子，因此n 是 m 的倍数时，先手必败（必败态）。

情况 2：n 不是 m 的倍数（n = t * m + r，1 ≤ r ≤ k）

当前玩家（先手）可以直接取r颗石子，剩下的石子数为t * m，是 m 的倍数，将必败态交给后手玩家。

此后后手玩家处于必败态，无论后手取多少，先手都能按照情况 1 的策略，让每次操作后剩下的石子数保持为 m 的倍数，最终先手取走最后一颗石子，因此n 不是 m 的倍数时，先手必胜（必胜态）。

至此，巴什博弈的核心结论得到严格证明，这个结论是解决所有巴什博弈问题的关键，只需通过一个取模运算就能直接判断胜负，时间复杂度为 O (1)，效率极高。

2.3 巴什博弈的核心思想

巴什博弈的核心是凑数策略：先手玩家通过第一次操作，让剩下的游戏状态成为必败态，而后手玩家无论如何操作，都无法摆脱必败态，先手玩家只需全程模仿后手的操作节奏，始终将必败态交给对方，最终获胜。

简单来说，就是先手创造必败态，后手被迫进入必败态，这也是所有公平组合游戏的核心解题思路。

三、巴什博弈经典例题实战

理论结合实践才是掌握算法的关键，本节将结合巴什博弈的经典例题，从基础模板题到变种题，逐一讲解解题思路，并附上完整的 C++ 代码实现，所有代码均经过验证，可直接用于算法竞赛。

3.1 例题 1：取石子游戏 1（巴什博弈基础模板题）

题目链接：https://ac.nowcoder.com/acm/problem/50614

题目来源

牛客网（信息学奥赛一本通）

题目描述

玩家为 2 人，道具为 N 颗石子，规则如下：

1. 双方轮流取石子；
2. 每人每次取走 1~K 颗石子（最少 1 颗，最多 K 颗）；
3. 石子取光游戏结束，最后取石子的一方获胜。

假设两名玩家都非常聪明，问最后谁会获胜？

输入描述

输入仅一行，两个整数 N 和 K，表示石子总数和每次最多取的石子数。

输出描述

输出仅一行，1 表示先手获胜，2 表示后手获胜。

解题思路

这是最标准的巴什博弈模板题，直接套用核心结论即可：

• 若N % (K+1) != 0，先手必胜，输出 1；
• 若N % (K+1) == 0，后手必胜，输出 2。

C++ 代码实现

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    // 直接套用巴什博弈结论
    if (n % (k + 1) != 0) {
        cout << 1 << endl; // 先手必胜
    } else {
        cout << 2 << endl; // 后手必胜
    }
    return 0;
}

示例测试

输入：23 3

计算：23 % (3+1) = 23 %4 = 3 ≠ 0 → 先手必胜

输出：1与题目示例一致，验证代码正确性。

3.2 例题 2：Roy&October 之取石子（巴什博弈变种 1）

题目链接：https://www.luogu.com.cn/problem/P4018

题目来源

洛谷 P4018

题目描述

共有 n 个石子，两人每次只能取p^k个石子（p 为质数，k 为自然数，且p^k ≤ 当前剩余石子数），谁取走最后一个石子谁赢。October 为先手，问她是否有必胜策略？若有，输出October wins!；否则输出Roy wins!。

输入描述

第一行一个正整数 T，表示测试用例组数；第 2~T+1 行，每行一个正整数 n，表示石子个数。

输出描述

T 行，每行输出对应的结果。

解题思路

这道题看似是新的规则，实则是巴什博弈的变种，核心是找到必败态的周期，通过推导可得出结论：

• 当 n 是 6 的倍数时，先手必败；
• 当 n 不是 6 的倍数时，先手必胜。

本质上，该规则下每次可取的石子数集合决定了k+1=6，因此转化为巴什博弈的标准模型，直接用 n 对 6 取模即可判断胜负。

C++ 代码实现

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n % 6 != 0) {
            cout << "October wins!" << endl;
        } else {
            cout << "Roy wins!" << endl;
        }
    }
    return 0;
}

示例测试

输入：34914

计算：4%6=4≠0 → October wins!

9%6=3≠0 → October wins!

14%6=2≠0 → October wins!

输出与题目示例一致，验证代码正确性。

3.3 例题 3：Roy&October 之取石子 II（巴什博弈变种 2）

题目链接：https://www.luogu.com.cn/problem/P4860

题目来源

洛谷 P4860

题目描述

共有 n 个石子，两人每次只能取p^k个石子（p 为质数，k=0 或 1，且p^k ≤ 当前剩余石子数），谁取走最后一个石子谁赢。October 为先手，问她是否有必胜策略？若有，输出October wins!；否则输出Roy wins!。

输入描述

第一行一个正整数 T，表示测试用例组数；第 2~T+1 行，每行一个正整数 n，表示石子个数。

输出描述

T 行，每行输出对应的结果。

解题思路

这道题是上一题的变种，规则中限制了 k 只能为 0 或 1，推导后可得核心结论：

• 当 n 是 4 的倍数时，先手必败；
• 当 n 不是 4 的倍数时，先手必胜。

该规则下k+1=4，依旧是巴什博弈的标准模型，直接用 n 对 4 取模即可。

C++ 代码实现

#include <iostream>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        if (n % 4 != 0) {
            cout << "October wins!" << endl;
        } else {
            cout << "Roy wins!" << endl;
        }
    }
    return 0;
}

示例测试

输入：35714

计算：5%4=1≠0 → October wins!

7%4=3≠0 → October wins!

14%4=2≠0 → October wins!

四、巴什博弈的延伸与拓展

掌握了经典巴什博弈和其变种后，我们可以对巴什博弈进行进一步的延伸，了解其反常版本和更复杂的组合版本，为后续学习更复杂的博弈模型做铺垫。

4.1 巴什博弈的反常版本

反常巴什博弈的规则与经典版本一致，唯一区别是胜负判定相反：取走最后一颗石子的玩家判负。

对于反常巴什博弈，核心结论需要稍作调整：

一共有 n 颗石子，每次取 1~k 颗，取走最后一颗石子的玩家判负，先手必胜的条件是(n-1) % (k+1) != 0。

推导思路：反常版本的核心是让对方取走最后一颗石子，因此先手玩家需要让剩下的石子数为 1 时，交给对方操作。此时问题转化为：先手玩家需要将 n-1 颗石子的经典巴什博弈必败态交给对方，因此只需对n-1套用经典巴什博弈的结论即可。

4.2 巴什博弈与其他博弈模型的组合

在算法竞赛中，纯巴什博弈的题目相对简单，更多的是将巴什博弈与其他博弈模型（如 Nim 博弈、SG 函数）结合，形成更复杂的组合博弈问题。

比如多堆石子的巴什博弈：有 m 堆石子，第 i 堆有n_i颗石子，两名玩家轮流操作，每次选择一堆石子，取 1~k 颗，取走最后一颗石子的玩家获胜。

这类问题的解题思路是对每堆石子判断巴什博弈的状态，再结合 Nim 博弈的异或规则，最终判断整体的胜负，核心是将巴什博弈的状态转化为 Nim 博弈中的堆值，再进行异或运算。在下期博客中我将为大家介绍Nim博弈的相关内容。

4.3 巴什博弈的解题技巧总结

无论是经典巴什博弈还是其变种，解题的核心技巧都可以总结为以下 3 步：

1. 分析游戏规则，确定玩家的操作空间（每次能取的石子数范围）；
2. 推导必败态的周期，找到k+1的取值（即必败态的间隔）；
3. 套用巴什博弈结论，通过取模运算直接判断先手的胜负。

对于变种问题，关键是将非标准规则转化为巴什博弈的标准模型，找到必败态的周期，这需要通过小数值推导或打表找规律实现（比如洛谷的 Roy&October 取石子问题，可通过打表找到 6 和 4 的周期）。

五、巴什博弈的学习意义与后续拓展

巴什博弈作为博弈论的入门模型，虽然简单，但蕴含着博弈论的核心思想 ——必胜态与必败态的推导，掌握巴什博弈的解题思路，能帮助我们建立博弈论的思维方式，为后续学习更复杂的博弈模型打下基础。

从巴什博弈出发，后续可以逐步学习以下博弈论模型：

1. Nim 博弈：多堆石子的经典公平组合游戏，核心是异或运算，是巴什博弈的多堆拓展；
2. 阶梯型 Nim 博弈：Nim 博弈的变种，将石子分布在阶梯上，核心是只考虑奇数台阶的异或；
3. SG 函数：博弈论的通用解决方案，将所有公平组合游戏转化为有向图游戏，通过 mex 运算求解 SG 值，再结合异或规则判断胜负；
4. 威佐夫博弈：另一种经典的公平组合游戏，基于两堆石子的取石子规则，核心是黄金分割数。

这些博弈模型都是在巴什博弈的基础上延伸而来，掌握巴什博弈的核心思想后，学习后续模型会事半功倍。

总结

本文从博弈论的基础概念出发，详细讲解了巴什博弈的核心原理、结论推导，并结合三道经典例题讲解了实战用法，同时附上了完整的 C++ 代码实现，还对巴什博弈的反常版本、变种问题和解题技巧进行了总结。 巴什博弈的核心结论非常简单，就是一个取模运算，但推导结论的过程比结论本身更重要，因为这个过程蕴含了博弈论的核心思维 —— 必胜态与必败态的推导。在算法竞赛中，真正的难点不是套用结论，而是将非标准的游戏规则转化为巴什博弈（或其他博弈模型）的标准模型，这需要大量的练习和思考。 希望本文能帮助你彻底吃透巴什博弈，为你打开博弈论的大门。后续我会继续讲解 Nim 博弈、SG 函数等更复杂的博弈模型，关注我，一起玩转算法竞赛的博弈论！