[課件]組合數(shù)學(xué)——組合游戲

1、組合數(shù)學(xué)（一）,李子星,內(nèi)容提要,組合游戲 巴什博弈 威佐夫博弈 尼姆博弈 有向圖游戲與有向圖游戲的和與SG函數(shù) 反尼姆博弈與反組合游戲 繼續(xù)探討ICG的和,組合游戲,組合游戲（Combinatorial Games），又稱為“Impartial Combinatorial Games”（以下簡(jiǎn)稱ICG）。 滿足以下條件的游戲是ICG： （1）有兩人參與游戲，輪流做出決策，兩人都最理性得追求勝利 （2）兩名選手交替做出決策，無法做出決策的人失敗，然后游戲結(jié)束。 （3）游戲總能在有限次決策后結(jié)束 （4）游戲的同一個(gè)狀態(tài)不會(huì)多次抵達(dá) （5）任意一個(gè)游戲者在某一確定狀態(tài)可以作出的決策集合只與當(dāng)前的狀

2、態(tài)有關(guān)，而與游戲者無關(guān),組合游戲,定義“先手必?cái)　睜顟B(tài)（必?cái)B(tài)），和“先手必勝”狀態(tài)（必勝態(tài)）： （1）無法進(jìn)行任何移動(dòng)的局面是必?cái)B(tài)； （2）可以移動(dòng)到必?cái)B(tài)的局面是必勝態(tài)； （3）所有移動(dòng)都導(dǎo)致必勝態(tài)的局面是必?cái)B(tài)。 按照這個(gè)定義，如果局面不可能重現(xiàn)，那么每個(gè)狀態(tài)或者是必勝態(tài)或者是必?cái)B(tài)，而且可以通過定義計(jì)算出來。,巴什博弈,【問題一】 有一堆n個(gè)物品，兩個(gè)人輪流從這堆物品中取物，規(guī)定每次至少取一個(gè)，最多取m個(gè)。取走最后一個(gè)物品的人獲得勝利。問先手是否必勝。,巴什博弈,這顯然是一個(gè)組合游戲問題 對(duì)于一個(gè)狀態(tài)，可以用當(dāng)前的物品數(shù)x來唯一描述。 容易知道，對(duì)于一個(gè)狀態(tài)x，如果x%(m+1)=0

3、，那么這個(gè)狀態(tài)肯定是必?cái)B(tài)，否則是必勝態(tài)。,巴什博弈,設(shè)當(dāng)前狀態(tài)是x： 如果x=0，那么顯然這是一個(gè)必?cái)B(tài) 如果x%(m+1)0，即0x%(m+1)=m，那么取走x%(m+1)件物品后得到的狀態(tài)就是一個(gè)模m+1等于0的狀態(tài) 如果x%(m+1)=0，那么不管怎么取，都一定是移動(dòng)到一個(gè)模m+1不等于0的狀態(tài) 這三條分別對(duì)應(yīng)了必?cái)”貏賾B(tài)定義的三條 所以狀態(tài)x是必?cái)B(tài)當(dāng)且僅當(dāng)若x%(m+1)=0,威佐夫博弈,【問題二】 有兩堆各若干個(gè)物品，兩個(gè)人輪流從某一堆或同時(shí)從兩堆中取同樣多的物品，規(guī)定每次至少取一個(gè)，多者不限，取走最后一顆石子的人獲得勝利。問先手是否必勝。,威佐夫博弈,從性質(zhì)入手： 令必?cái)《M

