博弈论结论
1.巴什博奕
问题模型:只有一堆n个物品,两个人轮流从这堆物品中取物品,规定每次至少取一个,最多取m个,最后取光者得胜。)
结论:n%(m+1)==0先手必败.否则先手必胜
变形:条件不变,改为最后取光的人输。 结论:(n-1)%(m+1)==0 先手必败,否则必胜
2. 威佐夫博奕
问题模型:有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,
最后取光者得胜。
结论: k=(b-a) (a>b) s = (double )( k * ( sqrt(5.0) + 1 ) / 2 ); s==a 先手必败,否则必胜
3.尼姆博弈
问题模型:有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
结论: 当石子堆数为n堆时,则推广为当对每堆的数目进行亦或之后值为零是必败态。
4.sg函数
对于ICG游戏,我们可以将游戏中每一个可能发生的局面表示为一个点。并且若存在局面i和局面j,且j是i的后继局面
(即局面i可以转化为局面j),我们用一条有向边,从i出发到j,连接表示局面i和局面j的点。则整个游戏可以表示成为
一个有向无环图:
根据ICG游戏的定义我们知道,任意一个无法继续进行下去的局面为终结局面,即P局面(先手必败)。在上图中我们
可以标记所有出度为0的点为P点。
接着根据ICG游戏的两条性质,我们可以逆推出所有点为P局面还是N局面:
因此,对于任意一个ICG游戏,我们可以采取逆推的方法,标记出所有局面是N局面还是P局面。
但仅仅只是标记N、P,所能得到的信息太少,于是我们定义了Sg(Sprague-Grundy)函数:
对于一个游戏可能发生的局面x,我们如下定义它的sg值:
(1)若当前局面x为终结局面,则sg值为0。
(2)若当前局面x非终结局面,其sg值为:sg(x) = mex{sg(y) | y是x的后继局面}。
mex{a[i]}表示a中未出现的最小非负整数。举个例子来说:
mex{0, 1, 2} = 3, mex{1, 2}=0, mex{0,1,3}=2
我们将上图用sg函数表示后,得到:
可以发现,若一个局面x为P局面,则有sg(x)=0;否则sg(x)>0。同样sg值也满足N、P之间的转换关系:
若一个局面x,其sg(x)>0,则一定存在一个后续局面y,sg(y)=0。
若一个局面x,其sg(x)=0,则x的所有后续局面y,sg(y)>0。
由上面的推论,我们可以知道用N、P-Position可以描述的游戏用sg同样可以描述。并且在sg函数中
还有一个非常好用的定理,叫做sg定理:
对于多个单一游戏,X=x[1..n],每一次我们只能改变其中一个单一游戏的局面。则其总局面的sg值
等于这些单一游戏的sg值异或和。
即:
sg(X) = sg(x[1]) xor sg(x[2]) xor … xor sg(x[n])
要证明这一点我们只要证明:
(1) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A,对于任意一个0 <= B < A,总存在一个X的后续局面Y,
使得sg(Y) = B。
(2) 假设sg(x[1]) xor sg(x[2]) xor … xor sg(x[n]) = A,不存在一个X的后续局面Y,使得sg(Y) = A。
下先证明(1):
假设M = A xor
B,设M表示为二进制之后最高位的1为第k位。所以A的第k位为1,B的第k位为0。又因为A的第k位为1,
至少存在一个i,sg(x[i])的第k位也为1。那么一定有sg(x[i]) xor M < sg(x[i]),即一定通过某个操作使x[i]变为x[i’],
且sg(x[i’]) = sg(x[i]) xor M。那么:
sg(x[i’]) xor Other = sg(x[i]) xor M xor Other = M xor A = B
下证明(2):
若sg(X) = A,sg(Y) = A。不妨设我们改变的游戏为x[i],则X=x[1..n], Y=x[1…i’…n]。有sg(x[i]) = sg(x[i’]),
产生矛盾,所以sg(Y)不可能等于A。
5.阶梯博弈
博弈在一列阶梯上进行...每个阶梯上放着自然数个点..两个人进行阶梯博弈...每一步则是将一个集体上的
若干个点( >=1 )移到前面去..最后没有点可以移动的人输..
阶梯博弈也是可以转化成尼姆博弈的.
把所有奇数阶梯看成N堆石子..做nim..把石子从奇数堆移动到偶数堆可以理解为拿走石子..就相当于几个
奇数堆的石子在做Nim..
有一个n*m的棋盘,每次可以取走一个方格并拿掉它右边和上面的所有方格。拿到左下角的格子(1,1)者输,如下图是8*3的
棋盘中拿掉(6,2)和(2,3)后的状态。
结论:答案是除了1*1的棋盘,对于其他大小的棋盘,先手总能赢。
分析:有一个很巧妙的证明可以保证先手存在必胜策略,可惜这个证明不是构造性的,也就是说没有给出先手怎么下才能赢。
证明如下:
如果后手能赢,也就是说后手有必胜策略,使得无论先手第一次取哪个石子,后手都能获得最后的胜利。那么现在假设先手
取最右上角的石子(n,m),接下来后手通过某种取法使得自己进入必胜的局面。但事实上,先手在第一次取的时候就可以和
后手这次取的一样,进入必胜局面了,与假设矛盾。
巧克力游戏的变形:
约数游戏:有1~n个数字,两个人轮流选择一个数字,并把它和它的约数擦去。擦去最后一个数的人赢,问谁会获胜。
分析:类似巧克力游戏,得到结论就是无论n是几,都是先手必胜。
翻棋子游戏:
题意:一个棋盘上每个格子有一个棋子,每次操作可以随便选一个朝上的棋子(x,y),代表第i行第j列的棋子,选择一个形
如(x,b)或(a,y)(其中b < y,a < x)的棋子,然后把它和(x,y)一起翻转,无法操作的人输。
分析:把坐标为(x,y)的棋子看成大小分别为x和y的两堆石子,则本题转化为了经典的Nim游戏,如果难以把棋子看作石
子,可以先把Nim游戏中的一堆石子看成一个正整数,则Nim游戏中的每次操作是把其中一个正整数减小或者删除。