SG函数(Sprague-Grundy)¶

约 932 个字 7 行代码预计阅读时间 3 分钟

给定博弈状态图，且是有向无环图，定义每个点的SG函数如下：

$SG(x)=mex\{SG(y) | y是x的后继\}$

如果 $SG(x)=n$ ，说明从当前状态可以转移到 $SG(y)=0,1,...,n-1$ 的局面

根据ICG定义， $SG=0$ 是必败态，否则是必胜态

对于单堆Nim游戏，SG(0)=0，那么SG(1)=1,SG(2)=2，归纳证明 SG(n)=n

求mex¶

int mex(auto v) // v可以是vector、set等容器 
{
    set<int> S(v.begin(),v.end());
    for (int i = 0;; ++i)
        if (S.find(i) == S.end())
            return i;
}

求所有点的SG函数¶

找出必败态，其SG=0
找出当前所有状态的前驱结点
根据定义计算结点SG值
重复上述步骤，直到所有点的SG函数值被计算过

求游戏SG函数（SG定理）¶

游戏：若干ICG的组合，这里ICG称为子游戏，每位玩家每回合只能选择一个子游戏操作，不能合法操作者输

游戏SG函数意义和点SG函数意义一样，后续局面的mex，但是真的去求后续局面，再求mex时间不现实，SG定理可以加速计算

SG定理：游戏SG函数等于它的所有子游戏的SG函数值的异或和

SG定理证明略

单堆石子就是一个子游戏，因此证明了上面的Nimm博弈

Anti-SG¶

如果是ICG，胜者判定改为不能合法操作者胜；如果是游戏，规定所有子游戏SG=0时，游戏结束

必胜仅当：游戏SG不为0且存在一个子游戏SG大于1，或者，游戏SG为0且不存在一个子游戏SG大于1

Multi-SG¶

在符合拓扑原则的前提下，一个子游戏的后继可以为多个子游戏。

上面这个说法有点抽象，结合最简单的Muti-SG模型理解：

有n堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)或把一堆数量不少于2 石子分为两堆不为空的石子，无合法操作者输

SG(3)的后继状态有{(0),(1),(2),(1,2)}，他们的SG值分别为{0,1,2,SG(1) XOR SG(2)} ，因此SG(3)=mex{0,1,2,3}=4

Every-SG¶

每个人每回合必须同时操作全部尚未结束的子游戏，无合法操作者输

玩家目标实际上变成最后一个子游戏的胜利，那么必胜的子游戏尽可能拖时间，相反，必输的子游戏尽快结束。时间，就是距离游戏结束还有多少回合。必胜找剩余回合数最多的，必败找剩余回合数最少的

$step(u) = \begin{cases} 0&&u为终止状态\\ max{step(v)}&& sg(u)≠0∧v为u的后继∧sg(v)=0\\ min{step(v)} && \text{sg(u)=0∧v为u的后继} \end{cases}$

必胜当且仅当子游戏最大的step为奇数

树的删边游戏¶

给出一个有 N个点的树，有一个点作为树的根节点。游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无法移动谁输。

叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1后的异或和。

无向图的删边游戏¶

一个无相联通图，有一个点作为图的根。游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部分将被移走。谁无路可走谁输。

边数是偶数的环缩成一个点，奇数的环缩成一个点加一条边

将任意一个无向图改成树结构，“无向图的删边游戏”就变成了“树的删边游戏”。