4、為(a, b)形式（aa2,b1b2,a1b2,a2b1。 推論二：對(duì)于任意兩個(gè)的必?cái)《M(a1,b1)，(a2,b2)，有b1-a1b2-a2。即，所有必?cái)《M的兩元之差的絕對(duì)值必定各不相同。,威佐夫博弈,利用性質(zhì)和推論，可以證明如下結(jié)論： 將必?cái)《M按首元為關(guān)鍵字排序，每個(gè)必?cái)《M中首元為未在前面的必?cái)《M中出現(xiàn)的最小正整數(shù)，并且第N組中兩個(gè)數(shù)差為N。,威佐夫博弈,可以利用數(shù)學(xué)歸納法證明： 前兩組為(0, 0)和(1, 2)，顯然符合前述的結(jié)論 若第0組到第N組都與前述的結(jié)論相符，則： 設(shè)未在第0到第N組中出現(xiàn)的最小正整數(shù)為M，考察二元組(M,M+N+1) 如果選擇從數(shù)量為M的堆

5、中取石子，不妨設(shè)變成了(M-X,M+N+1)，而(M+N+1)-(M-X)=N+1+XN，且M-X一定與之前的某個(gè)必?cái)《M中一元相等，這樣就有一個(gè)包含M-X，且不與之前任何一組必?cái)《M相同的二元組，根據(jù)推論一，(M-X,M+N+1)這個(gè)二元組一定不是必?cái)《M 如果選擇從數(shù)量為M+N+1的堆中取石子，不妨設(shè)變成了(M,K) 若K=M，由于M與之前的任何一個(gè)必?cái)《M中都未出現(xiàn)，且N+1K-M=0，根據(jù)推論二，(M, K)這個(gè)二元組一定不是必?cái)《M 若KN，根據(jù)推論一，(M-X,M+N+1-X)這個(gè)二元組一定不是必?cái)《M 即(M, M+N+1)能夠擴(kuò)展到的狀態(tài)都不是必?cái)B(tài)，所以它就是一個(gè)

6、必?cái)B(tài) 又根據(jù)排序的規(guī)則，(M,M+N+1)一定是必?cái)《M序列的第N+1項(xiàng) 所以第0到第N+1組必?cái)《M也與前述的結(jié)論相符,威佐夫博弈,由此，所有的必?cái)B(tài)都完美的找到了： (0,0) (1,2) (3,5) (4,7) (6,10) (8,13). 作為經(jīng)典問題，它還有更強(qiáng)的結(jié)論： 第n個(gè)必?cái)B(tài)一定是： (n*(1+5)/2, n*(1+5)/2+n) 其中“ ”是取下整。 所以判斷一個(gè)狀態(tài)(a,b)（a=b）是不是必?cái)B(tài)只需要判斷a是否等于(b-a)*(1+5)/2。,尼姆博弈,【問題三】 有若干堆石子，兩個(gè)人輪流從中取石子。每堆石子的數(shù)量都是有限的，合法的取石子操作是“選擇一堆石子并拿

7、走若干顆（不能不拿）”。拿走最后一顆石子的人獲得勝利。問先手是否必勝。,尼姆博弈,當(dāng)然這一題也可以用必勝必?cái)B(tài)的性質(zhì)用遞推來求解。 但若考慮時(shí)間復(fù)雜度，就會(huì)發(fā)現(xiàn)是行不通的（尤其是當(dāng)石子的堆數(shù)很多，且每堆石子初始的數(shù)量也很多的時(shí)候）。 它的解答當(dāng)然也完全配得上其經(jīng)典問題的稱號(hào)：對(duì)于一個(gè)尼姆博弈的局面(a1,a2,.,an)，它是必?cái)B(tài)當(dāng)且僅當(dāng)a1a2.an=0，其中“”表示異或(xor)運(yùn)算。,尼姆博弈,證明很簡(jiǎn)單。還是由必勝必?cái)B(tài)性質(zhì)入手： 對(duì)于局面(0,0,)，顯然00=0，且這是一個(gè)必?cái)B(tài)。 對(duì)于局面(a1,a2,.,an)，如果x=a1a2.an0，那么在a1到an這n個(gè)數(shù)中一定至少存在

