《編程之美》讀書筆記06： 1.13 NIM(3)兩堆石頭的游戲

問(wèn)題：

假設(shè)有兩堆石子，兩人輪流取石子，每次可以從一堆取任意個(gè)石子，或者從兩堆取相等數(shù)量的任意個(gè)石子，但不能不取。

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

若先把石子取光的一方為輸方，先取者的策略要進(jìn)行怎樣調(diào)整？

記得初中時(shí)在學(xué)校門口的書店，買到一本《智力游戲中的數(shù)學(xué)方法》，當(dāng)時(shí)如獲至寶。書中提到一個(gè)“皇后登山”游戲，就是在空的圍棋棋盤上放一個(gè)棋子，該棋子每次只能向上或向右或沿對(duì)角線向右上方向移動(dòng)（和國(guó)際象棋中的皇后移動(dòng)相似），可以移動(dòng)任意格，但不能不移動(dòng)，兩人輪流移動(dòng)棋子，先將棋子移動(dòng)到右上角者贏，問(wèn)先移棋者的必勝策略。書中還提到這個(gè)撿石子游戲，并說(shuō)明這兩個(gè)游戲是“同構(gòu)”，必勝策略是相同的。

NIM游戲的“必勝策略”可以概括為：找出最終獲勝局面具有的某種性質(zhì)，對(duì)具有該性質(zhì)的局面的一次操作得到的新局面必然不具有這種性質(zhì)，而對(duì)不具有該性質(zhì)的局面，總可以通過(guò)一次操作，得到一個(gè)具有該性質(zhì)的新局面。假設(shè)游戲雙方分別為A、B，只要A方能到達(dá)具有該性質(zhì)的某個(gè)局面，則B方一定不能到達(dá)具有該性質(zhì)的任意一個(gè)局面，從而不能到達(dá)獲勝局面，因而B方必?cái)。?span lang=EN-US>A方必勝。這種性質(zhì)可以是對(duì)稱性（1.11的策略）、每堆數(shù)二進(jìn)制表示各個(gè)位的和的奇偶性（1.12的策略）、屬于某個(gè)集合（1.13的策略）。

對(duì)于1.13的NIM游戲，就是尋找這樣的一系列關(guān)鍵局面（包括最終獲勝局面），總可以通過(guò)一次操作將一個(gè)非關(guān)鍵局面轉(zhuǎn)為關(guān)鍵局面，而一次操作必將一個(gè)關(guān)鍵局面轉(zhuǎn)為非關(guān)鍵局面。因此，從一個(gè)關(guān)鍵局面到另一個(gè)關(guān)鍵局面至少要（并且能只要）兩次操作（“兩次操作原則”）。

用<a, b> (a<=b)表示兩堆的石子數(shù)分別為a、b的局面。對(duì)所有的關(guān)鍵局面<x, y>，按x值大小升序排列，最終可用<F_n, G_n >（其中 F_n <= G_n，n>=0）來(lái)表示第n個(gè)關(guān)鍵局面M_n, 并記<F₀, G₀ >為最終獲勝局面M₀（對(duì)拿到最后一個(gè)獲勝的，M₀=<0,0>，而對(duì)拿到最后一個(gè)輸?shù)模?span lang=EN-US>M₀=<0,1>），定義T_n=G_n-F_n >=0。每次取石子的操作規(guī)則為：從某一堆取任意個(gè)石子，或從兩堆同時(shí)取任意個(gè)相同的石子。從M₀開始利用這個(gè)規(guī)則去除不合的局面。根據(jù)規(guī)則，顯然在已知M₀ M₁ … M_n 情況下，M_n+1 應(yīng)該滿足：F_n+1不與任意一個(gè)F_i或G_i（0<=i<=n）相同，T_n+1也不與任意一個(gè)T_i（0<=i<=n）相等。因而，可以假設(shè)：F_n+1是不與任意一個(gè)F_i、G_i（0<=i<=n）相同的最小非負(fù)整數(shù)，T_n+1是不與任意一個(gè)T_i相等的最小非負(fù)整數(shù)（0<=i<=n）。由該假設(shè)得到的<F_n, G_n >即為關(guān)鍵局面，符合“必勝策略”。

（證：由假設(shè)，顯然有F_i >= T_i (i>=1)

①  對(duì)關(guān)鍵局面<F_n, G_n >，設(shè)石子較少的那堆為X，較多的那堆為Y：

