这篇文章偏结论性,几乎没有什么证明。

一些定义

公平组合游戏

信息完全公开、双方交替行动、同一局面双方的决策集合相同、且一定会在有限步内结束的游戏。

N 态与 P 态

N 态:先手必胜的状态;P 态:先手必败的状态。

一个状态为 P 态当且仅当其所有出边都为 N 态;一个状态为 N 态当且仅当其出边中有一个为 P 态。从而 P 态不可能转移到 P 态。

游戏的和

设有两个游戏 $A,B$,每次双方选一个游戏移动一步,这样子得到的新游戏称作 $A,B$ 的和,记做 $A+B$。

SG 函数

一个局面的 SG 函数值定义为

$$ SG(x)=\begin{cases}0,&E_x=\varnothing\\\operatorname{mex}_{v\in E_x}(SG(v)),&\mathrm{otherwise}\end{cases} $$

其中 $E_x$ 指 $x$ 转移得到的状态集合,$\operatorname{mex}(S)$ 指最小的未在 $S$ 中的自然数。

定理 1:$SG(x)=0$ 当且仅当 $x$ 是 P 态。

定理 2:$SG(A+B)=SG(A)\oplus SG(B)$,这里的 $\oplus$ 表示按位异或。

一些常见的游戏

Anti-SG 游戏

一类不可操作者胜利的游戏。

对于该规则下的取石子游戏,先手必胜当且仅当所有堆中石子数都小于等于 $1$ 且异或和为 $0$,或者存在一个堆中石子数大于 $1$ 且异或和不为 $0$。

当我们尝试将其扩展到一般的 Anti-SG 游戏时,会出现问题,因为处在一个 $SG(x)=0$ 的状态时可能有出边,此时无法直接胜利。

所以 Anti-SG 游戏中先手必胜当且仅当

  • 所有局面中 SG 函数值都小于等于 $1$ 且异或和为 $0$,或者存在一个局面 SG 函数值大于 $1$ 且异或和不为 $0$。
  • 当 $SG(x)=0$ 时,游戏可以立刻结束,或者存在一条出边使得到达的边的 SG 函数值为 $1$。

Multi-SG 游戏

一类一个单一游戏的后继可能为多个游戏的游戏。

仍然可以使用 SG 函数,将后继多个游戏的 SG 函数值异或和作为后继状态的 SG 函数值即可。

Every-SG 游戏

一类对于任意没有结束的游戏,操作者都必须进行一步操作的问题。

每个游戏先手必胜还是先手必败是已经确定的,唯一有影响的就是时间。求出胜利的最早时间和失败的最晚时间,进行比较即可。

一些经典的博弈问题

Nim 博弈

有 $n$ 堆石子,双方轮流取石子,每次选定一堆并从中取出任意多的石子(不能不取),不能操作者输。

$SG(x)=x$。

Bash 博弈

有 $n$ 堆石子,双方轮流取石子,每次选定一堆并从中取出至少 $1$ 个、至多 $m$ 个石子,不能操作者输。

$SG(x)=x\bmod m+1$。

Wythoff 博弈

有两堆石子,双方轮流取石子,每次可以从两堆中取走相同数量的石子或者选择一堆取走若干石子(不能不取),不能操作者输。

令 $\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{3+\sqrt{5}}{2}$,$(x,y)$ 是先手必败状态当且仅当 $(x,y)=(\lfloor\alpha n\rfloor,\lfloor\beta n\rfloor)$。可以由 Beatty 定理证明。

阶梯博弈

$n$ 层阶梯,每层有一堆石子,每次选择一堆,取出若干个丢到低一层中(特别的,第 $1$ 层的直接扔掉),不能操作着输。

只把奇数层的拿出来,相当于一个 Nim 博弈。

翻硬币游戏

$n$ 枚硬币,有的正面向上,有的反面向上,每次按照某个规则翻转一些硬币,但最右边的必须是从反面翻转成正面,不能操作者输。

结论:局面的 SG 函数值等于局面中每枚正面向上的硬币单独存在时的 SG 函数值的异或和。

树上删边游戏

一个有根树,每次是选择一条边,删除此边以及删掉边后和根不连通的部分,不能操作者输。

$SG(x)=\oplus_{v\in son_x}(SG(v)+1)$,叶节点的 SG 函数值为 $0$。

1-动态减法博弈

有一个正整数 $n$,双方轮流将其减去一个正整数,第一次不能减完,接下来每次减的值不能超过上次,先将其减到 $0$ 者胜利。

先手必败当且仅当 $n=2^k$。

2-动态减法博弈

有一个正整数 $n$,双方轮流将其减去一个正整数,第一次不能减完,接下来每次减的值不能超过上次的两倍,先将其减到 $0$ 者胜利。

先手必败当且仅当 $n$ 为斐波那契数。

k-动态减法博弈

上面两种博弈的一般情况。

有一个正整数 $n$,双方轮流将其减去一个正整数,第一次不能减完,接下来每次减的值不能超过上次的 $k$ 倍,先将其减到 $0$ 者胜利。

设上一轮取了 $x$ 个,此轮至多取 $f(x)$ 个,其中 $f(x)$ 单调不降。再设 $H_i$ 表示第 $i$ 个先手必败态,且 $H_1=1$。

定理:$f(H_i)\geq H_i$,$S_{i+1}=\min\left\{H_x|f(H_x)\geq H_i\right\}$,$H_{i+1}=H_{i+1}+S_i$。

如果递推到第 $i$ 个时发现 $f(H_i)<H_i$,那么之后不存在任何先手必败局面。

最后修改:2021 年 01 月 07 日 07 : 49 PM