经典的公平组合游戏
nim 游戏
规则
\(n\) 堆物品，每堆有 \(a_i\) 个，两个玩家轮流取走任意一堆的任意个物品，但不能不取。
取走最后一个物品的人获胜。
结论
定义 $ Nim =a_1 \oplus a_2 \oplus \ldots \oplus a_n $ 。
当且仅当 $ Nim = 0 $ 时，该状态为必败状态；否则该状态为必胜状态。
威佐夫博弈
规则
有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，取走最后一个物品的人获胜。
结论
若两堆物品个数分别为 $x , y ( x < y ) $ ，若 $ x = \lfloor ( y - x ) \times \frac{1+\sqrt{5}}{2} \rfloor$ ，则该状态为必败状态；否则该状态为必胜状态。
SG 函数
任何一个可以用SG函数解决的问题都可以抽象成一个有向图游戏，SG函数是用于为这种有向图游戏提供最优策略的。（SG(x)=0代表x为必败态，SG（x）!=0代表x为必胜态）
定义 \(\operatorname{mex}\) 函数的值为不属于集合 \(S\) 中的最小非负整数，即：
\[\operatorname{mex}(S)=\min\{x\} \quad (x \notin S, x \in N) \]对于状态 \(x\) 和它的所有 \(k\) 个后继状态 \(y_1, y_2, \ldots, y_k\) ，定义 \(\operatorname{SG}\) 函数：
\[\operatorname{SG}(x)=\operatorname{mex}\{\operatorname{SG}(y_1), \operatorname{SG}(y_2), \ldots, \operatorname{SG}(y_k)\} \]而对于由 \(n\) 个有向图游戏组成的组合游戏，设它们的起点分别为 \(s_1, s_2, \ldots, s_n\) ，则有定理：当且仅当 \(\operatorname{SG}(s_1) \oplus \operatorname{SG}(s_2) \oplus \ldots \oplus \operatorname{SG}(s_n) \neq 0\) 时，这个游戏是先手必胜的。同时，这是这一个组合游戏的游戏状态 \(x\) 的 SG 值。
这一定理被称作 Sprague-Grundy 定理(Sprague-Grundy Theorem), 简称 SG 定理。
SG 定理适用于任何公平的两人游戏, 它常被用于决定游戏的输赢结果。