Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 算法 » 

取石子游戏

取石子是一种很有意思的游戏,一般给你若干堆石子,两个人根据指定规则轮流从中取若干石子,规定最后取光石子玩家获胜,假定双方玩家都采取最优策略,问先手是否有什么必胜策略。这个游戏看似简单,实则蕴含深刻的数学原理,本文将分析几种常见的取石子游戏的玩法。

问题一

题目:有一排石头共n个,两个玩家轮流从中取走若干石头,每个玩家每次可以选择任意的一个石头,或者两个相邻的石头,最后取光石头的玩家获胜。石头在游戏过程中位置不变,即取走一颗石头,这颗石头左右两边的石头不会变得相邻。

这个游戏非常简单。只需要根据石头的数量进行分类判断即可。

  • 如果只有1个或2个石头,先取者直接全部取走,获得胜利。
  • 如果石头数量大于2,先取者根据石头数量是奇数还是偶数,分别取走最中间的1个或2个,然后每次等后取者取走石头后,在其相对称的位置取走相同数量的石头,于是先取者必胜。

问题二

题目:有一堆石头共n个,两个玩家轮流从中取走若干石头,每次至少取1个,至多取m个,最后取光者胜。

这个问题又称为巴什博奕(Bash Game)。
由于至少取1个,至多取m个,那么如果只有m+1个石头,那么无论先取者取多少石头,后取者都能够一次性拿走剩下的石头从而取胜。于是我们可以从m+1这个特殊的数字入手:

  • 如果石头的数量是m+1的倍数,那么先取者取任意的x个,后取者总可以取m+1-x个使得剩下的石头数量仍是m+1的倍数,最终后取者拿走最后的石头。后取者必胜。
  • 如果石头的数量不是m+1的倍数,那么先取者可以拿走一定的石头使得剩下的石头数量是m+1的倍数,从而根据上面的策略获胜。先取者必胜。

问题三

题目:有两堆石头,两个玩家轮流从中取走若干石头,每次要么从一堆中取任意多的石头,要么从两堆中取相同数量的石头,至少一个,多则不限。最后取光者胜。

这个问题又称为威佐夫博奕(Wythoff Game)。
我们用(an, bn)表示一个局势,an和bn分别表示两堆石头的数量,称先手必胜的局势为安全局势,否则为不安全局势。我们考虑所有可能的局势寻找规律。
首先(x,x)是一个安全局势,因为可以同时在两堆石头中拿走x颗。
然后出现的(1,2)是一个不安全局势,先取者是必败的。那么可以一步到达(1,2)的局势都是安全局势,即(1,x)、(2,x)和(1+x,2+x)都是安全局势,它们的特点是要么包含1或2,要么是两数字之差为1。
下一个不安全局势是(3,5),因为前面已经确定了数字中包含1或2的必定为安全局势,下一个数字即为3;同时两数字之差为1的也是安全局势,于是另一个数字与3的差至少为2,于是考虑(3,5)。通过分析,其也为不安全局势。那么可以一步到达(3,5)的局势都是安全局势,即(3,x)、(5,x)和(3+x,5+x),他们的特点是要么包含3或5,要么两数字之差为2。
可以知道,下一个不安全局势为(4,7)。即(an,bn)为不安全局势的规律是:

  • 对于n=1,a1 = 1, b1 = 2
  • 对于n>1,an为前面没有出现过的第一个数字,而bn = an + n。

于是可以通过从底向上遍历,判断所给的局势是否为不安全局势。如果是,则先手必败,否则先手必胜。

另外,使用遍历的方法复杂度较高,根据数学上的Beatty定理,我们可以知道(an,bn)的通项公式为:

an = [a * n], bn = [b * n]

其中a = (1 + sqrt(5)) / 2, b = (3 + sqrt(5)) / 2,[]为下取整函数。

那么,我们可以使用如下函数判断一个局势是否为安全局势:

bool wythoff(int n, int m)
{
	double a = (1 + sqrt(5)) / 2, b = (3 + sqrt(5)) / 2;
	if (n > m) swap(n, m);
	return n == floor((m - n) * a);
}

问题四

题目:有三堆石头,两个玩家轮流从中取走若干石头,每次可以从某一堆取至少1个石头,多则不限。最后取光者胜。

这个问题又称尼姆博奕(Nimm Game)。
我们用(x1, x2, x3)表示一个局势,显然(0, 0, 0)是一个不安全局势,因为先取者没得取石头,相当于是上一轮的后取者取光了石头,即后取者得胜。注意到0 ^ 0 ^ 0 = 0,其中^表示异或。下面我们将证明,所有满足x1 ^ x2 ^ x3 = 0的局势都是不安全局势。

  • 对于满足x1 ^ x2 ^ x3 = 0的三个数,对其中任何一个数字的任何改变,都将导致其异或值不再为0。因为改变一个数字,至少改变其中的某一位,要么由0变1,要么由1变0。由于原来三个数字异或值为0,则原来这一位上的异或也是0,现在改变了一位,则这一位异或的结果不再为0,即三个数异或的结果也不再是0。
  • 对于不满足x1 ^ x2 ^ x3 = 0的三个数,我们可以对其中的某个数做一定的修改,使其异或值变为0。假设x1 < x2 < x3,则我们只需将x3变为x1^x2(即x3中减去x3 – (x1^x2))即可,此时x1 ^ x2 ^ x3 = x1 ^ x2 ^ (x1 ^ x2) = 0。

有了以上两点,则有:

  • 如果先手者遇到x1 ^ x2 ^ x3 = 0的局势,则其从任意一堆石头拿走了任意数量的石头之后,新的局势中x1 ^ x2 ^ x3肯定不再为0,因为(0, 0, 0)的异或值为0,故新的局势不可能是(0, 0, 0),即其不能在这一步中取得胜利。而其完成之后,后手者可以在数量为x3的石头堆中拿走(x3 – (x1^x2))个(假设x1 < x2 < x3),则新的局势中三个数异或重新为0。故后手者最终肯定在某一次取完石头之后,局势变为(0, 0, 0),取得胜利。后手必胜。
  • 如果先手者遇到x1 ^ x2 ^ x3 != 0的局势,则只要用一步将其变为x1 ^ x2 ^ x3 = 0的局势,然后采用上述策略,则最终必胜。

本题可以推广到n堆石头的情形,只要n个数异或值为0,先手必败,否则先手必胜。

 

上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论