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

（给算法爱好者加星标，修炼编程内功）

作者：obshilu

https://blog.csdn.net/ojshilu/article/details/16812173

取石子游戏是一个古老的博弈游戏，据说是发源于中国，它是组合数学领域的一个经典问题。

它有许多不同的玩法，基本上是两个玩家，玩的形式是轮流抓石子，胜利的标准是抓走了最后的石子。

玩家设定： 先取石子的是玩家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<cmath>
#include<iostream>
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 << "(" << out << ", " << out+i << ")" << endl;
    }
}

bool judge(int a, int b)
{
    int k = a/m;
    if ( a == int(k*m) )
    {
        if( b == a + k )
            return true;
    }
    else if( a == int((k+1)*m) )
    {
        if(b == a + k + 1 )
            return true;
    }
    return false;
}

void main()
{
    int a, b;
    cin >> a >> b;
    cout << judge(a,b) << endl;
}

玩家的策略：

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

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

推荐关注「算法爱好者」，修炼编程内功

点赞和在看就是最大的支持❤️