靜態(tài)博弈論
——“穿越沙漠”游戲決策設(shè)計(jì)

王永源 孟航宇 張 偉 陳春宇

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

1 概述

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

2 基本規(guī)則

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

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

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

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

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

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

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

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

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

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

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

天氣狀況

地圖

3 問題的分析

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

4 模型的假設(shè)

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

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

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

5 符號(hào)說明

?

6 模型的建立與求解

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

6.1 兩人單階段博弈

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

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

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

6.1.2 思路分析

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

6.2 題目一般決策

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

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

6.3 單階段博弈模型的建立

6.3.1 對(duì)于玩家的資源

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7.1 優(yōu)點(diǎn)分析

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

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

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

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

7.2 缺點(diǎn)分析

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

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

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

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

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

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

8 結(jié)論

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