Sprague-Grundy
Follow(x)：x的下一状态集合
mex, minimum excluded value: mex(list)指没被包含在list中的最小非负数。如 mex({2,4,5,6})=0，mex({0,1,2,6})=3
SG数：SG(x) = mex({ SG(y), y∈Follow(x) })，从x可达各状态的SG值集的mex。这是个递归定义，递归基础是SG(0)=0。
Sprague-Grundy定理：大游戏的SG值等于各子游戏SG值的异或和。SG(x1 . . .xn) = SG(x1) ⊕ . . . ⊕ SG(xn)
单堆的nim有x个球，每步可以取1到x个，下一步状态集合Follow(x)=[0..x-1]个。从递归基础SG(0)=0一步步反推：SG(1) = mex({SG(0)}) = 1，SG(2) = mex({SG(0), SG(1)}) = mex({0,1}) = 2，...，所以单堆的nim游戏SG(x)=x，即单堆的nim-sum为球数x。
n堆的nim，可以认为是n个 单堆的子游戏，大游戏的SG值是各子游戏SG值的异或和。
n堆的nim游戏
两人轮流、两人待遇相同（impartial）、没有平局的游戏，先手赢（normal play）的策略：player1每步都使SG值为0。
两人待遇相同（impartial）：两人的差别只在player1先走。黑白棋、象棋等不是impartial，因为只能动自己的棋子、不能动别人的。
先手赢（normal play）：自己走最后一步，让别人无步可走。
In normal play, the winning strategy is to finish every move with a nim-sum of 0. This is always possible if the nim-sum is not zero before the move.
To find out which move to make, let X be the nim-sum of all the heap sizes. Find a heap where 'the-heap-size ⊕ X = new-heap-size < heap-size' - the winning strategy is to play in such a heap, reducing that heap to the 'new-heap-size'. In the example above, taking the nim-sum of the sizes is X = 3 ⊕ 4 ⊕ 5 = 2. The nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are
A⊕X= 3⊕2 = 1 [Since (011)⊕(010) = 001 ] B⊕X= 4⊕2 = 6 C⊕X= 5⊕2 = 7The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).