【博弈论】博弈论与SG函数

前文#

有两个游戏者：$A$和$B$。有$n$颗石子。
约定：两人轮流取走石子，每次可取 1、2 或 3 颗。$A$先取，取走最后一颗石子的人获胜。
问题：$A$有没有必胜的策略？

这类经典的 NIM 游戏（Impartial Combinatorial Games——ICG 游戏的一种）可以通过博弈论与Sprague-Grundy 数——SG 函数解决，当然其前提要求是 ICG 游戏，也就是公平组合游戏，它往往要满足以下要求。

1. 两名选手；
2. 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3. 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4. 若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。

本文将详细介绍如何通过基础博弈论与 SG 函数通过归纳数学解决此类问题。

需要说明的是，棋类游戏都不是 ICG 游戏，包括封面的国际象棋。

从 ICD 到 DAG 的转化#

DAG（有向无环图）可以用来代表任意一个 ICG 游戏。我们把 ICG 假设我们有两种点，一种为值为 1，代表从这个状态出发，先手必胜；另一种值为 0，代表从这个状态出发，先手必败。对于两种状态，把每一条有向边看作是状态的转移，我们可以得出以下连边规则：

1. 一个状态是必败状态当且仅当它的所有后继都是必胜状态。
2. 一个状态是必胜状态当且仅当它至少有一个后继是必败状态。

第一条规则的含义很清楚了，如果我不管怎么走，我走之后对于对方来说永远都是必胜的，那么对我来说我这个状态就是必败的。

第二条规则也是一个道理，如果我从这个状态转移能够让我的对手进入必败状态，那么对于当前的我来说我这个状态就是必胜的。

需要注意的是，虽然我们的有向边是从起点->终点的，且终点值为 0。但是实际上我们应该倒推，从一个状态的子状态可以得到这个状态，换句话说就是从终点 0 开始向后走，用现在处理的状态得到前一个状态。

但是这样会有问题，我们 1->1 的不好处理，不仅不知道实际情况，也不好知道转移的结果，所以需要用到下文的 SG 函数来辅助求解我们每一个状态的 SG 数，用 SG 数代替 01。

Sprague-Grundy 数的推导#

SG 是 Sprague-Grundy 的缩写，查阅后才发现是两个人名，它使用起来非常简单，但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话，你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理，所以我们需要详细解释一下它的推导过程，这样才能加深理解。

首先我们定义一个概念，在一个状态节点$i$中，如果$SG[i]$大于零，则是必胜状态，如果如果$SG[i]$等于零，则是必败状态。那么这样就可以分开 1->1 的情况。

那么根据我们上面的守则，我们可以写出下面的更新过程：

1. 首先获得一个状态的所有子状态
2. 如果子状态中有 0，说明这个是一个必胜状态，给它打上一个与子状态不同的标记
3. 如果子状态都大于 0，说明这是一个必败状态，就打上标记 0

这个面向过程的更新多少有点繁琐，我们可以写一个$mex$函数一次解决，具体写法如下：

$SG\_{}\left(A\right)=mex\left\lbrace SG\left(B\right)\left|A\rightarrow B\right.\right\rbrace$

式子中的A 和 B 表示状态，$A\rightarrow B$表示$A$状态可以达到$B$状态，也就是$B$是$A$的子状态。mex 是一个定义在集合上的函数，返回的是不属于这个集合的最小非负整数。比如$mex(0, 1)= 2$，$mex(0, 2) = 1$, $mex(0,1, 2, 3)=4$。那么我们就把上面啰嗦的三句话整合成了等价的一个$mex$函数。

最后还有一点，就是我一个子状态可能包含几个“孙状态”。比如有一道例题如下：

在一个平面上有$n$个点勾勒了一个凸四边形的轮廓，有两个游戏者$A$和$B$，每一个人可以连接任意两个点画出一条实线，要求实线不能交叉，一个点也不能被多次选择，问谁胜？

在这个题目中，我举一个例子：当$n$为 4 时，我有两种子状态：连相近的两条边，剩下两个可以连接的边；还有连对角的两条边，剩下两个孤立的点。第一个很好判断，子状态就是$SG(2)$。而第二个子状态却是用两个孙状态拼起来的，也就是一个$SG(1+1)$，这与$SG(2)$是不等价的，我们规定$SG(A + B) = SG(A) xor SG(B)$，如果有多个孙状态，就是他们的异或和，如此一来就可以正常表示一个子状态了。

SG 的结论推导#

这个是博弈论最最困难的地方，像通过 SG 函数与$mex$你可以很轻松求出每一个状态的 SG 值，但是实际应用中总是不切实际的——你不可能枚举每一个子状态再计算。这就要求选手通过有限的打表推断出普遍规律，这总是很难的。

每一道题目的结论都不相同，但宗旨就是——把对手扔到必败状态。具体来说就是我们可以锁定最后几个失败的状态找到他们与众不同的特点，虽然在中间满足这些特点的状态不一定是必败的，但是我们可以确定 ICG 游戏一定是会结束的，所以如果你可以让对手一直保持这个特点，那么只要走到终点状态，对手一定是必败的。

SG 的结论推导需要多刷多看才能找出其奥妙所在，有时候也可以根据题面找线索，比如二分图想到最大连通分量这些。但最后还是要看选手自己对数的理解——实在不行也有 SG 陪着你不是吗，不论如何，ICG 游戏只有先手必胜和先手必败两种情况，虽然打表找规律这种方法不甚高明，但是在比赛中也无可厚非了。