基于馬爾可夫決策的穿越沙漠游戲策略研究

鄧晨晨 黃宇軒 齊澤坤 楊松

摘要：“穿越沙漠”游戲是一款綜合考慮資金、資源、天氣、時間、博弈等多種因素在內的復雜策略游戲。文章將基于圖論與馬爾可夫決策有關模型，分析討論玩家在未來信息已知與未來信息未知兩種情形下的最優策略。該模型綜合考慮了風險評估與多階段決策理論，可為優化算法與企業決策提供一定借鑒意義。

關鍵詞：沙漠掘金;圖論;動態規劃;馬爾可夫決策;最優化理論

一、引言

“穿越沙漠”游戲是一款綜合考慮資金、資源、天氣、時間、博弈等多種因素在內的多階段策略游戲。游戲要求玩家在沙暴天氣原地停留、到達礦山當天不許挖礦并且保證在路途中不得耗盡資源。游戲允許玩家挖礦獲得收益，并利用初始資金及收益在村莊隨時補給資源。玩家必須在截止日期之前抵達終點，并保留盡可能多的留存收益。該情景策略游戲將野外求生中多變的天氣與不定的決策通過情景模擬的方式真實呈現，對于玩家的數據意識、信息搜集與靈活決策能力以及風險防控都提出了很高要求。本文將基于圖論與馬爾可夫決策有關模型，綜合考慮玩家在兩種情形下所面臨的現實困境，并對該最優策略展開具體討論。

二、問題分析與求解

（一）未來信息已知：基于多階段決策的動態規劃模型

經濟學中，期望收益為根據已知信息對未來收益的預判。在游戲中，玩家期望在規定的時間內獲得盡可能多的資金。由于天氣數據與地圖完全已知，本文首先根據地圖信息建立圖論模型，接著使用動態規劃將沙漠掘金問題劃分為多階段決策模型，從基本邏輯出發，首先規劃出掘金路線，進而分析資源購置策略，在此基礎上依據天氣狀況與資源情況求解挖礦策略，最終通過篩選期望收益的最大值來求取玩家的最優策略。

1. 圖論模型

設地圖共有n個區域，其中含有k個村莊，記為集合A={a1、a2…ak};含有m座礦山，記為集合B={b1、b2…bm}。沙漠起始點記為s0，沙漠終點記為sn。w1（t）為第t日水資源基礎消耗量，w2（t）為第t日食物資源基礎消耗量。礦山的單日收益為r，每箱水資源的質量為m1，基準價格為p1，每箱食物資源的質量為m2，基準價格為p2。玩家在第t天的剩余水資源質量為M1（t）、剩余食物資源質量為M2（t）、剩余資金為C（t）。游戲時限為t0天，承重上限為Wmax。

玩家在任一區域可選擇“停留”狀態，其時間遞歸式如下：

在非沙暴天氣時，玩家在任一區域可選擇“移動”狀態，其時間遞歸式如下：

玩家在礦山區域時，可以選擇“挖礦”狀態，其時間遞歸式如下：

玩家經過或停留村莊區域時，可以購置資源，購置資源產生的遞歸式如下：

其中x為購置水資源的箱數，y為購置食物資源的箱數。由于村莊和礦山在游戲中的特殊性，將地圖轉化為如圖2所示的圖論模型。

該圖G中點集V與邊集E的表達式如下所示：

式中，si∈V。設第t天的玩家區域位置為St，可將原問題分解為不同區域集下的多階段決策問題，通過求解每一階段下的最優策略建立動態規劃模型。

2. 基本游戲策略

為獲取更多的資金，有兩種基本途徑：收益最大化與支出最小化。我們從這兩個基本途徑延伸出四條基本游戲策略：

滿載原則：資源不足時玩家需要前往村莊補充必備資源，多次重復前往村莊將增加路途資源的消耗，為減少前往村莊次數，除最后一次購置資源外，其余應使負重滿載。設第i次經過（或停留）村莊集合時購買的水資源為xi箱，食物資源為yi箱，應有：

不剩余原則：在終點剩余資源將以基準價格的一半退回，造成資金浪費，結合滿載原則，最后一次購置資源的數量xn、yn應有如下關系：

3. 掘金路線策略

玩家在起始點面臨三種選擇：向村莊集合A出發購買必備資源;向礦山集合B出發來獲取未來的資金收益;向終點sn出發以結束游戲。由此引申出三種掘金路線：

玩家在村莊補充資源后，若時間充裕將前往礦山采礦;玩家在礦山消耗大量資源后，若時間充裕將前往村莊補充資源。因此路線中村莊和礦山應交替出現，直至接近時限玩家向終點移動。則有：

由于游戲目標為在規定時限內獲取更多的資金，從期望收益角度分析三種路線，期望收益高的路線為最優掘金路線，并通過順路原則求解相應村莊和礦山位置。

4. 資源購置策略

在沙漠起始點可以低廉價格購買一次資源，在沙漠途中經過或停留村莊時均可購置資源，資源購置量應匹配于資源消耗量。此外，由于水資源和食物資源的價格不等，在村莊購買將進一步拉大兩種資源的差價，在不改變掘金路線的情況下，在初始點應以低廉價格購買盡可能多的貴重資源。

（2）村莊資源購置策略。在上節已經求得三種掘金路線，設第i次經過（或停留）村莊集合B時購買的水資源為xi箱，食物資源為yi箱，據滿載原則，xi與yi滿足：

設最后一次經過村莊經過（或停留）村莊集合B時購買的水資源為xn箱，食物資源為yn箱，據不剩余原則有：

5. 挖礦策略

