SG 定理
设游戏可以表示为有向无环图 \(G=(V,E)\),规定其中不存在平局,必胜态为其可以转移到一个必败态
那么对于其中某一状态 \(X\in V\),定义其 \(SG\) 函数值为:
据此,状态 \(X\) 是先手必败当且仅当 \(SG(X)=0\)
归纳证明:假设定理对于当前的 \(G\) 成立,那么新加入一个状态 \(X\),若 \(SG(X)>0\),则必然存在一个 \(Y\) 使得 \(SG(Y)=0,(X,Y)\in E\),转移到一个必败态符合定义
若 \(SG(X)=0\),则无出边或任意的 \((X,Y)\in E\) 都有 \(SG(Y)>0\),则为必败态
游戏的复合
定义游戏 \(X,Y\) 的复合是 \(X+Y\),其中 \(X,Y\) 互相不影响且都在游戏 \(X+Y\) 中
对于游戏 \(X=X_1+\cdots+X_n\)有 \(SG(X)=\operatorname{XOR}SG(X_i)\)
证明:设 \(b=\operatorname{XOR}SG(X_i)\),则只需证 \(\forall a<b,\exist X'=X_1+\cdots+X_i'+\cdots+X_n,SG(X')=a\) 和 \(\forall X',SG(X')\neq b\)
其中,\(X'\) 表示某一由 \(X\) 转移到的状态
对于第一个式子,设 \(d=b\operatorname{xor} a\),由于 \(a<b\),\(d\) 的二进制下最高位是最高的一个 \(b\) 是 \(1\) 但 \(a\) 不是 \(1\) 的位
由于 \(b\) 由所有 \(SG(X_i)\) 异或而来,必然存在某一 \(X_i\) 是的 \(SG(X_i)\) 的那一位也是 \(1\),因此 \(SG(X_i)\operatorname{xor} d<SG(X_i)\)
那么也存在 \(SG(X_i')=SG(X_i)\operatorname{xor} d\)
于是对于 \(X'=X_1+\cdots + X_i' +\cdots X_n\),有 \(SG(X')=b\operatorname{xor} d=a\)
对于第二个式子,设 \(\exist X',SG(X')=b\)
那么设 \(X'=X_1+\cdots + X_i'+\cdots X_n\),则可得 \(SG(X_i')=SG(X_i)\),矛盾
Nim
\(n\) 堆石子,每堆 \(a_i\) 个,每次选取一堆取任意个,恰好取完的胜
若只有一堆石子,那么有 \(SG(a_i)=a_i\)
\(n\) 堆符合以下,就是 \(\operatorname{XOR}a_i\)