雁过无痕

《编程之美》读书笔记06： 1.13 NIM(3)两堆石头的游戏

问题：

假设有两堆石子，两人轮流取石子，每次可以从一堆取任意个石子，或者从两堆取相等数量的任意个石子，但不能不取。

若先把石子取光的一方为胜方，先取者有什么必胜策略？

若先把石子取光的一方为输方，先取者的策略要进行怎样调整？

记得初中时在学校门口的书店，买到一本《智力游戏中的数学方法》，当时如获至宝。书中提到一个“皇后登山”游戏，就是在空的围棋棋盘上放一个棋子，该棋子每次只能向上或向右或沿对角线向右上方向移动（和国际象棋中的皇后移动相似），可以移动任意格，但不能不移动，两人轮流移动棋子，先将棋子移动到右上角者赢，问先移棋者的必胜策略。书中还提到这个捡石子游戏，并说明这两个游戏是“同构”，必胜策略是相同的。

NIM游戏的“必胜策略”可以概括为：找出最终获胜局面具有的某种性质，对具有该性质的局面的一次操作得到的新局面必然不具有这种性质，而对不具有该性质的局面，总可以通过一次操作，得到一个具有该性质的新局面。假设游戏双方分别为A、B，只要A方能到达具有该性质的某个局面，则B方一定不能到达具有该性质的任意一个局面，从而不能到达获胜局面，因而B方必败，即A方必胜。这种性质可以是对称性（1.11的策略）、每堆数二进制表示各个位的和的奇偶性（1.12的策略）、属于某个集合（1.13的策略）。

对于1.13的NIM游戏，就是寻找这样的一系列关键局面（包括最终获胜局面），总可以通过一次操作将一个非关键局面转为关键局面，而一次操作必将一个关键局面转为非关键局面。因此，从一个关键局面到另一个关键局面至少要（并且能只要）两次操作（“两次操作原则”）。

用<a, b> (a<=b)表示两堆的石子数分别为a、b的局面。对所有的关键局面<x, y>，按x值大小升序排列，最终可用<F_n, G_n >（其中 F_n <= G_n，n>=0）来表示第n个关键局面M_n, 并记<F₀, G₀ >为最终获胜局面M₀（对拿到最后一个获胜的，M₀=<0,0>，而对拿到最后一个输的，M₀=<0,1>），定义T_n=G_n-F_n >=0。每次取石子的操作规则为：从某一堆取任意个石子，或从两堆同时取任意个相同的石子。从M₀开始利用这个规则去除不合的局面。根据规则，显然在已知M₀ M₁ … M_n 情况下，M_n+1 应该满足：F_n+1不与任意一个F_i或G_i（0<=i<=n）相同，T_n+1也不与任意一个T_i（0<=i<=n）相等。因而，可以假设：F_n+1是不与任意一个F_i、G_i（0<=i<=n）相同的最小非负整数，T_n+1是不与任意一个T_i相等的最小非负整数（0<=i<=n）。由该假设得到的<F_n, G_n >即为关键局面，符合“必胜策略”。

（证：由假设，显然有F_i >= T_i (i>=1)

①  对关键局面<F_n, G_n >，设石子较少的那堆为X，较多的那堆为Y：

⑴  A方若在X堆，或在两堆同时取k个石子，则由假设可知，X堆剩余的石子数必然与某个F­_i或某个G_i（0<=i<n）相等，B方可在Y堆取石子，到达另一个关键局面< F_i, G_i >）。

⑵　A方若在Y堆取走k个石子：

⒈  若k <= T_n，由假设必然可找到i，使得T_i=T_n-k（0<=i<n），B方只要在两堆同时取F_n-F_i个石子，即可到达关键局面< F_i, G_i >）。

⒉　若k > T_n，则B堆剩余石子小于F_n，必然与某个F­_i或某个G_i（0<=i<n）相等。

A　若与某个G_i相等，则A堆只要再取F_n-F_i个石子，即可到达关键局面< F_i, G_i >。

