博弈论一般性解法总结

先是适用范围和限制条件:

甲乙两人取石子游戏及其类似的游戏;每一步只能对某一堆石子进行操作;每一步操作的限制,只与这堆石子的数目或一些常数有关;操作在有限步内终止,并不会出现循环;谁无法继续操作,谁就是输家。（反过来也行，不过为了方便后面的说明才这样定义）

然后做一些定义：

用一个 n 元组(a1, a2, …, an),来描述游戏过程中的一个局面，局面用S表示；用符号#S,表示局面 S 所对应的二进制数；定义集合 g(#S)为局面S的下一步可能出现的局面的二进制数的集合；令非负整数集为全集,集合 G(x)表示集合 g(x)的补集；定义函数 f(n)：f(n)=min{G(n)},即 f(n)等于集合 G(n)中的最小数；

解法规律：

设局面 S=(a1, a2, …, an)，则ans=f(a1)+f(a2)+…+f(an)，此处的“+”为一位的二进制加法；

若ans=0，则后行者必胜，反之先行者胜。

举个例子：

甲乙从n堆石头a1,a2,a3,…,an中取石头，每次只能且必须从其中任意一堆中取不少于1个石头（可以全部取完），谁无法继续取，谁则输。若甲先取，则问甲是否必胜。

分析： 假设给定局面为（3,3,7,4）共4堆石头。 g(0)={},G(0)={0,1,2,3…},f(0)=0;（没有下一个局面） g(1)={0},G(0)={1,2,3…},f(1)=1;（取1个，剩0个） g(2)={0,1},G(0)={2,3,4…},f(2)=2;（取1个，剩1个；取2个，剩0个） g(3)=(0,1,2),G(0)={3,4,5…},f(3)=3; ……….（以此类推） 最后得：

x1234567f(x)1234567

ans=f(3)+f(3)+f(7)+f(4)=1，因此甲必胜。