什么是公平组合游戏？

公平组合游戏：Impartial Combinatorial Games(简称ICG)

公平组合游戏的条件：

1. 有两名选手交替行动，每一步选手都可以在合法移动中任选一种行动；
2. 在游戏进行中的任意时刻，可以执行的合法行动与哪名选手无关，只取决于这个局面本身；
3. 无法进行行动的玩家判负。

举个反例：生活中的象棋游戏就不是公平组合游戏，一名玩家只能移动红棋，而另一名玩家只能移动黑棋，可以执行的合法行动与哪名选手有关，因此象棋游戏不是公平组合游戏。

 

什么是有向图游戏？

给定一个有向无环图，图中有唯一一个起点，在起点上放有一枚棋子。两名选手交替的将这枚棋子沿有向边进行移动，每一次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把局面看成图中的一个节点，并且每个局面向沿着合法移动能够到达的下一个局面连一条有向边。

 

Sprague-Garundy函数（SG函数）

Mex(minimal excludant)运算:

设S是一个非负整数集合，定义Mex(S)为不属于集合S的最小非负整数。例如：mex{0,1,2,4,5}=3、mex{1,2,3,5}=0、mex{Ø}=0。

在有向无环图的顶点上定义SG函数:

在有向图游戏中，对于每个节点x，设从x出发有k条有向边，分别到达节点y1,y2.....yk，定义SG(x)为x的后继节点y1,y2.....yk的SG函数值构成的集合再执行Mex运算的结果，即：

SG(x)=mex{SG(y1),SG(y2),........,SG(y3)}

特别地，整个有向图游戏G的SG函数值被定义为有向图游戏起点s的SG函数值，即：

SG(G)=SG(s)

如上图所示，这个图的叶节点的后继集合为空，因此无法移动，SG函数值为0，必败。往上推到A点，A的SG值为0，因此先手必败。

• 对于一个SG(x)=0的顶点x，它的所有后继y都满足SG(y)!=0
• 对于一个SG(x)!=0的顶点x，必定存在一个后继y满足SG(y)=0

 

有向图游戏胜负判定定理:

1.有向图游戏的某个局面必胜，当且仅当对应节点的SG值>0

2.有向图游戏的某个局面必败，当且仅当对应节点的SG值=0

有向图游戏的和：

设G1,G2,G3,...,Gm是m个有向图游戏。定义有向图G，它的行动是规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1,G2,G3,...,Gm的和。

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：

SG(G)=SG(G1)^SG(G2)^SG(G3)^.....^SG(Gm);