今天是算法和數(shù)據(jù)結(jié)構(gòu)專題第25篇文章，我們繼續(xù)博弈論專題。
在上一篇文章當中我們了解了最簡單的巴什博弈，今天我們來看看另一個經(jīng)典的博弈模型——威佐夫博弈。博弈論和機器學習有些類似，數(shù)學家們針對場景進行建模，設計出了幾個經(jīng)典模型。然后我們在面臨具體問題的時候，對問題進行深入分析，尋找最合適的模型應用來解決它。
我們來看一道經(jīng)典的例題，有兩堆石子，有兩個絕頂聰明的人在玩一個游戲。每次每個人可以從其中一堆石子當中取走任意數(shù)量的石子，或者是從兩堆當中同時取走相同數(shù)量的石子。無法取石子的人落敗，請問，在告知兩堆石子數(shù)量的情況下，這兩個人當中哪一方會獲勝？
我們簡單分析一下，會發(fā)現(xiàn)一些局面是先手必敗的。比如說(0, 0)，再比如(1, 2)。我們簡單分析一下(1, 2)，先手有4種策略，首先他可以取走第一堆，那么后手可以取完第二堆，顯然后手獲勝。他也可以在第二堆當中取1個，這時剩下(1, 1)，后手會同時取完，同樣是后手獲勝。第三種是他取走第二堆，后手可以取完第一堆，后手獲勝。第四種是他在第一堆和第二堆當中同時取走一個，這時第二堆剩下一個，后手勝。
那么，這些必敗的狀態(tài)之間有什么規(guī)律呢？我們怎么找到這個規(guī)律，并且找到解呢？
我們可以枚舉幾個必敗的狀態(tài)：(0, 0), (1, 2), (3, 5), (4, 7)...
我們觀察一下這些狀態(tài)，可以找到兩條規(guī)律。我們假設從小到大排的第k個必敗狀態(tài)是(x, y)，并且x < y。我們可以發(fā)現(xiàn)y = x + k。也就是說必敗狀態(tài)兩個數(shù)的差值是遞增的，這也說明了每一個必敗狀態(tài)的差值都各不相同。
其實這是很容易證明的，我們用反證法，假設(a, a+k), (b, b+k)都是必敗狀態(tài)，并且a < b。那么先手在面臨(b, b+k)的時候，只需要在兩堆當中同時取走b-a個石子，那么給后手的局面就是(a, a+k)。對于后手來說，這是一個必敗的局面，這就和(b, b+k)先手必敗矛盾，所以不存在兩個必敗局面的差值相等。
我們也可以作圖分析，我們把兩堆石子的數(shù)量看成是坐標軸上的一個點。所以游戲就變成了：棋盤上有一個點，每次每個人可以將它向下、向左或者向左下移動若干個格子，不能移動的人輸。終止節(jié)點顯然是原點，一步就能移動到原點的點顯然是必勝點，假設我們給這些所有必勝點都染色的話，剩下的的沒當中橫縱坐標和最小的點就是下一個必敗點。因為它不論如何移動，都會給對手留下一個必勝點。
我們根據(jù)上面的邏輯把必敗點都染色，可以得到下面這張圖：
從這張圖可以看出，必敗點之間不能通過一次移動得到，換句話說可以一次移動到必敗點的點都是必勝點，從圖上可以看出，除了必敗點的之外的點都是必勝點，并且每一個自然數(shù)都必然只會被包含在一個必敗狀態(tài)當中。
到這里，我們距離解法已經(jīng)很接近了，現(xiàn)在剩下的問題是，我們?nèi)绾胃鶕?jù)x和y的取值快速判斷它們是否構(gòu)成一個必敗局面呢？也就是說我們能不能找出一個通項公式，對于第k個必敗局面，它的坐標是(
x_k, y_k)呢？
求解為了寫出通項公式，我們需要引入Betty定理。
我們花了這么大力氣來證明Betty定理就是為了用的，因為我們發(fā)現(xiàn)必敗狀態(tài)的通項和Betty定理序列很像。我們不妨假設存在這樣的a, b同時滿足Betty定理與必敗狀態(tài)的性質(zhì)：
代入可以得到：
解這個方程，可以得到 a = (1 + sqrt(5) ) / 2 約等于 1.618，熟悉數(shù)學的同學相信一下就看出來了，這個數(shù)是黃金分割的比例，這是巧合嗎，還是藏著更深的道理呢？
至少，求出了a之后，我們就可以非常簡單地判斷必敗狀態(tài)了：
import mathdef lose_or_win(a, b): if a > b: a, b = b, a k = b - a # 根據(jù)差值k求出第k個必敗狀態(tài)，判斷是否相等 return not (int(k * (math.sqrt(5)+1) / 2)) == a和之前介紹的巴什博弈相比，威佐夫博弈的推導過程要復雜得多，但是雖然推導過程依然復雜，但是仍然擋不住最后實現(xiàn)的代碼非常簡單。
另外，在推導的過程當中，我們用到了Betty定理，這個定理的推導和證明雖然不難，但是如果不是數(shù)學專業(yè)的同學，可能大概率都沒有接觸過。這其實體現(xiàn)了博弈論本身和數(shù)學的關系是非常緊密的。一個看起來非常簡單的問題，引申出了一系列眼花繚亂的推導和證明，怎么樣，大家看得還過癮嗎？
今天的文章到這里就結(jié)束了，如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。
本文始發(fā)于公眾號：TechFlow
