两人取石子游戏 组合数学-博弈问题

    取石子游戏是一个古老的博弈游戏,据说是发源于中国,它是组合数学领域的一个经典问题。它有许多不同的玩法,基本上是两个玩家,玩的形式是轮流抓石子,胜利的标准是抓走了最后的石子。


玩家设定: 先取石子的是玩家A,后取石子的是玩家B。


经典的三种玩法:

一、Bash Game,有1堆含n个石子,两个人轮流从这堆物品中取物,规定每次至少取1个,最多取m个。取走最后石子的人获胜。

二、Nimm Game,有k堆各n个石子,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限。取走最后石子的人获胜。

三、Wythoff Game,有2堆各n个石子,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取1个,多者不限。取走最后石子的人获胜。


平衡状态的概念:

    引入一个概念,平衡状态,又称作奇异局势。当面对这个局势时则会失败。任意非平衡态经过一次操作可以变为平衡态。每个玩家都会努力使自己抓完石子之后的局势为平衡,将这个平衡局势留给对方。因此,玩家A能够在初始为非平衡的游戏中取胜,玩家B能够在初始为平衡的游戏中取胜。


玩法一(1堆n个石子每次最多取m个):

    最后一个奇异局势是n=(0)。一种奇异局势是,n=(m+1),那么无论我取走多少个,对方都能够一次取走剩余所有的物品取胜。

奇异局势的判定:

    一般的奇异局势是n=(m+1)*i,其中i为自然数,即n%(m+1)=0,面对这种情况无论我怎么取,对方总可以将其恢复为n%(m+1)=0,一直到n=(m+1)局势。

玩家的策略:

    就是把当前面对的非奇异局势变为奇异局势留给对方。如果当前的石子个数为(m+1)*i+s,那么就将s个石子取走,使其达到奇异局势。


玩法二(k堆石子每次只从1堆取):

    最后一个奇异局势是(0,0...,0)。另一个奇异局势是(n,n,0...0),只要对手总是和我拿走一样多的物品,最后会面对(0,0...,0)。

奇异局势的判定:

    对于一个普通的局势,如何判断其是不是奇异局势?对于一个局势(s1,s2,...sk),对所有石子个数做位的异或运算,s1^s2^s3^...^sk,如果结果为0,那么局势(s1,s2,...sk)就是奇异局势(平衡),否则就不是(非平衡)。

    从二进制位的角度上说,奇异局势时,每一个bit位上1的个数都是偶数。

玩家的策略:

    就是把面对的非奇异局势变为奇异局势留给对方。也就是从某一堆取出若干石子之后,使得每一个bit位上1的个数都变为偶数,这样的取法一般不只有一种。可以将其中一堆的石子数变为其他堆石子数的位异或运算的值(如果这个值比原来的石子数小的话)。


玩法三(2堆石子每次从一或两堆取一样数目的石子):

    最后一个奇异局势是(0,0)。紧接着的奇异局势有(1,2),(3,5),(4,7),(6,10)......

    现在把它们看成一个奇异局势组成的序列(0,0),(1,2),(3,5),(4,7),(6,10)......

奇异局势的判定:

    我们会发现这个序列的规律,设序列第k个奇异局势元素为(Ak,Bk),k为自然数。那么,初始条件k=0时是,A0=B0=0,递推关系为下一个奇异局势的Ak是未在前面出现过的最小自然数,且Ak = Bk + k。

    上面发现了奇异局势的递推公式,那么给出一个局势,如何判断其是否是奇异局势呢?

黄金分割数:数学真奇妙,竟然发现,这个序列跟黄金分割数有关系。黄金分割数是2/(1+sqrt(5))=(sqrt(5)-1)/2,其小数约等于0.61803398875,其倒数是(1+sqrt(5))/2,约等于1.61803398875。

    这个奇异局势的序列的通项公式可以表示为:

  Ak = [k*(1+sqrt(5.0)/2]

  Bk = Ak + k  

  其中k=0,1,2,...,n ,方括号表示int取整函数。

    有了这个通项式子,逆向的,对于某一个局势,只需要判断其A是否是黄金分割数的某个k的倍数,然后再确认B是否等于A+k即可。

这里写了一个简单的判断程序:

#include
#include
using namespace std;
const double m = (1+sqrt(5.0))/2;

void display()
{
	int i;
	int out;
	for(i=0;i<30;i++)
	{
		out = int(m*i);
		cout<<"("<>a>>b;
	cout<

玩家的策略:

    就是把面对的非奇异局势变为奇异局势留给对方。也就是说,玩家必须知道临近的奇异局势是什么,然后把当前局势变成奇异局势。


问题出现在:编程之美。组合数学。

游戏的一个变种:两个人轮流报数,每次至少报一个,最多报十个,谁能报到100者胜。

你可能感兴趣的