王姿婷 李建華

(1.海南省文昌中學 571300；2.北京師范大學數(shù)學科學學院 數(shù)學與復雜系統(tǒng)教育部重點實驗室 100875)

3.2 威索夫游戲

游戲介紹：

威索夫(W.A.Wythoff)游戲⑥是一種重要的組合游戲形式，其規(guī)則為：兩人輪流從甲乙兩堆棋子中移走一些棋子，移走棋子的方式可以以下方式中的一種：

1.從任意一堆中移走不少于1顆的棋子；

2.從甲乙兩堆棋子中同時移走相同數(shù)目(不少于1顆)的棋子；

游戲的目標是：誰移走最后一顆棋子誰就可以獲勝.

游戲中的數(shù)學：

很明顯，這與兩堆的經(jīng)典NIM游戲已有很大不同，由于這一游戲能夠從兩堆中同時取走相同數(shù)目的棋子，故原先兩堆相等的狀態(tài)不再是平衡的了，因為這種局勢下能夠在一次拿取后又回來，因此并不能穩(wěn)固地由一方控制.若我們假定兩堆的棋子的數(shù)目分別是p顆和q顆，從后繼局勢的角度來考慮，會發(fā)現(xiàn)先手在兩堆石子(p,q)中(不妨總設為p≤q)的取法似乎有很多種，又由于每一方都不知道對方會如何取棋子，故局面變數(shù)似乎挺大的，但真的只能走一步算一步嗎？

可知，(3,5)和(1,2)一樣，也是后手有利的局勢.于是現(xiàn)在又可以排除掉(3,p)、(5,p)以及除(3,5)外兩堆棋子數(shù)差值為2的局勢了，接下來可以考慮差值為3的，先前還未排除過含有4的局勢，故現(xiàn)在可以考慮分析(4,7)

經(jīng)過不多次的試探，我們可以很快發(fā)現(xiàn)，(1,2)，(3,5)，(4,7)，(6,10)，…都是后手有利的局勢.當然，隨著棋子數(shù)目的逐漸增多，后繼局勢的數(shù)量會迅速增加，一直這樣分析其后繼局勢顯然不現(xiàn)實.不過我們現(xiàn)在可以回過頭看看我們手頭已經(jīng)有的東西.

我們容易發(fā)現(xiàn)，從兩堆棋子顆數(shù)差值的角度確實能夠收有成效，另外我們在確定一個后手有利的局勢之后能夠排除掉一些數(shù)字已使用過的局勢，然后由未使用過的數(shù)字及差值能夠構造出新的局勢，往往這個局勢就是一個后手有利的局勢.下面我們可以嘗試檢驗我們這一想法：

我們假設差值為小于k的后手有利的局勢已得出，且尚未被使用過的數(shù)字為s，下面我們驗證(s,s+k)也是一個后手有利的局勢.

首先分類討論先手可能做出的拿取操作：

1.若先手從兩堆中同時拿取若干棋子，使其變?yōu)?t,t+k)，注意到，由于t

2.若先手在堆數(shù)為s的棋子中進行拿取，使其變?yōu)?t,s+k)，由于此時兩堆棋子的數(shù)目大于k并不是已找出的后手有利狀態(tài)，且t

3.若先手在堆數(shù)為s+k的棋子中進行拿取，使其變?yōu)?s,w)，若此時的ws，那么由于w

檢驗完畢.

借用歸納假設，我們知道，前面觀察得到的尋找后手有利的局勢的方法確實能夠幫我們由小到大遍歷出所有的后手有利的局勢！而且能夠知道，這些后手有利的局勢能夠穩(wěn)固地由后手控制，因此正是我們找尋的制勝關鍵局勢！

3.3 皇后登山游戲

游戲介紹：

