靜態博弈論
——“穿越沙漠”游戲決策設計

王永源 孟航宇 張 偉 陳春宇

（南京工業大學海外教育學院，江蘇 南京210000）

1 概述

沙漠作為近年來的熱門話題，其天氣和氣候特點對全球生態環境的影響逐漸增強，引起了社會各界人士的廣泛關注。保護自然，關注沙漠成為當下的熱點。為了引起更多人的關注，結合當今互聯網時代具有易傳播，發散性廣的特點，在游戲中融入沙漠元素已經成為一種發展趨勢。玩家在游戲中面對不同的地圖，會遇到不同的沙漠特色地區，例如礦山和村莊。玩家在礦山和村莊會有相應的材料進行補充，得到繼續游戲的機會。

2 基本規則

考慮本游戲：玩家憑借一張地圖，在初始點使用初始資金購買一定數量的水和食物（包括食品和其他日常用品），從初始點出發，在沙漠中徒步。在沙漠途中會遇到不同的天氣，玩家也可以在礦山、村莊補充資金或資源。目標是玩家在規定時間內到達終點，并保留盡可能多的資金（包括資源折合的資金）。

游戲的基本規則如下：

2.1 以天為基本時間單位，游戲的開始時間為第0 天，玩家位于初始點，必須在截止日期或之前到達終點，到達終點后該玩家的游戲結束。

2.2 穿越沙漠需水和食物兩種資源，它們的最小計量單位均為箱。每天玩家擁有的水和食物質量之和不能超過玩家負重上限。若未到達終點而水或食物已耗盡，視為游戲失敗。

2.3 每天的天氣為“晴朗”、“高溫”、“沙暴”三種狀況之一，沙漠中所有區域的天氣相同。

2.4 每天玩家可從地圖中的某個區域到達與之相鄰的另一個區域，也可選擇在原地停留。沙暴日必須在原地停留。

2.5 玩家在原地停留一天消耗的資源數量稱為基礎消耗量，行走一天消耗的資源數量為基礎消耗量的2 倍。

2.6 玩家第0 天可在起點處用初始資金以基準價格購買水和食物。玩家可在起點停留或回到起點，但不能多次在起點購買資源。玩家到達終點后可退回剩余的水和食物，每箱退回價格為基準價格的一半。

2.7 玩家在礦山停留時，可通過挖礦獲得資金，挖礦一天獲得的資金量稱為基礎收益。如果挖礦，消耗的資源數量為基礎消耗量的3 倍；如果不挖礦，消耗的資源數量為基礎消耗量。到達礦山當天不能挖礦，沙暴日也可挖礦。

2.8 玩家經過或在村莊停留時可用剩余的初始資金或挖礦獲得的資金隨時購買水和食物，每箱價格為基準價格的2 倍。

參數設定

天氣狀況

地圖

3 問題的分析

對于多人游戲，在分析機制后建立了靜態博弈模型。首先對卡關的幾種較優單人決策進行分析，建立起兩兩間的博弈收益函數表，根據收益表分別進行純決策和混合決策分析。然后得出均衡的解為雙方采用3 天到達終點的決策并會選擇在起點購買足夠生存的物資。最后我們分析了模型的優缺點和靈敏度，結果顯示模型對于這一類問題具有比較好的適應性，提煉出的規則可以有效指導玩家決策。

4 模型的假設

4.1 不存在半路丟掉食物或將食物暫時放到路上的情況。

4.2 保證補給點有足夠的食物補給，不存在斷貨缺貨的問題。

4.3 不考慮玩家其他時間消耗，只考慮題目中所提及的時間消耗。

5 符號說明

?

6 模型的建立與求解

由于有不止一個玩家，并且玩家在游戲中的狀態更新會受到對方情況的影響，因此每個玩家為了實現自己的游戲目標，必須考慮對方的行動決策。因此用博弈的模型來考慮，雙方同時進行一次決策，為單階段靜態博弈。

6.1 兩人單階段博弈

6.1.1 博弈設定與求解目標

有兩位玩家A、B。我們假設兩個玩家都是具有充分思維能力的理性玩家，可以依據情況進行判斷。設計的目標是使A 能夠在B 按照符合B 利益前提下行動時讓自己獲得最大的期望收益。

因為A、B 玩家角色地位是平等的，擁有相同的資金，即兩個玩家的決策集是完全一致，因此我們為A 設定的決策對B 也是同樣適用的。

6.1.2 思路分析

可行的方案大致有兩類：第一類為純決策，兩個玩家使用同一種固定決策，走同一條路徑。第二類為混合決策，根據題目可知，一名玩家的決策會影響其他玩家的利益，也就是說每個人的決策方案會影響到其他人的決策方案。且題目要求，n 名玩家需在第0 天時把方案確定，之后不能更改，此時玩家所剩資金（包括資源折合的資金）要達到最大值。因此我們查閱了博弈論有關的資料，針對題目要求建立相關博弈論模型。

