定义：
sg(x) = mex ( sg(y) |y是x的后继结点 )
其中mex（x）（x是一个自然是集合）函数是x关于自然数集合的补集中的最小值，比如x={0,1,2,4,6} 则mex（x）=3；
什么是后继结点？
所谓后继结点就是当前结点经过一个操作可以变成的状态。比如对于娶4石子游戏，假如每次可以取的数目是1,2,4，当前的石子数目也就是当前状态是5，那么5的后继结点就是{5-1, 5-2, 5-4}={4,3,1}；
如果5的三个后继结点的SG函数值分别为0,1,3，那么5的SG值就是集合{0,1,3}的补集的最小元素，也就是2。
关于整个游戏的sg值之和sum，定义sum=sg1 ^ sg2 ^ sg3 ^ ……sgn. 其中^表示按位异或运算。
结论：一个游戏的初始局面是必败态当且仅当sum=0
自认为sg函数应该算是博弈论中比较经典的东西了。。他几乎可以解决博弈论中的所有问题。你可以将sg函数看作是一个深搜的的过程。而每一堆的石子就相当于图中间的节点。所以说整个sg函数的过程就是在对一个有向无环图进行dfs的过程。
sg函数的具体内容可以用一个公式来表示（虽然我最不喜欢公式，不过我还是得写。不然这没法说清楚）：sg(x) =mex{sg(y) : y ∈ F(x)}。其中｛｝内的是一个集合（只要上过高中都应该知道吧），在：右边的是该集合元素所满足的条件。sg（y）为该元素的值（其实就是一个递归的过程）。重点来了。。mex（）函数表示是不在该集合中的最小的非负整数的值。比如mex({1,2,3})=0…mex({0,2,4})=1…mex({})=0..最后得出来的结果中。为0为必败点，不为零必胜点。。吊把·~~~
接下来才是sg函数精妙之处了。假如说是在一个游戏中有多个石子堆该怎么办了。我们只需要把对每个石子堆进行sg函数的调用，将得到的所有的值进行异或。得出来的结果为0则该情形为必败态。否则为必胜态。
入门一：
首先来玩个游戏，引用杭电课件上的：
(3)规则：游戏双方轮流取牌；扑克牌取光，则游戏结束；最后取牌的一方为胜者。
想一下。。
首先申明一点，博弈的讨论是在大家都玩的最好的情况下讨论的。（如果2个玩家智商有差别，那就没法讨论了～～～～开个玩笑哈。）
介绍概念：P点即必败点，某玩家位于此点，只要对方无失误，则必败；
N点即必胜点，某玩家位于此点，只要自己无失误，则必胜。
定理：
自己画下图看看。
这里具体是怎么算出来的看sg函数的定义
求解过程一般就是先写出sg函数，然后（如果数据很大就要考虑要不要找规律），根据sg函数求出sg的值，然后看是不是游戏可以看成多个9取石子的游戏，，就行异或运算求出最终的值。
大多数人想要改造这个世界，但却罕有人想改造自己。
