相关的定义
公平组合游戏 (impartial combinatorial game)
定义为满足下列条件的游戏：
- 两个玩家轮流操作，无法操作者输。
- 游戏会在有限的轮数内结束。
- 对于每个状态，每一个玩家可以进行的操作是相同的。也就是说可以进行的操作只取决于当前所处的状态而不取决于操作的玩家。
- 信息公开，且没有随机行为。即，两个玩家都能够知道关于游戏状态的所有信息以及对手的操作，且玩家的操作会转移到的后继状态是确定的（而不会受到随机因子的影响）。
状态 (position)
我们约定用如下的记号来表示游戏状态：假设某个状态$G$能够转移到的状态集合是$\{G_1,G_2\cdots G_k\}$，我们就用$\{G_1,G_2\cdots G_k\}$来表示$G$。没有可行的转移的状态记为$\{\}$。此外，我们用$n$表示有一个有$n$个石子的Nim游戏的状态，即：$0=\{\},n = (n-1) \cup \{(n-1)\} = \{(n-1),(n-2),\cdots 0\}$。
公平组合游戏的状态可以根据其结果分为两类，一类是 N-positions ，表示先手必胜态；另一类是 P-positions ，表示先手必败态。一个简单的结论是，一个状态是 N-position 当且仅当它存在一个后继状态是 P-positioin ，一个状态是 P-position 当且仅当它所有的后继状态都是 N-position。
组合 (to combine)
用$A+B$表示由$A$和$B$两个游戏组合起来得到的游戏。组合的含义是：$A+B = \{ a + B \mid a \in A\} \cup \{ b + A\mid b \in B\}$。
等价 (equivalence)
称两个状态$G,G’$是等价的当且仅当对于任意一个状态$H$，$G+H$和$G’+H$的结果相同。记为$G\approx G’$。
Sprague–Grundy theorem
任意一个公平组合游戏的任意一个状态都可以与唯一确定的一个Nim游戏的状态等价。我们把它所等价于的Nim游戏中的石子数称为Grundy number（也称为Grundy value, nim-value, nimber ）。
proof
First Lemma
对于任意一个 P-position $A$和任意一个状态$G$，$G\approx G+A$。
证明：等价于证明，对于任意一个状态$H$，$G+H$和$G+A+H$的结果是一样的。
假设$G+H$是必胜状态 ，则只需要说明$G+H+A$是必胜状态。先手只需要先进行$G+H$中的必胜策略的第一步，然后$G+H$转化成了必败状态，而此时$A$也是必败状态。接下来，如果后手操作$A$，先手也跟着操作$A$，使$A$仍然是必败状态；如果后手操作$G+H$，先手就跟着操作$G+H$。这样就可以保证$A$和$G+H$始终都是必败状态，直到结束。所以$G+H+A$是必胜状态。
假设$G+H$是必败状态，则$G+H+A$等价于上一种情况中第一步之后的局面，所以$G+H+A$也是必败状态。
综上，对于任意一个 P-position $A$和任意一个状态$G$，$G\approx G+A$。
Second Lemma
$G\approx G’$的充要条件是$G+G’$为P-position。
证明：
必要性：如果$G\approx G’$，则$G+G\approx G+G’$，而由于$G+G$显然是一个P-positiong（先手在某一个$G$上操作了之后，后手可以在另一个$G$上做同样的操作，这样先手就必败了），所以$G+G’$是一个P-position。
充分性：如果$G+G’$为P-position，那么对于任意一个状态$H$，我们有$G+H \approx G+H+(G+G’) \approx G’+H+(G+G) \approx G’+H$，所以$G\approx G’$。
证明Sprague–Grundy theorem
证明：考虑归纳。若状态为终态显然成立，此时等价于$0$。假设现在有一个不是终态的状态$G=\{G_1,G_2,\cdots G_k\}$，由归纳假设已经知道$G_i \approx n_i$。令$G’ = \{ n_1,n_2,\cdots *n_k\}$。令$m$为$\{n_1,n_2\cdots n_k\}$中没有出现过的最小自然数。
首先证明$G\approx G’$，等价于要证明$G+G’$是P-position。如果$G=\{\}$显然成立；如果先手把$G’$转移到了$n_i$，则后手可以把$G$转移到$G_i$，由于$n_i \approx G_i$，所以$n_i + G_i$为P-position；如果先手把$G$转移到了$G_i$，后手则可以把$G’$转移到$n_i$，也得到了$*n_i +G_i$。综上，$G\approx G’$。
下面证明$G\approx m$，由于等价的传递性，这个命题等价于$G’+m$为P-position。假设先手操作了$m$转移到了$n’$，则$G’$一定也包含$n’$这个转移，后手只要将$G’$转移到$n’$就可以把必败局面留给先手。而如果先手操作了$G’$转移到了$n’$，若$n’>m$则后手可以操作$n’$转移到$m$，而若$n’<m$则后手可以操作$m$转移到$*n’$。注意由于$m$的定义，不可能出现$n’=m$的情况。
证毕。