组合博弈与SG函数

在算法研究领域博弈论占有很重要的地位，本文将围绕 $SG$ 函数和NIM博弈分析积累典型的博弈论问题模型，并给出这一类问题的一般建模方法。

Bash Game基于同余理论，Nim Game基于异或理论，Wythoff Game基于黄金分割理论。这三种博弈问题都可以通过 $SG$ 函数的通用理论来解决。

NIM博弈

NIM博弈的定义是这样的：

有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。

Nim游戏是经典的公平组合游戏(ICG)，对于ICG游戏我们有如下定义：

两名选手；
两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。

对于第三条，我们有更进一步的定义Position，我们将Position分为两类：

P-position：在当前的局面下，先手必败。
N-position：在当前的局面下，先手必胜。

他们有如下性质：

合法操作集合为空的局面是P-position；
可以移动到P-position的局面是N-position；
所有移动都只能到N-position的局面是P-position。

在这个游戏中，我们已经知道 $A[] = {0,0,\dots,0}$ 的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为 $A[1] \times A[2] \times \dots \times A[N]$。并且每一次的状态转移很多。虽然耗时巨大，但确实是一个可行方法。

对于NIM博弈有如下结论(Bouton’s Theorem)：

对于一个局面，当且仅当 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = 0$ 时，该局面为P局面。

对于这个结论的证明如下：

全 $0$ 状态为P局面，即 $A[i]=0$，则 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = 0$。
从任意一个 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = k \neq 0$ 的状态可以移动到 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = 0$ 的状态。由于 $\textit{xor}$ 计算的特殊性，我们知道一定有一个 $A[i]$ 最高位与 $k$ 最高位的 $1$ 是相同的，那么必然有 $A[i] \textit{ xor } k < A[i]$ 的，所以我们可以通过改变 $A[i]$ 的值为 $A[i]’$，使得 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[i]' \textit{ xor } \dots \textit{ xor } A[N] = 0.$
对于任意一个局面，若 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = 0$，则不存在任何一个移动可以使得新的局面 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] = 0$。由于 $\textit{xor}$ 计算的特殊性，我们可以知道，一定是存在偶数个1时该位置的1才会被消除。若只改变一个 $A[i]$，无论如何都会使得1的数量发生变化，从而导致 $A[1] \textit{ xor } A[2] \textit{ xor } \dots \textit{ xor } A[N] \neq 0$。

以上三条满足ICG游戏中N,P局面的转移性质，所以该结论的正确性也得到了证明。

如果限制每次最多取 $K$ 个，那么将 $A[i]$ 都 $\textit{mod } K$ 便可以规约到普通的NIM博弈。

Sprague-Grundy函数

任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。

首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。

对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数 $g$ 如下：

