下面我們以一種游戲的方式來(lái)引進(jìn)三種基本的博弈問(wèn)題。
一．巴什博奕（Bash Game）：
首先我們來(lái)玩一個(gè)比較古老的報(bào)數(shù)游戲。A和B一起報(bào)數(shù)，每個(gè)人每次最少報(bào)一個(gè),最多報(bào)4個(gè)。輪流報(bào)數(shù),看誰(shuí)先報(bào)到30.
如果不知道巴什博弈的可能會(huì)覺(jué)得這個(gè)是個(gè)有運(yùn)氣成分的問(wèn)題，但是如果知道的人一定知道怎樣一定可以贏。
比如A先報(bào)數(shù)的話,那么B一定可以贏(這里假定B知道怎么正確的報(bào)數(shù))
B可以這樣報(bào)數(shù),每次報(bào)5-k(A)個(gè)數(shù),其中k(A)是A報(bào)數(shù)的個(gè)數(shù)這樣的話沒(méi)一次
兩人報(bào)完數(shù)之后會(huì)變成5 10 15 20 25 30這樣是不是B一定會(huì)贏呢?是不是有一種被欺騙的感覺(jué)呢?好吧下面我們來(lái)看看這個(gè)原理。我們先看下一個(gè)一眼就能看出答案的例子 比如說(shuō)我們報(bào)到5(4+1),每次報(bào)最多報(bào)4個(gè),最少報(bào)1個(gè).那么是不是后者一定可以贏呢？答案是肯定的。好了到這巴什博弈的精髓基本就OK了。
那么如果我們要報(bào)到n+1,每次最多報(bào)n個(gè),最少報(bào)1個(gè)的話,后者一定能夠贏。
現(xiàn)在我們需要報(bào)數(shù)到n,而每次最多報(bào)數(shù)m個(gè),最少報(bào)數(shù)1個(gè).我們可以化成這樣
n = k*(1+m)+r(0 <= r <= m）這樣的話如果r不等于0那么先手一定會(huì)贏，為什么呢？首先先手報(bào)r個(gè),那么剩下k倍(1+m)個(gè)數(shù),那么我們每次報(bào)數(shù)1+m-k(B)個(gè)數(shù)就一定能保證最后剩下1+m個(gè),那么就到了上面我們說(shuō)的那個(gè)了,先手就一定會(huì)贏,如果r=0那么后手一定會(huì)贏,道理一樣的。
到這巴什博弈也就介紹完了,知道這個(gè)道理之后我們也可以去騙小朋友了。-_-//
二．威佐夫博奕（Wythoff Game）：
這種博弈比前面一種要稍微復(fù)雜一點(diǎn)。我們來(lái)看下下面這個(gè)游戲。
有兩堆火柴棍,每次可以從某一堆取至少1根火柴棍(無(wú)上限)，或者從兩堆取相同的火柴棍數(shù)。最后取完的是勝利者。好了,如果你不知道這個(gè)博弈定理,對(duì)于小數(shù)目的火柴棍數(shù),可能還能推出來(lái),但是如果火柴棍數(shù)一多,就不行了。看了下面的這個(gè)介紹,你也會(huì)有一種被騙的感覺(jué)。
首先我們知道兩堆火柴是沒(méi)有差別的,也就是說(shuō)第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一樣的結(jié)果。
我們用一個(gè)二維的狀態(tài)（a,b)來(lái)記錄當(dāng)前剩下的火柴數(shù)，表示第一堆剩下a根火柴,第二堆剩下b根火柴。同樣我們假設(shè)兩個(gè)人的編號(hào)是A和B，且A先取。
那么如果某個(gè)人遇到了這樣的狀態(tài)(0,0)那么也就是說(shuō)這個(gè)人輸了。這樣的狀態(tài)我們叫做奇異狀態(tài),也可以叫做失敗態(tài)。
那么接下來(lái)的幾個(gè)失敗態(tài)為(1,2),(3,5),(4,7),(6,10),(8,13)……
我們用a[i]表示失敗態(tài)中的第一個(gè),b[i]表示失敗態(tài)中的第二個(gè).(i從0開(kāi)始).
那么我們可以看到b[i] = a[i]+i;（i >= 0）,a[i]是前面的失敗態(tài)中沒(méi)有出現(xiàn)過(guò)的最小的整數(shù)
下面我們可以得到三個(gè)基本的結(jié)論。
1.每個(gè)數(shù)僅包含在一個(gè)失敗態(tài)中
首先我們知道a[k]是不可能和前面的失敗態(tài)中的a[i],b[i]重復(fù)的(這點(diǎn)由a[i]的得到可以知道)
b[k] = a[k]+k > a[k-1]+k>a[k-1]+k-1+1>a[k-1]+(k-1) = b[k-1]>a[k-1]這樣我們知道每個(gè)數(shù)僅在一個(gè)失敗態(tài)中。
2.每個(gè)失敗態(tài)可以轉(zhuǎn)到非失敗態(tài)。
加入當(dāng)前的失敗態(tài)為(a,b)，那么如果我們只在一堆中取的話,肯定會(huì)變成非失敗態(tài)(這點(diǎn)由第一點(diǎn)可以保證),如果從兩堆同時(shí)取的話,由于每個(gè)失敗態(tài)的差是不一樣的,所以也不可能得到一個(gè)失敗態(tài)。也就是說(shuō)一個(gè)失敗態(tài)不管你怎么取,都會(huì)得到一個(gè)非失敗態(tài)。
3.每個(gè)非失敗態(tài)都可以轉(zhuǎn)到一個(gè)失敗態(tài)
對(duì)于這個(gè)結(jié)論,首先我們要知到每個(gè)狀態(tài)(a,b)要么a = a[i],要么b = b[i].(每個(gè)數(shù)都出現(xiàn)在一個(gè)失敗態(tài)中),下面我們分兩種情況來(lái)討論
I.a = a[i].如果b = a的話那么一次取完就變成了(0,0).如果b > b[i]的話,那么我們從第二堆中取走b-b[i]就變成了一個(gè)失敗態(tài)。如果b < b[i].那么我們從兩堆中同時(shí)取走a-a[b-a[i]]這樣得到失敗態(tài)(a[b-a[i]],a[b-a[i]]+b-a[i])(a[i] = a)
II.b = b[i].如果a > a[i]那么我們從第一堆中取走a-a[i]根火柴.
如果a < a[i].這里又分兩種情況。第一是a = a[k](k < i)
那么我們從第二堆取走b - b[k]就行了。
第二是a = b[k]這樣的話由于兩堆火柴是沒(méi)有區(qū)別的,所以我們把b變成a[k]就行了,也即是從第二堆火柴中取走b - a[k]就變成了失敗態(tài)
至于怎么判斷一個(gè)狀態(tài)是否是失敗態(tài).我們可以用下面的方法來(lái)判斷(本人暫時(shí)還不會(huì)證明)
a[i] = [i*(1+√5)/2](這里的中括號(hào)表示向下取整) b[i] = a[i]+i;
那么這就是一個(gè)失敗態(tài),
看了這之后可以去找POJ1067練練手
三．尼姆博奕（Nimm Game）：
這個(gè)已經(jīng)變成了三堆火柴了。每次只能從某一堆取任意個(gè)(至少為1)，最后取完的為勝利者。
這個(gè)博弈我們用三維的狀態(tài)來(lái)表示(a,b,c).對(duì)于每個(gè)失敗態(tài)我們有a^b^c = 0至于為什么我暫時(shí)不會(huì)證(記得陳景潤(rùn)的一本組合數(shù)學(xué)中有證明,后面要是懂了再來(lái)補(bǔ)吧)
對(duì)于一個(gè)非失敗態(tài)我們可以通過(guò)轉(zhuǎn)換得到一個(gè)失敗態(tài),也就是說(shuō)(a,b,c)我們可以通過(guò)如下的操作得到一個(gè)失敗態(tài),如果a^b < c那么我們從第三堆中取走c-a^b根,如果a^c < b那么我們從第二堆中取走b - a^c根.如果b^c < a那么我們從第一堆中取走a - b^c根。這樣就變成了一個(gè)失敗態(tài)。
由于水平有限,暫時(shí)只能寫(xiě)這么多了。