博弈论专题
Nim游戏
内容：
有 n 堆石子，每堆石子的石子数给出，甲乙两人回合制取石子，每次可以取任意一堆石子的任意多个（可以直接取完，但不能不取），每个人都按照最优策略来取（抽象），问先手必胜或先手必败？
结论：
设有 n 堆石子，每堆的个数分别为 a1 , a2 , a3 , …… , an-1 , an 。则有：
先手必胜态：a1 ^ a2 ^ a3 ^ …… ^ an-1!= 0
先手必败态：a1 ^ a2 ^ a3 ^ …… ^ an-1 = 0
证明：
每堆石子数的异或和等于零，说明：二进制位下，每个数的各位数对齐。将 2^0 , 2^1 , 2^2 , …… , 2^x 各位的 1 相加，每位一的个数和必定是偶数个（含0）。
先手必胜态：先手必然可以拿走一些石子，使异或和为0（感性可理解）。后手拿走石子后，异或和必然不为零，因为同一二进制位上最多只能拿一次（只能拿同一堆内的），又不能不拿。直到先手拿走最后一个。
先手必败态同理。
拓展：
台阶型Nim游戏，同样是异或和，必胜态与必败态之间的转化，自己推。
有向图游戏
内容：
给定一个有向无环图，图中只有一个起点，在起点上放一个棋子，两个玩家轮流沿着有向边推动棋子，每次走一步，不能走的玩家失败。
定理：
mex运算：mex( S ) 为集合 S 中没有的最小非负整数。 例：mex( { 1,2,3 } ) = 0 , mex( { 0 } )= 1
SG函数：SG(x) = mex( { SG(y1),SG(y2),SG(y3),……,SG(yk) } ) （其中y1等是x可以走到的点）
SG定理：i）当这个游戏只有一个有向图时，若 SG(start) != 0，则先手必胜；反之先手必败。
-
证明：因为起点值不为 0，所以它必定可以移动到一个值为 0的点，值为零的点又只能移动到值不为零的点，当值为 0 的点是走不动的点时，后手就输了，故后手必输
ii）当有多个有向图时，若 SG(s1) ^ SG(s2) ^ SG(s3) ^ …… ^ SG(sn) != 0 时先手必胜；反之先手必败
-
证明：此时每一个有向图游戏的起点处都有一颗棋子，先手后手可能走的是不同图上的棋子。若异或和不为 0，则先手一定可以选择其中一个有向图，那个点 (x) 所连的点的 SG() 值是 [ 0,SG(x) )，必定有构造将所有的 SG() 的异或值为 0（此时移动过后的有向图start发生改变），将必败态留给对手。当所有的 SG() 值都为不能继续走的 0 时，先手获胜。