“皇后登山”游戲是由 Rufus Isaacs 在 1960 年左右提出來的[注]Wythoff's game at Cut-the-knot.與前面介紹的取子游戲不同，這一游戲是將目標棋子按約定的方式進行移動，移動到目標位置即算成功.具體的規(guī)則是：在下圖7所示的有18×18=324個小的正方形格子的圍棋盤中，將在右上頂角處的格子設為目標位置，并用“ ▲” 這個符號標記，代表山頂.游戲雙方分別為A和B：首先，第一個游戲者A，把一位“皇后”(可以是一枚棋子或其他小物件)放在棋盤的最下面一行或最左邊一列的某個格子里(見灰色區(qū)域)，放好后就可以輪到B走了，之后兩人輪流決策，決策規(guī)則是：“皇后”只能向上、向右或向右上方(45度方向)斜著走，每次可以走的格數(shù)不限，但不得倒退，也不能不走；誰先把“皇后”移進目標位置即標有“▲ ”的山頂位置就算獲勝.

圖7

游戲中的數(shù)學：

上述規(guī)則其實相當于給定目標位置后就確定了上與右兩個正方向作為前進的方向，并允許斜向的前進方式，而移動的規(guī)則相當于規(guī)定整個過程不能后退或停滯不前，以“皇后”所在的位置作為左下角直指山頂所形成的線為對角線的矩形就是下一步“皇后”尚有可能移動到的范圍，隨著游戲的進行，這樣的矩形會越來越小，直至成為長或寬為1的矩形時，下一位玩家就可將其移至山頂，當然，若其間此矩形成了正方形，也即某一方使“皇后”恰好放置于45度方向能直指山頂?shù)奈恢脮r，下一方亦可直接到達山頂.于是我們不妨現(xiàn)在簡化版的小棋盤上進行分析，如圖8.而剛剛分析到的危險位置我們就可以用陰影部分將其呈現(xiàn)出來.

圖8

顯然，如果對手不慎把“皇后”走進圖8中帶陰影的格子里，由規(guī)則我們就知道，接下來，我們只需要一步就能夠把“皇后”移動至到山頂而獲勝，因此，任何一方都應該避免將“皇后”移動到這些危險位置也即有陰影的格子里，而且應該盡可能地壓制住對手，迫使他不得不把“皇后”走到有陰影的格子里去.而這一點，某些特殊位置似乎是可以辦到的.

例如，細心的讀者可以從圖8中看出，如果我方能設法將“皇后”移動至標號為①或②的格子里，那么對手就只能把“皇后”移動進有陰影的格子里了；換句話說，只要占領了①或②，且以后的走法得當，就必穩(wěn)操勝券.所以①和②這兩個關鍵位置的意義，像極了軍事上的“制高點”[注]倪進，朱明書.數(shù)學與智力游戲[M].大連：大連理工大學出版社，2008.4.pp. 135-149.，一旦占據(jù)便可居高臨下，一夫當關.

可是，怎樣做才能占領①或②呢？這時候相當于將原先搶占山頂?shù)膯栴}化歸為了搶占①或②這兩個位置，它們便變成了新的“山頂”，同樣的分析原理，如果對手把“皇后”走進有虛線的方格里，則我方就能在下一步占領①或②，從而最終獲勝，參看圖9.那么，怎么樣迫使對方不得不把“皇后”走進有虛線的方格呢？于是我們又將問題化歸為占領③或④這對關鍵位置的任一格了！

圖9

我們能夠知道，只要棋盤足夠大且對稱，這樣的關鍵位置總是成對出現(xiàn)的，而且耐心的話總可以能一對一對的找出來.所以我們只需要繼續(xù)運用上述分析方法進行遞推，就可以最終得到本游戲中18×18的圍棋盤上的全部關鍵位置，結果參看圖10.

從圖10中我們可以看到，若給由各個關鍵位置出發(fā)的橫縱斜三線畫上虛線，可以看到，所有的虛線將整個棋盤的格點無一遺漏地覆蓋上了！并且，從關鍵位置的特點，我們可以看出，一旦我們占據(jù)了某一個關鍵位置，這一關鍵位置的上方右方還有斜前方都不會有另一關鍵位置，故在下一步的操作中，對方必無法達到另一個關鍵位置，即我們這些關鍵位置具有“對位于關鍵位置的“皇后”進行任一操作均會離開關鍵位置”這一性質，并且，對方無論在下一步中將“皇后”移動到了哪里，我們必能找到其對應的另一個關鍵位置，因為所有的虛線將棋盤覆蓋遍了，那么無論“皇后”落在哪一條虛線上，末端總是指向這條虛線的出發(fā)點——關鍵位置上的！也就是說這些關鍵位置還具有的“對于任一偏離關鍵位置的“皇后”，先手總能找到辦法使其回到關鍵位置上”這一性質！這兩點恰好滿足了我們對制勝策略的要求.