8、一個(gè)數(shù)ap滿足0ak，都有 a1a2.pan a1a2.akan=0。,尼姆博弈,對(duì)于結(jié)論“如果x=a1a2.an0，那么在a1到an這n個(gè)數(shù)中一定至少存在一個(gè)數(shù)ap滿足apxap”的證明如下： （1）從x的二進(jìn)制表示入手，設(shè)x的二進(jìn)制最高的非0位是第m位 （2）那么a1到an中至少有一個(gè)數(shù)的二進(jìn)制數(shù)第m位為1，從其中隨便取一個(gè)假設(shè)為aq （3）那么aqx的結(jié)果的二進(jìn)制數(shù)第m位一定為0 （4）且aqx的結(jié)果的二進(jìn)制數(shù)中高于m位的部分全部與aq的一樣 （5）所以aqx一定小于aq。,尼姆博弈,aq：()1 x： 1 aqx：()0,故aqx aq，由此尼姆博弈問題也就完美的解決了。,更難的博弈問

9、題,既然尼姆博弈的必勝策略已經(jīng)找到了，那么如果規(guī)則改變一些，還能找到必勝策略么？ 比如說【問題四】 有n堆石子，兩個(gè)人輪流從中取石子。每次可以從第1堆石子里取1顆、2顆或3顆，或者從第2堆石子里取任意奇數(shù)顆，或者從第3到第n堆中任選一堆并取走任意正整數(shù)顆。取走最后一顆石子的人獲得勝利。問先手是否必勝。 這時(shí)問題瞬間復(fù)雜了很多。接下來我們就來討論這樣更進(jìn)一步的內(nèi)容。,有向圖游戲,先來研究一個(gè)看上去似乎更為一般的游戲：給定一個(gè)“有向無環(huán)”圖和一個(gè)起始頂點(diǎn)上的一枚棋子，兩名選手交替的將這枚棋子沿有向邊進(jìn)行移動(dòng)，無法移動(dòng)者判負(fù)?？梢苑Q這個(gè)游戲?yàn)椤坝邢驁D游戲”。 很容易發(fā)現(xiàn)，這個(gè)游戲可以認(rèn)為是所有組合游

10、戲的抽象模型。 也就是說，任何一個(gè)ICG都可以通過把每個(gè)局面看成一個(gè)頂點(diǎn)，對(duì)每個(gè)局面和它的子局面連一條有向邊來抽象成這個(gè)“有向圖游戲”。,有向圖游戲與SG函數(shù),下面我們就在有向無環(huán)圖的頂點(diǎn)上定義MEX（minimal excludant）運(yùn)算和SG（Sprague-Grundy）函數(shù)。 （1）首先定義MEX運(yùn)算，這是施加于一個(gè)集合的運(yùn)算，表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例如MEX0,1,2,4=3、MEX2,3,5=0、 MEX=0。 （2）對(duì)于一個(gè)給定的有向無環(huán)圖，定義關(guān)于圖的每個(gè)頂點(diǎn)的SG函數(shù)如下：SG(x)=MEXSG(y)|xy，即一個(gè)節(jié)點(diǎn)的SG函數(shù)值等于其所有后繼結(jié)點(diǎn)的SG函數(shù)值

11、集合經(jīng)過MEX運(yùn)算后的結(jié)果。,有向圖游戲與SG函數(shù),來看一下SG函數(shù)的性質(zhì)。 首先，所有的終結(jié)狀態(tài)所對(duì)應(yīng)的頂點(diǎn)，也就是沒有后繼結(jié)點(diǎn)的頂點(diǎn)，其SG值為0，因?yàn)樗暮罄^集合是空集。 然后對(duì)于一個(gè)SG(x)=0的頂點(diǎn)x，它的所有后繼y都滿足 SG(y)0。 對(duì)于一個(gè)SG(x)0的頂點(diǎn)，必定存在一個(gè)后繼y滿足SG(y)=0。,有向圖游戲與SG函數(shù),是不是和必勝必?cái)B(tài)性質(zhì)非常相似？ 沒錯(cuò)，這三條性質(zhì)就說明了：頂點(diǎn)x所代表的狀態(tài)是必?cái)B(tài)當(dāng)且僅當(dāng)SG(x)=0，我們通過計(jì)算有向無環(huán)圖的每個(gè)頂點(diǎn)的SG值，就可以對(duì)每種局面找到必勝策略了。 但是這樣看的話，SG函數(shù)的值域只需要在01范圍內(nèi)就夠了，干嘛還要搞個(gè)這么

