• $P$ 点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。
• $N$ 点：必胜点，处于此情况下，双方操作均正确的情况下必胜。

必胜点和必败点的性质：

• 所有终结点是必败点 $P$。
• 从任何必胜点 $N$ 操作，至少有一种方式可以进入必败点 $P$。
• 无论如何操作，必败点 $P$ 都只能进入必胜点 $N$。

两个人玩这个游戏，他们轮流操作。

有若干堆石子，每堆石子的数量都是有限的。

一次合法的移动是 “选择一堆石子并拿走若干颗（不能不拿）”。

如果轮到某个人时所有的石子堆都已经被拿空了，则判负。

如果双方都按照最优策略，谁必胜？

对于一个 nim 游戏的局面 $(a_1,a_2,\cdots,a_n)$，它是 $P$ 点当且仅当： $$ a_1\oplus a_2\oplus\cdots\oplus a_n=0 $$ 【证明】

1. 终结点只有一种，就是 $(0,0,\cdots,0)$，显然符合异或和为 $0$，为 $P$ 点。
2. 对于 $(a_1,a_2,\cdots,a_n)$ 且 $a_1\oplus a_2\oplus\cdots\oplus a_n=0$，经一次移动后必然到达 $(b_1,b_2,\cdots,b_n)$，其中 $$ b_1\oplus b_2\oplus\cdots\oplus b_n\ne 0 $$ 从而到达 $N$ 点。
3. 对于 $(a_1,a_2\cdots,a_n)$ 且 $a_1\oplus a_2\oplus\cdots\oplus a_n\ne 0$，必存在移动方法可以到达 $P$ 点。

我们设 $a_1\oplus a_2\oplus\cdots\oplus a_n=k$，那么设 $k$ 的二进制表示下最高位的 $1$ 为 第 $p$ 位。

那么，$a_1,a_2,\cdots,a_n$ 中必定存在至少一个 $a_i$ 使得 $a_i$ 二进制表示下第 $p$ 位为 $1$。

从而，将第 $i$ 堆石头取 $a_i-a_i\oplus k$ 个石头即可保证一定到达 $P$ 点。

首先，由于 $a_i\oplus k$ 第 $p$ 位为 $0$，所以 $a_i\oplus k<a_i$，从而 $a_i-a_i\oplus k>0$，符合游戏规则。

并且，取 $a_i-a_i\oplus k$ 个石头后，第 $i$ 堆石头变为 $a_i\oplus k$，对于新局面 $(a_1,a_2,\cdots,a_i\oplus k,\cdots,a_n)$： $$ a_1\oplus a_2\oplus\cdots\oplus(a_i\oplus k)\oplus\cdots\oplus a_n=k\oplus k=0 $$ 从而一定为 $P$ 点。

有向图移动游戏可以看作所有 Impartial Combinatorial Games 的抽象模型。

NIM 游戏就是 Impartial Combinatorial Games 其中的一种。

也就是说，所有 ICG 游戏都可以看成：

给定一个 DAG 及一个点上的一个棋子，两名选手交替将棋子沿边移动，无法移动判负。

我们把 NIM 游戏的每一个状态看成一个点，把这个状态和其可以转移到的下一个状态连边。那么 NIM 游戏也被抽象成了一个有向图移动游戏！

定义 $mex(S)=k$：$k$ 为最小的不属于集合 $S$ 的非负整数。

$SG$ 函数的定义：对于任意一个状态 $x$，都定义一个 $SG$ 函数。

我们先给出定义式，再具体说明意义。

对于任意状态 $x$，设 $x$ 的后继状态集合为 $S$，则： $$ sg(x)=mex(S) $$ 如果一个状态为终结点，则 $S=\emptyset$，从而 $sg(x)=0$。

事实上，如果把所有 $ICG$ 游戏抽象成有向图移动游戏，那么 $sg$ 函数就是： $$ sg(x)=mex\{sg(y)\mid(x\rightarrow y)\} $$ 我们有这样的结论： $$ \begin{cases} sg(x)=0\Leftrightarrow x~is~P\\ sg(x)\ne0\Leftrightarrow x~is~N \end{cases} $$ 对于这个结论的正确性显然：

对于 $sg(x)=0$ 的结点，显然根据定义，$x$ 的后继中一定不存在 $sg(y)=0$ 的结点 $y$。

同时，对于 $sg(x)\ne 0$ 的结点，根据定义，一定存在一个 $x$ 的后继 $y$ 使 $sg(y)=0$。

两个人取石子，每个人可以取 $1,3,4$ 个石子。

共有 $n$ 个石子，求是先手必胜还是后手必胜。

$sg(0)=0,sg(i)=mex\{sg(i-1),sg(i-3),sg(i-4)\}$

假设一个游戏可以分成若干个子游戏，这些子游戏的 $sg$ 函数值为 $s_1,s_2,\cdots,s_k$，则：整个游戏的 $sg$ 函数为： $$ sg(All)=s_1\oplus s_2\oplus\cdots\oplus s_k $$ 我们设 $sg(x)=a$，那么也就是说 $x$ 的后继结点 $y$ 能取遍 $1,2,\cdots,a-1$。

那么我们选取后继，事实上可以看成 “取石子” 的过程。

这样想的话，就可以利用 Bouton’s Theorem 的证明来理解 $SG$ 定理了。