1|0基本定义

1|1策梅洛定理（Zermelo's theorem）

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

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

1|0推论

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$

2|0SG游戏

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

2|1NIM游戏

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

1|0Bouton定理

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

1|0单堆NIM游戏

• SG函数（定义见下）
  ??(?)=?$SG\left(x\right)=x$
• 游戏结果
  ?(?)={01?=0??ℎ??????$P\left(x\right)=\{\begin{array}{ccc}& 0& x=0\\ & 1& otherwise\end{array}$

2|2SG函数

一个游戏局面的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)$

1|0Sprague-Grundy 定理

游戏和的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$

1|0SG函数性质

??(?)=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$

3|0反SG(Anti-SG)游戏

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

3|1反NIM (Anti-NIM)游戏

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

1|0单堆反NIM游戏

• 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个石子，因此为必胜状态。

1|0反NIM游戏的游戏结果

?(?)={??(?)=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}$

3|2Sprague Grundy——Jia Zhihao 定理

对于任意一个 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}$

1|0引论

“规定当局面中所有的单一游戏的 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$

4|0SG游戏和反SG游戏模型

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

4|1巴什博弈（Bash game）

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

1|0巴什博弈游戏结果

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

1|0反巴什博弈（Anti-Bash game）游戏结果

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

4|2威佐夫博弈（Wythoff's game）

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

1|0奇异局势

?=(?[?]，?[?]),?∈ℝ,?(?)=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$。

1|0Betty 定理 （Betti theorem）

设?$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^{+}$。

1|0Betty序列

?[?]$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)$)

5|0参考资料

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

__EOF__

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