526互联

浅谈SG函数

发布时间 2023-07-22 19:43:42作者: luo_shen

公平组合游戏和策梅洛定理

公平组合游戏是指满足以下条件的一个博弈游戏：

  1. 游戏对参加的两人公平，没有随机因素，信息公开透明
  2. 两名玩家轮流行动，一名玩家不能行动时游戏结束。
  3. 游戏状态有限，且游戏一定能在有限步内结束，没有平局
  4. 游戏局势不能区分玩家

对于一个公平组合游戏，我们会关心给定初始状态，它是否存在先手必胜的策略。

为了解决这个问题，就有了策梅洛定理。策梅洛定理指出，公平组合游戏中的任何一个状态，要么先手有必胜策略，要么后手有必胜策略。

证明这件事，我们可以将一个状态看作一个点，每个状态向它的后继状态连边，形成一个有向图。因为公平组合游戏的定义中有一定在有限步内结束，所以这个有向图中不能有环，所以这又是个拓扑图。我们将操作者必败的点称为必败态，操作者必胜的点称为必胜态。
对于拓扑图的没有出度的点，必为必败态。如果一个点的后继都是必胜态，则当前点为必败态。如果一个点的后继存在必败态，则当前点为必胜态。可以发现除去这两种条件，没有其它条件了，所以每个点的状态都是确定的。于是我们得到了上述结论。

得到这个结论，我们对于所有的公平博弈游戏就有了一种通解了：对抗搜索，也就是使用记忆化搜索来完成博弈的过程。

SG函数

虽然我们有了通解，可以使用记忆化搜索完成，但我们寻求更优的做法。

先举一个例子：有一堆 \(n\) 个石头，每次能拿走 \(1\sim 3\) 个石头，取走最后一个石头的人获胜。

这是一个很经典也很简单的公平组合问题。但是如果不止一堆呢？搜索的总状态数会大大增加。但我们发现每一堆是等价的，所以我们可以算出每一堆的获胜情况，进而推出最后的获胜情况。如果用 \(0\) 表示必败态，\(1\) 表示必胜态，那么最后的结果为所有堆结果的异或和。
等等，我们需要考虑一件事，必胜态真的必胜吗？这可能未必，就比如 \(5\) 既可以转移到 \(4\) 这个必败态，也可以转移到 \(2\) 这个必胜态，也就是 \(5\) 这个状态的最终胜负情况是可以通过先手的操作改变的，自然也不能和原来的必胜态一概而论。

这时候我们引出一个阶数的概念，令必败态为 \(0\) 阶，能转移到必败态的必胜态为 \(1\) 阶状态，能转移到必败态和 \(1\) 阶状态的必胜态为 \(2\) 阶状态。于是我们得到一个 \(n\) 阶状态的定义：能转移到 \(0\sim n-1\) 阶状态中任意一阶的状态。
我们用 \(SG(S)\) 表示状态 \(S\) 的阶。根据阶数的定义，我们可以知道，当且仅当 \(SG(S)=0\) 时，状态 \(S\) 为必败态。且 \(SG(S)=\mathop{\mathrm{mex}}\{SG(S')\mid S\rightarrow S'\}\)，其中 \(S\rightarrow S'\) 表示能从状态 \(S\) 转移到 状态 \(S'\)。这个 \(mex\) 很好理解，因为 \(SG(S)\) 以下的阶数都能达到，所以状态 \(S\) 的阶数为 \(SG(S)\)。

SG 定理

先给出结论，\(SG(A+B)=SG(A)\oplus SG(B)\)

令 \(A'\) 为 \(A\) 的后继状态，\(B'\) 为 \(B\) 的后继状态。\(SG(A)=a,SG(B)=b,SG(A')=a',SG(B')=b'\)，根据计算式可以得到 \(a'\in [0,a-1]\cup [a+1,+\infty],b'\in [0,b-1]\cup [b+1,+\infty]\)。首先可以得到 \(a' \in [a+1,+\infty]\) 和 \(b'\in [b+1,+\infty]\) 是无意义的，因为对方可以转移回 \(a\) 阶状态和 \(b\) 阶状态。剩下的考虑分类讨论。

1. a=b=0

此时显然，因为每局游戏先手都必败，所以他将一直是先手，所以他最终必败。

2. 其它

考虑使用数学归纳法证明。我们假定局面 \(A+B'\) 和 \(B+A'\) 均满足要求，所以存在 \(SG(A+B')\in[0,a\oplus b'),SG(A'+B)\in[0,a'\oplus b)\)。令 \(c=a\oplus b\)，\(t\) 在二进制下有 \(sum\) 个 \(1\)，\(p_i\) 表示 \(c\) 的第 \(i\) 个为 \(1\) 的位置。则 \(c=\sum\limits_{i=1}^{sum}2^{p_i}\)。我们找到 \(p_1\) 该位如果要为 \(1\)，一定为一个该位为 \(1\) 的数和一个该位为 \(0\) 的数异或得到，\(a\oplus b'\) 和 \(b\oplus a'\) 的并集一定包含长为 \(2^{p_1}\) 的区间 \([0,2^{p_1})\)，令第 \(p_1\) 位均为 \(1\)，可以同理得到一定包含 \([2^{p_1},2^{p_1}+2^{p_2})\)，一步步往下走可以得到所有取值集合的并集为 \([0,c)\)，根据计算式，得到 \(SG(A+B)=c=SG(A)\oplus SG(B)\)，也就证明了 SG 定理的正确性。

参考资料