6.2 題目一般決策

天氣情況全部已知且存在多個玩家的單階段博弈：

由于中途失敗造成的損失巨大，玩家的首要目的是生存，因此要在起點處購買足夠多的食物和水，然后猜測其他玩家可能會采取的行走路線，這些路線是天氣已知的單玩家模式下的較優行走決策，運用博弈論的方法尋找納什平衡，納什平衡給出的決策就是玩家們的行動決策。

6.3 單階段博弈模型的建立

6.3.1 對于玩家的資源

設共有n 名玩家，由題意可知，當有多名玩家走相同路線時，消耗的資源量會增加，挖礦獲得的收益會減少，購買補給所需的資源也會翻倍。所以為了獲取最大利益，我們應盡量安排各位玩家不同的路線，即進行兩兩比較。

在一個博弈過程中，無論對方的決策選擇如何，當事人一方都會選擇某個確定的決策，則該決策被稱作支配性決策。如果任意一位參與者在其他所有參與者的決策確定的情況下，其選擇的決策是最優的，那么這個組合就被定義為納什平衡。

根據納什平衡，我們進行模型建立：

以玩家1，2 為例，不妨設他們各有n1,n2 種決策方案，則他們在同一地圖中所用方案的集合為：

對于各名玩家來說，當一名玩家決定其路線時，其他玩家應避免相同路徑，并從其他剩余路徑中選擇最適路徑。這一規則也符合納什平衡。由于各位玩家選擇的路徑決定了他們資金的多少。

則玩家1，2 所用資金可由下列矩陣表示：

該矩陣中，aij（i=1,2……，j=1,2……）表示，玩家1 在玩家2選擇路徑之后選擇的其他最優路徑數目。

6.3.2 對于兩名玩家的數值期望

設玩家1 選擇第i 條路的概率為Pi(i=1,2……)，玩家2 選擇第j 條路的概率為Qj(j=1,2……)

則其數學期望分別為：

6.3.3 基于靜態博弈論所設計的決策模型

對于玩家1 和玩家2，他們選擇的決策應使其數學期望最大，即

在博弈論中，我們由納什平衡可知，無論對方的決策選擇如何，當事人一方都會選擇某個確定的決策，則該決策被稱作支配性決策。如果任意一位參與者在其他所有參與者的決策確定的情況下，其選擇的決策是最優的。此時，總存在各玩家獲利達到最大值與其他玩家獲利達到最小值的情況。所以，該模型可轉化為：

由于本卡關只有兩名玩家，情況較少，所以可以用Lingo 編程求解。為獲得最佳決策，玩家一定會從我們之前制定的路徑進行選擇。因此我們首先確定幾條較好路徑，兩名玩家到達終點時剩余資金（包括剩余資源折合的資金）較多。

7 模型的總結與優缺點分析

7.1 優點分析

7.1.1 本關卡的最終結果可猜證

由于玩家人數少且天氣情況已知，所以結果具有可猜證性，但能給出充分的思想來源和令人信服的論證并不容易。我們從統計結果抽取決策，并利用隨機模擬較為完整地論證了該方案確實優于其他合理方案。

7.1.2 本關卡問題的二人博弈模型給出一系列有效的局部決策

由于多人游戲的復雜性使得一些規律性結論比確定性的計算機算法更有意義。因此這一部分我們用數學推導給出的可靠決策結論能夠更有效地幫助實際游戲。

7.2 缺點分析

7.2.1 利用確定天氣情況下求解結果后本問題時沒有定量分析產生的偏差

盡管我們可以通過動態規劃回溯出優秀解，但在天氣未知的情況下這些解具有偶然性。雖然天氣已知，但最高收益和存活率二者是相互制衡的，而我們在分析一些優秀解的時候雖然也重點考慮了存活率，但無法給出描述幸存者偏差的量并加以討論。

7.2.2 給出的決策更加客觀合理

我們給出的有些決策難以通過直覺或人工計算快速得到驗證，都需要一定的程序，所以這些結果可能不易于從直觀上理解。

7.2.3 對于多人玩家的情況沒有給出完全最優解

雖然我們給出了最優決策，但對于多人的多階段靜態博弈沒有給出完全最優解。由于博弈的過程難以由程序體現，最后的博弈過程沒有進行模擬和全局計算。

8 結論

本文我們對“穿越沙漠”游戲的決策進行了由淺入深的分析，對于越來越復雜的問題也有確定性決策求解轉化為帶有隨機性、局部性優化，并利用各種評價方法進行討論分析。