【专题】SG函数

公平组合游戏

公平组合游戏(Impartial Combinatorial Games)简称ICG,大致定义如下:

  1. 游戏有2名选手
  2. 对于游戏任何一种可能的局面(position),合法的操作集合只取决于这个局面本身
  3. 选手轮流操作(move),且只能在合法操作集合中选择
  4. 在游戏出于某状态,当前选手合法操作集合为空时判负,游戏结束
查看解析

一个公平游戏可以抽象地用一个有向无环图来表示,这个图中每个点都对应一个状态,每条有向边代表从一个状态到另一个状态的合法操作。

我们可以想象一个硬币最初放在某个点上,然后两个玩家轮流将其从当前的点移动到它的后继点。当硬币移动到汇点(没有出度的点)时游戏结束,无法操作的玩家判负。

ICG


必胜态和必败态

  • 必败态(P-position):上一个选手(previous player先前刚操作完的选手)处于必胜局面,即此时先手必败
  • 必胜态(N-position):下一个选手(next player当前即将操作的选手)处于必胜局面,即此时先手必胜
查看解析

更加严谨的定义:1.无法进行任何移动的局面终结点(也就是terminal position)是P-position;2.可以移动到P-position的局面是N-position;3.所有移动都导致N-position的局面是P-position。

NP

P-position和N-position的局面信息提供了游戏的必胜策略。如果轮到我们操作且游戏处在一个N-position,我们应该移动到一个P-position。接着我们的对手就会被迫进入N-position,依次类推。我们最终会移入一个汇点并获得胜利。


SG函数

先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{2,3,5}=0、mex{0,1,2,4}=3、mex{}=0。
对于任意状态x,定义SG(x)=mex(S),其中S是x后继状态的SG函数值的集合。如x有三个后继状态分别为a、b、c,那么SG(x)=mex{SG(a), SG(b), SG(c)}。 这样,集合S的终态必然是空集,所以当且仅当x为必败点P时,SG函数的终态为SG(x)=0。

查看解析

通过SG函数,每个ICG都可以转换成Nim博弈。SG函数的定义域为ICG的决策树上的所有节点,此时具体定义为:SG(x)=mex{SG(y)|y是x的节点}。对于ICG的决策树上的节点u,我们可以把它想象成一个只有一堆石子,个数为SG(u)的Nim博弈。

对于节点u的子节点v:

  1. 根据SG函数的定义,必有SG(u) $ \neq $ SG(v) 。
  2. 若SG(u) $ < $ SG(v),则根据SG函数的定义,v节点必定存在子节点w使得SG(w)=SG(u)。倘若先手尝试使得局面的SG函数值变大,由局面u移动到局面v,则后手必定可以将局面由v转移到w,恢复SG函数值。故先手无有效的手段让局面的SG函数值增大,我们只需要考虑SG(u) $ > $ SG(v)的情况。
  3. 对于全体SG(u)>SG(v)的子节点v,其SG函数值将完整覆盖区间[0, SG(u)-1]上的所有整数。我们从局面u移动到局面v,其实相当于在一堆个数为SG(u)的石子上取走若干石子,使剩下一堆个数为SG(v)的石子。

当ICG中存在n个互相不干扰的移动类型时,我们可以将这n种移动类型视为n堆石子,将该ICG视为n堆石子的Nim博弈,运用Bouton定理,该ICG的先手必胜与否的情况可以通过计算每个移动类型下的初始状态的SG函数,并计算这些SG函数值的异或和来得出。即下面的SG定理

SG


SG定理

Sprague-Grundy定理:

游戏和的SG函数等于各个游戏SG函数的Nim和(Nim和:各个数相异或的结果)。

这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim博弈中的直接应用。因为单堆Nim博弈(在一堆n个石子中可以取1~n个石子)的SG函数满足SG(n)=mex(n-1, n-2, n-3, …, n-n)=n,根据SG定理,每一堆石子总数相互异或即为答案。


模板

查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// POJ 2311
int SG[205][205];

// 递归
int getSg(int n, int m){
if(SG[n][m]!=-1) return SG[n][m];
bool S[1005]={0};

for(int i=2; i<=n-i; i++)
S[getSg(i, m) ^ getSg(n-i, m)] = 1;
for(int i=2; i<=m-i; i++)
S[getSg(n, i) ^ getSg(n, m-i)] = 1;

int mex = 0;
while(S[mex]) mex++;
return SG[n][m]=mex;
}

// 递推

void getSg(int n, int m) {
for(int i = 2; i <= n; i++){
for(int j = 2; j <= m; j++){
bool S[1005]={0};
for(int k = 2; i - k >= 2; k++) S[SG[k][j] ^ SG[i-k][j]] = 1;
for(int k = 2; j - k >= 2; k++) S[SG[i][k] ^ SG[i][j-k]] = 1;
int mex = 0;
while(S[mex]) mex++;
SG[i][j] = mex;
}
}
}
_/_/_/_/_/ EOF _/_/_/_/_/