雁過無痕

《編程之美》讀書筆記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;
}