Nim游戲-博弈論

1、淺析Nim游戲武鋼三中吳豪一、引言Nim游戲是一個(gè)非常經(jīng)典的組合游戲，它具有很強(qiáng)的趣味性與數(shù)學(xué)性，而且其 解法也蘊(yùn)含了一些比較具冇啟發(fā)性的思維方式在本文中，我們將探討Nim游 戲屮滲透的些數(shù)學(xué)思想。席望讀者通過本文，能對Nim游戲仃更加深入的認(rèn) 識.并能對其中的數(shù)學(xué)思想有進(jìn)一步的體會。二、Nim游戲Nim游戲是一個(gè)由兩個(gè)玩家輪流進(jìn)行的游戲：一開始，有n堆便幣，毎堆分別 有pl.72"枚硬幣。每個(gè)冋介，玩家都可以選擇一堆硬幣，并從中取走k枚 礎(chǔ)幣（KAfCnJ,取完最*枚碾幣的玩家獲得勝利。試問，對先玩家是 否有必勝策略？三、初步分析一開始拿到這個(gè)問題似乎毫無頭緒，我們就何IL先把問題

2、簡化，石慮“=2的悄 況經(jīng)過兒番實(shí)驗(yàn)之后.我們不難發(fā)現(xiàn)n=2時(shí)的規(guī)律：能否必勝，并不是看這 兩堆有多少個(gè)石子，而圧看這兩堆的石子數(shù)楚否相等。當(dāng)兩堆的石子數(shù)不等 時(shí).第一個(gè)玩家取出一定量的右使得這胸堆的右了數(shù)相等.接右冃要第 個(gè) 玩家從一堆中取出了k個(gè)石子.第一個(gè)玩家就模仿他住另一堆取出k個(gè)石子。如 此往父.第一個(gè)玩家-定可以獲得勝利。同樣.如果-開始兩堆的石子數(shù)相 第個(gè)玩家就可以完全模仿第一個(gè)玩家的操作以獲得勝利四、結(jié)論的抽彖與泛化在前一部分,我們分析了Nim游戲在n=2時(shí)的觀律與策略。但僅憑這個(gè)特例的 結(jié)論.還不足以解決一般的Nim游戲。因此.在這里我們需要對原結(jié)論進(jìn)行 進(jìn)-步抽象與泛化，來

3、給-般Nim游戲的解決提供切入點(diǎn)。我們不難注意到， 必勝判定的關(guān)鍵在于“狀態(tài)”，例如在n=2時(shí),這個(gè)狀態(tài)就是“相等”與“不相等” > 而且這兩種狀態(tài)Z間在某種依賴關(guān)系，從而能給某個(gè)玩家的必勝制適 了契機(jī)。我們不妨設(shè)這兩個(gè)狀態(tài)分別為“V狀態(tài)衲和“L狀態(tài)” 那么這兩個(gè)狀態(tài)必然滿 足以下關(guān)系：條條條（目標(biāo)狀態(tài)p Gy,無論如何操作V狀態(tài)都會變成L狀態(tài)、 一罡存在某種操作使得狀態(tài)L能變成狀態(tài)匕雪如在n=2的時(shí)候V狀態(tài)就是兩堆相等，L狀態(tài)就是兩堆不相等。日標(biāo)狀態(tài)是兩 堆均為6是V狀態(tài)中的一種（條件1）。如果兩堆相等，從一堆中取出一些石 子，兩堆必然不等（條件2）如果兩堆的石子不等可以從多的一堆中取

4、出兩 堆的是值，使兩堆相等（條件3）。這兩種狀態(tài)Z間的邏輯關(guān)系如卜圖所示：這個(gè)圖很淸晰的反映rwifn提到的3個(gè)條件。圖中的三條邊表示了三種狀態(tài)轉(zhuǎn)移 的方式顯然，如果一個(gè)玩家不幸地要從v狀態(tài)出發(fā).那么下一玩家會不斷 從L進(jìn)向V,并獲得勝利。換句話說,如果一個(gè)玩家從L出發(fā),只要每次從L走 向V即可獲得勝利。因而，沒有人會愿意從L走到L,因?yàn)檫@樣就把主動權(quán)讓給 了對手五、構(gòu)造模型經(jīng)過詢-部分的分析，我們（2經(jīng)得到了必勝策略的邏輯模型。那么接著，我們 就需要為一般Nim游戲就身怎做一個(gè)符合以卜模糧的V狀態(tài)和L狀態(tài)。這里.我們不妨考慮把備堆分解為石子數(shù)為2.4,& 1G.21的子堆。顯然，最后

5、取完時(shí)， 每種子堆都是0個(gè)，即毎種子堆都仃偶數(shù)個(gè)。因此，我們猜想，是否可以令所仃 子堆數(shù)都為偶數(shù)時(shí)為V狀態(tài)？這里我們就來考察這種猜想是否滿足以上模醴的 其余兩個(gè)族本條件.為了方便起見，我們將所冇堆的石子數(shù)轉(zhuǎn)為2進(jìn)制，令所冇 右子數(shù)在二進(jìn)制時(shí)第i位上的數(shù)字Z利為 那么V狀態(tài)就是如為偶數(shù)，L狀態(tài) 就是日偽為奇數(shù).先來看條件2：設(shè)玩家選擇第i堆令這堆石子數(shù)用:進(jìn)制表示是久矢幾該:進(jìn)制數(shù)與務(wù)位剩余T的數(shù)目如下:b、b2、63,、bi、bm9 q °2,如、,bm從P沖取出一些石子，則其對應(yīng)進(jìn)制數(shù)屮必然存在位®的值發(fā)工變化（否則 沒?。?那么該位上的數(shù)字和由（®-bj） +

6、 bj = aj變?yōu)榭?心）+（1-如=（仃+1-2小 因?yàn)槿≈笆荲狀態(tài)，冇©足偶數(shù)，故取定 Z后該位數(shù)字和© + 1-2®是奇數(shù)，轉(zhuǎn)變成了L狀態(tài)。因此無論玩家如何操 作.V狀態(tài)都只能轉(zhuǎn)移到L狀態(tài)。接著來看條件3:對于上述二進(jìn)制數(shù)，由于當(dāng)詢是L狀態(tài)，我們町以選擇一個(gè)最高的和為奇數(shù)的 數(shù)位J.然后任意選擇-堆該位為1的石子堆i.把這一位上的1改為山接著對于 低位，無論怎么改，都比原數(shù)小，因此我們一定叮以通過訓(xùn)整低位便得毎-位上 的數(shù)字和均為偶數(shù)，所以我們一定可以通過取出一些石子，從L狀態(tài)轉(zhuǎn)移到V狀 態(tài)至此,我們已經(jīng)說明了這種猜想的完備性。因此我們可以認(rèn)為對于 般Nim問 題其必勝的判定，可以以石子數(shù)在二進(jìn)制中每一位上1的個(gè)數(shù)的奇偶性為依 據(jù)。我們可以把Nim游戲的結(jié)論表述如卜：對于II堆石子PXP2Pn1.若pi xor p2 xor . pn = 0 （二進(jìn)制每-位上的數(shù)字和足