定义必胜状态为当前局面先手必胜的状态，必败状态为当前局面先手必败的状态。
有向图游戏
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。
对于点 u 和它的 k 个后继点 v1,v2,⋯,vk，定义 SG 函数：
SG(u)=mex{SG(v1),SG(v2),⋯,SG(vk)}
特别地，当 u 没有后继状态时 SG(u)=0。
显然，先手必胜当且仅当 SG(u)=0。
对于 n 个有向图游戏组合而成的游戏，即两个玩家轮流推动 n 个棋子之一，设这个游戏的初始状态为 S，棋子的起点分别为 s1,s2,⋯,sn，则有 SG 定理：
SG(S)=SG(s1)⊕SG(s2)⊕⋯⊕SG(sn)。
证明：由于组合而成的游戏也是有向图游戏，因此所有的状态存在一个拓扑序，以下使用数学归纳法证明：
-
归纳奠基：对于没有后继的状态 S，∀i∈[1,n],SG(si)=0,SG(S)=0，命题成立。
-
归纳假设：设当前状态 S 满足 SG(s1)+SG(s2)+⋯+SG(sn)=m，对于所有满足 SG(s1′)+SG(s2′)+⋯+SG(sn′)<m 的状态以及所有满足 SG(s1′)+SG(s2′)+⋯+SG(sn′)=m 并且拓扑序小于 S 的状态命题成立。
-
归纳递推：设 SG(s1)⊕SG(s2)⊕⋯⊕SG(sn)=k。
先证明 ∀k′<k, S 都存在一个后继状态 S′ 满足 SG(S′)=k′。
设 k⊕k′ 在二进制下的最高位为第 m 位，因为 k′<k, 所以 k′ 的第 m 位为 0，k 的第 m 位为 1。
根据异或定义，存在 i 满足 SG(si) 的第 m 位为 1。
那么 SG(si)⊕k⊕k′<SG(si)，根据 SG 函数定义，si 一定存在后继点 si′，满足 SG(si′)=SG(si)⊕k⊕k′。
把 si 推到 si′ 后满足 SG(s1)+SG(s2)+⋯+SG(si′)+⋯+SG(sn)<m，因此 SG(S′)=SG(s1)⊕SG(s2)⊕⋯⊕SG(si′)⊕⋯⊕SG(sn)=k′。
再证明 S 不存在后继状态 S′ 满足 SG(S′)=k。
如果把 si 推到 si′，一定 SG(si′)=SG(si)。
如果 SG(si′)<SG(si)，那么 SG(s1)+SG(s2)+⋯+SG(si′)+⋯+SG(sn)<m，因此 SG(S′)=SG(s1)⊕SG(s2)⊕⋯⊕SG(si′)⊕⋯⊕SG(sn)=k。
如果 SG(si′)>SG(si)，那么 SG(s1)+SG(s2)+⋯+SG(si′)+⋯+SG(sn)>m，因此 SG(S′) 未知，但我们只需证 SG(S′)=k。根据 SG 函数定义，si′ 一定存在后继点 si′′，满足 SG(si′′)=SG(si)，此时 SG(s1)+SG(s2)+⋯+SG(si′′)+⋯+SG(sn)=m，并且 S′′ 的拓扑序小于 S，因此 SG(S′′)=SG(s1)⊕SG(s2)⊕⋯⊕SG(si′′)⊕⋯⊕SG(sn)=k，所以一定有 SG(S′)=k。
NIM 游戏
很多的公平组合游戏都可以转化为多个有向图游戏的组合，比如 NIM 游戏。
n 堆物品，每堆有 ai 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。
取走最后一个物品的人获胜。
对于每一堆石子，定义结点 x 表示有 x 个物品的状态。所有编号大的结点向编号小的结点连边。
这样，NIM 游戏就转化 n 个有向图游戏的组合了。
易得 SG(x)=x，根据 SG 定理，当且仅当 a1⊕a2⊕⋯⊕an=0 时，先手必胜。
阶梯 NIM 游戏
n 堆物品，每堆有 ai 个，两个玩家轮流取走任意第 i 堆（i>1）的任意个物品移到第 i−1 堆中，但不能不取。
最后没有物品可取的人输。
结论：此游戏等价于 ⌊2n⌋ 堆物品，每堆有 a2i 个物品的 NIM 游戏。
不妨假设在 NIM 游戏中 A 必胜，B 必败，则 A 可以使用以下策略：
- 如果前一步 B 从第 2i 堆里取物品或者当前为第一步，A 按照 NIM 里的策略从对应的堆里取物品。
- 如果前一步 B 从第 2i+1 堆里取物品，A 将这些物品再移到第 2i−1 堆。
这样奇数堆中的物品就不会影响胜负情况，而在偶数堆中取物品相当于直接删除（因为它们到奇数堆后就不会影响胜负情况）。