【专题】SG函数

发表于 分类于 ， 本文字数： 1.7k 阅读时长 ≈ 3 分钟
博弈论专题，介绍关于公平组合游戏、必胜态和必败态、SG函数、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) $ $ 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;
        }
    }
}