在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当一必有一方有必胜/必不败的策略。

即对于游戏局面𝑋$X$，存在确定的游戏结果𝑃(𝑋)=0 𝑜𝑟 1$P\left(X\right)=0or1$，𝑠𝑢𝑐𝑐(𝑋)$succ\left(X\right)$为𝑋$X$的后继局面。

1. 一个状态是必败状态，当且仅当，它的所有后继状态都是必胜状态
   𝑃(𝑋)=0⟺∀𝑖,𝑃(𝑠𝑢𝑐𝑐(𝑋𝑖))=1$P\left(X\right)=0⟺\forall i,P\left(succ\right(X_i\left)\right)=1$

2. 一个状态是必胜状态，当且仅当，它的至少一个后继状态是必败状态
   𝑃(𝑋)=1⟺∃𝑖,𝑃(𝑠𝑢𝑐𝑐(𝑋𝑖))=0$P\left(X\right)=1⟺\exists i,P\left(succ\right(X_i\left)\right)=0$

• SG游戏定义：没有后继状态为必败状态
  𝑠𝑢𝑐𝑐(𝑋)=∅⇒𝑃(𝑋)=0$succ\left(X\right)=\varnothing \Rightarrow P\left(X\right)=0$

桌上n堆石子，游戏者轮流在某一堆取若干(>0)个，取走最后一个石子人胜。
最后局面为
𝑋𝑒𝑛𝑑={𝑋1=0,𝑋2=0,⋯,𝑋𝑛=0}$X_{end}=\{X_1=0,X_2=0,\cdots ,X_n=0\}$
可知NIM游戏是SG游戏。

在NIM游戏中的必胜状态为：当前局面下所有单堆石子数目的异或和不为0
𝑃(𝑋)=((𝑥1⊕𝑥2⊕⋯⊕𝑥𝑛)≠0)$P\left(X\right)=\left(\right(x_1\oplus x_2\oplus \cdots \oplus x_n)\ne 0)$

• SG函数（定义见下）
  𝑆𝐺(𝑥)=𝑥$SG\left(x\right)=x$
• 游戏结果
  𝑃(𝑥)={01𝑥=0𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒$P\left(x\right)=\{\begin{array}{ccc}& 0& x=0\\ & 1& otherwise\end{array}$

一个游戏局面的SG函数为该局面的后继局面的SG函数集合的mex值
𝑆𝐺(𝑋)=𝑚𝑒𝑥(𝑆)$SG\left(X\right)=mex\left(S\right)$
其中
𝑆={𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋1)),𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋2)),⋯𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑛))}$S=\left\{SG\right(succ\left(X_1\right)),SG(succ\left(X_2\right)),\cdots SG(succ\left(X_n\right)\left)\right\}$
mex表示不在集合内的最小非负整数
𝑚𝑒𝑥(𝑆)=𝑚𝑖𝑛(𝑥|(𝑥∈ℝ)&(𝑥∉𝑆))$mex\left(S\right)=min\left(x|\right(x\in R\left)\&\right(x\notin S\left)\right)$

游戏和的SG函数等于各子游戏SG函数的NIM和
𝑆𝐺(𝑋)=𝑆𝐺(𝑋1)⊕𝑆𝐺(𝑋2)⊕⋯⊕𝑆𝐺(𝑋𝑛)$SG\left(X\right)=SG\left(X_1\right)\oplus SG\left(X_2\right)\oplus \cdots \oplus SG\left(X_n\right)$
其中
SG游戏局面为若干SG子游戏之和
𝑋=𝑋1+𝑋2+⋯+𝑋𝑛$X=X_1+X_2+\cdots +X_n$

𝑆𝐺(𝑋)=0⟺∀𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))≠0$SG\left(X\right)=0⟺\forall i,SG\left(succ\right(X_i\left)\right)\ne 0$
2.
𝑆𝐺(𝑋)≠0⟺∃𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))=0$SG\left(X\right)\ne 0⟺\exists i,SG\left(succ\right(X_i\left)\right)=0$
3.
𝑠𝑢𝑐𝑐(𝑋)=∅⇒𝑆𝐺(𝑋)=0$succ\left(X\right)=\varnothing \Rightarrow SG\left(X\right)=0$