（1）前往終點決策。當剩余時間較少且資源不足時，玩家面臨的選擇為：前往村莊補給后返回礦山挖礦;直接前往終點，由此生成兩種不同的決策方案。我們從期望收益角度分析兩種方案，期望收益高的方案為最優決策。

（2）前往村莊時機。由于不同天氣對路途的資源消耗不同，在給定所有天氣數據的情況下可以選擇合適的天氣前往村莊購置資源。設fj和gj分別表示第次前往礦山挖礦，則前往村莊的最優決策為：

（3）暫停挖礦。由于在村莊購置資源價格為基礎價格的二倍，在沙暴或高溫天氣挖礦將承擔高額的資源費用，在時間期限允許的條件下，可以嘗試選擇在沙暴或高溫天氣暫停挖礦休息，本策略的觸發條件為：

綜上，從玩家狀態分析，策略示意圖如圖3所示。

（二）未來信息未知：基于風險預測的多階段馬爾可夫決策模型

經濟學中，風險預測或風險評估指對未來不確定性的量化計算和預測。玩家在游戲中通過目前的狀態與當天的天氣情況（環境狀態），產生移動、停留挖礦等行為（對環境做出動作），并通過環境的反饋調整決策。由于玩家的目標仍為到終點時資金的最大化，本文利用概率論相關理論的對期望收益進行定量評估預測，進而做出最優決策。由于情景的相似性，我們沿用前問題的變量符號與游戲基本策略。

1. 馬爾可夫決策模型

馬爾可夫決策（MDP）的流程圖如圖4所示。

馬爾可夫決策包含一組交互對象：智能體：MDP中進行機器學習的代理，可以感知外界環境的狀態進行決策、對環境做出動作并通過環境的反饋調整決策。環境：mdp模型中智能體外部所有事物的集合，其狀態會受智能體動作的影響而改變，且上述改變可以完全或部分地被智能體感知。

馬爾可夫決策過程由五部分組成：{State，Action，Psa，γ，Reward}，其中State表示狀態集合，Action表示行動集合，Psa表示狀態轉移概率，γ表示阻尼系數，Reward表示該行動的回報。針對該游戲，State包含位置變量s（t）、所剩資金變量C（t）、所剩水資源變量M1（t）、所剩食物資源變量M2（t）;Action有四種情況：“停留”、“移動”、“挖礦”、“購置資源”;阻尼系數γ在該問題中為1;Reward由資金時間遞推式決定。最終的路線與資源購置方案仍由期望收益最大給出：

2. 風險預測模型

設晴朗、高溫、沙暴天氣的概率為h1～h3，其對應的水資源基礎消耗量為w11～w13，食物資源基礎消耗量為w21～w23。利用概率論，對不同行為的資源消耗與資金變化進行預測。

（1）停留。玩家在任意天氣均可以選擇“停留”，兩種資源的變化期望為：

（2）移動。玩家在非沙暴天氣可以選擇“移動”。由于每次移動成功的概率為h1+h2，需要求解移動距離為l時的時間消耗。這是一個帕斯卡過程，據概率論，帕斯卡分布的分布函數如下：

因此，該過程的耗時與資源消耗期望如下：

考慮到天氣的隨機因素，需要多準備一些資源以應對極端情況（多次出現沙暴天氣無法移動）。由于不同玩家有不同的游戲偏好，我們引入風險偏好系數k，多準備k·σ的資源（σ為標準差），兩種資源消耗的期望更正為：

（3）挖礦。玩家在礦山區域可以選擇“挖礦”，類比“停留”時的資源消耗，挖礦天的資源消耗與資金變化的期望為：

（4）資源購置。玩家經過或停留村莊區域時，可以購置資源，購置資源產生的遞歸式如下：

其中x為購置水資源的箱數，y為購置食物資源的箱數。

3. 基本游戲策略

與前問題相比，游戲規則除天氣情況未知外完全一致，因此最短路原則、滿載原則、順路原則與不剩余原則仍然適用。針對未來天氣的未知性，根據風險預測原理，我們期望決策具有較小的風險性，由此引申出第五條基本策略：同路原則。

4. 玩家策略

由于情景的相似性，我們仍沿用前問題模型中的掘金路線策略、資源購置策略與挖礦策略，并針對未來天氣情況未知的條件進行改進。

（3）挖礦策略。挖礦策略依然包含三部分內容：前往終點決策;前往村莊時機;暫停挖礦，與前問題保持一致。特別是當滿足下式時，啟用暫停挖礦策略。

三、結論與推廣

本文根據圖論、博弈論的有關原理建立數學模型，對游戲玩家多階段、多目標的最優策略展開探究。基于馬爾科夫的決策模型是本文的一大特色，綜合考慮到模型擁有的優化功能，可以考慮將其推廣至現實生活中個人面對復雜情境時的決策與權衡，以及企業面臨變幻莫測的市場環境時合理的應對之策等相關議題的探討之中。（注：本文數據與資料來源：2020年全國大學生數學建模比賽B題）

參考文獻：

[1]Brihaye T，Geeraerts G，Hallet M，et al.On the termination of dynamics in sequential games[J].Information and Computation， 2019，272：104505.

[2]Dhiman A，Uttam T，Balakrishnan S. Implementation of sequential game on quantum circuits[J].Quantum Information Processing，2020，19（04）：1-16.

[3]陳如峰.自學習策略價值風險模型研究與應用[D].成都：電子科技大學，2020.

[4]王中玉，曾國輝，黃勃，方志軍.改進A*算法的機器人全局最優路徑規劃[J]. 計算機應用，2019，39（09）：2517-2522.

（作者單位：西安交通大學）