王永源 孟航宇 張 偉 陳春宇

（南京工業(yè)大學(xué)海外教育學(xué)院，江蘇 南京210000）

1 概述

沙漠作為近年來的熱門話題，其天氣和氣候特點對全球生態(tài)環(huán)境的影響逐漸增強(qiáng)，引起了社會各界人士的廣泛關(guān)注。保護(hù)自然，關(guān)注沙漠成為當(dāng)下的熱點。為了引起更多人的關(guān)注，結(jié)合當(dāng)今互聯(lián)網(wǎng)時代具有易傳播，發(fā)散性廣的特點，在游戲中融入沙漠元素已經(jīng)成為一種發(fā)展趨勢。玩家在游戲中面對不同的地圖，會遇到不同的沙漠特色地區(qū)，例如礦山和村莊。玩家在礦山和村莊會有相應(yīng)的材料進(jìn)行補(bǔ)充，得到繼續(xù)游戲的機(jī)會。

2 基本規(guī)則

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

游戲的基本規(guī)則如下：

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

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

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

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

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

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

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

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

參數(shù)設(shè)定

天氣狀況

地圖

3 問題的分析

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

4 模型的假設(shè)

4.1 不存在半路丟掉食物或?qū)⑹澄飼簳r放到路上的情況。

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

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

5 符號說明

?

6 模型的建立與求解

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

6.1 兩人單階段博弈

6.1.1 博弈設(shè)定與求解目標(biāo)

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

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

6.1.2 思路分析

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

6.2 題目一般決策

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

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

6.3 單階段博弈模型的建立

6.3.1 對于玩家的資源

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

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

根據(jù)納什平衡，我們進(jìn)行模型建立：

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

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

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

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

6.3.2 對于兩名玩家的數(shù)值期望

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

則其數(shù)學(xué)期望分別為：

6.3.3 基于靜態(tài)博弈論所設(shè)計的決策模型

對于玩家1 和玩家2，他們選擇的決策應(yīng)使其數(shù)學(xué)期望最大，即

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

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

7 模型的總結(jié)與優(yōu)缺點分析

7.1 優(yōu)點分析

7.1.1 本關(guān)卡的最終結(jié)果可猜證

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

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

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

7.2 缺點分析

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

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

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

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

7.2.3 對于多人玩家的情況沒有給出完全最優(yōu)解

雖然我們給出了最優(yōu)決策，但對于多人的多階段靜態(tài)博弈沒有給出完全最優(yōu)解。由于博弈的過程難以由程序體現(xiàn)，最后的博弈過程沒有進(jìn)行模擬和全局計算。

8 結(jié)論

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