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