下面我們以一種游戲的方式來引進三種基本的博弈問題。

一．巴什博奕（Bash Game）：

首先我們來玩一個比較古老的報數游戲。A和B一起報數，每個人每次最少報一個,最多報4個。輪流報數,看誰先報到30.

如果不知道巴什博弈的可能會覺得這個是個有運氣成分的問題，但是如果知道的人一定知道怎樣一定可以贏。

比如A先報數的話,那么B一定可以贏(這里假定B知道怎么正確的報數)

B可以這樣報數,每次報5-k(A)個數,其中k(A)是A報數的個數這樣的話沒一次

兩人報完數之后會變成5 10 15 20 25 30這樣是不是B一定會贏呢?是不是有一種被欺騙的感覺呢?好吧下面我們來看看這個原理。我們先看下一個一眼就能看出答案的例子 比如說我們報到5(4+1),每次報最多報4個,最少報1個.那么是不是后者一定可以贏呢？答案是肯定的。好了到這巴什博弈的精髓基本就OK了。

那么如果我們要報到n+1,每次最多報n個,最少報1個的話,后者一定能夠贏。

現在我們需要報數到n,而每次最多報數m個,最少報數1個.我們可以化成這樣

n = k*(1+m)+r(0 <= r <= m）這樣的話如果r不等于0那么先手一定會贏，為什么呢？首先先手報r個,那么剩下k倍(1+m)個數,那么我們每次報數1+m-k(B)個數就一定能保證最后剩下1+m個,那么就到了上面我們說的那個了,先手就一定會贏,如果r=0那么后手一定會贏,道理一樣的。

到這巴什博弈也就介紹完了,知道這個道理之后我們也可以去騙小朋友了。-_-//

二．威佐夫博奕（Wythoff Game）：

   這種博弈比前面一種要稍微復雜一點。我們來看下下面這個游戲。

   有兩堆火柴棍,每次可以從某一堆取至少1根火柴棍(無上限)，或者從兩堆取相同的火柴棍數。最后取完的是勝利者。好了,如果你不知道這個博弈定理,對于小數目的火柴棍數,可能還能推出來,但是如果火柴棍數一多,就不行了。看了下面的這個介紹,你也會有一種被騙的感覺。

   首先我們知道兩堆火柴是沒有差別的,也就是說第一堆有a根,第二堆有b根和第一堆有b根,第二堆有a根是一樣的結果。

   我們用一個二維的狀態（a,b)來記錄當前剩下的火柴數，表示第一堆剩下a根火柴,第二堆剩下b根火柴。同樣我們假設兩個人的編號是A和B，且A先取。

那么如果某個人遇到了這樣的狀態(0,0)那么也就是說這個人輸了。這樣的狀態我們叫做奇異狀態,也可以叫做失敗態。

那么接下來的幾個失敗態為(1,2),(3,5),(4,7),(6,10),(8,13)……

我們用a[i]表示失敗態中的第一個,b[i]表示失敗態中的第二個.(i從0開始).

那么我們可以看到b[i] = a[i]+i;（i >= 0）,a[i]是前面的失敗態中沒有出現過的最小的整數

下面我們可以得到三個基本的結論。

  1.每個數僅包含在一個失敗態中

  首先我們知道a[k]是不可能和前面的失敗態中的a[i],b[i]重復的(這點由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]這樣我們知道每個數僅在一個失敗態中。

  2.每個失敗態可以轉到非失敗態。

 加入當前的失敗態為(a,b)，那么如果我們只在一堆中取的話,肯定會變成非失敗態(這點由第一點可以保證),如果從兩堆同時取的話,由于每個失敗態的差是不一樣的,所以也不可能得到一個失敗態。也就是說一個失敗態不管你怎么取,都會得到一個非失敗態。

   3.每個非失敗態都可以轉到一個失敗態

對于這個結論,首先我們要知到每個狀態(a,b)要么a = a[i],要么b = b[i].(每個數都出現在一個失敗態中),下面我們分兩種情況來討論

   I.a = a[i].如果b = a的話那么一次取完就變成了(0,0).如果b > b[i]的話,那么我們從第二堆中取走b-b[i]就變成了一個失敗態。如果b < b[i].那么我們從兩堆中同時取走a-a[b-a[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]這樣的話由于兩堆火柴是沒有區別的,所以我們把b變成a[k]就行了,也即是從第二堆火柴中取走b - a[k]就變成了失敗態

至于怎么判斷一個狀態是否是失敗態.我們可以用下面的方法來判斷(本人暫時還不會證明)

  a[i] = [i*(1+√5)/2](這里的中括號表示向下取整)   b[i] = a[i]+i;

  那么這就是一個失敗態,

 看了這之后可以去找POJ1067練練手

三．尼姆博奕（Nimm Game）：

  這個已經變成了三堆火柴了。每次只能從某一堆取任意個(至少為1)，最后取完的為勝利者。

  這個博弈我們用三維的狀態來表示(a,b,c).對于每個失敗態我們有a^b^c = 0至于為什么我暫時不會證(記得陳景潤的一本組合數學中有證明,后面要是懂了再來補吧)

  對于一個非失敗態我們可以通過轉換得到一個失敗態,也就是說(a,b,c)我們可以通過如下的操作得到一個失敗態,如果a^b < c那么我們從第三堆中取走c-a^b根,如果a^c < b那么我們從第二堆中取走b - a^c根.如果b^c < a那么我們從第一堆中取走a - b^c根。這樣就變成了一個失敗態。

由于水平有限,暫時只能寫這么多了。