头条超市

博弈论

2024-07-25 21:50 由 ppllxx_9G 发表于 #其他

博弈论

强烈推荐 浅谈SG函数和博弈论

策梅洛定理

考虑对于一个游戏，他满足以下的特点

  • 两人单挑，轮流操作

  • 信息公开透明

  • 没有随机因素

  • 有限步内必然结束

  • 不存在平局

根据策梅洛定理：对于这样的一个游戏，任何一个局面先手或者后手其中之一必然存在必胜策略。

既然每个局面都有一方会必胜，那我们的目的就是在最初游戏开始时就确定，谁会赢。

如何证明呢？

我们先考虑最后的状态，根据游戏规则，必然有一方必胜。

  1. 如果已经到了最终状态，按照游戏规则，必然有一方已经获胜

  2. 如果某一状态的所有后继状态都为先手必胜，那么此状态先手必败。

  3. 如果某一状态存在后继状态为先手必败，那么此时先手必胜。

因此，任何一个局面一定存在某一方必胜。

SG 函数

我们把上面的定理转化为数学语言。

定义先手必败的状态为零，先手必胜的状态为非零。则最后一个状态一定为 \(0\)。

根据上面的定理，判断一个局面的必胜，只需要观察它的后继状态是否存在零即可，

我们定义 SG 函数为所有子状态 SG 函数的 mex，SG 函数记录了这一状态能转移到的所有子状态。

如果子状态 SG 存在零，那么此时 SG 函数一定不为零，即 如果某一状态存在后继状态为先手必败，那么此时先手必胜。

如果子状态 SG 全部大于零，那么此时 SG 函数一定能取到零，即 如果某一状态的所有后继状态都为先手必胜，那么此状态先手必败。。

因此 SG 函数很好的模拟了上述的策梅洛定理，并且将它转化为了可运算的数学公式。

我们顺便完善 SG 函数的定义：

  • 阶数：能转移到 \(0\) 至 \(n-1\) 中任一阶状态的状态，称为 \(n\) 阶状态。
    （根据 \(SG\) 函数的定义，\(阶数=SG 值\)）

  • \(SG(x)=mex \{ SG(y)|x \to y \}\) [1]

SG 定理

定义了 SG 函数，开始研究有关 SG 函数的运算，既然是运算，就涉及不同状态间的拆分和合并。

（注意：不同 SG 函数之间为不同子游戏的并列和包含关系，而不是上文所说的状态的前驱和后继关系，放在 Nim 游戏里就是不同石子堆的关系。）

令 \(z=x+y\) （状态 \(z\) 的子游戏为 \(x,y\)）。

再次重申：\(z=x+y\) 的意思是同一个状态时，\(z\) 所包含的子游戏可以划分为 \(x,y\)。

以 Nim 游戏为例，可以理解成 \(z\) 表示两堆石子的状态，\(x,y\) 分别表示其中一堆石子单独看成一场游戏。

那么显然，对于游戏 \(z\)，我们一次只能移动一个石子堆，也就是只能改变 \(x,y\) 中的一场子游戏的状态。

  • 如果 \(SG(x)=0,SG(y)=0\) 那么显然必败。（这是后面推理的基础）

  • 如果 \(SG(x)=1,SG(y)=0\)，后继状态只可能是 \(SG(x)=0,SG(y)=0\)，后继必败，所以当前必胜。

  • 如果 \(SG(x)=1,SG(y)=1\)，后继状态只可能是 \(SG(x)=1,SG(y)=0\)，\(SG(x)=0,SG(y)=1\)，根据刚刚讨论的，无论怎么移动对方都会进入必胜态，所以当前必败。

这样得到结论，任意两个同阶的 SG 函数总能有一种操作使双方进行一轮操作后仍保持同阶，

先手无论怎么移动一定得到不同阶的后继状态。

对于任意一个不同阶的状态，对方一定能使它回到同阶的状态，这样先手又接到了一个同阶状态。

而随着越来越接近最终态，后继状态不停在减少，所以一定会落在 \(SG(x)=0,SG(y)=0\) 的必败状态上。

