阅读了《由感性认识到理性认识——透析一类搏弈游戏的解答过程》、《解析一类组合游戏》、《组合游戏略述——浅谈SG游戏的若干拓展及变形》这三篇论文，对组合游戏以及SG函数有了更深的理解。这篇文章摘下了这三篇论文的部分重要内容，以及部分我对组合游戏的理解。

一些名词与约定：

• 游戏：这里的游戏指的并不是平时玩的那些游戏（Dota2啥的），而是只一些如Nim取石子之类的“益智”组合游戏。并且，我们关注的不是游戏好不好玩，而是游戏有没有必胜策略。下文详细介绍。
• 状态：用一些数字来表示的游戏进行中的一个局面。
• 必胜状态：存在一种走法走到一个必败状态。
• 必败状态：后继状态都为必胜状态。

*特别的在组合游戏中一个状态不是必胜状态就是必败状态。

组合游戏是满足以下一些性质的游戏：

1. 游戏只有两名参与者。
2. 游戏过程中任意时刻有确定的状态。
3. 规则规定了任意状态参与者可以到达的状态集合。
4. 参与者轮流进行操作。
5. 在游戏处于某状态，当前参与者不能进行操作时，游戏结束。此时按照规则决定胜负。
6. 无论参与者做出怎样的操作游戏都可以在有限步数内结束（没有平局）。
7. 信息对于两位参与者都是公平的透明的。

*我们还假设参与者都足够聪明，在有必胜策略时一定会走必胜策略。

几个游戏

游戏0：

有一堆石子，甲乙两人轮流取，不能不取，最多取完，当轮到一个人取不了时这个人输。
　　这个游戏很显然，只要现在有石子，就可以都取完，然后第二次另一个人就没法取。
所以在这个游戏里{0}是必败状态，其他都是必胜状态。

游戏1：

有两堆石子，甲乙两人轮流取，每次只能从其中一堆取，不能不取，最多取完一堆，当轮到一个人取不了时这个人输。
　　这个游戏相当于两个第一个游戏的“和”。我们可以很轻松的发现，如果两堆的石子个数一样的时候是先手必败的，因为不论先手怎样取石子，后手可以在另一堆中用相同的策略取，知道先手没有可以取的石子。而两堆石子个数不一样的时候是先手必胜的，先手可以拿较多的一堆使得两堆石子一样多。

游戏2：

甲乙两人面对若干堆石子，其中每一堆石子的数目可以任意确定，每一步应取走至少一枚石子，每一步只能从某一堆中取走部分或全部石子，如果谁无法按规则取子，谁就是输家。
　　这个游戏看起来更复杂了，现在我们要引入一个有力的工具，叫做SG函数和SG定理。

SG函数：

• 一个游戏的终态x的SG(x)=0。
• 其余状态x的SG(x)=min( n|n∈N且n!=SG(F(x)) )

其中F(x)为状态x能转移到的任意一个状态。
*第二个式子也写作 SG(x)=mex{SG(F(x))}
SG函数的性质：所有SG(x)==0的状态都是必败状态，所有SG(x)!=0的状态都是必胜状态。

SG定理：几个单个的组合游戏组成的游戏状态的SG值为每个单个游戏状态SG值的Xor和。
*证明见论文。
　　然后对于游戏0有x个石子时SG(x)=x,所以求以下这些状态的Xor和就可以得到整个状态的SG值。

游戏3：

甲乙双方事先约定一个数m，并且每次取石子的数目不能超过m个，其余规则同游戏2。
　　设只有一堆且m=3：
　　SG(0)=0，SG(1)=1,SG(2)=2,SG(3)=3,SG(4)=0,SG(5)=1...
　　所以SG(x)=x mod (m+1)。
　　求一下整个状态的SG值就可以判断了。

游戏4：

甲乙两人面对若干排石子，其中每一排石子的数目可以任意确定。两人轮流取走一些石子,每一步必须从某一排中取走两枚石子,并且这两枚石子必须是紧紧挨着的,拿走后这一排就会断裂成两排。如果谁无法按规则取子，谁就是输家。（发挥想象力）
　　这个题看起来不像前几道题那么裸了。但是与前几道题还是很像，也可以用SG解决。
　　只是没有那么明显的规律了。需要从SG(0)=0,SG(1)=0,开始枚举可能转移的状态递推计算SG函数，程序实现可以记忆化搜索。

　　组合游戏还有许多的问题，定理，这里只是最基础的入门，还需要深入学习啊。

　　人们认识事物的过程中，开始只是看到了各个事物的现象。这就是认识的感性阶段。在这个阶段中，还不能作出合乎逻辑的结论。 随着研究的深入，这些感觉和印象的东西反复了多次，于是在人们的脑子里生起了一个认识过程中的突变，最后产生出合乎逻辑的结论。这就是认识的理性阶段。
　　“由此及彼、由表及里、去粗取精、去伪存真” ，这才是由感性认识上升到理性认识的关键。(摘)
*本文缺少一些证明，若需了解详细，请参考原论文。