綜上，我們所要做的就是尋找棋盤上的這些關鍵位置！

圖10

現(xiàn)在我們試著將剛剛的倒推分析用代數(shù)的方式呈現(xiàn)出來.若將關鍵位置放在笛卡爾坐標系下刻畫(由于這些關鍵位置總是成對且對稱出現(xiàn)的，故在對稱意義下的不妨只取每對中斜下方的那個作為代表，即橫坐標不大于縱坐標的那個).現(xiàn)取山頂為坐標原點倒著分析，即將下與左分別為正方向，單位長度就自然取為每個相鄰方格中心的距離，并將所有的關鍵位置所對應的坐標按自然數(shù)大小的順序排列，即可得到如下的六個點：

A1(1,2),A2(3,5),A3(4,7),A4(6,10),A5(8,13),A6(9,15).

若對前面提過的游戲有所了解的話，會發(fā)現(xiàn)，這些關鍵位置所對應的坐標數(shù)對，恰好是威索夫游戲中的平衡狀態(tài)！這其實很好理解，將棋盤中的位置與坐標系中的點建立對應后，可以發(fā)現(xiàn)橫向和縱向的操作會使橫坐標或縱坐標減小，這其實就對應著威索夫游戲中在一堆中取子的操作，45度方向的斜向的操作會使橫縱坐標同時減小相同數(shù)目，這正好對應威索夫游戲中在兩堆棋子中拿取相同數(shù)目棋子的操作，也就是說，這個游戲同威索夫游戲是貌異實同的，于是這一游戲的制勝策略便可化歸為威索夫游戲策略解決問題了.

3.5 斐波那契型的NIM游戲

游戲介紹：

此游戲[注]EP8:Fibonacci Nim(斐波那契取石子博弈)與經(jīng)典NIM游戲一樣都是取棋子游戲，不過它只有一堆棋子，而游戲的規(guī)則是：有一堆棋子n顆，兩人輪流取走棋子，拿取方法為：

1.開局后的第一次取棋子不能一次取完；

2.每次至少取走一顆棋子；

3.每次取的棋子數(shù)不能超過上一個人取得棋子數(shù)的二倍.

4.誰將最后一顆棋子取走誰就勝利.

相對于經(jīng)典NIM游戲每次取棋子數(shù)目任意這一點來說，這一游戲中后一玩家受前一個玩家的影響明顯要大得多，似乎每一輪游戲中的不確定因素會更大一些，因為保不準前一個玩家會取走多少，而這一數(shù)目的兩倍卻是后一個玩家的上限.

游戲中的數(shù)學：

我們首先從較小的n開始嘗試：

當n=2時，先手只能取走一顆，后手即可取完，先手必??！

當n=3時，先手只能取走一顆或兩顆，而無論是哪一種情況，后手都可以取完，故先手必敗！

當n=4時，為了不讓后手取完，先手第一次只能取走1顆(否則后手能在其取棋子的兩倍內將剩余棋子取完)剩下n=3的情況給后手，如之前分析，這種情況下是先手必勝！

當n=5時，同樣的，先手第一次也只能取走1顆，剩下n=4的情況，故這種情況下先手也只能接受必敗的結果！

當n=6時，由于取到兩顆及以上時后手會將剩余棋子取空，故先手只能取1顆棋子，剩下5顆，同上分析，先手必勝！

當n=7時，為避免后手一次取空，先手至多取2顆棋子.先手若取走1顆棋子剩下6顆，則其必勝！若先手取走2顆棋子，剩下5顆，則先手勢必會失利！當然，先手肯定不會選擇后者，故此情況下先手必勝！

