博弈论基础知识: 巴什博奕+斐波那契博弈+威佐夫博奕+尼姆博弈(及Staircase)
博弈論基礎知識: 巴什博奕+斐波那契博弈+威佐夫博奕+尼姆博弈(及Staircase)
轉載自:
http://tieba.baidu.com/p/1474319443
http://blog.sina.com.cn/s/blog_6842b59101017sx7.html
https://www.cnblogs.com/kls123/p/6970414.html
(一)巴什博奕(Bash Game):
只有一堆n個物品,兩個人輪流從這堆物品中取物,規定每次至少取一個,最多取m個.最后取光者得勝.
若(m+1) | n,則先手必敗,否則先手必勝。
顯然,如果n=m+1,那么由于一次最多只能取m個,所以,無論先取者拿走多少個,后取者都能夠一次拿走剩余的物品,后者取勝.因此我們發
現了如何取勝的法則:如果n=(m+1)r+s,(r為任意自然數,s≤m),那么先取者要拿走s個物品,如果后取者拿走k(≤m)個,那么先取者再拿
走m+1-k個,結果剩下(m+1)(r-1)個,以后保持這樣的取法,那么先取者肯定獲勝.總之,要保持給對手留下(m+1)的倍數,就能最后獲勝.
(二)斐波那契博弈(Fibonacci Nim)
有一堆個數為n(n>=2)的石子,游戲雙方輪流取石子,規則如下:
1)先手不能在第一次把所有的石子取完,至少取1顆;
2)之后每次可以取的石子數至少為1,至多為對手剛取的石子數的2倍。
約定取走最后一個石子的人為贏家,求必敗態。
結論:當n為Fibonacci數的時候,必敗。
f[i]:1,2,3,5,8,13,21,34,55,89……
用第二數學歸納法證明:
為了方便,我們將n記為f[i]。
1、當i=2時,先手只能取1顆,顯然必敗,結論成立。
2、假設當i<=k時,結論成立。
則當i=k+1時,f[i] = f[k]+f[k-1]。則我們可以把這一堆石子看成兩堆,簡稱k堆和k-1堆。(一定可以看成兩堆,因為假如先手第一次取的石子數大于或等于f[k-1],則后手可以直接取完f[k],因為f[k] < 2*f[k-1])對于k-1堆,由假設可知,不論先手怎樣取,后手總能取到最后一顆。下面我們分析一下后手最后取的石子數x的情況。如果先手第一次取的石子數y>=f[k-1]/3,則這小堆所剩的石子數小于2y,即后手可以直接取完,此時x=f[k-1]-y,則x<=2/3*f[k-1]。我們來比較一下2/3*f[k-1]與1/2*f[k]的大小。即4*f[k-1]與3*f[k]的大小,對兩值作差后不難得出,后者大。所以我們得到,x<1/2*f[k]。即后手取完k-1堆后,先手不能一下取完k堆,所以游戲規則沒有改變,則由假設可知,對于k堆,后手仍能取到最后一顆,所以后手必勝。即i=k+1時,結論依然成立。那么,當n不是Fibonacci數的時候,情況又是怎樣的呢?
這里需要借助“Zeckendorf定理”(齊肯多夫定理):任何正整數可以表示為若干個不連續的Fibonacci數之和。
關于這個定理的證明,感興趣的同學可以在網上搜索相關資料,這里不再詳述。
分解的時候,要取盡量大的Fibonacci數。
比如分解85:85在55和89之間,于是可以寫成85=55+30,然后繼續分解30,30在21和34之間,所以可以寫成30=21+9,
依此類推,最后分解成85=55+21+8+1。
則我們可以把n寫成 n = f[a1]+f[a2]+……+f[ap]。(a1>a2>……>ap)
我們令先手先取完f[ap],即最小的這一堆。由于各個f之間不連續,則a(p-1) > ap + 1,則有f[a(p-1)] > 2*f[ap]。即后手只能取f[a(p-1)]這一堆,且不能一次取完。
此時后手相當于面臨這個子游戲(只有f[a(p-1)]這一堆石子,且后手先取)的必敗態,即先手一定可以取到這一堆的最后一顆石子。
同理可知,對于以后的每一堆,先手都可以取到這一堆的最后一顆石子,從而獲得游戲的勝利。
(三)威佐夫博奕(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 > ak-1 ,而bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 .所以性質1.成立.
2、任意操作都可將奇異局勢變為非奇異局勢.
事實上,若只改變奇異局勢(ak,bk)的某一個分量,那么另一個分量不可能在其他奇異局勢中,所以必然是非奇異局勢.如果使(ak,bk)的兩
個分量同時減少,則由于其差不變,且不可能是其他奇異局勢的差,因此也是非奇異局勢.
3、采用適當的方法,可以將非奇異局勢變為奇異局勢.
假設面對的局勢是(a,b),若b = a,則同時從兩堆中取走a 個物體,就變為了奇異局勢(0,0);如果a = ak ,b > bk,那么,取走b - bk個物
體,即變為奇異局勢;如果a = ak , b < bk ,則同時從兩堆中拿走ak - ab - ak個物體,變為奇異局勢( ab - ak , ab - ak+ b - ak)
;如果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∈N)
奇妙的是其中出現了有關黃金分割數的式子:(1+√5)/2 =1.618…,若兩堆物品個數分別為x,y(x<y),則k=y-x,再判斷x是否等于[(y
-x)( √5+1)/2] 即可得知是否是奇異局勢。
參考例題:POJ1067取石子游戲
參考代碼:
var a,b:longint;begin repeat readln(a,b); if a>b then begin a:=a xor b; b:=a xor b; a:=a xor b; end; if a=trunc((b-a)(sqrt(5)+1)/2) then writeln(0) else writeln(1); until seekeof;end.
(四)尼姆博奕(Nimm Game):
有三堆各若干個物品,兩個人輪流從某一堆取任意多的物品,規定每次至少取一個,多者不限,最后取光者得勝.
這種情況最有意思,它與二進制有密切關系,我們用(a,b,c)表示某種局勢,首先(0,0,0)顯然是奇異局勢,無論誰面對奇異局勢,都必然失
敗.第二種奇異局勢是(0,n,n),只要與對手拿走一樣多的物品,最后都將導致(0,0,0).仔細分析一下,(1,2,3)也是奇異局勢,無論對手如
何拿,接下來都可以變為(0,n,n)的情形.
計算機算法里面有一種叫做按位模2加,也叫做異或的運算,我們用符號xor表示這種運算.這種運算和一般加法不同的一點是1+1=0.先看
(1,2,3)的按位模2加的結果:
1 =二進制01
Xor 2 =二進制10
Xor 3 =二進制11
———————
0 =二進制00
對于奇異局勢(0,n,n)也一樣,結果也是0.
任何奇異局勢(a,b,c)都有a xor b xor c =0。該結論可以推廣至若干堆,都是成立的。
如果我們面對的是一個非奇異局勢(a,b,c),要如何變為奇異局勢呢?假設a < b< c,我們只要將c 變為a xor b,即可,因為有如下的運算
結果: a xor b xor (a xor b)=(a xor a) xor (b xor b)=0 xor 0=0.要將c 變為a xor b,只要從c中減去c-(a xor b)即可.
(五)Nim Staircase博奕:
這個問題是尼姆博弈的拓展:游戲開始時有許多硬幣任意分布在樓梯上,共n階樓梯從地面由下向上編號為0到n。游戲者在每次操作時
可以將樓梯j(1<=j<=n)上的任意多但至少一個硬幣移動到樓梯j-1上。游戲者輪流操作,將最后一枚硬幣移至地上(0號)的人獲勝。
算法:將奇數樓層的狀態異或,和為0則先手必敗,否則先手必勝。證明略。
例題:Poj1704
這道題可以把兩個棋子中間間隔的空格子個數作為一堆石子,則原題轉化為每次可以把左邊的一堆石子移到相鄰的右邊的一堆中。也就
是階梯尼姆博弈,注意對輸入數據先排序,然后倒著往前數(a[n]-a[n-1]-1為第一個),奇數個數到的就做一下xor,其中最前面的看
做a[1]-0-1,參考程序:
var t,n,b,i,j:longint; a:array[0…1000]of longint;begin readln(t); repeat dec(t); readln(n); for i:=1 to n do read(a[i]); qsort(1,n);//快排略 j:=0; b:=0; for i:=n downto 1 do begin inc(j); if odd(j) then b:=b xor (a[i]-a[i-1]-1); end; if b=0 then writeln(‘Bob will win’) else writeln(‘Georgia will win’); until t=0;end.
源地址:http://tieba.baidu.com/p/1474319443
http://blog.sina.com.cn/s/blog_6842b59101017sx7.html總結
以上是生活随笔為你收集整理的博弈论基础知识: 巴什博奕+斐波那契博弈+威佐夫博奕+尼姆博弈(及Staircase)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: vue3使用useMouseInElem
- 下一篇: 综日三册第八课