博弈论入门

几种经典博弈的总结

巴什博弈：

经典的巴什博奕模型：

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个，最后取光者得胜。

解决思路：
当n=m+1时，由于一次最多只能取m个，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜，所以当一方面对的局势是n%(m+1)=0时，其面临的是必败的局势。所以当n=（m+1)r+s，（r为任意自然数，s≤m)时,如果先取者要拿走s个物品，如果后取者拿走x（≤m)个，那么先取者再拿走m+1-x个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜。
结论：当n%(m+1)=0时，在最优策略下，后手必胜。

变形
最后取光的人输…
结论：当n%(m+1)=1 时，在最优策略下，后手必胜。

为什么？因为赢得人肯定会先取完(n - 1)个石子。

巴什博奕的简单变形：

只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取a，最多取b个，最后取光者得胜。

威佐夫博弈：

两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

参考博客

inline bool check(int x, int y) {
	int a = min(x, y), b = max(x, y);
	double c = (double)abs(b - a);
	double r = (sqrt(5.0) + 1) / 2;
	int tmp = int(c * r);
	if (a == tmp) return 0; //后手必胜 
	else return 1; //先手必胜 
}

尼姆博奕

有N堆石子。A B两个人轮流拿，A先拿。每次只能从一堆中取若干个，可将一堆全取走，但不可不取，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N及每堆石子的数量，问最后谁能赢得比赛。

参考博客

斐波那契博弈

有一堆个数为n的石子，游戏双方轮流取石子，满足：

（1）先手不能在第一次把所有的石子取完；

（2）之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间（包含1和对手刚取的石子数的2倍）。 约定取走最后一个石子的人为赢家。

结论：当n为Fibonacci数时，先手必败。即存在先手的必败态当且仅当石头个数为Fibonacci数。

公平组合博弈（ICG）

每次只能走到必胜点的是必败点，可以走到必败点的是必胜点。