⑴  A方若在X堆，或在兩堆同時(shí)取k個(gè)石子，則由假設(shè)可知，X堆剩余的石子數(shù)必然與某個(gè)F­_i或某個(gè)G_i（0<=i<n）相等，B方可在Y堆取石子，到達(dá)另一個(gè)關(guān)鍵局面< F_i, G_i >）。

⑵　A方若在Y堆取走k個(gè)石子：

⒈  若k <= T_n，由假設(shè)必然可找到i，使得T_i=T_n-k（0<=i<n），B方只要在兩堆同時(shí)取F_n-F_i個(gè)石子，即可到達(dá)關(guān)鍵局面< F_i, G_i >）。

⒉　若k > T_n，則B堆剩余石子小于F_n，必然與某個(gè)F­_i或某個(gè)G_i（0<=i<n）相等。

A　若與某個(gè)G_i相等，則A堆只要再取F_n-F_i個(gè)石子，即可到達(dá)關(guān)鍵局面< F_i, G_i >。

B  若與某個(gè)F_i相等：

如果F_n>G_i則在則A堆只要再取F_n-G_i個(gè)石子，即可到達(dá)關(guān)鍵局面< F_i, G_i >；

如果F_n<G_i，必然可以找到j（0<=j<i）使得T_j=F_n-F_i，兩堆同時(shí)取F_i-F_j個(gè)石子到達(dá)關(guān)鍵局面< F_j, G_j >。

②  對(duì)非關(guān)鍵局面<a, b>，由假設(shè)可知，a必與某個(gè)F­_i或某個(gè)G_i（0<=i<n）相等，因而，可以從另一堆取石子數(shù)，到達(dá)關(guān)鍵局面< F_i, G_i >；或從關(guān)鍵局面< F_i, G_i >某堆取石子到達(dá)非關(guān)鍵局面<a, b>，而由上面的證明可知，可以再通過(guò)一次操作，到達(dá)某個(gè)關(guān)鍵局面< F_j, G_j >。因此，總可以一次操作從非關(guān)鍵局面到達(dá)關(guān)鍵局面。

總之，由假設(shè)得到的關(guān)鍵局面符合“必勝策略”。）

拿最后一個(gè)贏：

由于T₀=0，根據(jù)T_n的定義可得T_n=n，剛好是beatty序列，可由beatty序列的通項(xiàng)公式求得F_n的通項(xiàng)公式。

拿最后一個(gè)輸：

當(dāng)n>=2時(shí)，關(guān)鍵局面與拿最后一贏的相同。

勝利條件為拿最后一個(gè)贏時(shí)，要找出所有關(guān)鍵局面（即書中的不安全點(diǎn)），最快的辦法就是得用通項(xiàng)公式，雖然通項(xiàng)公式有無(wú)理數(shù)，轉(zhuǎn)成浮點(diǎn)數(shù)，引起的誤差對(duì)結(jié)果沒(méi)多大影響（只有當(dāng)N極大時(shí)，才會(huì)使結(jié)果不對(duì)）。對(duì)浮點(diǎn)計(jì)算十分昂貴的平臺(tái)，還是用篩選法，利用“在兩個(gè)G_i、G_j間的數(shù)必然是某個(gè)F_k值”，篩選過(guò)程只須保留一部分G_n就可以計(jì)算出新的F_n。

另外，對(duì)關(guān)鍵點(diǎn)<F_n, G_n=F_n+n>，當(dāng)n>1時(shí)，從1到F_n這F_n個(gè)數(shù)，有n個(gè)在F_i，還有F_n-n個(gè)在G_j。因而0<F_n-n<n，即有：n< F_n<2*n (n>1時(shí))，在判斷<x,y>（y>=x）是否是關(guān)鍵點(diǎn)，先判斷是否滿足這個(gè)不等式，如果滿足，才生成第y-x個(gè)F值再進(jìn)行判斷。由通項(xiàng)公式可知，

F_n≈int(1.618*n)，可以強(qiáng)化邊界條件為：int(n*3/2)和int(n*7/4)。

（書上給出的定理是beatty定理。該定理的證明相當(dāng)簡(jiǎn)單，有興趣的可以google下。另外，上個(gè)世紀(jì)五六十年代，我國(guó)數(shù)學(xué)家曾在《數(shù)學(xué)通論》（有網(wǎng)絡(luò)版）發(fā)表過(guò)證明，好像還用到了Fibonacci的通項(xiàng)公式。）

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;
}