博弈论

简介 #

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

公平组合游戏 ICG #

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

NIM 游戏 #

简介 #

有 $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$ 时,后手可以同样的方法制胜. 此时先手必败.

有向图游戏 #

简介 #

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

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

策略 #

Mex 运算 #

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

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

SG 函数 #

状态 $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 游戏 的方法制胜.