（本文章主要涉及Nim博弈及相关变种，二分图博弈以后再补_(:з)∠)_）

Nim博弈是最经典的博弈论问题之一，一般可以描述为如下：两个人轮流从若干堆石子中取石子，每次只能取一堆石子中的任意个，最后无法取（即所有石子都被取完）的玩家判负。Nim游戏拥有简洁的规则和优雅的结论，也是SG函数的基础。

基本概念

首先明确一些概念，Nim博弈是公平组合游戏（Impartial Combinatorial Games, ICG）的一种，所谓公平组合游戏，需要满足以下几个条件

  • 有两个玩家
  • 两个玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面
  • 一个局面的合法操作只与游戏当前局面有关，与当前玩家和次序等其他因素无关（公平）
  • 无法操作者判负

为什么要提这个呢？因为从这些条件里，我们可以得出一个最基本的定理：一局游戏的胜负只与当前的局面有关，与当前是哪个玩家在操作无关，因为当局面确定，由于合法操作不受其他因素影响，那么其所有可以进行的操作与操作后的局面都是确定的，在两个玩家都绝对理性的情况下（这是大前提，否则就没有意义了），其胜负自然也是确定的。

那么，我们就可以把所有局面分成两种：必胜局面和必败局面。如果一个局面可以通过一步操作移动到一个必败局面，那么这就是一个必胜局面，否则就是一个必败局面。

SG函数

有了上面的结论，我们就有了一种判断一个局面是否是必胜局面的办法：找出所有子局面，判断其中是否有必败局面。因为在取石子游戏中，操作之后问题规模一定会变小，也就相当于把当前问题划分为子问题。而对于足够小的子问题，我们可以很容易判断其胜负，如当石子数为00时显然是必败局面。
这显然是一个递归的问题，我们可以用记忆化搜索暴力解决，为了方便，我们假设只有两堆石子，且数量不超过100100。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int dp[110][110]; // -1表示未访问，0为必败，1为必胜。
memset(dp, -1, sizeof(dp));
dp[0][0] = 0;
bool dfs(int x, int y) 
{
    if (~dp[x][y])
        return dp[x][y];
    bool res = false;
    for (int i = 1; i <= x; ++i) // 暴力枚举所有子局面
        res |= !dfs(x - i, y); // 只要有一个局面为必败就是必胜局面
    for (int i = 1; i <= y; ++i)
        res |= !dfs(x, y - i);
    return dp[x][y] = res;
}

显然，当石子数或石子堆数过大时，上述方法都是不可行的，我们需要找到更本质的规律。

为了解决这个问题，我们引入SG函数。
一个局面的SG函数定义为其所有子局面的SG函数值的mex⁡\operatorname{mex}，即未出现过的最小整数。比如mex⁡(0,1,2,4)=3\operatorname{mex}(0,1,2,4)=3，mex⁡(1,2,3)=0\operatorname{mex}(1,2,3)=0，特别的，当一个局面没有子局面（石子数为00）时，其SG函数值为00。

为什么要这么定义呢，不难发现mex⁡\operatorname{mex}函数有一个性质：如果一个局面的子局面包含SG值为00的局面，那么其SG值一定不为00，反之如果不包含SG值为00的子局面，其SG值一定为00。
然后，你就会发现这个东西好像似曾相识。仔细一想，这不就是我们之前定义必胜局面与必败局面的规则吗！把SG值为00的局面对应为必败局面，不为00的局面定义为必胜局面，这两个规则不能说一模一样，只能说毫无差异。

有了上面的说明，我们就可以很容易的写出SG函数的打表代码

1
2
3
4
5
6
7
8
9
10
11
int SG[100010], vis[100010];
// 石子数为n的局面的SG值
for (int i = 1; i <= n; ++i) { // 从小规模局面往大递推
    for (int j = 1; j <= i; ++j) { // 枚举所有子局面
        vis[SG[i - j]] = i;
    }
    int res = 0;
    while (vis[res] == i) // 计算mex
        ++res;
    SG[i] = res;
}

然后当我们满怀期待地运行打表代码时，就会发现，对于这种不限石子数量的取法，其SG值与石子数是相等的……原因很明显，只要一堆石子不为00，先手就可以一次取完，也就是一个必胜局面。
好像走了条死路，让我们重新考虑两种局面之间的关系其实只是因为我讲的顺序有点问题才导致这种尴尬的局面，但是写了这么多不想改了（

