博弈模型

Fibonacci博弈

一堆$n$个石子，两人轮流取，每次最少取1个，最多不超过对手刚取的个数的2倍（第一次无限制，但不能取完）。取完获胜。

先手必败当且仅当$n$为Fibonacci数。

Wythoff博弈

两堆各若干个石子，两人轮流从一堆中取任意个或从两堆中取同样多个。每次至少取1个，取光者胜利。

定义后手必胜的局面为奇异局势。

从小到大依次为 $(0,0), (1,2), (3,5), ...$

（可以考虑方格纸上，从左下角依次放点，每个点可以向上、右、右上方向发出射线）

设第$k$个局面为$(a_k,b_k)$，则$a_k-a_{k-1}=k, b_k=[\frac{1+\sqrt{5}}{2}a_k]$

nim-k游戏

有n堆石子，每次可以从至多k堆中拿走任意数量的石子。（可以每堆拿的不一样）

不能拿的输。

先手必胜条件：把n堆石子用二进制表示，统计每一位上面的1的个数，如果每一位1的个数 mod (k+1)全为0，则先手必败。否则先手必胜。

证明：类比一堆石子共n个，每次去1~m个，不能动为输。

（比较显然，考虑不全是0的时候，从高位到低位取成0，如果这位的数比之前少，那么可以在前面不全去完，而是剩一些，在这里加个1之类的，比之前多就把新的弄小

二分图博弈

给一张二分图和一个起点，轮流在上面走，不能走重复的点，不能走就输。

先手必败当且仅当存在一个最大匹配使得起点不在这个匹配里面。（去掉起点跑最大匹配，加回来再跑一次，增广了就是先手败）

结论可以扩展到一般图上面，结论不变。

二分图证明：因为是二分图，停在起点一边就是先手败，否则后手败。

如果起点可以不在最大匹配：先手随便走，后手按照匹配边走。这样不可能停在另一边，否则就是一条增广路。

如果起点必须在最大匹配：先手按照固定的一个最大匹配走，随便后手怎么走，最后如果是停在先手一边，说明是$k$条匹配边，$k$条非匹配边，并且终点一定是一个非匹配点，否则先手还能走。异或一下就是一个不包括起点的最大匹配。

这个证明也适用于一般图。