《編程之美》讀書筆記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值大小升序排列，最終可用<Fn, Gn >（其中 Fn <= Gn，n>=0）來(lái)表示第n個(gè)關(guān)鍵局面Mn, 并記<F0, G0 >為最終獲勝局面M0（對(duì)拿到最后一個(gè)獲勝的，M0=<0,0>，而對(duì)拿到最后一個(gè)輸?shù)模?span lang=EN-US>M0=<0,1>），定義Tn=Gn-Fn >=0。每次取石子的操作規(guī)則為：從某一堆取任意個(gè)石子，或從兩堆同時(shí)取任意個(gè)相同的石子。從M0開始利用這個(gè)規(guī)則去除不合的局面。根據(jù)規(guī)則，顯然在已知M0 M1 … Mn 情況下，Mn+1 應(yīng)該滿足：Fn+1不與任意一個(gè)Fi或Gi（0<=i<=n）相同，Tn+1也不與任意一個(gè)Ti（0<=i<=n）相等。因而，可以假設(shè)：Fn+1是不與任意一個(gè)Fi、Gi（0<=i<=n）相同的最小非負(fù)整數(shù)，Tn+1是不與任意一個(gè)Ti相等的最小非負(fù)整數(shù)（0<=i<=n）。由該假設(shè)得到的<Fn, Gn >即為關(guān)鍵局面，符合“必勝策略”。
（證：由假設(shè)，顯然有Fi >= Ti (i>=1)
① 對(duì)關(guān)鍵局面<Fn, Gn >，設(shè)石子較少的那堆為X，較多的那堆為Y：
⑴ A方若在X堆，或在兩堆同時(shí)取k個(gè)石子，則由假設(shè)可知，X堆剩余的石子數(shù)必然與某個(gè)Fi或某個(gè)Gi（0<=i<n）相等，B方可在Y堆取石子，到達(dá)另一個(gè)關(guān)鍵局面< Fi, Gi >）。
⑵ A方若在Y堆取走k個(gè)石子：
⒈ 若k <= Tn，由假設(shè)必然可找到i，使得Ti=Tn-k（0<=i<n），B方只要在兩堆同時(shí)取Fn-Fi個(gè)石子，即可到達(dá)關(guān)鍵局面< Fi, Gi >）。
⒉ 若k > Tn，則B堆剩余石子小于Fn，必然與某個(gè)Fi或某個(gè)Gi（0<=i<n）相等。
A 若與某個(gè)Gi相等，則A堆只要再取Fn-Fi個(gè)石子，即可到達(dá)關(guān)鍵局面< Fi, Gi >。
B 若與某個(gè)Fi相等：
如果Fn>Gi則在則A堆只要再取Fn-Gi個(gè)石子，即可到達(dá)關(guān)鍵局面< Fi, Gi >；
如果Fn<Gi，必然可以找到j（0<=j<i）使得Tj=Fn-Fi，兩堆同時(shí)取Fi-Fj個(gè)石子到達(dá)關(guān)鍵局面< Fj, Gj >。
② 對(duì)非關(guān)鍵局面<a, b>，由假設(shè)可知，a必與某個(gè)Fi或某個(gè)Gi（0<=i<n）相等，因而，可以從另一堆取石子數(shù)，到達(dá)關(guān)鍵局面< Fi, Gi >；或從關(guān)鍵局面< Fi, Gi >某堆取石子到達(dá)非關(guān)鍵局面<a, b>，而由上面的證明可知，可以再通過(guò)一次操作，到達(dá)某個(gè)關(guān)鍵局面< Fj, Gj >。因此，總可以一次操作從非關(guān)鍵局面到達(dá)關(guān)鍵局面。
總之，由假設(shè)得到的關(guān)鍵局面符合“必勝策略”。）
拿最后一個(gè)贏：
|
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，根據(jù)Tn的定義可得Tn=n，剛好是beatty序列，可由beatty序列的通項(xiàng)公式求得Fn的通項(xiàng)公式。
拿最后一個(gè)輸：
|
n
|
0
|
1
|
2
|
3
|
4
|
|
T
|
1
|
0
|
2
|
3
|
4
|
|
F
|
0
|
2
|
3
|
4
|
6
|
|
G
|
1
|
2
|
5
|
7
|
10
|
當(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è)Gi、Gj間的數(shù)必然是某個(gè)Fk值”，篩選過(guò)程只須保留一部分Gn就可以計(jì)算出新的Fn。
另外，對(duì)關(guān)鍵點(diǎn)<Fn, Gn=Fn+n>，當(dāng)n>1時(shí)，從1到Fn這Fn個(gè)數(shù)，有n個(gè)在Fi，還有Fn-n個(gè)在Gj。因而0<Fn-n<n，即有：n< Fn<2*n (n>1時(shí))，在判斷<x,y>（y>=x）是否是關(guān)鍵點(diǎn)，先判斷是否滿足這個(gè)不等式，如果滿足，才生成第y-x個(gè)F值再進(jìn)行判斷。由通項(xiàng)公式可知，
Fn≈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;
}