雲栖号資訊：【 點選檢視更多行業資訊】
在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！
博弈論是一門很龐大的學科，它算是數學的一個分支，也和運籌學甚至是經濟學有關。雖然它嚴格說起來并不是算法領域的内容，但是有不少關于博弈論有趣的算法和問題。關于博弈的相關理論從很早就已經有了雛形，但是正式建構理論成為一門學科是從計算機之父馮諾依曼開始的。從這點上來說也和計算機有點關系。
今天我們來聊聊博弈論當中最簡單的巴什博奕（Bash Game）。
報數問題
說到巴什博奕就不能不提報數問題，它實在是太經典了，以至于我覺得你很有可能也聽說過。題目是這樣的，說是A和B兩個人一起玩一個報數遊戲，兩個人輪流報數，每次最少報一個數，最多報5個數，第一個報到100的人獲勝。如果你是先手的A，應該采取什麼政策？
如果之前沒有思考過這個問題或者是了解過博弈論的話，估計你可能會覺得這個問題很複雜，也很困難，應該沒有什麼好的辦法。因為兩個人每次都可以做好幾種選擇，每一種選擇又會帶來不同的選擇，這樣依次交錯會帶來大量的可能性。在這種情況下，似乎很難想出一個算法來解決問題。
報到100看不出來，我們縮小一下，如果報到6的人獲勝呢？是不是就很明顯了，先手的A不論采取什麼政策都一定輸。因為它不論報幾個數，B都可以直接報到6。
既然報6個數的時候A一定必輸，那麼可以推導得到報的數如果是6的倍數A都一定必輸。假設它在某一輪當中報了i，對方隻要報6-i就行了。這樣重複若幹次之後最後一定會剩下6，那麼就回到了上面說的最簡單的情況。
假設我們開發出了一個state函數可以計算某個狀态先手是必勝還是必敗，我們用1表示先手必勝，0表示必敗。那麼顯然state(0) = 0，state(6) = 0。由于不論先手在每一輪當中報幾，後手都可以控制報一個和它加起來等于6的數，是以可以得到state(n) = state(n-6)。于是，我們可以推導出state(6n) = 0。
由于先手每次可以報1-5個數，當他面臨一個6n+k的局面的時候，隻要k不等于0。那麼他就報k個數，就可以讓局面轉化成6n的必敗局面給B。是以可以知道，除了6n的局面之外的所有局面都是先手必勝的。
我們用代碼實作的話就隻有一行：
def win_or_lose(n):
return n % 0 != 0 博弈論的精髓在于對問題的分析，展現在代碼上就是思維比較複雜，但是代碼極為精簡。
報數這個問題比較直覺，是以找找規律仔細想想也是可以猜出答案來的。但如果我們包裝一下，可能就不一樣了。
打牌問題
這題源自HDU1847，題面是兩個人打牌，一共有n張牌，雙方輪流抓牌。規定每人每次抓牌的數量必須是2的幂，最後抓完排的人獲勝。假設兩人都是極端聰明，請問最後會是誰獲勝。
假設兩個人極端聰明，這是博弈論問題的前提，也就是說兩個人都會采取最優政策。沒有這個前提，就無法使用博弈論進行分析了，因為它就不再是單純的數學問題了。
和上面的題目相比，這題變得複雜了。因為每個人采取的政策數量變了，之前是嚴格限制了隻有5種可能，現在則變成了無數種。但其實這裡使用了障眼法，藏了一個trick。
我們首先把2的幂都列出來，從2的0次方開始，分别是1, 2, 4, 8...。看到這個1和2不知道大家有沒有什麼想法，其實如果你稍微了解一點數論的話就會知道，2的幂一定不能被3整除。也就是說2的幂模3的結果隻會有兩種，也就是1或者是2。是以這道題其實和上面一題是一樣的， 我們拿2的幾次幂不重要，重要的是拿的數模3之後餘下的幾。
state(0) = 0，因為對方已經拿完了。那麼state(1) = state(2) = 1，隻剩一張或者兩張牌的時候可以一次全拿完。state(3) = 0，因為無法一次拿完。我們推廣可以得到state(3n) = 0。也就是3的倍數對于先手是必敗的。由于我們剛才說了，2的幂模3一定是1或者是2。是以可以得到，對于先手來說，隻要面臨的狀态不是3的倍數，就一定必勝。因為他一定可以找到一個2的幂，使得拿完之後留下3的倍數給對方。
分析完了之後，代碼又隻有一行：
def win_or_lose(n):
return n % 3 != 0 總結
巴什博奕的問題很簡單，一旦摸清楚了套路之後，這一系列類似的問題都手到擒來。但是要注意的是，面臨巴什博奕的問題，我們不能隻是簡單地了解成是湊成一個數，或者是找到一個必勝或者必敗的政策。而是要從狀态的角度去分析它，究竟什麼樣的狀态是必勝或者是必敗的，狀态之間又存在什麼樣的轉移關系。
從這點上來看似乎又有點動态規劃的意思，但不一樣的是動态規劃算法解決的都是邊界有限的問題。而博弈論當中有的時候政策或者是狀态可能是無限的，但是兩者的确有相通的部分。巴什博奕隻是博弈論算法當中最簡單的算法，後面我們還會繼續研究其他更複雜一些的博弈論問題。
【雲栖号線上課堂】每天都有産品技術專家分享！
課程位址：
https://yqh.aliyun.com/live立即加入社群，與專家面對面，及時了解課程最新動态！
【雲栖号線上課堂 社群】
https://c.tb.cn/F3.Z8gvnK
原文釋出時間：2020-06-13
本文作者：承志
本文來自：“
掘金”，了解相關資訊可以關注“掘金”
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)