SG 函数 & 博弈论

Link_Cut_Y · 2024-07-30 15:23:56 · 个人记录

一直没学结果今天被创了。

一些定义：

博弈状态

• 定义 P-position 为“必胜态”，即 positive-position，简称 P。某个玩家到达该状态则一定胜。
• 定义 N-position 为“必败态”，即 negative-position，简称 N。某个玩家到达该状态则一定败。
• 定义某个状态的”后继状态”当前玩家从当前状态进行一次操作能够到达的状态集合。
• 一个状态为 P，当且仅当其后继状态存在至少一个必败状态。
• 一个状态为 N，当且仅当其后继状态全部都是必胜状态。

博弈图

• 将每个状态向其后继状态连边，每条边表示转移，形成一个有向无环图称为博弈图。

SG 函数

• 定义有向图游戏上的函数 \mathrm{SG}(x)。对于 x 的后继状态 S，有 \mathrm{SG}(x) = \mathrm{mex} \{y \in S :\mathrm{SG(y)}\}。对于必败态定义其 \mathrm{SG} 为 0。

• 在有向图游戏中，\mathrm{SG} 是容易递推求出的。

SG 定理

• 对于有 n 个起点的有向图游戏，设他们的起点分别为 s_1, s_2 \cdots s_n，则有：当且仅当 \oplus_{i \le n} \mathrm{SG}(s_i) \ne 0，该游戏先手必胜。
• 不会定理的证明/ll

尼姆游戏（Nim 游戏）

• 又称取石子游戏。有 n 堆石子，每一堆有 a_i 个。两个人以最优策略轮流取，不能操作的失败。求先手必胜还是必败。
• 我们将 Nim 游戏转化称有向图游戏。发现每一堆是相互独立的。将每一堆建成有向无环图，节点 x 连向 y 当且仅当 y < x。不难发现 \mathrm{SG}(x) = x。根据 SG 定理，先手必胜当且仅当 \oplus_{i \le n} a_i \ne 0。

SG 函数的应用

• 例 1：UVA1482 Playing With Stones：仍然是取石子游戏，但是每次取的个数有限制，从每次随便取，变成每次取不超过每堆的一半。

  我们通过打表观察 \mathrm{SG} 函数，可以发现一些规律：

  • 若 n \bmod 2 = 0，则 \mathrm{SG}(n) = n / 2。
  • 若 n \bmod 2 = 1，则 \mathrm{SG}(n) = (n - 1) / 4。
  • 若 n \bmod 2 = 1，则 \mathrm{SG}(n) = \mathrm{SG}((n - 1) / 2)。

将每一堆的 SG 异或起来。复杂度 O(n \log V)。

• 例 2：台阶-Nim 游戏：还是取石子，但是石子放在台阶上，每次可以从上面的台阶上拿下来若干个放到下面的台阶上去。放到地上的不能再动。求先手必胜还是必败。

  可以将该问题等价为奇数位置的石子组成的尼姆游戏。我们考虑，设该游戏的 SG 值为奇数位置的石子个数的亦或和。如果先手下，先手一定可以移动石子使得 SG 变为 0。否则，后手无论怎么移动，先手可以将他移动个数相同多的石子移动到下一级，让 \mathrm{SG} = 0 的状态转移给后手。