\[g(x)=mex\{ g(y) \mid \textit{ y is x's successor.} \}\]

例如：取石子问题，有 $1$ 堆 $n$ 个的石子，每次只能取 ${1，3,4}$ 个石子，先取完石子者胜利，那么各个数的 $SG$ 值为多少？

$sg[0]=0$，$f[]={1,3,4}$,
$x=1$ 时，可以取走 $1-f{1}$ 个石子，剩余 ${0}$ 个，$mex{sg[0]}={0}$，故 $sg[1]=1$;
$x=2$ 时，可以取走 $2-f{1}$ 个石子，剩余 ${1}$ 个，$mex{sg[1]}={1}$，故 $sg[2]=0$；
$x=3$ 时，可以取走 $3-f{1,3}$ 个石子，剩余{2,0}个，$mex{sg[2],sg[0]}={0,0}$，故 $sg[3]=1$;
$x=4$ 时，可以取走 $4-f{1,3,4}$ 个石子，剩余{3,1,0}个，$mex{sg[3],sg[1],sg[0]}={1,1,0}$，故 $sg[4]=2$;
$x=5$ 时，可以取走 $5-f{1,3,4}$ 个石子，剩余 ${4,2,1}$ 个，$mex{sg[4],sg[2],sg[1]}={2,0,1}$，故 $sg[5]=3$。

以此类推，得到：

x       0  1  2  3  4  5  6  7  8....
sg[x]   0  1  0  1  2  3  2  0  1....

考虑一下顶点的 $SG$ 值的意义。从上述计算过程，我们不难看出，$SG$ 函数实际上代表的一个状态值。如果值为 $0$，表示当前已经是P状态，否则表示通过第几个可选操作可以到达一个P状态（即当前状态为N状态）。在前面对Nim博弈的分析中，我们知道，N状态可以一步到达P状态，而P状态当前选手必输。

进一步考虑 $SG$ 函数与Nim博弈。当 $g(x)=k$ 时，表明对于任意一个 $0 \le i<k$，都存在 $x$ 的一个后继 $y$ 满足 $g(y)=i$。也就是说，当某枚棋子的 $SG$ 值是 $k$ 时，我们可以把它变成 $0$、变成 $1$、$\cdots$、变成 $k-1$，但绝对不能保持 $k$ 不变。不知道你能不能根据这个联想到Nim游戏，Nim游戏的规则就是：每次选择一堆数量为 $k$ 的石子，可以把它变成 $0$、变成 $1$、$\dots$、变成 $k-1$，但绝对不能保持 $k$不变。这表明，如果将 $n$ 枚棋子所在的顶点的 $SG$值看作 $n$ 堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这 $n$ 枚棋子的必胜策略！这也与以下结论(Sprague-Grundy Theorem)相对应：

$g(G)=g(G1) \textit{ xor } g(G2) \textit{ xor } \dots \textit{ xor } g(Gn)$。也就是说，游戏的和的 $SG$ 函数值是它的所有子游戏的 $SG$ 函数值的异或。

当 $g(G)$ 为 $0$ 时，先手必输，否则先手必胜。同时，$SG$ 函数也揭示了Nim博弈中的必胜方案。

求解SG函数的实现：

int sg[N];

// N求解范围 S[]数组是可以每次取的值，t是s的长度。
void sg_solve(int *s, int t, int N) {
    int i,j;
    bool hash[N];
    memset(sg,0,sizeof(sg));
    for(i=1;i<=N;i++) {
        memset(hash,0,sizeof(hash));
        for(j=0;j<t;j++) {
            if(i - s[j] >= 0) {
                hash[sg[i-s[j]]] = 1;
            }
        }
        for(j=0;j<=N;j++) {
            if(!hash[j]) { break; }
        }
        sg[i] = j;
    }
}

除了按照定义递推以外，还可以通过DFS求解：

// 注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
// n是集合s的大小 S[i]是定义的特殊取法规则的数组

int s[110], sg[10010], n;

int SG_dfs(int x) {
    int i;
    if(sg[x]!=-1) {
        return sg[x];
    }
    bool vis[110];
    memset(vis,0,sizeof(vis));
    for(i=0;i<n;i++) {
        if(x>=s[i]) {
            SG_dfs(x-s[i]);
            vis[sg[x-s[i]]]=1;
        }
    }
    int e;
    for(i=0;;i++) {
       if(!vis[i]) {
            e=i;
            break;
       }
    }
    return sg[x]=e;
}

Nimble游戏是另一种Nim博弈的应用场景：

游戏开始时有许多硬币任意分布在楼梯上，共N阶楼梯从地面由下向上编号为0到N。游戏者在每次操作时可以将任意一枚硬币向下移动，直至地面。

游戏者轮流操作，将最后一枚硬币移至地面(即第 $0$ 阶)的人获胜。在双方都采取最优策略的情况下，对于给定的初始局面，问先手必胜还是先手必败。每一枚硬币仍然对应了一个石子堆，向下移动就等价于从石子堆里面取出石子。

Lasker’s Nim游戏

Lasker’s Nim游戏是指这样一种博弈模型：

每一轮允许两会中操作之一：

从一堆石子中取走任意多个；

将一堆数量不少于2的石子分成都不为空的两堆。

很明显：

$sg(0) = 0$，$sg(1) = 1$。
状态 $2$ 的后继有：$0, 1, (1, 1)$，他们的 $SG$ 值分别为 $0,1,0$，所以 $sg(2) = 2$。
状态 $3$ 的后继有：$0, 1, 2, (1, 2)$，他们的 $SG$ 值分别为 $0,1,2,3$，所以 $sg(3) = 4$。
状态 $4$ 的后继有：$0, 1, 2, 3, (1,3), (2,2)$，他们的 $SG$ 值分别为 $0,1,2,4,5,0$，所以 $sg(4) = 3$。

由数学归纳法可以得出

sg(4k)=4k-1;
sg(4k+1)=4k+1;
sg(4k+2)=4k+2;
sg(4k+3)=4k+4;

通过这个 $SG$ 函数的应用可以看出分析后继状态的重要性。

练习题目：HDU 3032 Nim or not Nim?

巴什博弈(Bash Game)

巴什博奕（Bash Game）问题的叙述：

只有一堆 $n$ 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 $m$ 个。最后取光者得胜。

显然，如果 $n=m+1$，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果 $n=(m+1) \times r+s$，($r$为任意自然数，$s \leq m$),那么先取者要拿走 $s$ 个物品，如果后取者拿走 $k$ ($\leq m$)个，那么先取者再拿走 $m+1-k$个，结果剩下 $(m+1)(r-1)$ 个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下 $(m+1)$ 的倍数，就能最后获胜。也就是说，如果初始状态有 $n\%(m+1)=0$，那么先手必输，否则必胜。

这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。等等。

显然，$SG$ 函数的一般模型也适用于巴什博弈问题。

威佐夫博弈（Wythoff Game）

威佐夫博弈（Wythoff Game）：

有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

这种情况下是颇为复杂的。我们用 $(a_k, b_k), a_k \le b_k, k = 0,1,2,\dots,n$ 表示两堆物品的数量并称其为局势，如果甲面对 $(0，0)$，那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：

\[(0,0),(1,2),(3,5),(4,7),(6,10),(8，13),(9,15),(11,18),(12,20)\]

可以看出, $a_0=b_0=0$，$a_k$ 是未在前面出现过的最小自然数，而 $b_k = a_k + k$，奇异局势有如下三条性质：

任何自然数都包含在一个且仅有一个奇异局势中。由于 $a_k$ 是未在前面出现过的最小自然数，所以有 $a_k > a_k-1$，而 $b_k = a_k + k > a_k-1 + k-1 = b_k-1 > a_k-1$。所以性质1成立。
任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势 $(a_k, b_k)$ 的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使 $(a_k, b_k)$ 的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
采用适当的方法，可以将非奇异局势变为奇异局势。

假设面对的局势是 $(a,b)$，若 $b=a$，则同时从两堆中取走 $a$ 个物体，就变为了奇异局势 $(0,0)$；如果 $a = a_k, b > b_k$，那么，取走 $b–b_k$ 个物体，即变为奇异局势；如果 $a = a_k, b < b_k$，则同时从两堆中拿走 $a_k – ab – a_k$ 个物体,变为奇异局势 $(ab–a_k, ab–a_k+b–a_k)$；如果 $a>a_k, b=a_k+k$，则从第一堆中拿走多余的数量 $a–a_k$ 即可；如果 $a < a_k, b = a_k + k$，分两种情况，第一种，$a = a_j (j < k)$，从第二堆里面拿走 $b – b_j$ 即可；第二种， $a = b_j (j < k)$，从第二堆里面拿走 $b – a_j$ 即可。

从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。

那么任给一个局势 $(a, b)$，怎样判断它是不是奇异局势呢？有如下公式：

\[a_k = \lfloor {k \times \frac{1+\sqrt{5}}{2}} \rfloor, b_k= a_k + k (k = 0, 1, 2, \dots, n)\]

奇妙的是其中出现了黄金分割数 $\frac{1+\sqrt{5}}{2} = 1.618\dots$ 因此，由 $a_k, b_k$ 组成的矩形近似为黄金矩形，由于 $\frac{2}{1+\sqrt{5}} = \frac{\sqrt{5}-1}{2}$，可以先求出 $j = \lfloor { a \times \frac{\sqrt{5}-1}{2}} \rfloor$，

若 $a = \lfloor {j \times \frac{1+\sqrt{5}}{2}} \rfloor$ 那么 $a = a_j, b_j = a_j + j$
若不等于，那么 $a = a_j+1, b_j+1 = a_j+1+j+1$
若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。

一道Wythoff Game的题目:

题目：POJ 1067. 取石子游戏

按照威佐夫博弈模型的结论，不难得到题解：

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

int main(int argc, char **argv) {
    int a, b, k;
    double p=(1+sqrt(5.0))/2;
    while(scanf("%d%d",&a,&b)==2) {
        if(a>b) {
            swap(a,b);
        }
        k = a / p;
        if((a==int(k*p)&&b==a+k) || (a==int((k+1)*p)&&b==a+k+1)) {
            printf("0\n");
        }
        else {
            printf("1\n");
        }
    }
    return 0;
}