付芷睿 李雪純 李興睿

（武漢大學(xué)，湖北 武漢 430000）

1 模型假設(shè)

1.假設(shè)玩家都是理性的，追求的目標(biāo)僅是到達(dá)終點(diǎn)時(shí)獲取的總利益最大；

2.假設(shè)區(qū)域可以抽象成一個(gè)點(diǎn)；

3.假設(shè)以下的初始值是不變的：負(fù)重上限恒為1200kg，初始資金恒為10000元，每箱水的質(zhì)量為3kg，食物的質(zhì)量為2kg，每箱水的基準(zhǔn)價(jià)格為5元/箱，食物的基準(zhǔn)價(jià)格為10元/箱。

2 模型準(zhǔn)備

2.1 地圖的要素提取及簡(jiǎn)化

首先，對(duì)于形狀不規(guī)則的地圖進(jìn)行抽象處理，提取出起點(diǎn)、終點(diǎn)、村莊和礦山四個(gè)要素，其余點(diǎn)均視為普通點(diǎn)。

2.2 最短路徑

為了使得到達(dá)終點(diǎn)時(shí)剩余資金最大，玩家應(yīng)盡量減少行走過(guò)程中的消耗，因此玩家在起點(diǎn)出發(fā)后，會(huì)立即以最短路徑前往村莊、礦山或終點(diǎn)其中之一。

2.3 定義消耗上限與收益下限

消耗上限：假設(shè)全程30天均為沙暴天氣，計(jì)算出玩家的物資消耗量，稱作消耗上限。

收益下限：假設(shè)挖礦時(shí)均遇到沙暴天氣，計(jì)算出此時(shí)的挖礦收益，稱作收益下限。

在只知道當(dāng)天天氣的情況下，玩家應(yīng)對(duì)此后的天氣進(jìn)行最壞的打算，計(jì)算出消耗上限與收益下限，權(quán)衡下一步的行動(dòng)。

2.4 停留

初步分析可知，停留的條件有兩種：

（1）沙暴時(shí)必須在原地，不能移動(dòng)；

（2）到達(dá)礦山后，由于挖礦的消耗為基礎(chǔ)消耗量的三倍，并且高溫天氣與沙暴天氣相對(duì)于晴朗天氣的基礎(chǔ)消耗量都顯著提高，所以為了挖礦期間的消耗盡可能少，可能會(huì)根據(jù)需要在沙暴天或高溫天不挖礦，通過(guò)簡(jiǎn)單演算，我們規(guī)定每一關(guān)卡除沙暴天以外，其余總的停留時(shí)間不超過(guò)兩天。

3 基于單目標(biāo)規(guī)劃模型的最優(yōu)策略求解

3.1 單目標(biāo)規(guī)劃模型的建立

3.1.1 決策變量的確定

（1）玩家在第i天的位置xi，i=0,…,N，xi∈A。其中，N表示游戲的截止日期，A表示地圖上所有區(qū)域的序號(hào)的集合。特別地，當(dāng)玩家在第n天到達(dá)終點(diǎn)后，我們約定玩家位置始終位于終點(diǎn)；

綜合上述變量，決策變量可統(tǒng)一表示為向量Xi=(xi,vi,ui,ai,bi)，。

3.1.2 目標(biāo)函數(shù)的確定

其中：

S0表示挖礦的基礎(chǔ)收益，ai和bi分別表示玩家在第i天購(gòu)買的水和食物的數(shù)量，wi為第i天的天氣狀況：

3.1.3 約束條件

條件一：任意第i天包內(nèi)都有剩余物資且總負(fù)重mi不超過(guò)負(fù)重上限1200kg；

條件三：當(dāng)天氣狀況為沙暴時(shí)，玩家必須在原地停留一天，即第i+1天和第i天位置相同；

條件四：玩家每天只能從目前區(qū)域到達(dá)與之相鄰的區(qū)域，或在目前區(qū)域停留一天；

綜上，建立單目標(biāo)規(guī)劃模型即可。

3.2 求解模型得出一般策略

3.2.1 求解一般策略的思維過(guò)程

由于直接求解上述優(yōu)化問(wèn)題時(shí)間和電腦儲(chǔ)存空間開銷較大，因此我們首先根據(jù)不同類型的地圖所含要素進(jìn)行分類討論，將全程路線分為挖礦與不挖礦兩種路線。

