博弈论

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

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

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

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

当且仅当 $A_1\oplus A_2\oplus\cdots\oplus A_n\not=0$ 时，先手必胜（$\oplus$ 表示二进制异或）.

$A\oplus B$：将 $A$ 和 $B$ 的二进制位对齐，相等取 $0$，不相等取 $1$.

$$\begin{aligned} 1 \ 0 \ 0 \ 1 \ 0 \ 1 \ 0\\ \underline{\oplus \ 1 \ 1 \ 0 \ 1 \ 1 \ 0 \ 1}\\ 0 \ 1 \ 0 \ 0 \ 1 \ 1 \ 1 \end{aligned}$$

证明

引理 1

设 $A_1\oplus A_2\oplus\cdots\oplus A_n=k\not=0$.

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

由异或的定义得，至少存在一个 $i$，使 $A_i$ 的第 $\text{len}(k)$ 位为 $1$，这样才能保证 $k$ 的第 $\text{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’$，都有：

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

即任意一步操作都会导致异或和 $\not=0$.

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

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

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

$$\xymatrix { 异或和\not=0 }$$

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

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

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

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

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

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

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

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

设起点为 $s$，当且仅当 $SG(s)\not=0$ 时，先手必胜.

证明

• 当棋子无法移动时失败，此时没有后继状态，$SG(s)=\mex(\varnothing)=0$.

• 存在一步操作，使 $SG(s)\not=0\Longrightarrow SG(s)=0$.

• 任意一步操作，使 $SG(s)=0\Longrightarrow SG(s)\not=0$.

当 $SG(s)\not=0$ 时，先手可以通过类似于 NIM 游戏 的方法制胜.

当 $SG(s)=0$ 时，后手必胜.

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

证明

由 单图游戏 可知：

• $SG(s_i)=0$（无法移动每个棋子）时失败，此时异或和 $=0$.

• 存在一步操作，使异或和 $\not=0\Longrightarrow$ 异或和 $=0$.

• 任意一步操作，使异或和 $=0\Longrightarrow$ 异或和 $\not=0$.

当 $SG(s_1)\oplus SG(s_2)\oplus\cdots\oplus SG(s_n)\not=0$ 时，先手可以通过类似于 NIM 游戏 的方法制胜.