博弈论初步：图上的游戏, Nim 游戏和 SG 定理

---

さぁ、ゲームをはじめよう
来吧，游戏开始了。

- NO GAME NO LIFE

综述

在 OI/XCPC 的范畴中, 博弈论的题目往往是在研究公平组合游戏, 似乎称为组合博弈论会好一点, 是寻常意义下的博弈论的一部分.

本文由有向图游戏开始, 到 Nim 游戏和 SG 定理结束, 介绍了一些简单的博弈论相关的内容.

有向图上的游戏

给定一张任意的有向图 $G$, 允许 $G$ 中存在环. 初始状态下, 某个结点 $s$ 上存在一枚棋子. 记棋子当前位于的结点为 $u$, 每一次操作可以将棋子沿着以 $u$ 为起点, $v$ 为终点的有向边移动到 $v$. 现在两名玩家轮流操作, 规定无法进行操作的玩家胜利或者失败. 此外, 视能无限进行的情况为平局. 现在已知 $G$ 与 $s$, 两名玩家都使用最优策略, 判断先手是否必胜, 必败, 或者平局.

一个直观的结论为, 如果 $G$ 中不存在环, 即 $G$ 为有向无环图 (Directed Acyclic Graph, DAG), 那么就不存在平局的情况. 但如果 $G$ 中存在环, 却有可能不是平局. 感性理解就是当一名玩家选择让棋子在环上转圈时, 另一位玩家可能有更好的选择而并不需要陪着他转圈…

既然双方都采用最优策略, 后手可以看作是初始状态不同的先手. 因此只需关注结点是否为先手必胜或者必败就好了. 对于一个结点 $u$, 如果以 $u$ 为棋子的起点, 先手无论如何操作总会失败, 那么称 $u$ 为必败结点. 相应地有必胜结点和平局结点. 同时称一个结点能够到达的结点为该结点的后继结点. 那么有

• 不存在后继的结点是必胜结点或者必败结点, 取决于规则的限制.
• 一个结点是必败结点, 当且仅当所有后继结点都是必胜结点.
• 一个结点是必胜结点, 当且仅当存在一个后继结点是必败结点.
• 如果一个结点既不是必败结点又不是必胜结点, 则为平局结点.

反转 $G$ 中每条边的起点和终点, 从必败结点或者必胜结点开始 DFS, 根据上述条件依次判定就好了. 记 $G$ 的边数为 $m$, 则可以在 $O(m)$ 的时间复杂度内完成对所有点的判断.

Nim 游戏

给定 $n$ 堆石子, 石子数分别为 $a_1, a_2, \ldots, a_n$. 每一次操作可以选择唯一一堆, 取出正整数个石子. 现在两名玩家轮流操作, 规定无法进行操作的玩家失败, 也就是取走最后一枚石子的玩家胜利. 显然此时不存在平局的情况. 判断先手必胜或者必败.

将石子序列看作一个状态, 每次操作看作一条有向边, 则得到一张 DAG. 当前状态的变化可以视作棋子在 DAG 上的移动, 于是可以利用有向图游戏来解决 Nim 游戏. 但直接建图然后 DFS 的时间复杂度过大, 并不可取.

事实上存在直接的结论. 记 $\oplus$ 表示异或, 当且仅当 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$ 时先手必败, 其余情况先手必胜. 借助于有向图游戏可以证明这个结论.

首先, 最终状态 $(0, 0, \ldots, 0)$ 满足所有数异或和为 $0$ 且为先手必败态.

其次, 对于一个不全为 $0$ 的状态 $(a_1, a_2, \ldots, a_n)$, 记 $a_1 \oplus a_2 \oplus \cdots \oplus a_n = s$, 一次操作之后异或和更改为 $s’$. 只需证明 $s=0$ 状态的后继状态中 $s’$ 均不为 $0$, 以及 $s\neq 0$ 状态的后继状态中存在 $s’=0$ 的状态.

对于前者, 任选一个位置 $i$ 并将 $a_i$ 变为 $a_i’$. 由于 $a_i > a_i’$, 有

$$s'=s\oplus a_i\oplus a_i' = a_i \oplus a_i'\neq 0$$

对于后者, 选择满足 $a_i > a_i\oplus s$ 的位置 $i$ 并将 $a_i$ 变为 $a_i\oplus s$ 即可, 此时有 $s’=0$. 根据异或的性质可以得出满足该条件的 $a_i$ 一定存在.

允许添加石子的 Nim 游戏

在 Nim 游戏的基础上添加一种操作: 选择唯一一堆石子, 加入正整数个石子. 每回合可以选择添加或去除操作中的一种, 同时不允许游戏无限地进行下去.

容易发现这个操作在不允许游戏无限进行的限制下是没有意义的. 因为接下来的玩家可以通过去除相同位置的等量石子来抵消掉添加石子的影响. 同时, 考虑到双方都采用最优策略, 添加石子不会影响状态的输赢.

所以, 对于允许添加石子的 Nim 游戏而言, 每个状态的后继状态中一定包含所有的由去除操作得到的状态, 而就由添加操作得到的状态而言, 其存在与否并不对当前状态的输赢产生影响, 可有可无. 后续在 SG 定理的证明中这一点会有体现.

