组合博弈与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,...,0}的局面是P局面，那么我们可以通过反向枚举来推导出所有的可能局面，总共的状态数量为A1A2...*A[N]。并且每一次的状态转移很多。虽然耗时巨大，但确实是一个可行方法。
对于NIM博弈有如下结论(Bouton's Theorem)：
对于这个结论的证明如下：
- 全0状态为P局面，即
A[i]=0，则A[1] xor A[2] xor ... xor A[N] = 0。 - 从任意一个
A[1] xor A[2] xor ... xor A[N] = k != 0的状态可以移动到A[1] xor A[2] xor ... xor A[N] = 0的状态。由于xor计算的特殊性，我们知道一定有一个A[i]最高位与k最高位的1是相同的，那么必然有A[i] xor k < A[i]的，所以我们可以通过改变A[i]的值为A[i]'，使得A[1] xor A[2] xor ... xor A[i]' xor ... xor A[N] = 0。 - 对于任意一个局面，若
A[1] xor A[2] xor ... xor A[N] = 0，则不存在任何一个移动可以使得新的局面A[1] xor A[2] xor ... xor A[N] = 0。由于xor计算的特殊性，我们可以知道，一定是存在偶数个1时该位置的1才会被消除。若只改变一个A[i]，无论如何都会使得1的数量发生变化，从而导致A[1] xor A[2] xor ... xor A[N] != 0。
以上三条满足ICG游戏中N,P局面的转移性质，所以该结论的正确性也得到了证明。
如果限制每次最多取K个，那么将A[i]都 mod K便可以规约到普通的NIM博弈。
Sprague-Grundy函数
任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。
首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。
对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。
例如：取石子问题，有1堆n个的石子，每次只能取{1，3,4}个石子，先取完石子者胜利，那么各个数的SG值为多少？
- sg[0]=0，f[]={1,3,4},
- x=1时，可以取走1-f{1}个石子，剩余{0}个，mex{sg[0]}={0}，故sg1=1;
- x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg1}={1}，故sg2=0；
- x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg2,sg[0]}={0,0}，故sg3=1;
- x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg3,sg1,sg[0]}={1,1,0},故sg4=2;
- x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg4,sg2,sg1}={2,0,1},故sg5=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<=i<k，都存在x的一个后继y满足g(y)=i。也就是说，当某枚棋子的SG值是k时，我们可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。不知道你能不能根据这个联想到Nim游戏，Nim游戏的规则就是：每次选择一堆数量为k的石子，可以把它变成0、变成1、……、变成k-1，但绝对不能保持k不变。这表明，如果将n枚棋子所在的顶点的SG值看作n堆相应数量的石子，那么这个Nim游戏的每个必胜策略都对应于原来这n枚棋子的必胜策略！这也与以下结论(Sprague-Grundy Theorem)相对应：
g(G)=g(G1)g(G2)...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函数的应用可以看出分析后继状态的重要性。
巴什博弈(Bash Game)
巴什博奕（Bash Game）问题的叙述：
只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。
显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果 n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走 k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。也就是说，如果初始状态有 n%(m+1)==0，那么先手必输，否则必胜。
这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。等等。
显然，SG函数的一般模型也适用于巴什博弈问题。
威佐夫博弈（Wythoff Game）
威佐夫博弈（Wythoff Game）：
有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ,k=0，1，2，…,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：
(0,0),(1,2),(3,5),(4,7),(6,10),(8，13),(9,15),(11,18),(12,20)
可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k，奇异局势有如下三条性质：
- 任何自然数都包含在一个且仅有一个奇异局势中。由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1成立。
- 任意操作都可将奇异局势变为非奇异局势。事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。
- 采用适当的方法，可以将非奇异局势变为奇异局势。
假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b > bk，那么，取走b – bk个物体，即变为奇异局势；如果 a = ak ， b < bk ,则同时从两堆中拿走 ak – ab – ak个物体,变为奇异局势（ ab – ak , ab – ak+ b – ak）；如果a > ak ，b= ak + k,则从第一堆中拿走多余的数量a – ak 即可；如果a < ak ，b= ak + k,分两种情况，第一种，a=aj （j < k）,从第二堆里面拿走 b – bj 即可；第二种，a=bj （j < k）,从第二堆里面拿走 b – aj 即可。
从如上性质可知，两个人如果都采用正确操作，那么面对非奇异局势，先拿者必胜；反之，则后拿者取胜。
那么任给一个局势（a，b），怎样判断它是不是奇异局势呢？我们有如下公式：
ak =[k(1+sqrt(5))/2], bk= ak + k (k=0，1，2，…,n 方括号表示取整函数)
奇妙的是其中出现了黄金分割数(1+sqrt(5))/2 = 1.618…, 因此,由ak，bk组成的矩形近似为黄金矩形，由于2/(1+sqrt(5))=(sqrt(5)-1)/2，可以先求出j=[a(sqrt(5)-1)/2]，若a=[j(1+sqrt(5))/2]，那么a = aj，bj = aj + j，若不等于，那么a = aj+1，bj+1 = aj+1+j+1，若都不是，那么就不是奇异局势。然后再按照上述法则进行，一定会遇到奇异局势。
一道Wythoff Game的题目:
按照威佐夫博弈模型的结论，不难得到题解：
#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;
}
参考
Tags: Algorithm