《編程之美》讀書筆記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值大小升序排列,最終可用<Fn, Gn >(其中 Fn <= Gn,n>=0)來表示第n個關鍵局面Mn, 并記<F0, G0 >為最終獲勝局面M0(對拿到最后一個獲勝的,M0=<0,0>,而對拿到最后一個輸的,M0=<0,1>),定義Tn=Gn-Fn >=0。每次取石子的操作規則為:從某一堆取任意個石子,或從兩堆同時取任意個相同的石子。從M0開始利用這個規則去除不合的局面。根據規則,顯然在已知M0 M1 … Mn 情況下,Mn+1 應該滿足:Fn+1不與任意一個Fi或Gi(0<=i<=n)相同,Tn+1也不與任意一個Ti(0<=i<=n)相等。因而,可以假設:Fn+1是不與任意一個Fi、Gi(0<=i<=n)相同的最小非負整數,Tn+1是不與任意一個Ti相等的最小非負整數(0<=i<=n)。由該假設得到的<Fn, Gn >即為關鍵局面,符合“必勝策略”。
(證:由假設,顯然有Fi >= Ti (i>=1)
① 對關鍵局面<Fn, Gn >,設石子較少的那堆為X,較多的那堆為Y:
⑴ A方若在X堆,或在兩堆同時取k個石子,則由假設可知,X堆剩余的石子數必然與某個Fi或某個Gi(0<=i<n)相等,B方可在Y堆取石子,到達另一個關鍵局面< Fi, Gi >)。
⑵ A方若在Y堆取走k個石子:
⒈ 若k <= Tn,由假設必然可找到i,使得Ti=Tn-k(0<=i<n),B方只要在兩堆同時取Fn-Fi個石子,即可到達關鍵局面< Fi, Gi >)。
⒉ 若k > Tn,則B堆剩余石子小于Fn,必然與某個Fi或某個Gi(0<=i<n)相等。
A 若與某個Gi相等,則A堆只要再取Fn-Fi個石子,即可到達關鍵局面< Fi, Gi >。
B 若與某個Fi相等:
如果Fn>Gi則在則A堆只要再取Fn-Gi個石子,即可到達關鍵局面< Fi, Gi >;
如果Fn<Gi,必然可以找到j(0<=j<i)使得Tj=Fn-Fi,兩堆同時取Fi-Fj個石子到達關鍵局面< Fj, Gj >。
② 對非關鍵局面<a, b>,由假設可知,a必與某個Fi或某個Gi(0<=i<n)相等,因而,可以從另一堆取石子數,到達關鍵局面< Fi, Gi >;或從關鍵局面< Fi, Gi >某堆取石子到達非關鍵局面<a, b>,而由上面的證明可知,可以再通過一次操作,到達某個關鍵局面< Fj, Gj >。因此,總可以一次操作從非關鍵局面到達關鍵局面。
總之,由假設得到的關鍵局面符合“必勝策略”。)
拿最后一個贏:
n
|
0
|
1
|
2
|
3
|
4
|
T
|
0
|
1
|
2
|
3
|
4
|
F
|
0
|
1
|
3
|
4
|
6
|
G
|
0
|
2
|
5
|
7
|
10
|
由于T0=0,根據Tn的定義可得Tn=n,剛好是beatty序列,可由beatty序列的通項公式求得Fn的通項公式。
拿最后一個輸:
n
|
0
|
1
|
2
|
3
|
4
|
T
|
1
|
0
|
2
|
3
|
4
|
F
|
0
|
2
|
3
|
4
|
6
|
G
|
1
|
2
|
5
|
7
|
10
|
當n>=2時,關鍵局面與拿最后一贏的相同。
勝利條件為拿最后一個贏時,要找出所有關鍵局面(即書中的不安全點),最快的辦法就是得用通項公式,雖然通項公式有無理數,轉成浮點數,引起的誤差對結果沒多大影響(只有當N極大時,才會使結果不對)。對浮點計算十分昂貴的平臺,還是用篩選法,利用“在兩個Gi、Gj間的數必然是某個Fk值”,篩選過程只須保留一部分Gn就可以計算出新的Fn。
另外,對關鍵點<Fn, Gn=Fn+n>,當n>1時,從1到Fn這Fn個數,有n個在Fi,還有Fn-n個在Gj。因而0<Fn-n<n,即有:n< Fn<2*n (n>1時),在判斷<x,y>(y>=x)是否是關鍵點,先判斷是否滿足這個不等式,如果滿足,才生成第y-x個F值再進行判斷。由通項公式可知,
Fn≈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;
}

