博弈论之 SG 函数

NIM 游戏

在许多地方曾经流行过这样一个小游戏: 摆出三堆硬币, 分别包含 3 枚、5 枚、7 枚。两人轮流行动, 每次可以任选一堆, 从中取走任意多枚硬币, 可把一堆取光, 但不能不取。取走最后一枚硬币者获得胜利。

这类游戏可以推广为更加一般的形式:

给定 $n$ 堆物品, 第 $i$ 堆物品有 $A_{i}$ 个。两名玩家轮流行动, 每次可以任选一堆, 取走任意多个物品, 可把一堆取光, 但不能不取。取走最后一件物品者获胜。两人都采取最优策略, 问先手能否必胜。

我们把这种游戏称为 NIM 博亦。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手, 第二个行动的称为后手。若在某一局面下无论采取何种行动, 都会输掉游戏, 则称该局面必败。所谓采取最优策略是指, 若在某一局面下存在某种行动, 使得行动后对手面临必败局面, 则优先采取该行动。同时, 这样的局面被称为必胜。我们讨论的博恋问题一般都只考虑理想情况, 即两人均无失误, 都采取最优策略行动时游戏的结果。NIM 博亦不存在平局, 只有先手必胜和先手必败两种情况。

定理： NIM 博亦先手必胜, 当且仅当 $A_{1}\; xor\; A_{2}\; xor \cdots xor \;A_{n} \neq 0$ 。

证明：

所有物品都被取光是一个必败局面 (对手取走最后一件物品, 已经获得胜利), 此时显然有 $A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_{n}=0$ 。

对于任意一个局面, 如果 $A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_{n}=x \neq 0$ , 设 $x$ 的二进制表示下最高位的 1 在第 $k$ 位, 那么至少存在一堆石子 $A_{i}$ , 它的第 $k$ 位是 1 。显然 $A_{i}\; xor\; x< A_{i}$ , 我们就从 $A_{i}$ 堆中取走若干石子, 使其变为 $A_{i}\; xor\; x$ , 就得到了一个各堆石子数异或起来等于 0 的局面。

$\begin{align*} A_{1} \;xor\; A_{2} \;xor \cdots xor\; (A_i \;xor\; x) \;xor \cdots xor\; A_{n}&= \\ A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_i \;xor \cdots xor\; A_{n} \;xor\; x &=\\ x \;xor \; x &=0 \end{align*}$

对于任意一个局面, 如果 $A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_{n}=0$ , 那么无论如何取石子, 得到的局面下各堆石子异或起来都不等于 0 。可用反证法证明, 假设 $A_{i}$ 被取成了 $A_{i}^{\prime}$ , 并且 $A_{1}\; xor\; A_{2}\; xor \cdots xor\; A_{i}^{\prime}\; xor \cdots xor \;A_{n}=0$ 。由异或运算的消去律得 $A_{i}^{\prime}=A_{i}$ , 与 “不能不取石子” 的规则矛盾。

综上所述, 再由数学归纳法可知, $A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_{n} \neq 0$ 为必胜局面, 一定存在一种行动让对手面临 “各堆石子异或起来等于 0 ”。 $A_{1} \;xor\; A_{2} \;xor \cdots xor\; A_{n}=0$ 为必败局面, 无论如何行动, 都会让对手面临一个 “各堆石子异或起来不等于 0 ” 的必胜局面。

证毕。

公平组合游戏 ICG

若一个游戏满足:

由两名玩家交替行动。
在游戏进程的任意时刻, 可以执行的合法行动与轮到哪名玩家无关。
不能行动的玩家判负。

则称该游戏为一个公平组合游戏。

NIM 博亦属于公平组合游戏, 但常见的棋类游戏, 比如围棋, 就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子, 胜负判定也比较复杂, 不满足条件 2 和条件 3。

有向图游戏

给定一个有向无环图, 图中有一个唯一的起点, 在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动, 每次可以移动一步, 无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是, 把每个局面看成图中的一个节点, 并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

定理 1：没有后继节点的局面是必败局面。
定理 2：一个局面是必胜局面当且仅当存在至少一个必败局面为它的后继节点。
定理 3：一个局面是必败局面当且仅当它的所有后继节点均为必胜局面。

Mex 运算