當n=8時，先手若取走1顆棋子剩下7顆，則后手必會取走2顆剩下5顆，使得先手必??！先手若取走2顆棋子剩下6顆，則后手必會取走1顆剩下5顆，同樣是先手必??！而若先手取走3顆及以上的棋子，勢必會造成后手將剩余棋子取空的敗局.

當n=9時，同理分析，先手第一次最多取走2顆棋子，先手若取走1顆棋子剩下8顆，則后手只能取走1顆或者2顆而剩下7顆或者6顆，于是先手便可再取走1顆剩下5顆，使得先手必勝！而先手若取走2顆棋子剩下7顆，則后手必會取走2顆剩下5顆，那么后手就可獲勝！當然，由先手先選擇的話勢必會選擇先取走1顆，故此情況亦為先手必勝！

當n=10時，先手初次可選擇拿走1至3顆，也就是剩下9或8或7顆，但由之前分析過8顆是先手必敗局面可知，故此時拿走2顆剩下8顆方為明智之選.所以此情況亦為先手必勝！

當n=11時，先手初次亦可選擇拿走1至3顆，也就是剩下10或9或8顆，同樣，由之前的分析可知，此時拿走3顆剩下8顆則必勝.故此情況亦為先手必勝！

當n=12時，先手初次可選擇拿走1至3顆，也就是剩下11或10或9顆，由于剩下10顆或9顆時，后手可立刻拿取至剩余8顆而占據(jù)優(yōu)勢，故先手必須繞開這兩種情況而選擇剩下11顆，那么后手就只能拿走1或2顆，也就是剩下10顆或9顆，這正好可以使得先手能夠順勢拿取至8顆繼而取勝.故此情況先手必勝！

當n=13時，此時先手初次最多顆取走4顆，也即可剩下12顆11或10或9顆，由于剩下11顆、10顆或9顆時，后手均可拿取至剩下8顆，故先手勢必會選擇拿取1顆剩下12顆，那么后手只能選擇拿取1或2顆，也就是剩下11顆或者10顆，若剩下10顆，那么先手就可以拿取至剩下8顆， 當然后手絕不會做此選擇，只會選擇拿走1顆剩下11顆，那么先手只能拿至10或9顆，遂后手便可拿至剩余8顆！故此情況先手必??！

……

通過上面的嘗試，我們能夠發(fā)現(xiàn)，存在著若干的“先手必敗點”及“先手必勝點”，我們可以先看“先手必勝點”，它們是4，6，7，9，10，11，12這些，直接看上去似乎并沒有太多特點.那我們可以試著看看“先手必敗點”，一旦遇到這樣的局面，先手穩(wěn)輸，而這些狀態(tài)是2，3，5，8，13這些，而這一串數(shù)字很容易觀察出它們是有規(guī)律的，那就是從第三個數(shù)開始，每個數(shù)都是前兩個數(shù)字之和，這也剛好是斐波那契數(shù)列！雖然會花費一些時間進行分析，但只要耐心，我們不難驗證，21、34恰好也是有利局勢！這給了我們很大的啟示！

那么，斐波那契數(shù)是否真的是先手必敗的局勢呢？當然，基于對平衡狀態(tài)的考量，我們還需要考慮，反過來先手必敗的局勢是否一定是斐波那契數(shù).下面試試證明當且僅當n為斐波那契數(shù)時，局勢為先手必敗的.即意味著當棋子數(shù)為斐波那契數(shù)時，先手不能一次將棋子取至剩余的另一個斐波那契數(shù)，而一個棋子數(shù)不是斐波那契數(shù)時，先手總可以在若干次拿取后率先拿到剩余一個斐波那契數(shù).

首先，顆據(jù)斐波那契數(shù)列的性質，我們有：

f(k)=f(k-1)+f(k-2)=2f(k-2)+f(k-3)

且觀察易知，k>5時，則有f(k-2)-f(k-3)>1，因而

向上取整即有

故有

即在當前局勢是斐波那契數(shù)的情形下，先手無論怎么取，都不可能一次將棋子取至剩余的另一個斐波那契數(shù)！

