$$$$

简介

博弈论研究在一局博弈中如何最优化玩家的策略。

公平组合游戏（ICG）

• 两名玩家轮流行动，且行动规则相同；
• 最终不能行动的玩家判负。

NIM 游戏

简介

有 $n$ 堆石子，第 $i$ 堆石子数为 $A_i$。两名玩家轮流取走任意一堆的任意个石子，但不能不取。取走最后一个石子的玩家胜。

NIM 游戏属于 公平组合游戏，且不存在平局，只有「先手必胜」和「后手必胜」两种情况。

策略

当且仅当 $A_1\oplus A_2\oplus \cdots \oplus A_n\ne 0$ 时，先手必胜。

$A\oplus B$：表示二进制异或：将 $A$ 和 $B$ 的二进制位对齐，相等取 $0$，不相等取 $1$。

$$\begin{array}{r}1001010\\ \underset{―}{\oplus 1101101}\\ 0100111\end{array}$$

证明

引理 1

设 $A_1\oplus A_2\oplus \cdots \oplus A_n=k\ne 0$。

设 $k$ 在二进制下有 $\mathrm{len}(k)$ 位。

由异或的定义得，至少存在一个 $i$，使 $A_i$ 的第 $\mathrm{len}(k)$ 位为 $1$，这样才能保证 $k$ 的第 $\mathrm{len}(k)$ 位也为 $1$。在此条件下，显然有 $A_i>A_i\oplus k$。

于是可以取第 $i$ 堆石子，使其剩下 $A_i\oplus k$ 个。取完石子后有

$$(A_1\oplus \cdots \oplus A_{i-1})\oplus (A_i\oplus k)\oplus (A_{i+1}\oplus \cdots \oplus A_n)=k\oplus k=0$$

引理 2

设 $A_1\oplus A_2\oplus \cdots \oplus A_n=0$。此时更改任意一个 $A_i$ 为 $A_i^{\prime }$，都有：

$$(A_1\oplus \cdots \oplus A_{i-1})\oplus (A_i^{\prime })\oplus (A_{i+1}\oplus \cdots \oplus A_n)=0\oplus A_i\oplus A_i^{\prime }\ne 0$$

即任意一步操作都会导致异或和 $\ne 0$。

结合引理 1，引理 2 可得：

• 存在一步操作，使异或和 $\ne 0⟹$ 异或和 $=0$；
• 任意一步操作，使异或和 $=0⟹$ 异或和 $\ne 0$；
• 石子被取光时失败（对手取走最后一个石子，获胜），此时异或和为 $0$。

当 $A_1\oplus A_2\oplus \cdots \oplus A_n\ne 0$ 时，先手可以使博弈进入一种循环：

轮到后手时，异或和必为 $0$，即失败的局面只可能轮到后手。先手必胜。

当 $A_1\oplus A_2\oplus \cdots \oplus A_n=0$ 时，后手可以同样的方法制胜。此时先手必败。

有向图游戏

简介

在一个有向无环图中，只有一个起点，上面有一枚棋子。两名玩家轮轮流沿有向边推动棋子，无法移动者判负。

任何公平组合游戏都可以转换为有向图游戏：每个节点表示一个状态，并且向后继状态连有向边。

策略

Mex 运算

设 $S$ 为非负整数集合。$\mathrm{mex}(S)$ 为不属于 $S$ 的最小非负整数。

$$\mathrm{mex}(S)=min\{x\mid x\in N,x\notin S\}$$

SG 函数

状态 $x$ 有 $k$ 个后继状态 $y_1,y_2,\cdots ,y_k$，定义 $\mathrm{SG}$ 函数：

$$\mathrm{SG}(x)=\mathrm{mex}(\{\mathrm{SG}(y_1),\mathrm{SG}(y_2),\cdots ,\mathrm{SG}(y_k)\})$$

单图游戏

设起点为 $s$，当且仅当 $\mathrm{SG}(s)\ne 0$ 时，先手必胜。

证明

• 当棋子无法移动时失败，此时没有后继状态，$\mathrm{SG}(s)=\mathrm{mex}(\varnothing )=0$；
• 存在一步操作，使 $\mathrm{SG}(s)\ne 0⟹\mathrm{SG}(s)=0$；
• 任意一步操作，使 $\mathrm{SG}(s)=0⟹\mathrm{SG}(s)\ne 0$。

当 $\mathrm{SG}(s)\ne 0$ 时，先手可以通过类似于 NIM 游戏 的方法制胜。

当 $\mathrm{SG}(s)=0$ 时，后手必胜。

组合图游戏

对于 $n$ 个有向图游戏组合成的游戏，起点分别为 $s_1,s_2,\cdots ,s_n$。当且仅当 $\mathrm{SG}(s_1)\oplus \mathrm{SG}(s_2)\oplus \cdots \oplus \mathrm{SG}(s_n)\ne 0$ 时，先手必胜（$\oplus$ 表示异或）。

证明

由 单图游戏 可知：

• $\mathrm{SG}(s_i)=0$（无法移动每个棋子）时失败，此时异或和 $=0$；
• 存在一步操作，使异或和 $\ne 0⟹$ 异或和 $=0$；
• 任意一步操作，使异或和 $=0⟹$ 异或和 $\ne 0$。

当 $\mathrm{SG}(s_1)\oplus \mathrm{SG}(s_2)\oplus \cdots \oplus \mathrm{SG}(s_n)\ne 0$ 时，先手可以通过类似于 NIM 游戏 的方法制胜。