分類
發燒車訊

博弈論——兩人取子遊戲與威佐夫博弈,隱藏在背後的黃金分割

本文始發於個人公眾號: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定理與必敗狀態的性質:

\[[an] + n = [bn], \frac{1}{a} + \frac{1}{b} = 1 \]

\[[an] + n = [an + n] = [(a+1)n] = [bn] \]

代入可以得到:

\[\frac{1}{a} + \frac{1}{a+1} = 1 \]

解這個方程,可以得到\(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定理,這個定理的推導和證明雖然不難,但是如果不是數學專業的同學,可能大概率都沒有接觸過。這其實體現了博弈論本身和數學的關係是非常緊密的。一個看起來非常簡單的問題,引申出了一系列眼花繚亂的推導和證明,怎麼樣,大家看得還過癮嗎?

今天的文章到這裏就結束了,如果喜歡本文,可以的話,請點個關注,給我一點鼓勵,也方便獲取更多文章。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站,提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞,目前市場使用率逐漸普及化

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?