根据必胜局面与必败局面的定义，一个必败局面要么已经无法操作，要么所有子局面都是必胜局面，也就是后手面对的一定是一个必胜局面，那么后手为了取胜，一定会将游戏局面移向必败局面。如果我们可以找到必败局面的某个共同特点，并且这个特点满足：

  • 只要操作了就会被破坏（到达必胜局面）
  • 只要被破坏就可以通过一次操作恢复（恢复必败局面）

那么就可以简单地判断一个局面是否是必败局面——只要判断是否有这个特点。
为了方便，我就直接给出结论（主要是真不知道这个是怎么想出来的，太抽象了）——当所有石子数异或和为00时为必败局面，否则为必胜局面。

也就是说，异或和为00就是我们要找的那个共同特点。证明也很简单：

  • 当异或和为00时，不论先手怎么操作，都无法保持异或和不变，因为异或和为00说明二进制每一位上的11都出现了偶数次，而一次只能改变一堆石子的数量，所以无法保持异或和不变。
  • 当先手破坏这个特点时，由于只能让某一堆的石子变少，那么这堆石子的数量前后一定存在一个最高位11不同，如将1212变成99，写成二进制1100，1001，第三位（从右往左）11不同。并且由于之前异或和为00，所以这一位上至少还存在着另一个11，那么后手就可以通过操作这一堆石子，把先手破坏了11的个数奇偶性的位恢复为偶数，由于被破坏的位一定小于我们之前找的最高位，所以这样的恢复总是可以做到的。

至此，我们就找到了解决Nim博弈的办法，只要求出每一堆石子的异或和，判断是否为00，现在看来，之前求的SG函数好像没有用，因为值等于石子堆数，要想看到SG函数发挥作用，需要分析另一种博弈——巴什博弈。

巴什博弈

巴什博弈基本规则与Nim博弈相同，不同之处在于巴什博弈只有一堆石子，并且限制每次取的石子不超过mm，也就是每次最少取11个，最多取mm个。
为了展示SG函数的作用，在这里我们先不分析，直接掏出之前的SG函数打表代码，当mm为44时，打出来的SG函数如下

1
0, 1, 2, 3, 4, 0, 1, 2, 3, 4

神奇的事情就发生了，SG函数的值出现了循环，循环节为55，根据SG函数的定义，当且仅当SG值为00时为必败局面，因此我们可以大胆猜测，当且仅当石子堆数为m+1m+1的倍数时，为必败局面，否则为必胜局面。

接下来分析为什么会这样，当石子个数为m+1m+1的倍数时，假设先手取了aa个石子，那么后手就可以取m+1−am+1-a个石子，由于1≤a≤m1\leq a \leq m，所以1≤m+1−a≤m1 \leq m+1-a \leq m，即后手的操作一定是合法的，这样一轮下来，石子的堆数减少了m+1m+1，那么若干轮后石子堆数就会减为00，此时先手没有石子可取，判负。
而如果石子堆数不是m+1m+1的倍数，那么先手就可以取走nmod  m+1n \mod {m+1}个石子从而让石子个数变成m+1m+1的倍数，因此是必胜局面。

这也说明了SG函数确实可以简单的表示局面的胜负，当游戏变得复杂时，比如限制取石子个数只能是1,2,51, 2, 5或者别的什么限制，SG函数都能以一种通用的方式解决这些问题。

多个游戏组合

SG函数的作用不止如此。还记得我们对Nim游戏分析的结果吗，当且仅当所有堆的石子数异或和为00时为必败局面。其实并不是石子数的异或和，而是SG函数的异或和，只不过SG值与石子数相等而没有表现出来而已。

至于证明可以直接套用之前的分析，根据SG函数的定义，一个值为mm的局面一定包含了SG值从00到m−1m-1的所有子局面，当先手把局面向SG值较小的局面移动时，后手总是可以保持异或和为00，而如果先手把局面向SG值较大的局面移动，后手就可以把那个局面再移回来，同样保持异或和为00，游戏就会在保持异或和为00的情况下不断进行下去，一直到没有可以操作的游戏，则先手判负。

也就是说，当我们面对多个游戏且每个游戏都有不同的规则时，我们依然可以快速判断出胜者是谁，只需要分别计算每一个游戏的SG函数，然后计算异或和，为00时先手必败，否则先手必胜。

总结

从上面的分析可以看出来，面对公平组合博弈论问题，打表求SG函数是通用的解法，但当数据范围过大时，依然是不可行的。这时有两种选择，一是对小范围数据进行打表，寻找规律，二是寻找必败态的共同特点。后者显然更具难度，但也是更涉及本质的做法。