所以同阶必败，不同阶一定有一个同阶的后继状态，所以不同阶必胜。

以上讨论以分成两个子游戏为例，由于不同子游戏间一定是并列关系，所以 SG 函数也满足结合律和交换律。

综上，SG 函数的运算具有以下性质：

  • 满足交换律，结合律。

  • 单位元为零（必败状态）。

  • 同阶组合必败（逆元是自己） 。

通过瞪眼法 我们通过观察得到，SG 函数的性质实际上和异或运算是一样的。

因此得出结论：\(SG(x)=SG(x_1+x_2+ \dots +x_n)=SG(x_1)\ xor\ SG(x_2)\ \dots\ xor\ SG(x_n)\)

(感性证明：性质一样，理性证明如下)

SG 定理证明

设 $$z=x+y,\ z \to w$$

目标

  1. \(SG(x)\ xor\ SG(y)\ \notin\ SG(w)\)

  2. \(\forall\ W < SG(x)\ xor\ SG(y),\ W \in\ SG(w)\)

根据定义

\[SG(z)=mex \{ SG(w)|z \to w \} \]

因为每次只能进行一次操作，设

\[x \to u，y \to v \]

\[w=(u+y)\ \bigcup\ (x+v) \]

\[SG(z)=mex \{ \{SG(u+y)|x \to u \}\ \bigcup\ \{SG(v+x)|y \to v \} \} \]

既然 \(u,v\) 是 \(x,y\) 的任意 后继状态，不妨设

\[u=0,v=0 \]

根据 SG 函数定义，显然

\[SG(u+y)=SG(u)\ xor\ SG(y) \]

\[SG(v+x)=SG(v)\ xor\ SG(x) \]

则

\[SG(z)=mex \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \]

因为 \(u,v\) 分别是 \(x,y\) 的子状态，所以

\[SG(u) \ne SG(x)\ ,SG(v) \ne SG(y) \]

所以

\[\forall\ x \to u\ ,SG(x)\ xor\ SG(y) \ne SG(u)\ xor\ SG(y) \]

\[\forall\ y \to v\ ,SG(x)\ xor\ SG(y) \ne SG(v)\ xor\ SG(x) \]

\[SG(x)\ xor\ SG(y) \notin \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \tag{1} \]

设 $$X=SG(x)\ ,Y=SG(y)\ ,W<X\ xor\ Y$$

则

\[\forall\ W\ xor\ Y < X,\ \exists\ SG(u)=W\ xor\ Y < X \]

\[W=SG(u)\ xor\ Y \]

同理

\[W=SG(v)\ xor\ X \]

所以 $$\forall\ W<X\ xor\ Y,\ \exists\ SG(v)=W\ xor\ X\ or\ SG(u)=W\ xor\ Y$$

\[\forall\ W<X\ xor\ Y\ , W \in \{ \{SG(u)\ xor\ SG(y)|x \to u \}\ \bigcup\ \{SG(v)\ xor\ SG(x)|y \to v \} \} \tag{2} \]

因此根据 \(mex\) 定义，由 \((1),(2)\) 可得

\[SG(z)=SG(x)\ xor\ SG(y) \]

上述讨论了 \(u=0,v=0\) 的情况，由最终态向上归纳即可。

应用

既然我们上文已经证明了 SG 定理，那么就可以放心用啦！

对于任意一个游戏，我们都可以把它分解成子游戏，就像 \(z=x+y\) 一样。

如树上问题分成子树，石子堆分成单个石子堆。

然后明确最终的 \(0\) 状态，推出每个子游戏的 SG，求异或和。

好像大部分人都是打表找规律。。。 E&D

还有很多 dp，跟 SG 函数没什么关系，一般是计算最大得分判断胜负。通过计算双方得分差值来判断

好多题

参考资料

完结撒花！！！✿ヽ(°▽°)ノ✿

https://www.luogu.com.cn/article/shyocttb

https://blog.csdn.net/A_Comme_Amour/article/details/79347291

https://www.cnblogs.com/Ratio-Yinyue1007/p/18317441

  1. 本文中 \(x \to u\) 表示 \(u\) 是 \(x\) 的后继状态。 ↩︎