博弈论和SG函数

潘老师镇楼

帅气的潘老师

在很久很久以前，有这样一个广为流传的小游戏：

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜，两人都采取最优策略，问先手能否必胜。

这其实就是著名的采石子游戏。

由此引来第一个知识点：

NIM 博弈

在 NIM 博弈中，把游戏过程中面临的状态称为局面。整局游戏中第一个行动的称为先手，第二个行动的称为后手。若在某一局面下存在某种行动，都会输掉游戏，则称该局面必败。所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对手面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。NIM 博弈不存在平局，只有先手必胜和先手必败两种情况。

定理

NIM 博弈先手必胜，当且仅当 $A_1$ xor $A_2$ xor ··· xor $A_n$ $\not=$ $0$ 。

证明:

所有物品被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 $A_1$ xor $A_2$ xor ··· xor $A_n$ $=$ 0。

对于任意一个局面，如果 $A_1$ xor $A_2$ xor ··· xor $A_n$ $=$ $x$ $\not=$ $0$ ，设 $x$ 的二进制表示下最高位的 $1$ 在第 $k$ 位，那么至少存在一堆石子 $A_i$ ,它的第 $k$ 位是 $1$ 。显然 $A_i$ xor $x$ $<$ $A_i$ ，我们就从 $A_i$ 堆中取走若干石子，使其变为 $A_i$ xor $x$ ，就得到了一个各堆石子数异或起来等于 $0$ 的局面。

对于任意一个局面，如果 $A_1$ xor $A_2$ xor ··· xor $A_n$ $=$ $0$ ，那么无论如何取石子，得到的局面下各堆石子异或起来都不等于 $0$ 。可用反证法证明，假设 $A_i$ 被取成了 $A$ ’ $_i$ ，并且 $A_1$ xor $A_2$ xor ··· xor $A$ ’ $_i$ xor ··· xor $A_n$ $=$ $0$ 。由异或运算的消去律得 $A$ ’ $_i$ $=$ $A_i$ ,与不能不取石子的规则矛盾。

然后用数学归纳法就出来了。

公平组合游戏 ICG

若一个游戏满足：

有两名玩家交替行动。
在游戏进程的任意时刻，可以执行的合法运动与轮到哪名玩家无关。
不能行动的玩家判负。

则称该游戏为一个公平组合游戏。
NIM 博弈属于公平组合游戏。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。方法：把每个局面看成图中一个节点，并且从每个局面沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 $S$ 表示一个非负整数集合。定义 mex( $S$ ) 为求出不属于集合 $S$ 的最小非负整数的运算，即：

mex(S)= {\min \{x\}\atop x \in N,x \notin S}

SG函数

在有向图游戏中，对于每个节点 $x$ ，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1$ ， $y_2$ ，··· ， $y_k$ ，定义 $SG(x)$ 为 $x$ 的后继节点 $y_1$ ， $y_2$ ，··· ， $y_k$ 的 $SG$ 函数值构成的集合再执行 mex 运算的结果，即：

SG(x)=mex(\{SG(y_1),SG(y_2),···,SG(y_k)\})

特别地，整个有向图游戏 $G$ 的 $SG$ 函数值被定义为有向图游戏起点 $s$ 的 $SG$ 函数值，即 $SG(G)=SG(s)$ 。

有向图游戏的和

设 $G_1,G_2,···,G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$ ，它的行动规则是任选某个有向图游戏 $G_i$ ，并在 $G_i$ 上行动一步。 $G$ 被称为有向图游戏 $G_1,G_2,···G_m$ 的和。

有向图游戏的和的 $SG$ 函数值等于它包含的各个子游戏 $SG$ 函数值的异或和，即：

SG(G)=SG(G_1)\ \text{xor}\ SG(G_2)\ \text{xor}\ \cdots\ \text{xor}\ SG(G_m)

定理

有向图的某个局面必胜，当且仅当该局面对应节点的 $SG$ 函数值大于 $0$ 。

有向图的某个局面必败，当且仅当该局面对应节点的 $SG$ 函数值等于 $0$ 。

例题：取石子游戏

有一堆 $n$ 个的石子，每次只能取 $\{ 1, 3, 4 \}$ 个石子，先取完石子者胜利，那么各局面的 $SG$ 值为多少？

$SG[0]=0,f[]=\{1,3,4\}$ ，

$x=1$ 时，可以取走 $1 - f\{1\}$ 个石子，剩余 $\{0\}$ 个，所以 $SG[1] = mex\{ SG[0] \}= mex\{0\} = 1$ ;

$x=2$ 时，可以取走 $2 - f\{1\}$ 个石子，剩余 $\{1\}$ 个，所以 $SG[2] = mex\{ SG[1] \}= mex\{1\} = 0$ ;

$x=3$ 时，可以取走 $3 - f\{1,3\}$ 个石子，剩余 $\{2,0\}$ 个，所以 $SG[3] = mex\{SG[2],SG[0]\} = mex\{0,0\} =1$ ;

$x=4$ 时，可以取走 $4- f\{1,3,4\}$ 个石子，剩余 $\{3,1,0\}$ 个，所以 $SG[4] = mex\{SG[3],SG[1],SG[0]\} = mex\{1,1,0\} = 2$ ;

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

以此类推……

$x$	0	1	2	3	4	5	6	7	8
$SG[x]$	0	1	0	1	2	3	2	0	1

由上述实例我们就可以得到 $SG$ 函数值求解步骤，那么计算 $1-n$ 的 $SG$ 函数值步骤如下：

1、使用数组 $f$ 将可改变当前状态的方式记录下来。

2、然后我们使用另一个数组将当前状态 $x$ 的后继状态标记。

3、最后模拟 mex 运算，也就是我们在标记值中搜索未被标记值的最小值，将其赋值给 $SG[x]$ 。

4、我们不断的重复 $2 - 3$ 的步骤，就完成了计算 $1\sim n$ 的函数值

//f[N]:可改变当前状态的方式，N为方式的种类，f[N]要在getSG之前先预处理
//SG[]:0~n的SG函数值
//S[]:为x后继状态的集合
int f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0,sizeof(SG));
    //因为SG[0]始终等于0，所以i从1开始
    for(i = 1; i <= n; i++){
        //每一次都要将上一状态 的 后继集合 重置
        memset(S,0,sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  //将后继状态的SG函数值进行标记
        for(j = 0;; j++) if(!S[j]){   //查询当前后继状态SG值中最小的非零值
            SG[i] = j;
            break;
        }
    }
}