博弈论初步——公平组合游戏

公平组合游戏（Impartial Combinatorial Games, ICG）指的是：

两人共同参与，轮流行动，均知道游戏的完整信息
在某一状态下可以做出的决策集合仅与当前的局面有关，与游戏者无关
经过有限步数后一定会以非平局结束游戏，一般是以某一玩家无法继续行动为结束点

公平组合游戏有多种，其中最经典的是 Nim 游戏，并且其他的公平组合游戏都可以转化为 Nim 游戏。

Nim 游戏

$n$ 堆物品，每堆有 $a_i$ 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。

取走最后一个物品的人获胜，也就是玩家无法行动的时候即为输。

不妨假设两位玩家都是绝顶聪明，行动必采取最优策略。在这种情况下，如果每种局面都存在最优策略，那么当初始局面给定时一定可以确定先手/后手必输，因此我们先考虑是否一定存在最优策略。

可以发现，所有局面对应的结束局面都是：

$a_i = 0, \forall i = 1, 2, \dots. n$ 此时先手必输

我们在此基础上加石子，枚举该局面可能的父局面，显然这些父局面都是先手必赢的。依此类推，不断地加石子必然可以得到初始局面，不难发现这个过程得到的是一张单起点单终点的有向图，其中每个结点对应某个局面（称为状态），每条边对应一种行动，我们将这个图称为博弈状态图。

先给出两个定义：

P-position: 当前局面先手必输，后手必赢
N-position: 当前局面先手必赢，后手必输

显然 $(0, 0, 0)$ 是 P-position，于是我们可以标记它的父节点为 N-position，自底向上标记，如果某个结点存在一个子节点为 P-position，那么它一定是 N-position，否则为 P-position（不存在最优策略）。这样一来，整张图的所有结点必然都会有一个标记，因此对于任意局面，如果每次采取最优策略那么它的结局从一开始就是确定好了的。

之后我们考虑如何确定某一局面是 P-position 还是 N-position。

最简单粗暴的办法当然是在这张图上自下而上遍历，由于会有重复的状态所以还需要记忆化，这样时间复杂度和空间复杂度都是 $O(\prod_{i=1}^{n}a_i)$ 的。

这时候你也许会认为没有更优的办法了，但是，回想一下之前标记的过程：

如果某个结点存在一个子节点为 P-position，那么它一定是 N-position，否则为 P-position（不存在最优策略）。

直觉告诉我，它一定还存在优化的空间！

事实上，确实有更好的办法，并且理论上应该也是最优的算法，那就是可以利用异或（ $\otimes$ ）操作 $O(n)$ 地求解。

结论：如果 $a_1 \otimes a_2 \otimes \dots \otimes a_n=0$ ，则先手必败。

使用数学归纳法证明：

对于有且仅有的 terminal position $a_1=a_2=\dots=a_n=0$ ，上述结论显然满足
对于任何 N-position $a_1 \otimes a_2 \otimes \dots \otimes a_n=k \not=0$ $a_{1} \otimes a_{2} \otimes \dots \otimes a_{n} = k \neq = 0$ ，必然存在某种行动使得它的子局面满足 $a_1^\prime \otimes a_2^\prime \otimes \dots \otimes a_n^\prime=0$ $a_{1}^{'} \otimes a_{2}^{'} \otimes \dots \otimes a_{n}^{'} = 0$
- $k$ 二进制下最高位的 1 必然由某个 $a_i$ 贡献而来，令 $a_i^\prime=k \otimes a_i < a_i$ 其余保持不变，此时 $a_1\otimes \dots \otimes a_i^\prime \otimes \dots \otimes a_n=0$
对于任何 P-position $a_1 \otimes a_2 \otimes \dots \otimes a_n=0$ $a_{1} \otimes a_{2} \otimes \dots \otimes a_{n} = 0$ ，无论如何行动，它的子局面必然为 $a_1^\prime \otimes a_2^\prime \otimes \dots \otimes a_n^\prime\not=0$ $a_{1}^{'} \otimes a_{2}^{'} \otimes \dots \otimes a_{n}^{'} \neq = 0$
- 假设拿 $a_j$ 中的石子，那么无论拿走多少， $a_j$ 的二进制位下至少有一位翻转了，最终异或和下的那一位必然变成 1，因此子局面的异或和不可能为 0

自此，我们可以根据异或和判断 P/N-position 。

但是问题来了，异或的操作无论是和 Nim 游戏还是和上面的博弈状态图看上去都风马牛不相及，为什么异或和可以求出某一个局面是 P 还是 N-position 呢？上述的证明使用了数学归纳法，也仅仅是已知结论进行推导它确实成立而已。

一个揭示了有向图游戏和异或操作的本质关联的解释用到了群论²，另外一个更 intuitive 的解释在 John Conway 的 Winning Ways for Your Mathematical Plays 书中有提到（当然我没看过，之后有时间也许会看看这本书？）

SG 函数

To be continued…

参考文献

Author: f1a3h

Permalink: https://blog.rbkou.me/Algorithm/game-theory-impartial-game/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可，使用时请注意遵守协议。

updated at 2024-12-19

# Game Theory

博弈论初步——公平组合游戏

Nim 游戏

SG 函数

参考文献

Comments