Home

$\qquad$游戏规则：地上有 $n$ 堆石子。每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。 我们计算一下所有堆石子的异或和: $S = a_1\ xor\ a_2\ xor\ \cdots\ xor\ a_n$ 我们注意到，当游戏到达终点，即场上没有石子，此时 $S = 0$, 此时先手必输. 当此时 $S = k$ 时, 若 $k$ 的最高位 $1$ 所在位置为第 $i$ 位，我们找到第 $i$ 位为 $1$ 的 $a_j$, 使 $a_j' = a_j\ xor\ k$（$a_j'$ 一定小于 $a_j$，因为 $a_j$的变化都在后i位上，而其中最高的第 $i$ 位从 $1$ 变为 $0$，后面无论多少位从 $0$ 变为 $1$ 也还是变小了）, 那么 $S' = S\ xor\ k = k\ xor\ k = 0$, 当 $S = 0$ 且 场上仍有石子时，无论这么取都会让 $S$ 不再为 $0$. 显然，若起手时 $S = 0$, 以后每一步 $S$ 都为 0, 最终也一定会走向游戏终点的 $S=0$,并输掉比赛 ①。

$\qquad$最终我们得到结论：当异或和为 $0$ 时，先手必输，反之必胜。

$\qquad$公平组合游戏 (ICG) 的定义如下：

$\qquad$游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；

$\qquad$任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；

$\qquad$游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。

$\qquad$显然，上述取石子游戏就是公平组合游戏，每一个ICG模型都可以根据不同的状态和状态转移的关系抽象成若干棋子在有向图上移动，从起点开始，谁最后一步移动到终点就获胜的问题, 取石子游戏可以抽象为下图（因为不同堆之间相互独立，所以只给出其中一堆的情况）假设有 $5$ 个石子：

$\qquad$引入 $SG$ 函数：

$\qquad$定义：某一点的 $sg$ 值为在这一点后继（该点的出边指向的点，如上图 $3$ 的后继为 $2,1,0$）的 $sg$ 值中未出现的最小自然数，对于本图, $sg(0) = 0, sg(1) = 1, sg(2) = 2, sg(3) = 3, sg(4) = 4, sg(5) = 5.① $

$\qquad$这样可能不太好看出sg函数的用处，我们改一下取石子的规则：每次只能取走 $1$ 或 $2$ 个石子。 这样图就变为：

$\qquad$显然，终点的 $sg$ 值为 $0$。 我们注意到，所有 $sg$ 值不为0的点都能一步移动到 $sg$ 值为$0$的点，所有 $sg$ 值为 $0$ 的点（非终点）能且只能移动到 $sg$ 不为$0$ 的点。

和我们上文的思维一样，若先手时sg值为0，那么该选手以后每次移动前的局面 $sg$ 值都为0，显然他会迎来终局并输掉比赛。于是我们得到了一个棋子情况下，起点 $sg$ 值为 $0$ 时

$\qquad$我们再回到我们之前得到的结论：所有石堆石子数异或和不为0时先手必胜。在 $②$ 处注意到，某石堆的起始 $sg$ 值就为该石堆的石子数，实质上，我们并不是对石堆石子数求异或和，而是对每个石堆的其实 $sg$ 值求异或和，推而广之到所有 $ICG$ 模型。

$\qquad$按照之前思路当一个局面的异或和为 $k$, 和之前一样，我们找到 $k$ 的最高位 $1$ 所在位置也为1的一个棋子的 $sg$ 值，让它异或上 $k$，得到的结果一定比原有的值小，又因为 $sg$ 值是后继 $sg$ 值中首个未出现的自然数，所以一定能找到一个新 $sg$ 值对应的后继，此时棋子就移动到那个后继所在的位置上，新异或和为 $0$（由先前论述可知）。

$\qquad$同 $①$ 理我们得到结论，对于 $ICG$ 模型，当所有棋子位置的起始 $sg$ 值的异或和不为 $0$ 时先手必胜，反之必败。