另外，對于n較小的情況，我們不經(jīng)幾次嘗試就可以發(fā)現(xiàn)，若n不是一個斐波那契數(shù)，則先手總可以率先取到下一個斐波那契數(shù).下面我們假設當棋子數(shù)小于n時這種狀況都成立，我們接下來分類討論一下n的所有可能情況：

1)當前可以直接取走若干棋子，使得剩下的棋子數(shù)為一個斐波那契數(shù).

顯然，此時先手能夠率先取到斐波那契數(shù).

2)當前的局勢在一次取棋子的操作中無論怎么取棋子，剩下的棋子數(shù)都不是一個斐波那契數(shù).

不妨設f(k)

A)若m不是一個斐波那契數(shù)，則問題轉化為，經(jīng)過若干輪后，誰恰好能將這m顆棋子取完造出斐波那契數(shù)f(k).而由之前的假設我們知道，m小于n，因此先手能率先將這m顆棋子取完.

B)若m是一個斐波那契數(shù)，則因為f(k)≠m≠f(k-1)因此m≤f(k-2)，于是又有：2m≤2f(k-2)

綜上，在當前局勢是斐波那契數(shù)的情形下，先手無論怎么取，都不可能一次將棋子取至剩余的另一個斐波那契數(shù)，當棋子數(shù)n為非斐波那契數(shù)，先手能率先將其取至斐波那契數(shù)，由此我們得出結論：對于?n∈N，n≥2，當且僅當n為斐波那契數(shù)時，先手必敗，當n不為斐波那契數(shù)時，該局勢先手必勝的.而上述的這些性質恰好能使斐波那契數(shù)作為平衡狀態(tài)，誰能夠率先給對方留下斐波那契數(shù)的局面，誰將最終獲勝.

至此，我們已經(jīng)借用幾個游戲將經(jīng)典NIM游戲通過調整規(guī)則可得的這一類變式游戲進行了舉例.通過對經(jīng)典NIM游戲以及穆爾游戲、威索夫游戲、斐波那契型NIM游戲等的介紹，我們可以發(fā)現(xiàn)，這些游戲都有著異曲同工的制勝規(guī)律，可謂“貌離神合”.

容易知道，經(jīng)典NIM游戲的兩類變式游戲，其制勝規(guī)律本質都在于某方對有利局勢的牢固控制，若一方能夠每次都占據(jù)有利局勢并且留給對方不利局勢的話，該方必能夠穩(wěn)操勝券，從這個角度來看，這些游戲從策略上看都是有著很強的相似性的.由此，我們完全可以給出一個基于上述所提及游戲找出的策略，總結出更廣義的游戲類型——NIM型游戲.而在兩類變式游戲描述中，都提到了平衡數(shù)組、后手有利的局勢等這些關鍵狀態(tài)，為了說明的完整性，我們有必要對這樣的狀態(tài)進行說明.故在定義NIM型游戲之前，我們先給出平衡狀態(tài)的一般性定義：

在一個二人輪流進行決策游戲中，若存在這么一類游戲狀態(tài)，能夠滿足下面幾種條件，我們就稱其為平衡狀態(tài)：

1.該狀態(tài)是在游戲規(guī)則下的可行操作中能夠出現(xiàn)的；

2.游戲中，一旦游戲的某一方(記為A)在決策中達到了該狀態(tài)，那么另一方(記為B)接下來無論如何決策都勢必要破壞這種狀態(tài)；

3.當該狀態(tài)被之后的決策破壞后，必存在某種策略能夠保證，繼續(xù)游戲時，這樣的狀態(tài)必能率先回到A的手中.

在存在平衡狀態(tài)的游戲中，不滿足上述條件的游戲狀態(tài)則稱為非平衡狀態(tài).

由定義我們知道，平衡狀態(tài)的判定主要有兩點，一個是“他人必破壞”，簡稱為“必破性”，一個是“自己必能還原”，簡稱為“還原性”，而且平衡狀態(tài)完全是可操控的、穩(wěn)定由一方牽制的游戲局面，根據(jù)平衡狀態(tài)這一策略特征，我們便可以對滿足策略符合這些特征的游戲進行定義了.下面，我們給出NIM型游戲的定義：

