EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

博弈论和 SG 函数

$$ \def\xor{\text{ xor }} \def\mex{\mathrm{mex}} \def\SG{\mathrm{SG}} $$

博弈论题目的特点:

  • 没有什么套路;
  • 需要具体分析博弈性质;
  • 经常需要打表猜结论,很多结论和二进制有关系。

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

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

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

我们把这种游戏称为 NIM 博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手,第二个行动的称为后手

若在某一局面下无论采取何种行动,都会输掉游戏,则称该局面必败。所谓采取最优策略是指,若在某一局面下存在某种行动,使得行动后对手面临必败局面,则优先采取该行动。同时,这样的局面被称为必胜

我们讨论的博弈问题一般都只考虑理想情况,即两人均无失误,都采取最优策略行动时游戏的结果。NIM 博弈不存在平局,只有先手必胜和先手必败两种情况。

NIM 博弈定理

NIM 博弈先手必胜,当且仅当

$$ A_1 \xor , A_2 \xor , \cdots \xor , A_n \neq 0 $$

证明:

  1. 必败局面的性质:所有物品都被取光是一个必败局面(对手取走最后一件物品,已经获得胜利),此时显然有

    $$ A_1 \xor , A_2 \xor , \cdots \xor , A_n = 0 $$

  2. 非零异或和的策略构造:对于任意一个局面,如果 $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$ 的局面。

  3. 零异或和的不变性: 对于任意一个局面,如果 $A_1 \xor , A_2 \xor , \cdots \xor , A_n = 0$,那么无论如何取石子,得到的局面下各堆石子异或起来都不等于 $0$。

综上所述,再由数学归纳法可知,$A_1 \xor , A_2 \xor , \cdots \xor , A_n \neq 0$ 为必胜局面,一定存在必胜策略。

公平组合游戏

一个游戏若满足以下三个条件,则称为公平组合游戏(ICG):

  1. 交替行动:游戏由两名玩家轮流进行操作。
  2. 行动对等性:在游戏的任意时刻,当前玩家可执行的所有合法行动,与轮到哪一方行动无关(即双方可选择的操作集合完全相同)。
  3. 失败判定:当某玩家无法执行任何合法行动时,该玩家判负,游戏结束。

典型例子分析

  1. NIM 博弈属于 ICG:符合 ICG 的所有条件:两名玩家轮流从若干堆石子中取走任意数量,行动选择仅依赖于当前石子堆状态,与玩家身份无关;无法取石子者判负。

  2. 围棋不属于 ICG

  • 不满足条件 2:双方只能分别落黑子或白子,行动选择受限于玩家身份(黑方/白方)。
  • 不满足条件 3:胜负判定依赖复杂的规则(如气、围地、劫争等),而非简单的“无法行动则判负”。

策梅洛定理(Zermelo's Theorem)

在 ICG 中,一个局面是必胜的,当且仅当:

  • 可以一步之内赢得游戏;
  • 或其后继局面中至少有一个是必败的;

一个局面是必败的,当且仅当:

  • 无论如何决策,都将马上输掉游戏;
  • 或其后继局面中都是必胜的。

有向图游戏

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

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

mex 运算

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

$$ \mex(S) = \min_{x \in \mathbb{N}, x \notin S} \set{x} $$

例如: $$ \mex(\set{0,1,2,4}) = 3\ \mex(\set{2,3,5}) = 0 \ \mex(\emptyset) = 0 $$

SG 函数

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

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

NIM 游戏可以看成 SG 函数的直接应用,单堆石子的 SG 函数为 $\SG(n) = n$。

SG 定理

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

该定理可以用数学归纳法轻松证明,本质上是策梅洛定理的代数形式:

  • 在一个没有出边的节点上,棋子不能移动,它的 SG 值为 0,对应必败局面。
  • 若一个节点的某个后继节点 SG 值为 0,在 mex 运算后,该节点的 SG 值大于 0。这等价于,若一个局面的后继局面中存在必败局面,则当前局面为必胜局面。
  • 若一个节点的后继节点 SG 值均不为 0,在 mex 运算后,该节点的 SG 值为 0。这等价于,若一个局面的后继局面全部为必胜局面,则当前局面为必败局面。

有向图游戏的和

设 $G_1, G_2, \ldots, G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$,它的行动规则是任选某个有向图游戏 $G_i$,并在 $G_i$ 上行动一步。$G$ 被称为有向图游戏 $G_1, G_2, \ldots, G_m$ 的和。

有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和,即:

$$ \SG(G) = \SG(G_1) \xor \SG(G_2) \xor \cdots \xor \SG(G_m) $$

对于若干个有向图游戏的和,其证明方法与 NIM 博弈类似。