设 $S$ 表示一个非负整数集合。定义 $\operatorname{mex}(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算, 即：

$\operatorname{mex}(S)=\min _{x \in N, x \notin S}\{x\}$

SG 函数

在有向图游戏中, 对于每个节点 $x$ , 设从 $x$ 出发共有 $k$ 条有向边, 分别到达节点 $y_{1}, y_{2}, \cdots, y_{k}$ , 定义 $\operatorname{SG}(x)$ 为 $x$ 的后继节点 $y_{1}, y_{2}, \cdots, y_{k}$ 的 SG 函数值构成的集合再执行 mex 运算的结果, 即:

$\mathrm{SG}(x)=\operatorname{mex}\left(\left\{\mathrm{SG}\left(y_{1}\right), \mathrm{SG}\left(y_{2}\right), \cdots, \mathrm{SG}\left(y_{k}\right)\right\}\right)$

特别地, 整个有向图游戏 $G$ 的 SG 函数值被定义为有向图游戏起点 $s$ 的 SG 函数值, 即 $\mathrm{SG}(G)=\mathrm{SG}(s)$ 。

有向图游戏的和

设 $G_{1}, G_{2}, \cdots, G_{m}$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$ , 它的行动规则是任选某个有向图游戏 $G_{i}$ , 并在 $G_{i}$ 上行动一步。 $G$ 被称为有向图游戏 $G_{1}, G_{2}, \cdots, G_{m}$ 的和。有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和, 即:

$\operatorname{SG}(G)=\operatorname{SG}\left(G_{1}\right) \;xor\; SG \left(G_{2}\right) \;xor \cdots xor\; SG \left(G_{m}\right)$

SG 定理：

有向图游戏的某个局面必胜, 当且仅当该局面对应节点的 SG 函数值大于 0 。
有向图游戏的某个局面必败, 当且仅当该局面对应节点的 SG 函数值等于 0 。

我们不再详细证明该定理。读者可以这样理解:

在一个没有出边的节点上, 棋子不能移动, 它的 SG 值为 0, 对应必败局面。

若一个节点的某个后继节点 SG 值为 0, 在 mex 运算后, 该节点的 SG 值大于 0 。这等价于, 若一个局面的后继局面中存在必败局面, 则当前局面为必胜局面。

若一个节点的后继节点 SG 值均不为 0 , 在 mex 运算后, 该节点的 SG 值为 0 。这等价于, 若一个局面的后继局面全部为必胜局面, 则当前局面为必败局面。

对于若干个有向图游戏的和, 其证明方法与 $\mathrm{NIM}$ 博亦类似。

SG 定理的应用

SG 定理适用于 任何公平的两人游戏, 它常被用于决定游戏的输赢结果。

计算给定状态的 SG 值的步骤一般包括：

获取从此状态所有可能的转换；
每个转换都可以导致 一系列独立的博弈（退化情况下只有一个）。计算每个独立博弈的 SG 值并对它们进行 异或求和。
在为每个转换计算了 SG 值之后，状态的值是这些数字的 mex 值。
如果该值为零，则当前状态为输，否则为赢。

219. 剪纸游戏

给定一张 $N \times M$ 的矩形网格纸，两名玩家轮流行动。

在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。

首先剪出 $1 \times 1$ 的格纸的玩家获胜。

两名玩家都采取最优策略行动，求先手是否能获胜。

提示：开始时只有一张纸可以进行裁剪，随着游戏进行，纸张被裁剪成 $2,3,…$ 更多张，可选择进行裁剪的纸张就会越来越多。

输入格式

输入包含多组测试数据，每组数据占一行。

每组数据包括两个整数 $N$ 和 $M$ ，表示初始网格纸的尺寸。

输出格式

每组测试数据输出一个结果，结果占一行。

如果先手方必胜，则输出 WIN；

如果先手方必输，则输出 LOSE。

数据范围

$2 \le N,M \le 200$

输入样例：

1
2
3

2 2
3 2
4 2

输出样例：

1
2
3

LOSE
LOSE
WIN

算法分析

Solution

294. 翻转游戏 II

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将连续的两个 "++" 反转成 "--" 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。默认每个人都会采取最优策略。

请你写出一个函数来判定起始玩家 是否存在必胜的方案 ：如果存在，返回 true ；否则，返回 false 。

示例 1：

1 2	"++" "+--+" 从而得胜。

示例 2：

1 2	输入：currentState = "+" 输出：false

提示：

1 <= currentState.length <= 60
currentState[i] 不是 '+' 就是 '-'

进阶： 请推导你算法的时间复杂度。

Solution

class Solution {
public:
    unordered_map<string, int> SG;

    bool canWin(string currentState) {
        dfs(currentState);
        if (SG[currentState]) return true;
        else return false;
    }

    int mex(vector<int> &sg) {
        unordered_set<int> hs;
        for (auto x : sg) hs.insert(x);
        for (int i = 0; true; ++i) {
            if (hs.count(i) == 0) return i;
        }
        return -1;
    }

    void dfs(string &s) {
        int n = s.size();
        bool flag = false;
        vector<int> sg;
        for (int i = 0; i < n; ++i) {
            if (i + 1 < n && s[i] == '+' && s[i + 1] == '+') {
                flag = true;
                s[i] = s[i + 1] = '-';
                if (SG.count(s) == 0) dfs(s);
                sg.push_back(SG[s]);
                s[i] = s[i + 1] = '+';
            }
        }
        if (flag == false) SG[s] = 0;
        else SG[s] = mex(sg);
    }
};