B  若与某个F_i相等：

如果F_n>G_i则在则A堆只要再取F_n-G_i个石子，即可到达关键局面< F_i, G_i >；

如果F_n<G_i，必然可以找到j（0<=j<i）使得T_j=F_n-F_i，两堆同时取F_i-F_j个石子到达关键局面< F_j, G_j >。

②  对非关键局面<a, b>，由假设可知，a必与某个F­_i或某个G_i（0<=i<n）相等，因而，可以从另一堆取石子数，到达关键局面< F_i, G_i >；或从关键局面< F_i, G_i >某堆取石子到达非关键局面<a, b>，而由上面的证明可知，可以再通过一次操作，到达某个关键局面< F_j, G_j >。因此，总可以一次操作从非关键局面到达关键局面。

总之，由假设得到的关键局面符合“必胜策略”。）

拿最后一个赢：

由于T₀=0，根据T_n的定义可得T_n=n，刚好是beatty序列，可由beatty序列的通项公式求得F_n的通项公式。

拿最后一个输：

当n>=2时，关键局面与拿最后一赢的相同。

胜利条件为拿最后一个赢时，要找出所有关键局面（即书中的不安全点），最快的办法就是得用通项公式，虽然通项公式有无理数，转成浮点数，引起的误差对结果没多大影响（只有当N极大时，才会使结果不对）。对浮点计算十分昂贵的平台，还是用筛选法，利用“在两个G_i、G_j间的数必然是某个F_k值”，筛选过程只须保留一部分G_n就可以计算出新的F_n。

另外，对关键点<F_n, G_n=F_n+n>，当n>1时，从1到F_n这F_n个数，有n个在F_i，还有F_n-n个在G_j。因而0<F_n-n<n，即有：n< F_n<2*n (n>1时)，在判断<x,y>（y>=x）是否是关键点，先判断是否满足这个不等式，如果满足，才生成第y-x个F值再进行判断。由通项公式可知，

F_n≈int(1.618*n)，可以强化边界条件为：int(n*3/2)和int(n*7/4)。

（书上给出的定理是beatty定理。该定理的证明相当简单，有兴趣的可以google下。另外，上个世纪五六十年代，我国数学家曾在《数学通论》（有网络版）发表过证明，好像还用到了Fibonacci的通项公式。）

void nim(int num) //print all the unsafe points
{
  assert(num>0);
  vector<int> g(num+3);
  int n=2;            // f[2] is between [ g[1]+1 , g[2]-1 ]
  g[1]=2; g[2]=99;   //  g[2] should be initialized with a value above g[1]+1=3.
  int fn=g[1];
  int *low=&g[2];
  int *high=&g[n];
  for( ; n <= num; ++n){
    if( ++fn == *low){
      ++low;
      ++fn;
    }
    *high++ = fn + n;      //f(n)=fn, g(n)=f(n)+n
  }

  for(int i=1;i<=num;++i) {
    //const double SS=(1.0+sqrt(5))/2.0+1.0;
    //if ( (int)(i*SS) != g[i] )   cout<<"Error: " << i<< "\n";
    cout<< g[i]-i<< ","<<g[i]<<"  ";
  }
  cout<<endl;

}



bool nim(int x, int y)     //whether win the game
{
  assert(x>=0);
  assert(y>=0);
  assert( !(x==0 && y==0));
  int ff=x, gg=y, num;
  if (x > y) ff=y, gg=x;   
  num=gg-ff;            
  if ( ff < num || ff > ( num << 1) ) return true;  //win the game

  vector<int> g(num+3);
  g[1]=2; g[2]=99;
  int n=2, fn=g[1];
  int *low=&g[2];
  int *high=&g[n];
  
  for( ; n <= num; ++n){
    if ( ++fn == *low) { ++low; ++fn;}
    *high++ = fn + n;
  }  

 if (*--high == gg) return false;
 else return true;
}