• 在SG游戏（𝑠𝑢𝑐𝑐(𝑋)=∅⇒𝑃(𝑋)=0$succ\left(X\right)=\varnothing \Rightarrow P\left(X\right)=0$）条件下的等价结论

𝑃(𝑋)=0⟺𝑆𝐺(𝑋)=0$P\left(X\right)=0⟺SG\left(X\right)=0$
𝑃(𝑋)=1⟺𝑆𝐺(𝑋)≠0$P\left(X\right)=1⟺SG\left(X\right)\ne 0$

• Anti-SG游戏定义：决策集合为空的为必胜状态
  𝑠𝑢𝑐𝑐(𝑋)=∅⇒𝑃(𝑋)=1$succ\left(X\right)=\varnothing \Rightarrow P\left(X\right)=1$

桌上n堆石子，游戏者轮流在某一堆取若干(>0)个，取走最后一个石子人败。

• SG函数:不变
  𝑆𝐺(𝑥)=𝑥$SG\left(x\right)=x$
• 游戏结果:判断标准改变
  𝑃(𝑥)={01𝑥=1𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒$P\left(x\right)=\{\begin{array}{ccc}& 0& x=1\\ & 1& otherwise\end{array}$
  解释：

1. 若堆中有1个石子，根据定义，为必败状态。
2. 若堆中有0个石子，根据定义，为必胜状态。
3. 若堆中石子数目大于1，存在导致必败状态的取法：取剩下1个石子，因此为必胜状态。

𝑃(𝑋)={𝑆𝐺(𝑋)=0𝑆𝐺(𝑋)≠0∀𝑖,𝑥𝑖=1𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒$P\left(X\right)=\{\begin{array}{ccc}& SG\left(X\right)=0& \forall i,x_i=1\\ & SG\left(X\right)\ne 0& otherwise\end{array}$

对于任意一个 Anti-SG 游戏，如果我们规定当局面中所有的单一游戏的 SG 值为 0 时，游戏结束，则先手必胜当且仅当：

1. 游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1；
2. 游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。
   即，在Anti-SG游戏（𝑠𝑢𝑐𝑐(𝑋)=∅⇒𝑃(𝑋)=1$succ\left(X\right)=\varnothing \Rightarrow P\left(X\right)=1$）条件下的等价结论
   𝑃(𝑋)={𝑆𝐺(𝑋)=0𝑆𝐺(𝑋)≠0∀𝑖,𝑆𝐺(𝑋𝑖)≤1∃𝑖,𝑆𝐺(𝑋𝑖)>1$P\left(X\right)=\{\begin{array}{ccc}& SG\left(X\right)=0& \forall i,SG\left(X_i\right)\le 1\\ & SG\left(X\right)\ne 0& \exists i,SG\left(X_i\right)>1\end{array}$

“规定当局面中所有的单一游戏的 SG 值为 0 时，游戏结束”过于严格， 完全可以替换成“当局面中所有的单一游戏的 SG 值为 0 时，存在一个单一游戏它的 SG 函数能通过一次操作变为 1”。
(∀𝑖,𝑆𝐺(𝑋𝑖)=0)&(∃𝑖,𝑆𝐺(𝑠𝑢𝑐𝑐(𝑋𝑖))=1)⇒𝑃(𝑋)=1$(\forall i,SG(X_i)=0)\&(\exists i,SG(succ\left(X_i\right))=1)\Rightarrow P\left(X\right)=1$

除了上述提到的NIM游戏和反NIM游戏，还存在几类博弈论组合游戏中的经典变体。

有一堆总数为n的物品，2名玩家轮流从中拿取物品。每次至少拿1件，至多拿m件，不能不拿，最终将物品拿完者获胜。
（单堆NIM游戏变式-有上限的单堆NIM游戏）

在先取完者胜的巴什博弈中，若n可被m+1整除，则先手必败，否则先手必胜。
𝑃(𝑛)=((𝑛%(𝑚+1))≠0)$P\left(n\right)=\left(\right(n\%(m+1))\ne 0)$

在先取完者败的反巴什博弈中，若n整除m+1的余数为1则先手必败，否则先手必胜。
𝑃(𝑛)=((𝑛%(𝑚+1))≠1)$P\left(n\right)=\left(\right(n\%(m+1))\ne 1)$

有两堆各若干个物品，两个人轮流从任一堆取至少一个或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。

𝑋=(𝑎[𝑘]，𝑏[𝑘]),𝑘∈ℝ,𝑃(𝑋)=0$X=\left(a\right[k\left]，b\right[k\left]\right),k\in R,P\left(X\right)=0$
𝑎[0]=𝑏[0]=0$a\left[0\right]=b\left[0\right]=0$,𝑎[𝑘]$a\left[k\right]$是未在前面出现过的最小自然数，即𝑚𝑒𝑥({𝑎[0],𝑎[1],⋯,𝑎[𝑘−1],𝑏[0],𝑏[1],⋯,𝑏[𝑘−1]})$mex\left(\right\{a\left[0\right],a\left[1\right],\cdots ,a[k-1],b\left[0\right],b\left[1\right],\cdots ,b[k-1]\left\}\right)$,而 𝑏[𝑘]=𝑎[𝑘]+𝑘$b\left[k\right]=a\left[k\right]+k$。

设𝑎$a$、𝑏$b$是正无理数且 1𝑎+1𝑏=1$\frac{1}{a}+\frac{1}{b}=1$。记𝑃={⌊𝑛𝑎⌋∣∣𝑛∈ℕ+}$P=\{\lfloor na\rfloor |n\in N^{+}\}$，𝑄={⌊𝑛𝑏⌋∣∣𝑛∈ℕ+}$Q=\{\lfloor nb\rfloor |n\in N^{+}\}$，(⌊𝑥⌋$\lfloor x\rfloor$指的是取𝑥$x$的整数部分𝑓𝑙𝑜𝑜𝑟(𝑥)$floor\left(x\right)$)，则𝑃$P$与𝑄$Q$是ℕ+$N^{+}$的一个划分，即𝑃∩𝑄=Ø$P\cap Q=Ø$且𝑃∪𝑄=ℕ+$P\cup Q=N^{+}$。

𝑎[𝑛]$a\left[n\right]$、𝑏[𝑛]$b\left[n\right]$是Betty序列，可以通过Betty定理求解。

𝑎𝑛=[α𝑛],𝑏𝑛=[β𝑛]$a_n=\left[\alpha n\right],b_n=\left[\beta n\right]$，有 𝑎𝑛+𝑛=[(α+1)𝑛]=[β𝑛]$a_n+n=\left[\right(\alpha +1\left)n\right]=\left[\beta n\right]$，解方程 1α+1+1𝛼=1$\frac{1}{\alpha +1}+\frac{1}{\alpha }=1$

α=5√+12,β=α+1$\alpha =\frac{\sqrt{5}+1}{2},\beta =\alpha +1$

𝑎𝑛=[5√+12𝑛]$a_n=\left[\frac{\sqrt{5}+1}{2}n\right]$，𝑏𝑛=𝑎𝑛+𝑛$b_n=a_n+n$ （方括号[𝑥]$\left[x\right]$表示四舍五入取整函数𝑟𝑜𝑢𝑛𝑑(𝑥)$round\left(x\right)$)

1. 百度百科
2. 维基百科
3. 《算法竞赛入门提高》刘汝佳
4. 国家集训队论文集2009-贾志豪

__EOF__

本文作者：炯炯目光
本文链接：https://www.cnblogs.com/jjmg/p/15645777.html
关于博主：正在努力的ACM狗
版权声明：欢迎分享或转载
声援博主：To be or not to be, is a question.