路線一：不經(jīng)過(guò)村莊或礦山。通過(guò)選擇最短路徑，計(jì)算出玩家最快到達(dá)終點(diǎn)的日期n，可得最終剩余資金為：

路線二：經(jīng)過(guò)村莊和礦山。當(dāng)玩家采取挖礦的路線時(shí)，我們又將全程分為從起點(diǎn)到礦山、挖礦過(guò)程和從礦山到終點(diǎn)三個(gè)階段處理，并且給出每個(gè)階段玩家應(yīng)采取的策略，最后給出整體算法。

階段1：起點(diǎn)-礦山

1.起點(diǎn)物資量

由于村莊中物資的價(jià)格為基準(zhǔn)價(jià)格的2倍，因此為了節(jié)約資金，玩家應(yīng)在起點(diǎn)處購(gòu)買盡可能多的物資。

2.到達(dá)礦山的路徑及日期

為了減少行走的消耗，玩家應(yīng)當(dāng)盡快前往礦山，僅在沙暴天氣停留。通過(guò)選擇最短路徑，可以得到玩家最快到達(dá)礦山的路徑及日期。

階段2：礦山挖礦，中途去村莊補(bǔ)給

1.挖礦天數(shù)

根據(jù)階段1和階段2計(jì)算的到達(dá)與離開礦山的日期，可得玩家挖礦的天數(shù)。

2.去村莊補(bǔ)給的日期

在物資即將不足但是恰好能維持玩家抵達(dá)村莊時(shí)，離開礦山前往村莊。根據(jù)往返礦山和村莊之間需要花費(fèi)的時(shí)間，計(jì)算出最多可以前往村莊的次數(shù)。

3.購(gòu)買補(bǔ)給的數(shù)量

應(yīng)滿足補(bǔ)給后的物資足夠玩家維持到下一次補(bǔ)給。

階段3：礦山-終點(diǎn)

離開礦山的日期。為了使收益最大，玩家應(yīng)當(dāng)用盡可能多的天數(shù)挖礦，通過(guò)選擇最短路徑并且考慮食物和水的約束可以得到玩家最晚離開礦山的日期。

3.2.2 求解一般過(guò)程的整體算法

Step1：采用Dijkstra算法計(jì)算從起點(diǎn)到礦山的日期；

Step2：根據(jù)食物和水的余量的初步計(jì)算從礦山離開到終點(diǎn)的日期范圍，而后采用Dijkstra算法計(jì)算從礦山離開到終點(diǎn)的確切日期；

Step3：遍歷玩家離開礦山到達(dá)村莊進(jìn)行補(bǔ)給的日期，對(duì)于多種可能的路線，分別計(jì)算出終點(diǎn)時(shí)玩家的資金剩余量，求出最大資金剩余量所在路線，則該路線即為所求玩家最佳策略；

step4：綜合前四步，得到全過(guò)程的策略。

4 基于動(dòng)態(tài)規(guī)劃的最優(yōu)決策求解

4.1 多階段決策過(guò)程的動(dòng)態(tài)規(guī)劃模型

本問(wèn)題中，玩家不知道全程的天氣，此時(shí)不便利用第一問(wèn)中分3個(gè)階段的方法，而是應(yīng)該每天根據(jù)當(dāng)前的狀態(tài)進(jìn)行下一步行動(dòng)的決策，因此我們建立動(dòng)態(tài)規(guī)劃模型如下：

劃分階段：以天為單位，假設(shè)游戲的截止日期為第n天，則全程分為n-1個(gè)階段。

狀態(tài)變量：Xi=(xi,vi,ui,ai,bi)，，其中i表示第i天，xi表示玩家所在位置，vi表示玩家是否在村莊，ui表示玩家是否挖礦，ai表示購(gòu)買水的數(shù)量，bi表示購(gòu)買食物的數(shù)量[1]。

決策變量：當(dāng)一個(gè)階段的狀態(tài)確定后，玩家需要做出選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策，描述決策的變量稱為決策變量。設(shè)玩家在位置xi的決策變量為fi(xi)。

