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