公平组合游戏
公平组合游戏（Impartial Game）的定义如下：
- 游戏有两个人参与，二者轮流做出决策，双方均知道游戏的完整信息；
- 任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关；
- 游戏中的同一个状态不可能多次抵达，游戏以玩家无法行动为结束，且游戏一定会在有限步后以非平局结束。
有向图游戏
给定一个 \(Dag\) 和唯一的一个起点，起点处有一个棋子，双方轮流沿一条边移动棋子，无法移动者判负。
任何公平组合游戏都可以转化为有向图游戏，即点是状态，边是转移。
定义必胜态是先手必胜，必败态是先手必败，有如下三个定理：
- 若节点 \(x\) 没有后继，则 \(x\) 是必败态。
- 若节点 \(x\) 可以转移到一个必败态，则 \(x\) 是必胜态。
- 若节点 \(x\) 的后继都是必胜态，则 \(x\) 是必败态。
有向图的核
对于一个有向无环图 \(G = (V, E)\)，如果存在点集 \(S\)，满足 \(S\) 是独立集，且 \(V - S\) 与 \(S\) 中的某一个点有直接连边，则称 \(S\) 是 \(G\) 的核。
定理： 核的点集都是必败态。
证明考虑，对于 \(S\) 内的每一个点，若其向 \(V - S\) 中的点 \(x\) 有边，则 \(x\) 一定可以通过一条边回到 \(S\)。
四种经典组合游戏
尼姆游戏
普通 Nim
阶梯 Nim
K-Nim
巴什博弈
威佐夫博弈
斐波那契博弈
其肯多夫表示