狀態(tài)轉(zhuǎn)移方程：在確定性過(guò)程中，一旦某階段的狀態(tài)和決策已知，下階段的狀態(tài)便完全確定。用狀態(tài)轉(zhuǎn)移方程表示這種演變規(guī)律，即通過(guò)玩家目前位置和決策變量fi(xi)來(lái)確定下一步的位置xi+1的方程，設(shè)為xi+1=Ti(xi,fi)。

指標(biāo)函數(shù)：是衡量過(guò)程優(yōu)劣的數(shù)量指標(biāo)。由于玩家的目標(biāo)是使剩余的資金最大，因此選擇每一天的凈收益作為指標(biāo)函數(shù)，凈收益即玩家當(dāng)天可能挖礦的收益與消耗資金之差，記為。

在上述動(dòng)態(tài)規(guī)劃模型的基礎(chǔ)上增加第一問(wèn)中的約束條件，即為第二問(wèn)的總模型。

4.2 求解模型得出一般策略

通過(guò)該動(dòng)態(tài)規(guī)劃模型，我們希望求解出全過(guò)程的最優(yōu)策略S*={f1(x1)*，f2(x2)*，…，fn(xn)*}，即玩家在每一天的決策fi(xi)*的集合。但是，由于該動(dòng)態(tài)規(guī)劃模型的時(shí)間復(fù)雜度是O(n3)，直接采用逆序求解法的消耗巨大，無(wú)法在滿意的時(shí)間內(nèi)求得最優(yōu)解。因此我們采用拆分的思想，將求解過(guò)程拆分成兩步[2]：

（1）首先利用貪心算法的思想制定出某一特定的策略S0，作為初值；

（2）接著通過(guò)與最優(yōu)策略的比較，不斷修改該策略S0，得到最終的一般策略S*，S*就是上述動(dòng)態(tài)規(guī)劃問(wèn)題的近似最優(yōu)解。

4.2.1 基于貪心算法的特定策略S1

（1）當(dāng)玩家位于起點(diǎn)時(shí)，假如玩家經(jīng)過(guò)礦山的時(shí)間超過(guò)天數(shù)上限，則直接前往終點(diǎn)；否則，時(shí)間充足，可以經(jīng)過(guò)礦山。

（2）當(dāng)玩家在第i天位于村莊時(shí)，我們利用貪心算法，使得玩家始終做出利益最大化的選擇。即，先計(jì)算從當(dāng)前日期到最后一天的消耗上限，若此時(shí)包內(nèi)水的數(shù)量或者包內(nèi)食物的數(shù)量小于該數(shù)值，那么玩家進(jìn)行補(bǔ)給，否則不補(bǔ)給。

（3）當(dāng)玩家位于礦山時(shí)，利用貪心算法，使得玩家始終做出利益最大化的選擇。即，先將水和食物的消耗上限按照村莊的價(jià)格折算成資金，再與挖礦收益進(jìn)行比較。若，那么玩家不挖礦，否則挖礦。

（4）當(dāng)玩家位于其他位置時(shí)，由于約束條件過(guò)于復(fù)雜，無(wú)法確定應(yīng)該前往終點(diǎn)、礦山還是村莊。此時(shí)我們首先計(jì)算出所有可能的移動(dòng)路線的消耗上限，當(dāng)包內(nèi)水的數(shù)量和食物的數(shù)量均大于消耗上限時(shí)，在這些路線中，我們約定玩家等可能選擇其中一條。

（5）當(dāng)玩家位于終點(diǎn)時(shí)，游戲結(jié)束。

4.2.2 通過(guò)比較Z*對(duì)策略Z1進(jìn)行修正

1.定義兩條路徑的差別εij。在該問(wèn)題中，定義向量，εij中的元素為兩條路徑xi和路徑y(tǒng)j中每個(gè)位置的差，用于衡量?jī)蓷l路線的相似程度。其中，εij的零位越多，兩條路徑越相似。

2.根據(jù)ε0k修正一般策略Z1的算法。

Step1：編寫程序模擬玩家采用一般策略Z1后走的路徑K1；

Step2：采用第一問(wèn)的算法計(jì)算玩家采用的策略Z0以及對(duì)應(yīng)的路徑K0；

Step3：根據(jù)ε0k修正策略Z1，得到策略Z2，當(dāng)向量ε0k中有超過(guò)兩位元素不為零時(shí)，繼續(xù)修正策略；

