SG 函数之取石子博弈

在2002年张一飞写过一篇论文 《由感性认识到理性认识-透析一类博弈游戏的解答过程》 从此开启了这类博弈问题的大门,留下学习笔记。

取石子游戏

$A,B$ 两人面对若干堆石子,按照如下规则取石子

  1. 每步至少取一枚石子
  2. 每步只能在某一堆取走部分或者全部石子
  3. 谁无法按照规则取石子,谁就是输家

首先抛开问题,我们先从一般的入手。

我们可以用一个 $n$ 元组 $(a_1,a_2,\cdots,a_n)$ 表示一个局面 $S$。显然改变 $n$ 元组的顺序仍然是一个局面。

一个局面 $n$ 元局面$(a_1,a_2,\cdots,a_n)$和一个 $m$ 元局面 $(b_1,b_2,\cdots,b_m)$ 之和显然就是一个 $m + n$ 元局面 $(a_1,a_2,\cdots,a_n,b_1,b_2,\cdots,b_m)$。类似的一个局面也可以有多种分解。

对于局面 $S$,若先行者有必胜策略,则称 “$S$ 胜”;
对于局面 $S$,若后行者有必胜策略,则称 “$S$ 负”。

如果局面 $S$ 胜,则必然存在取子方式 $S \to T$,且 $T$ 负;
如果局面 $S$ 负,则对任意取子方式 $S \to T$,有 $T$ 胜。

局面分解理论,若 $S = A + B$ 则下面结论显然

  1. 若 $A,B$ 一胜一负,则 $S$ 胜
  2. 若 $A,B$ 全为负,则 $S$ 负
  3. 若 $A,B$ 全为胜,则 $S$ 无法判断
  4. 若 $A=B$,则 $S$ 负
  5. 空局面是负局面

因此根据上面的分解理论,可以将一个局面进行化简。例如 $(2,2,2,7,9,9)$ 可以化简成 $(2,7)$

而局面分解的关系,很容易让人联想到整数的位运算-异或。

对于上面取石子问题,每一个局面都可以分解成只有一堆石子的局面。
对一个局面,定义一个函数 $f$,然后把它们异或是不是,然后判断是非为0,作为是否胜的充要条件.这样做是否可行呢?先对原始例子进行实验。

函数 $f$:若局面 $S$ 只有一个石子,设 $S={a}$,则定义 $f(a) = a$。
设局面 $S = (a_1,a_2,\cdots,a_n)=(a_1)+(a_2)+\cdots (a_n)$,则 $f(S) = f(a_1) \oplus f(a_2) \oplus \cdots \oplus f(a_n)$
对于一个局面 $S$,若 $f(S) = 0$,则 $S$ 负,否则,$S$ 胜。

下面证明上面的结论。
引理:$a_1 \oplus a_2 \oplus a_n = p \neq 0$,则必存在 $1 \leq k \leq n$,使得 $a_k \oplus p < a_k$。这是因为我们看 $p$ 的最高位即知存在 $a_k$ 其最高位也为 $1$, 那么与 $p$ 异或后,这一位就从 $1$ 变为 $0$,证毕。

若 $f(S) = 0$,则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$。
若 $f(S) \neq 0$,则先行者存在一种取法 $S \to T$, 使得 $f(T) = 0$。这是因为由引理 $a_1 \oplus a_2 \oplus a_n = p \neq 0$,存在 $1 \leq k \leq n$,使得 $x = a_k \oplus p < a_k$。那么我们在第 $k$ 堆取走 $a_k - x$ 个石子,那么 $a_1 \oplus a_2 \oplus a_n \oplus p = 0$,证毕。

这说明了上述想法的可行性。下面把这种思想推广成一般的 SG 函数的情形

SG 函数

当对石子的取法进行限制时,例如每次最多能去 $m$ 个,或每次最少取 $l$ 个等,此时再令 $f(x) = x$ 就不合适了。那么应该选择怎样的 $f$ 呢。显然 $f$ 必须满足:

  1. 若 $f(S) = 0$, 则无论先行者如何取子 $S \to T$,都有 $f(T) \neq 0$
  2. 若 $f(S) \neq 0$, 则先行者存在一种取子 $S \to T$,使得 $f(T) = 0$。

我们用 $(S) = \lbrace S_1,S_2, \cdots S_k \rbrace$ 表示 $S$ 的下一个可能的局面,定义 $g(S) = \lbrace f(S_1),f(S_2), \cdots f(S_k) \rbrace $

由 $f$ 满足条件1知

由条件2知

因此我们定义函数 $f(S)$ 为 $f(S) \doteq \min g(S)$

写的这么乱,估计只有自己看的懂 0.0

欧尼酱,人家想喝可乐!