SG函数

有向图游戏

题意：给定一个有向无环图，图中只有一个起点，在起点上放一个棋子，两个玩家轮流沿着有向边推动棋子，每次走一步，不能走的玩家失败

先分析一下

对于这样一个游戏，最终结束状态是棋子走到一个没有出度的点，这种状态属于必输状态，结合前两篇的 Nim 游戏可以知道，所有连向这个必输状态的状态都属于必赢状态，而没有后继状态或者后继状态都是必赢状态的状态则是必输状态

需要更严谨的理解与证明，先引入两个新东西

mex 运算

\(mex\) 运算是指对于一个集合，取集合中没有的最小非负整数
举个栗子
\(mex(0，1，2)=3\)
\(mex(1，2)=0\)

SG 函数

设当前状态 \(X\) 有后继状态 \(y_1 , y_2... y_k\)
而 \(SG(x) = mex(\small SG(y_1),SG(y_2),...,SG(y_k)\normalsize)\)

分析

现在有了这两个东西，那他是干什么用的呢

来进入刚刚分析的思路
考虑对于没有后记状态的节点，根据定义，它的 \(SG\) 值肯定是 \(0\)，而对于它的前驱节点，\(SG\) 值就肯定非 \(0\) 了，而对于全部连着必胜状态的节点，\(SG\) 值就肯定又是 \(0\) 了
所以很明确，\(SG\) 值为 \(0\) 则代表这种状态为必输状态，否则则为必胜状态

那为什么不直接是 bool 类型的值呢？不是知道是否非 \(0\) 就行了吗？

NONONO！

假如一个有向图上，却有多个棋子，这个时候这个组合游戏又该如何判断呢？

注意，后文说的SG值异或和指的都是棋子所在点位的 \(SG\) 值异或和

还是先考虑最终的必输态，所有的棋子走到出度为 \(0\) 的必输点，每个 \(SG\) 值自然为 \(0\)，所有 \(SG\) 值异或和自然也为 \(0\)，考虑这样一件事，是否面对一个当前 \(SG\) 值异或和为 \(0\) 的局面一定会走向必输呢

考虑如果对手面对这样一种局面，对手无论进行怎样的操作，都会打破异或和为 \(0\) 的局面，因为一个 \(SG\) 值为 \(k\) 的节点，走向的后继节点 \(SG\) 值一定在 \(0\) 到 \(k-1\) 范围

忽然联想到什么，这和上上篇讲的取石子不完全一样吗，可以让当前这个 \(k\) 转变为 \(0\) 到 \(k-1\) 任意一个值

继续证明

现在到自己操作，自己也是一定可以将异或和非 \(0\) 的局面再次转变为 \(0\)，理由同 Nim 游戏中那样，略过

不断的这样操作，终究会转变为最终的必输状态，并且此时轮到对手操作，所以，必胜

再回看那个联想，如果打个表会发现，对于 Nim 游戏的每个石堆的 \(SG\) 值，完全等于这个石堆的石子数量，所以，其实 Nim 游戏是 \(SG\) 函数的一种特例

后话

对于各种组合游戏，其实都本质相同，只是对于后继状态的转化各有不同罢了，博弈论还是颇有意思的，不过，咋想出来的异或和是组合游戏的结果哇