Step4：直到向量ε0k中只有小于等于兩位元素不為零時(shí)，可以認(rèn)為兩條路徑足夠接近，此時(shí)迭代得到的Zk即為所求Z*。

5 多玩家參與情況下的最優(yōu)策略求解

現(xiàn)在，將第一問(wèn)和第二問(wèn)的情況分別推廣到存在n名玩家的情況下。由于不同玩家處于同一區(qū)域時(shí)，他們的消耗量會(huì)增加為2k倍而挖礦的收益變?yōu)?/k，此時(shí)會(huì)出現(xiàn)多人博弈的問(wèn)題，每個(gè)玩家的策略會(huì)受到環(huán)境和他人決策的共同影響。

由于無(wú)順序選擇模式較為簡(jiǎn)單，我們假設(shè)游戲模式為有順序模式：n個(gè)玩家同一天從起點(diǎn)出發(fā)，但選擇策略有先后順序，即抽到的編號(hào)越小，越先選擇策略。

為了簡(jiǎn)化模型，我們只考慮玩家A應(yīng)選擇的策略。

5.1 第一小問(wèn)：已知全部天氣狀況

首先，根據(jù)第一問(wèn)，確定單名玩家的最佳策略S*，A的策略選擇流程為：

（1）n名玩家在開始游戲前分別獲得其編號(hào)，按編號(hào)從小到大先后進(jìn)入游戲并確定策略，即抽到第i號(hào)的玩家是第i個(gè)確定策略的玩家；

（2）玩家A根據(jù)第二問(wèn)中的一般策略推測(cè)前i-1名玩家的策略的集合Pi，并根據(jù)Pi推測(cè)出自己的策略；

（3）玩家A根據(jù)第二問(wèn)中的一般策略推測(cè)后n-i名玩家的策略的集合Qi，并根據(jù)Pi和Qi以及自己的策略得出自己的最終收益。

5.2 第二小問(wèn)：不知道天氣狀況

首先根據(jù)第二問(wèn)，確定單名玩家的最佳策略S*，A的選擇流程為：

（1）n名玩家在開始游戲前分別獲得其編號(hào)，按編號(hào)從小到大先后進(jìn)入游戲并確定策略，即抽到第i號(hào)的玩家是第i個(gè)確定策略的玩家；

（2）玩家A根據(jù)第二問(wèn)中的一般策略推測(cè)前i-1名玩家的策略的集合Pi，并根據(jù)Pi推測(cè)出自己的策略；

（3）玩家A根據(jù)第二問(wèn)中的一般策略推測(cè)后n-i名玩家的策略的集合Qi，并根據(jù)Pi和Qi以及自己的策略得出自己的最終收益。

6 模型評(píng)價(jià)

6.1 模型優(yōu)點(diǎn)

（1）綜合考慮各種因素，建立路徑?jīng)Q策的單目標(biāo)規(guī)劃模型，模型可遷移性強(qiáng)；

（2）建立動(dòng)態(tài)規(guī)劃模型，詳細(xì)考慮玩家在各個(gè)情況下的決策，模型完備；

（3）采用拆分的思想對(duì)模型進(jìn)行求解，求解迅速且結(jié)果較準(zhǔn)確。

6.2 模型缺點(diǎn)

（1）第三問(wèn)求解多名玩家的游戲時(shí)，簡(jiǎn)化了模型，并未考慮多者博弈的情況；

（2）算法普適性有待提高，對(duì)于不同的關(guān)卡，運(yùn)行程序得到的結(jié)果需要進(jìn)行一定步數(shù)的手動(dòng)調(diào)整，結(jié)果才能更準(zhǔn)確。

6.3 模型推廣

（1）可以嘗試手動(dòng)調(diào)整得到更復(fù)雜的算法，允許算法運(yùn)行更長(zhǎng)時(shí)間得到更優(yōu)的結(jié)果；

（2）可以嘗試采用強(qiáng)化學(xué)習(xí)的方法學(xué)習(xí)得到的游戲策略與本文中算法求得的策略進(jìn)行對(duì)比，并疊加強(qiáng)化學(xué)習(xí)的狀態(tài)轉(zhuǎn)移等要素改進(jìn)本文算法，得到更好的結(jié)果。