SG 定理

公平组合游戏 (Impartial Game), 也有人称作无偏博弈, 指满足以下条件的游戏.

• 游戏存在两名玩家, 两者轮流操作直到游戏到达最终状态.
• 在无法进行操作时决定游戏的胜负.
• 两名玩家操作数均有限, 游戏将在有限次操作后以非平局结束.
• 对于一个状态, 玩家双方能够做出的决策只和状态有关而同游戏者无关. 即同一个状态下两者可以做的操作相同.
• 游戏中的操作不依赖于概率, 操作的结果都是确定的.

显然 Nim 游戏就是一个公平组合游戏. 事实上, 通过 SG 定理 (Sprague-Grundy Theorem) 可以将任何公平组合游戏转化为 Nim 游戏, 这也就是 SG 定理的强大之处.

对于集合 $S$, 记 $\operatorname{mex}(S)$ 表示不在 $S$ 中的最小非负整数.

对于一个公平组合游戏中的状态 $x$, 设 $x$ 后继状态有 $y_1, y_2, \ldots, y_k$. 定义 $x$ 的 SG 函数 $\operatorname{SG}(x)$ 为

$$\operatorname{SG}(x) = \operatorname{mex}(\operatorname{SG}(y_1),\ \operatorname{SG}(y_2),\ \ldots,\ \operatorname{SG}(y_k))$$

特别地, 如果 $x$ 不存在后继状态, 则 $x$ 为先手必败态, 有 $\operatorname{SG}(x) = 0$.

其中 $\operatorname{SG}(x)$ 也被称为 Nim 数, Grundy 值等. 状态 $x$ 可以视为包含个数为 $\operatorname{SG}(x)$ 的一堆石子的 Nim 游戏. 接下来将证明这一点

可以用归纳法来证明.

对于不存在后继的状态 $x$, $\operatorname{SG}(x) = \operatorname{mex}(\varnothing) = 0$, 同时初始状态为 $0$ 的 Nim 游戏也是先手必败.

对于存在后继的状态 $x$, 假设定理对 $x$ 的后继 $y_1, y_2, \ldots, y_k$ 均成立, 现在需要证明定理对 $x$ 也成立.

记 $p = \operatorname{mex}(\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k))$, 那么在后继状态中, 对于所有小于 $p$ 的状态, 均可以由 $p$ 通过去除石子的操作得到; 对于存在的大于 $p$ 的状态, 可以由 $p$ 通过添加石子的操作得到. 因此 $\operatorname{SG}(x) = p$.

根据 SG 定理, 对于 $n$ 个同时进行且相互独立的公平组合游戏 $x_1, x_2, \ldots, x_n$, 每回合选择一个游戏进行一次操作, 那么当且仅当 $\operatorname{SG}(x_1) \oplus \operatorname{SG}(x_2) \oplus \cdots \oplus \operatorname{SG}(x_n) = 0$ 时先手必败, 否则先手必胜.

应用

Crosses-crosses

直接从 cp-algorithms.com 搬来的例子.

题目链接

• https://cp-algorithms.com/game_theory/sprague-grundy-nim.html#crosses-crosses

题目大意

给定一个 $1\times n$ 的网格图, 每次操作可以选择一个格子画 $\times$, 要求不能有两个 $\times$ 相邻. 已知 $n$, 问先手必败还是必胜.

解题思路

状态 $n$ 表示当前在 $1\times n$ 的网格上操作. 分别讨论 $\times$ 画在网格端点和中间的情况可以得到

$$\operatorname{SG}(n) = \operatorname{mex}\left(\{ \operatorname{SG}(n-2)\} \cup \{ \operatorname{SG}(i-2)\oplus \operatorname{SG}(n-i-1) | 2\le i\le n-1\}\right)$$

直接计算的时间复杂度为 $O(n^2)$. 此外, $\operatorname{SG}(n)$ 从某一位开始以一定的长度循环, 开始位置和循环节都不大, 实际上可以做到 $O(1)$.

CF1312F Attack on Red Kingdom

题目链接

• https://codeforces.com/problemset/problem/1312/F

解题思路

问题的关键在于判断先手操作后, 后手再进行操作时的局面是否是先手必败. 显然要用到 SG 函数.

首先城堡之间互相独立, 分别考虑每个城堡. 对于每个状态, 除去守军数量 $a_i$ 外, 额外记录一个标记 $c$ 表示当前城堡上一次所受攻击的种类. 这样就能递推计算出 $\operatorname{SG}(a_i, c)$ 的值.

同时, 考虑到 $1\le x,y,z \le 5$, $\operatorname{SG}(a_i, c)$ 从某个位置之后开始循环, 循环节的一个很松的上界为 $4^{15}$. 但实际上循环节并不大, 通过暴力可以得知循环节最大为 $36$. 每次暴力找到循环开始位置和循环节就好了.

参考资料

• https://cp-algorithms.com/game_theory/games_on_graphs.html
• https://cp-algorithms.com/game_theory/sprague-grundy-nim.html
• https://oi-wiki.org/math/game-theory/impartial-game/
• https://en.wikipedia.org/wiki/Impartial_game

---