12、麻煩的MEX運(yùn)算呢？,多棋子有向圖游戲與SG函數(shù),因?yàn)镾G函數(shù)的用途遠(yuǎn)沒有這樣簡(jiǎn)單。 如果將有向圖游戲變復(fù)雜一點(diǎn)：有向圖上并不是只有一枚棋子，而是有n枚棋子，每次可以任選一枚進(jìn)行移動(dòng)（可以稱這個(gè)游戲?yàn)槎嗥遄佑邢驁D游戲），這時(shí)怎樣確定當(dāng)前的必勝必?cái)顟B(tài)？ 這當(dāng)然還是個(gè)ICG，于是肯定也能轉(zhuǎn)化到某個(gè)單棋子有向圖游戲，但是這樣顯然太麻煩了。,多棋子有向圖游戲與SG函數(shù),讓我們?cè)賮砜紤]一下頂點(diǎn)的SG值的意義。 當(dāng)SG(x)=k時(shí)，表明對(duì)于任意一個(gè)0=ik，都存在x的一個(gè)后繼y滿足SG(y)=i。也就是說，當(dāng)某枚棋子的SG值是k時(shí)，我們可以從這里出發(fā)移動(dòng)到一個(gè)SG值為0或1或或k-1的另一個(gè)節(jié)點(diǎn)，但絕對(duì)

13、不能移動(dòng)到一個(gè)SG值為k的另一個(gè)節(jié)點(diǎn)。 聯(lián)想一下尼姆博弈，尼姆博弈的規(guī)則就是：每次選擇一堆石子（假設(shè)數(shù)量為k），可以把它的數(shù)量變成0、變成1、變成k-1，但絕對(duì)不能保持k不變。 這表明：如果將n枚棋子所在的頂點(diǎn)的SG值看作n堆相應(yīng)數(shù)量的石子，那么這個(gè)尼姆博弈的每個(gè)必勝策略都對(duì)應(yīng)于原來這n枚棋子的必勝策略！,多棋子有向圖游戲與SG函數(shù),對(duì)于n個(gè)棋子，設(shè)它們對(duì)應(yīng)的頂點(diǎn)的SG值分別為(a1,a2,an)，再設(shè)局面(a1,a2,an)的尼姆博弈的一種最佳策略是把a(bǔ)i變成ai。 那么原本的多棋子有向圖游戲的一種最佳策略就是把第i枚棋子移動(dòng)到一個(gè)SG值為ai的頂點(diǎn)上去。 是不是很神奇繞了一圈又回到尼姆博弈

14、了！,多棋子有向圖游戲與SG函數(shù),只要證明“這種多棋子的有向圖游戲的局面是必?cái)B(tài)當(dāng)且僅當(dāng)所有棋子所在的節(jié)點(diǎn)的SG函數(shù)值的異或結(jié)果為0”就好了。而這個(gè)的證明與前面尼姆博弈的證明幾乎完全相同，只要適當(dāng)修改幾個(gè)名詞就行了。 唯一的偏差只有：在有向圖游戲中，一個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)的SG值可能會(huì)大于當(dāng)前節(jié)點(diǎn)的SG值，而尼姆博弈中卻不能讓某一堆石子的數(shù)量增加。 而在多棋子有向圖游戲中這個(gè)偏差并不會(huì)產(chǎn)生錯(cuò)誤：由于ICG是有限的（就是說總會(huì)結(jié)束），而之前關(guān)于異或運(yùn)算的結(jié)論并不強(qiáng)制要求每次必須讓某一項(xiàng)變小。,多棋子有向圖游戲與SG函數(shù),剛才，為了使問題看上去更容易一些，默認(rèn)了n枚棋子是在一個(gè)有向圖上移動(dòng)。但如果不是