1.在預定好的游戲規(guī)則下，游戲中的雙方輪流進行決策，不能在有決策空間時選擇不實施任何操作；

2.在無法進行決策時游戲結束并分出勝負；

3.每次決策只針對當前局面進行，不可有回退操作；

4.游戲中存在平衡狀態(tài).

若某一個多人游戲能夠滿足以上四種條件，這個游戲就是一個NIM型游戲.

NIM型游戲拋開了游戲本身的規(guī)則設定、游戲道具等方面的限制，它的關注點是游戲中是否存在一些特殊的狀態(tài)——平衡狀態(tài)，并在得到肯定結論后進一步將平衡狀態(tài)分析清楚.這樣一來，許多看似無直接聯(lián)系的游戲都能夠納入這類體系中了.

需要說明的是，包括羅見今老師在內的許多數(shù)學工作者對NIM型游戲的定義等已進行過一些討論，這并不是一個全新的概念，此處的定義是筆者對經(jīng)典NIM游戲及其變式呈現(xiàn)出的內在本質關聯(lián)，所進行的一些自然的思考與總結.

先前文章中所提到的平衡數(shù)組、后手有利的局勢等都是平衡狀態(tài)，事實上，在雙人決策游戲中，平衡狀態(tài)又可根據(jù)優(yōu)勢方分為兩種，即先手有利的平衡狀態(tài)或者后手有利的平衡狀態(tài).

NIM型游戲不僅樂趣橫生，而且處處體現(xiàn)著數(shù)學的美妙，讓人嘖嘖稱奇.而判定一款游戲是否歸為NIM型游戲，關鍵在于對其是否具有平衡狀態(tài)這一條件的判定，也就是對游戲狀態(tài)中“必破性”與“還原性”的證明.NIM型游戲的一般性定義使得它可囊括一大類滿足上述特點的游戲，它關注到了游戲結構及策略特點而非停留在游戲形式上，為之后一些系統(tǒng)性的整理工作帶來便利.

4 結束語

在第一種類型的變式游戲中，變式的味道較濃，其本質無非是將經(jīng)典NIM游戲的游戲形式用另外的方式進行表達處理，例如棋子堆數(shù)變成了可操作棋子的個數(shù)，而每堆棋子的數(shù)目變成了相應棋子的關鍵行棋步數(shù)，可以說，為經(jīng)典NIM游戲量體后裁了衣裳，稍加修飾后再進行呈現(xiàn).雖說將原理進行對應后，熟悉經(jīng)典NIM游戲的玩家就能夠輕易地按照制勝策略進行決策了，但正是建立對應及進行轉換這一舉足輕重的處理措施，并非想象的那樣可以輕松被考慮到，因為那需要對經(jīng)典NIM游戲有較多的了解與較深的理解，而現(xiàn)實中玩家或是學生往往是只見樹木不見森林的，會被所進行的游戲本身牽著走，故還是可以具備一定挑戰(zhàn)性的.而這種游戲的變形方式可以有很多種，此處所舉的例子只是其中某些變式形式，也就是說，這類型的變式游戲里面，能夠有更多的變式可能，施展的空間也相當大.

第二種類型的變式游戲，是對經(jīng)典NIM游戲中規(guī)則做了變動，故最后的制勝策略不簡單的遵循經(jīng)典NIM游戲策略，往往是背后的數(shù)學原理已經(jīng)發(fā)生了較大變化從而帶來制勝策略的較大調整的，這種通過增減限制來調整規(guī)則的處理方法或許能夠給試圖對游戲進行變式處理的學者及玩家很多嘗試的啟示，應用到課堂上也能有利于學生思維能力的培養(yǎng).

通過這兩類變式游戲的介紹，可以發(fā)現(xiàn)經(jīng)典NIM游戲策略給出后，這條由“游戲皇后”開辟出的道路沒有走到盡頭，反而同樹木一般，不斷在各種方向上生長出枝蔓，編織出一個充滿智趣的世界.或許，這正是研究NIM型游戲的樂趣之一，能夠與各種美好不期而遇.