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

鄧晨晨 黃宇軒 齊澤坤 楊松

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

關(guān)鍵詞：沙漠掘金;圖論;動態(tài)規(guī)劃;馬爾可夫決策;最優(yōu)化理論

一、引言

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

二、問題分析與求解

（一）未來信息已知：基于多階段決策的動態(tài)規(guī)劃模型

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

1. 圖論模型

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

玩家在任一區(qū)域可選擇“停留”狀態(tài)，其時間遞歸式如下：

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

玩家在礦山區(qū)域時，可以選擇“挖礦”狀態(tài)，其時間遞歸式如下：

玩家經(jīng)過或停留村莊區(qū)域時，可以購置資源，購置資源產(chǎn)生的遞歸式如下：

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

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

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

2. 基本游戲策略

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

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

不剩余原則：在終點剩余資源將以基準(zhǔn)價格的一半退回，造成資金浪費，結(jié)合滿載原則，最后一次購置資源的數(shù)量xn、yn應(yīng)有如下關(guān)系：

3. 掘金路線策略

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

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

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

4. 資源購置策略

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

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

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

5. 挖礦策略

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

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

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

綜上，從玩家狀態(tài)分析，策略示意圖如圖3所示。

（二）未來信息未知：基于風(fēng)險預(yù)測的多階段馬爾可夫決策模型

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

1. 馬爾可夫決策模型

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

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

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

2. 風(fēng)險預(yù)測模型

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

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

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

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

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

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

（4）資源購置。玩家經(jīng)過或停留村莊區(qū)域時，可以購置資源，購置資源產(chǎn)生的遞歸式如下：

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

3. 基本游戲策略

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

4. 玩家策略

由于情景的相似性，我們?nèi)匝赜们皢栴}模型中的掘金路線策略、資源購置策略與挖礦策略，并針對未來天氣情況未知的條件進行改進。

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

三、結(jié)論與推廣

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

參考文獻(xiàn)：

[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]陳如峰.自學(xué)習(xí)策略價值風(fēng)險模型研究與應(yīng)用[D].成都：電子科技大學(xué)，2020.

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

（作者單位：西安交通大學(xué)）