博弈論總結框架?今天是算法與數據結構專題的第24篇文章，我們一起來聊聊有趣的博弈論問題，今天小編就來聊一聊關于博弈論總結框架?接下來我們就一起去研究一下吧!

博弈論總結框架

今天是算法與數據結構專題的第24篇文章，我們一起來聊聊有趣的博弈論問題。

博弈論是一門很龐大的學科，它算是數學的一個分支，也和運籌學甚至是經濟學有關。雖然它嚴格說起來并不是算法領域的内容，但是有不少關于博弈論有趣的算法和問題。關于博弈的相關理論從很早就已經有了雛形，但是正式構建理論成為一門學科是從計算機之父馮諾依曼開始的。從這點上來說也和計算機有點關系。

今天我們來聊聊博弈論當中最簡單的巴什博奕（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 % 6 != 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。所以可以得到state(2^k)=1，對于先手來說，隻要面臨的狀态不是3的倍數，就一定必勝。因為他一定可以找到一個2的幂，使得拿完之後留下3的倍數給對方。

分析完了之後，代碼又隻有一行：

def win_or_lose(n): return n % 3 != 0

總結

巴什博奕的問題很簡單，一旦摸清楚了套路之後，這一系列類似的問題都手到擒來。但是要注意的是，面臨巴什博奕的問題，我們不能隻是簡單地理解成是湊成一個數，或者是找到一個必勝或者必敗的策略。而是要從狀态的角度去分析它，究竟什麼樣的狀态是必勝或者是必敗的，狀态之間又存在什麼樣的轉移關系。

從這點上來看似乎又有點動态規劃的意思，但不一樣的是動态規劃算法解決的都是邊界有限的問題。而博弈論當中有的時候策略或者是狀态可能是無限的，但是兩者的确有相通的部分。巴什博弈隻是博弈論算法當中最簡單的算法，後面我們還會繼續研究其他更複雜一些的博弈論問題。

如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本文始發于公衆号：TechFlow

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!