从ICG到SG函数

博弈论 数学

SG函数是用于解决博弈论中公平组合游戏（ICG）问题的一种方法

ICG

这是啥？

定义大概就几条：

1. 双方参与，轮流决策，决策最优
2. 无法决策时游戏结束，无法决策者输，不论如何决策游戏都能在有限步完成
3. 同一状态不可多次抵达，游戏无平局，任意决策者在决策点的行为与决策者无关仅与决策点有关

这就是 ICG，公平组合游戏

典型例子是 nim 游戏

必胜必败态

必败态：记为 P，直观理解就是到达这个状态的人已经必死无疑了
必胜态：记为 N，直观理解就是到这里就稳了，脑子不犯蠢就一定会赢

可以证明 ICG 里任意状态一定都是这两种状态，有策梅洛定理：

策梅洛定理：ICG 游戏中，任何一个局面先手或者后手其中之一必然存在必胜策略

如何判断一个状态是 N 是 P 呢？

最直观的方法是：

• 无法移动的状态一定是 P，称为初必败态
• 能够移动到必败态的一定是必胜态，因为你只要往必败态走就行了
• 只能移动到必胜态的就是必败态，因为你无论如何行动对手都必胜了

DAG的博弈

有这样一个问题

给定一个有向无环图，在给定的起点处有一个棋子，两个炒鸡聪明的人交替移动这个棋子，不能移动者输

看起来是一个很呆的问题，但是这个问题单独拿出来的意义在于 任意一个 ICG 问题都可以归纳到这种形式（状态为点，状态间连边）

mex运算

马上要开始探究 SG 函数，但是在此之前......

首先我们需要定义一个奇怪的运算，mex

这是一个数集的运算符号，$mex(S)$ 代表的是不在集合 $S$ 中 的最小自然数

例如 $mex(\{0,1,3,5\})=2$

SG函数

用 $v(u,v)$ 表示从 $u$ 到 $v$，存在直接的有向边，则

对于给定的 DAG，我们定义每个点的SG函数为：

$SG(x)=mex(\{SG(y)|v(x,y)\})$

但是只有这一个函数呢，他是啥用么有的

SG函数的性质

• 所有汇点（也就是各个初必败态）的 $SG$ 函数值为 $0$

这个应该比较显然的说，因为此时后继状态都是空集

• $SG(x)=0$ 是 $x$ 为必败态的充要条件，$SG(x)\neq 0$ 是 $x$ 是必胜态的充要条件

以上就是一维 $SG$ 函数的基本内容，利用这个例子我们可以解决一个简单的经典小问题

巴什博弈：一堆石子有 $n$ 个，每次可以取 $[1,m]$ 个石子。先取完者获胜。问何时先手必胜，何时后手必胜？

发现暴力算是可以解决的

如果追求效率，经常不会真的去暴力算 $SG$，而是考虑直接归纳每个状态的 $SG$ 函数

如果算一遍 $SG$ 的代价可以承受，就可以考虑直接去算

但是如果不能归纳出 $SG$ 函数，这种博弈问题我们就是不能得出结论通解的

先介绍一下考场实用的一种方法：打表

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m;
int SG[N];
bitset<N> S,clr;
void get_SG(){
    SG[0]=0;
    for(int i=1;i<=n;i++){
        S&=clr;
        for(int j=1;j<=min(m,i);j++){
            S[SG[i-j]]=1;
        }
        for(int j=0;;j++){
            if(!S[j]) {SG[i]=j;break;}
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    get_SG();
    for(int i=1;i<=n;i++) cout<<SG[i]<<endl;
}

根据定义，这份代码可以打出巴什博弈的 $SG$ 函数

我们可以观察出 $SG$ 在巴什博弈的规律是 $SG(x)=x\bmod (m+1)$，这是我们观察出的结论

一般我们可以打出表来，然后再证明（当然不证也不是啥大事，只要你多看看确认是对的就行）

巴什博弈的证明是显然的，就不赘述了

SG定理

如果 $SG$ 只能解决一维的博弈问题，那这个玩意其实有点弱了

nim游戏

先用一个简单的例子来引入一下

nim game

这是一个可拆分的组合游戏

我们考虑一个子游戏，即考虑拿出任意一堆来做游戏

我们称 $SG(x)$ 表示大小为 $x$ 的堆的 $SG$ 函数，显然有 $SG(x)=x$

我们很容易得出面前的每一堆的子游戏是必胜还是必败

尝试用子问题的胜败推出总问题的胜败！

这里先考虑两个子问题的复合，因为多个子问题本质上就是两个的情况的扩展

• 当我面前两个游戏都是必败的，则我必败

  必败的走一步必然走到必胜的
  
  等会对面再把另一个变成必败的，我又收到了两个必败游戏
  
  最后我会收到两个无子可动的终盘游戏，则我必败
  

• 假如我面前摆着一败一胜的游戏，实际上我必胜

  必胜的走一步能走到必败的
  
  对面会收到两个必败，对面一定会输
  
  故我必胜
  

• 假如面前是两个必胜......

等会，好像不太对劲

两个必胜在我面前时，我根本无法判断我必胜还是必败

有点悲哀，好像寄了，单个的 $SG$ 函数貌似无法直接复合生成，那难道没有办法了吗

SG定理

此时某位我不知道是谁的伟大的人给出了一个伟大的定理，SG定理

SG定理：游戏的“和”（其实是复合）的 $SG$ 值是各个子问题 $SG$ 的异或和

然后我们可以发现这个问题我们解决了！

于是nim游戏的 $SG$ 已经非常简单的搞定了

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n;
int a[N];
int T;
void work(){
    cin>>n;
    int xr=0;
    for(int i=1;i<=n;i++)cin>>a[i],xr^=a[i];
    if(xr==0) cout<<"No\n";
    else cout<<"Yes\n";
}
int main(){
    cin>>T;
    while(T--){
        work();
    }
}

短小精悍

证明不会

后面是例题环节

题目

XYD_OIFC2024 noip10.30T2

here（需要权限）

考察每个数的 $SG$，容易得出 $SG(1)=1$，其余情况 $SG(x)=mex_{u=1}^{x-1}(\oplus_{i=1}^{u} SG(x))$，显然 $mex$ 里面那一坨要么大于 $2$ 要么是 $1$ 所以 $SG(x)=2$，然后就做完了