组合游戏模型

前置：

有向图游戏：给定一个无环图，图中有唯一的起点，在起点上放有一枚棋子，两名玩家将这枚棋子沿有向边移动，每次可以移动一步，无法移动者判负.该游戏被称为有向图游戏，任何公平组合游戏都可以看为有向图游戏，具体方法是把每个局面看成图中的一个节点，局面的转换看成有向边.

mes（S）定义为求出不属于集合S的最小非负整数的运算

sg游戏：

定义：无法操作者输.
在有向图游戏中，对于每个节点x，设从x出发共有k条有向边，分别到达节点y1,y2,y3…，定义sg(x)为x的后继节点的SG函数值的值构成的集合再执行mex运算，即：
sg(x)=mex({sg(y1),sg(y2),…,sg(yk)})

sg函数性质
1,对于任意局面，如果它的SG值为0，那么它的任意后继SG值不为0
2,对于任意局面，如果它的SG值不为0，那么一定有一个后继状态的SG值为0
在SG游戏中，SG值为0时先手必败。

有向图游戏的和：设G1，G2，…GM是m个有向图游戏，定义为有向图游戏G，它的行动规则是任选某个有向图游戏G1，并在G1上行动一步，G被称为有向图游戏的和.若只考虑游戏的和.
我们可以将其中任一游戏换成SG值相等的其他游戏，游戏的和的SG值不变。因此，在考虑游戏的和时，我们不关心每个单一游戏具体是什么，我们唯一要关心的就是这个单一游戏的SG值。由此可见，我们可以把任意游戏的和转换为Nim游戏,这样计算起来就很方便了。

Anti-SG游戏：

定义： 无法操作者赢
结论：先手必胜当且仅当：
1.游戏的SG函数不为0且游戏中某个单一游戏的SG函数大于1
2…游戏的SG函数为0且游戏中没有单一游戏的SG函数大于1

Multi-SG游戏（hdu5795）：

定义：
1，在符合拓扑原则的前提下，一个单一游戏的后继可以为多个单一游戏
2，其他规则与SG游戏相同
求解：
可以通过将SG函数适当变形来解决。只需要证明：我们依然可以用SG函数来定义局面。
因为局面在游戏树中满足拓扑关系(无环)，所以我们可以根据拓扑关系用数学归纳法来证明。

Every-SG游戏（hdu3595）：

定义:
1，对于任意单一游戏，如果还未结束，那么就必须操作
2，其他规则同SG游戏