1.游戏规则
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子(至少取1个)。
每次有两种不同的取法,规则如下:
1.一是可以在任意的一堆中取走任意多的石子;
2.二是可以在两堆中同时取走相同数量的石子。
最后把石子全部取完者为胜者,假设双方都采取最好的策略,给定初始数量,你是否有必胜的把握?
2.分析
为方便描述,设f[x,y]表示两堆石子数量分别为x,y,且你先取。
1.f[x,y]=1表示必胜
2.f[x,y]=0表示必败
3.石堆没有顺序优先级,所以f[x,y]=f[y,x]
2.1首先分析3种特殊情况
1.两堆石子数量一样,两堆都取n个,必胜,得f[n,n]=1
2.只有一堆石子,一堆取n个,必胜,得f[n,0]=f[0,n]=1
3.石子数量为f[2,1],只能取(1,0),(2,0),(1,1),剩下石子为(1,1),(0,1),(1,0)对方都能胜,所以必败,得f[2,1]=f[1,2]=0,称此为奇异局势(必败局势)。
2.2列出前面的几种情况如下:
可以得到如下规律:
- 奇异局势有f[2,1],f[5,3],f[7,4],f[10,6]...,必败
- 蓝色为先取的数量,一次就可以将状态转为奇异局势,必胜
- f[x+1,x],f[1,x],f[2,x]都可以转为f[2,1],必胜
- f[x+2,x],f[3,x],f[5,x]都可以转为f[5,3],必胜
- f[x+k,x]可以转化为f[x1,y1],x1-y1=k的奇异局势,而且f[x1,x],f[y1,x]也可以转化为f[x1,y1]
即奇异局势为f[x,y],|x-y|=1,2,3,4,x,y为正整数,且x,y不能重复出现
结论:如果两个人都采取最优策略,面对非奇异局势,先拿必胜;面对奇异局势,后拿必胜。
3.理论推广
这个其实是经典的威佐夫博弈问题,但首先我们先介绍另一个定理,贝蒂定理。
3.1贝蒂定理
3.2回归威佐夫问题
3.3如何快速判断
3.4例题
poj1067:http://poj.org/problem?id=1067
3.5代码实现
const double q = (1 + sqrt(5.0)) / 2.0;
bool isWythoff(int a, int b) {
int t;
if (a > b) t = a, a = b, b = t;
return (int) ((b - a) * q) == a;
}
关注我,涨知识,公众号:几何思维