在许多地方曾经流行过这样一个小游戏
摆出三堆硬币，分别包含 3 枚、5 枚、7 枚。两人轮流行动，每次可以任选一堆，从中取走任意多枚硬币，可把一堆取光，但不能不取。取走最后一枚硬币者获得胜利。
这类游戏可以推广为更加一般的形式：
给定 堆物品，第 堆物品有 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手能否必胜。
我们把这种游戏称为 NIM 博弈。
把游戏过程中面临的状态称为局面。
整个游戏第一个行动的称为先手，第二个行动的称为后手。
若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对手面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。
我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。NIM 博弈不存在平局，只有先手必胜和先手必败两种情况。
NIM 博弈先手必胜，当且仅当：
证明
-
终态局面：所有物品都被取光是一个必败局面（对手取走最后一件物品，已经获得胜利），此时显然有 。
综上所述，再由数学归纳法可知， 为必胜局面。存在一种行动让对手面临“各堆石子异或起来等于 0”。 为必败局面，无论如何行动，都会让对手面临一个“各堆石子异或起来不等于 0”的必胜局面。
证毕。
公平组合游戏 ICG
若一个游戏满足：
- 由两名玩家交替行动。
- 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关。
- 不能行动的玩家判负。
则称该游戏为一个公平组合游戏。
NIM 博弈属于公平组合游戏，但常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 2 和条件 3。
有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这张棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面沿合法行动能够到达的下一个局面连有向边。
Mex 运算
设 表示一个非负整数集合。定义 为求出不属于集合 的最小非负整数的运算，即：
SG 函数
在有向图游戏中，对于每个节点 ，设从 出发共有 条有向边，分别到达节点 ，定义 为 的后继节点 的 SG 函数值构成的集合再执行 运算的结果，即：
定理
- 有向图游戏的某个局面必胜，当且仅当该局面对应节点的 SG 函数值大于 0。
- 有向图游戏的某个局面必败，当且仅当该局面对应节点的 SG 函数值等于 0。
我们不再详细证明该定理。读者可以这样理解：
- 在一个没有出边的节点上，棋子不能移动，它的 SG 值为 0，对应必败局面。
- 若一个节点的某个后继节点 SG 值为 0，在 mex 运算后，该节点的 SG 值大于 0。这等价于，若一个局面的后继局面中存在必败局面，则当前局面为必胜局面。
- 若一个节点的后继节点 SG 值均不为 0，在 mex 运算后，该节点的 SG 值为 0。这等价于，若一个局面的后继局面全部为必胜局面，则当前局面为必败局面。
有向图游戏的和
设 是 个有向图游戏。定义有向图游戏 ，它的行动规则是任选某个有向图游戏 ，并在 上行动一步。 被称为有向图游戏 的和。 有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即：
对于若干个有向图游戏的和，其证明方法与 NIM 博弈类似。