愛悠閑 > 博弈的三個巨人 巴什博奕 威佐夫博奕 尼姆博奕

博弈的三個巨人 巴什博奕 威佐夫博奕 尼姆博奕

分類: ====博弈論====  |  標簽: 博弈論  |  作者: userluoxuan 相關  |  發布日期 : 2015-11-30  |  熱度 : 289°

轉載一篇有關博弈寫得不錯的文章,同時也對文章中的錯誤部分修正。

博客正容:【一】(先來苦澀的理論)

(一)巴什博奕(Bash Game):只有一堆n 個物品,兩個人輪流從這堆物品中取物,
規定每次至少取一個,最多取m 個。最后取光者得勝。
顯然,如果n=m+1,那么由于一次最多只能取m 個,所以,無論先取者拿走多少個,后取者都能夠一次拿走剩余的物品,后者取勝。

因此我們發現了如何取勝的法則:如果n=(m+1)r+s,(r 為任意自然數,s≤m),那么先取者要拿走s 個物品,如果后取者拿走k(≤m)個,那么先取者再拿走m+1-k個,結果剩下(m+1)(r1)個,以后保持這樣的取法,那么先取者肯定獲勝。

總之,要保持給對手留下(m+1)的倍數,就能最后獲勝。
這個游戲還可以有一種變相的玩法:兩個人輪流報數,每次至少報一個,最多報十個,誰能報到100 者勝。
(二)威佐夫博奕(Wythoff Game):有兩堆各若干個物品,兩個人輪流從某一堆或同時從兩堆中取同樣多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
這種情況下是頗為復雜的。

我們用(ak,bk)(ak ≤ bk ,k=0,1,2,...,n)表示兩堆物品的數量并稱其為局勢,如果甲面對(0,0),那么甲已經輸了,這種局勢我們稱為奇異局勢。
前幾個奇異局勢是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
可以看出,a0 = b0 = 0,ak 是未在前面出現過的最小自然數,而bk= ak + k,奇異局勢有如下三條性質:
1、任何自然數都包含在一個且僅有一個奇異局勢中。
由于ak 是未在前面出現過的最小自然數,所以有ak > ak1,而bk= ak + k > ak1+ k1=bk1> ak1。所以性質1成立。
2、任意操作都可將奇異局勢變為非奇異局勢。
事實上,若只改變奇異局勢(ak,bk)的某一個分量,那么另一個分量不可能在其他奇異局勢中,所以必然是非奇異局勢。

如果使(ak,bk)的兩個分量同時減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢。
3、采用適當的方法,可以將非奇異局勢變為奇異局勢。
假設面對的局勢是(a,b),若b = a,則同時從兩堆中取走a 個物體,就變為了奇異局勢(0,0);

如果a = ak ,b > bk,那么,取走b-bk個物體,即變為奇異局勢;

如果 a = ak , b < bk ,則同時從兩堆中拿走a-a[b-a] 個物體變為奇異局勢( a[b-a], b-a+a[b-a]);
如果a > ak ,b = ak + k,則從第一堆中拿走多余的數量a - ak即可;

如果a < ak ,b= ak + k,分兩種情況,第一種,a=aj (j < k),從第二堆里面拿走b - bj即可;

第二種,a=bj (j < k),從第二堆里面拿走b - aj即可。
從如上性質可知,兩個人如果都采用正確操作,那么面對非奇異局勢,先拿者必勝;反之,則后拿者取勝。
那么任給一個局勢(a,b),怎樣判斷它是不是奇異局勢呢?我們有如下公式:
ak =[k(1+√5)/2],bk= ak + k (k=0,1,2,...,n 方括號表示取整函數)
奇妙的是其中出現了黃金分割數(1+√5)/2 = 1.618...,因此,由ak,bk 組成的矩形近似為黃金矩形,

由于2/(1+√5)=(√51)/2,可以先求出j=[a(√51)/2],若a=[j(1+√5)/2],
那么a = aj,bj = aj + j,若不等于,那么a = aj+1,bj+1 = aj+1+ j + 1,若都不是,那么就不是奇異局勢。

然后再按照上述法則進行,一定會遇到奇異局勢。

奇異局勢見圖:


(三)尼姆博奕(Nimm Game):有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最后取光者得勝。
這種情況最有意思,它與二進制有密切關系,我們用(a,b,c)表示某種局勢。

首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失敗。

第二種奇異局勢是(0,n,n),只要與對手拿走一樣多的物品,最后都將導致(0,0,0)。

仔細分析一下,(1,2,3)也是奇異局勢,無論對手如何拿,接下來都可以變為(0,n,n)的情形。
計算機算法里面有一種叫做按位模2 加,也叫做異或的運算,我們用符號(+)表示這
種運算。這種運算和一般加法不同的一點是1+1=0。先看(1,2,3)的按位模2 加的結果:
1 =二進制01
2 =二進制10
3 =二進制11 (+)
———————
0 =二進制00 (注意不進位)
對于奇異局勢(0,n,n)也一樣,結果也是0。
任何奇異局勢(a,b,c)都有a(+)b(+)c =0。
如果我們面對的是一個非奇異局勢(a,b,c),要如何變為奇異局勢呢?

假設a < b< c,我們只要將c 變為a(+)b,即可,因為有如下的運算結果: a(+)b(+)(a(+)b)=(a(+)a)(+)(b(+)b)=0(+)0=0。

要將c 變為a(+)b,只要從c 中減去c(a(+)b)即可。
例1:(14,21,39),14(+)21 = 27,39  -  27 = 12,所以從39 中拿走12 個物體即可達到奇異局勢(14,21,27)。
例2:(55,81,121),55(+)81 = 102,121 - 102 = 19,所以從121 中拿走19 個物品就形成了奇異局勢(55,81,102)。
例3:(29,45,58),29(+)45=48,58 - 48 = 10,從58 中拿走10 個,變為(29,45,48)。
例4:我們來實際進行一盤比賽看看:
甲:(7,8,9)>(1,8,9)奇異局勢
乙:(1,8,9)>(1,8,4)
甲:(1,8,4)>(1,5,4)奇異局勢
乙:(1,5,4)>(1,4,4)
甲:(1,4,4)>(0,4,4)奇異局勢
乙:(0,4,4)>(0,4,2)
甲:(0.4,2)>(0,2,2)奇異局勢
乙:(0,2,2)>(0,2,1)
甲:(0,2,1)>(0,1,1)奇異局勢
乙:(0,1,1)>(0,1,0)
甲:(0,1,0)>(0,0,0)奇異局勢
甲勝。



快乐彩中奖说明