15、在同一個(gè)有向圖上，而是每個(gè)棋子在一個(gè)獨(dú)立的有向圖上，每次可以任選一個(gè)棋子（也就是任選一個(gè)有向圖）進(jìn)行移動(dòng)，這樣也不會(huì)給結(jié)論帶來任何變化。 因?yàn)槟闫鋵?shí)可以認(rèn)為所有棋子還是在一個(gè)有向圖上，雖然這個(gè)圖是不連通的。,有向圖游戲的和與SG函數(shù),于是，我們可以定義有向圖游戲的和（Sum of Graph Games）： 設(shè)G1、G2、Gn是n個(gè)有向圖游戲，定義游戲G=G1+G2+Gn的移動(dòng)規(guī)則是：任選一個(gè)子游戲Gi并將上面的棋子移動(dòng)一步。 則SG(G)=SG(G1)SG(G2)SG(Gn)。 也就是說，游戲的和的SG函數(shù)值是它的所有子游戲的SG函數(shù)值的異或。,有向圖游戲的和與SG函數(shù),再考慮前面的一句話：

16、任何一個(gè)ICG都可以抽象成一個(gè)有向圖游戲。所以“SG函數(shù)”和“游戲的和”的概念就不是局限于有向圖游戲。 當(dāng)我們面對(duì)由n個(gè)子游戲組合成的一個(gè)游戲時(shí)，只需對(duì)于每個(gè)子游戲找出求它的各局面的SG值的方法，就可以把這些SG值全部看成尼姆博弈中的石子堆，然后依照找尼姆博弈的必勝策略的方法來找這個(gè)游戲的必勝策略了！,有向圖游戲的和與SG函數(shù),那么現(xiàn)在，回到前面提出的進(jìn)階游戲： 有n堆石子，兩個(gè)人輪流從中取石子。每次可以從第1堆石子里取1顆、2顆或3顆，或者從第2堆石子里取任意奇數(shù)顆，或者從第3到第n堆中任選一堆并取走任意正整數(shù)顆。取走最后一顆石子的人獲得勝利。問先手是否必勝。,有向圖游戲的和與SG函數(shù),我們

17、可以把它看作3個(gè)子游戲： （一）第1個(gè)子游戲只有一堆石子，每次可以取1、2、3顆，很容易看出x顆石子的局面的SG值是x%4。這實(shí)際上就是一個(gè)m=3的巴什博弈問題。 （二）第2個(gè)子游戲也是只有一堆石子，每次可以取任意奇數(shù)顆，經(jīng)過簡(jiǎn)單的思考可以知道這個(gè)游戲有x顆石子時(shí)的SG值是x%2。 （三）第3個(gè)子游戲有n-2堆石子，就是一個(gè)樸素的尼姆博弈問題。 對(duì)于原游戲的每個(gè)局面，把三個(gè)子游戲的SG值異或一下就得到了整個(gè)游戲的SG值，然后就可以根據(jù)這個(gè)SG值判斷是否有必勝策略以及做出決策了。,有向圖游戲的和與SG函數(shù),這樣，當(dāng)我們遇到看上去有些復(fù)雜的游戲時(shí)，思路就應(yīng)該是： 試圖將這個(gè)游戲分成若干個(gè)子游戲，對(duì)

