博弈论基础

算法竞赛中的博弈论问题：
ICG（Impartial Combinatorial Games 公平组合游戏） 特征如下：
1.两名选手
2.轮流操作，每次一步，每步在有限合法集合中选取一种进行
3.任何情况，合法操作只取决于情况本身，与选手无关
4.游戏败北条件：当某位选手需要进行操作时，当前没有任何可以执行的合法操作，则该选手败北

经典问题：
1.巴什博弈：n个物品，两人轮流取1~m个，最后取光的人获胜。
同余定理：a-b能被m整除，则整数a，b对模m同余（ 记作a≡b(mod m) ）
n=k(m+1)+r。先手取r个，后手不论取多少，先手只要取的数和后手和为m+1，先手必胜。
n=k(m+1)。先手必输。
if (n % (m + 1)) return 1;//先手胜
else return 0;

2.威佐夫博弈：两堆各若干个，两人轮流取，一堆取至少一个/两堆取相同个数（至多），最后取光者获胜。
差值黄金分割比=最小值 的话，后手胜，否则先手胜。
abs(a-b)r=min(a,b) 2分之（根号5-1）注意精度问题
//注意精度
double r = (sqrt(5.0) - 1) / 2;
int d = abs(a - b) * r;
if (d != min(a, b)) return 1;//先手胜
else return false;

3.尼姆博弈：n堆物品（每堆任意值），两人轮流取，每次取某堆中不少于1个，最后取完获胜。
（证明较为繁琐）结论：n堆数量全部异或后结果为0则必败，否则必胜
int res = 0;
for (int i = 1; i <= n; i ++)
res = res ^ a[i];
if (res) return 1;//先手胜
else return 0;

对于更加一般的博弈论问题，通过SG函数转化为尼姆博弈
SG函数：首先给出一种ICG博弈游戏模型：给定一个有向无环图和一个起始顶点上的一枚棋子，两人交替移动，无法移动者判负。任何一个ICG都可以把每个局面看成一个顶点，对每个局面和他的子局面连一条有向边来抽象成这个“有向图游戏”。

首先定义mex运算，表示最小的不属于这个集合的非负整数。如mex{0,1,2,4}=3, mex{2,3,5}=0, mex{}=0。
对于一个给定的有向无环图，定于关于图的每个顶点的SG函数如下：sg(x)=mex{sg(y)}(y是x的后继)

1.找出必败态(sg的值为0)
2.找出当前所有状态的前驱节点
3.根据定义计算节点sg值
重复上述步骤直到整棵树建立完成

每个节点拥有一个sg值(设为x)，一个操作(移动到该节点的后继)实际上就是把棋子移到0~x-1的某个节点上，等价于从x个物品中取走至少1个，至多x个。（不存在走到超过x的情况，博弈条件每个人选择自己的最优方案）

SG定理：G1,G2,...Gn是n个有向图游戏，G是n个游戏的和，游戏G的移动规则：任选一个子游戏Gi并移动上面的棋子。SG定理就是sg(G)=sg(G1)^...sg(Gn) (即看成nim的n个堆)