18、于每個(gè)比原游戲簡(jiǎn)化很多的子游戲找出它的SG函數(shù)，然后全部異或起來就得到了原游戲的SG函數(shù)，就可以解決原游戲了。,有向圖游戲的和與SG函數(shù),再舉一個(gè)小例子： 【問題五】 有n堆石子，每堆初始有ai顆。兩個(gè)人輪流從中取石子。每次必須任選一堆并取走1到m顆石子。問是否先手必勝。 解法： SG=(a1%(m+1)(a2%(m+1)(an%(m+1),反尼姆博弈,下面我們來看另一個(gè)問題： 【問題六】 有若干堆石子，兩個(gè)人輪流從中取石子。每堆石子的數(shù)量都是有限的，合法的取石子操作是“選擇一堆石子并拿走若干顆（不能不拿）”。拿走最后一顆石子的人失敗。問先手是否必勝。,反尼姆博弈,這個(gè)問題的勝利條件與尼姆博弈

19、正好相反，所以被稱為反尼姆博弈問題。 這實(shí)際上已經(jīng)不符合我們之前定義的ICG了，那它還有像尼姆博弈那樣漂亮的結(jié)論么？ 答案是：有的！,反尼姆博弈,SG=0,SG0,存在ai1必?cái)B(tài)（1）,不存在ai1必勝態(tài)（2）,存在ai1必勝態(tài)（3）,不存在ai1必?cái)B(tài)（4）,反尼姆博弈,必?cái)B(tài)（1）,必勝態(tài)（2）,必勝態(tài)（3）,必?cái)B(tài)（4）,反尼姆博弈與反組合游戲,于是反尼姆博弈問題就這樣漂亮的解決了。 但是這個(gè)結(jié)論能像尼姆博弈一樣，推廣到任意的“反有向圖游戲”和“反多棋子有向圖游戲” 么（即勝利條件改為“無法移動(dòng)棋子的人勝利” ） ？ 答案是：不行！,反尼姆博弈與反組合游戲,回顧一下我們之前討論SG函數(shù)

20、時(shí)提到的那個(gè)偏差：在有向圖游戲中，一個(gè)節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)的SG值可能會(huì)大于當(dāng)前節(jié)點(diǎn)的SG值，而尼姆博弈中卻不能讓某一堆石子的數(shù)量增加。 在有向圖游戲里，這個(gè)偏差不會(huì)引發(fā)錯(cuò)誤，但是在反有向圖游戲里，這個(gè)偏差就會(huì)產(chǎn)生錯(cuò)誤了。,反尼姆博弈與反組合游戲,SG=0,SG0,存在ai1“必?cái)B(tài)（1）”,不存在ai1“必勝態(tài)（2）”,存在ai1“必勝態(tài)（3）”,不存在ai1“必?cái)B(tài)（4）”,反尼姆博弈與反組合游戲,“必?cái)B(tài)（1）”,“必勝態(tài)（2）”,“必勝態(tài)（3）”,“必?cái)B(tài)（4）”,只能到達(dá)“必勝態(tài)”的狀態(tài)肯定不是必勝態(tài),反尼姆博弈與反組合游戲,1,0,2,0,“必勝態(tài)（2）”,“必勝態(tài)（2）”,“必?cái)B(tài)（4）”,“必勝態(tài)（3）”,反尼姆博弈與反組合游戲,可以發(fā)現(xiàn)這個(gè)偏差產(chǎn)生錯(cuò)誤的當(dāng)且僅當(dāng)： （2）不能到達(dá)（4），但卻能到達(dá)（3） 這種情形只有在當(dāng)前所有ai都是0，并且無法將任意一個(gè)改變?yōu)?的時(shí)候才會(huì)出現(xiàn)。 所以想辦法屏蔽掉這個(gè)偏差產(chǎn)生的錯(cuò)誤，反尼姆博弈的結(jié)論就可以推廣了。 而要屏蔽這個(gè)錯(cuò)誤，只需要保證“當(dāng)所有的ai都是0時(shí)游戲結(jié)束”就行。,繼續(xù)探討ICG的和,之前我們提出了“多個(gè)游戲之和”某個(gè)狀態(tài)的SG函數(shù)值計(jì)算方法（各個(gè)子游戲的SG函數(shù)值全部異或起來）。 而提出的“