静态博弈论——“穿越沙漠”游戏决策设计

王永源 孟航宇 张 伟 陈春宇

（南京工业大学海外教育学院，江苏 南京210000）

1 概述

沙漠作为近年来的热门话题，其天气和气候特点对全球生态环境的影响逐渐增强，引起了社会各界人士的广泛关注。保护自然，关注沙漠成为当下的热点。为了引起更多人的关注，结合当今互联网时代具有易传播，发散性广的特点，在游戏中融入沙漠元素已经成为一种发展趋势。玩家在游戏中面对不同的地图，会遇到不同的沙漠特色地区，例如矿山和村庄。玩家在矿山和村庄会有相应的材料进行补充，得到继续游戏的机会。

2 基本规则

考虑本游戏：玩家凭借一张地图，在初始点使用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从初始点出发，在沙漠中徒步。在沙漠途中会遇到不同的天气，玩家也可以在矿山、村庄补充资金或资源。目标是玩家在规定时间内到达终点，并保留尽可能多的资金（包括资源折合的资金）。

游戏的基本规则如下：

2.1 以天为基本时间单位，游戏的开始时间为第0 天，玩家位于初始点，必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。

2.2 穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过玩家负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。

2.3 每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。

2.4 每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可选择在原地停留。沙暴日必须在原地停留。

2.5 玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2 倍。

2.6 玩家第0 天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱退回价格为基准价格的一半。

2.7 玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的3 倍；如果不挖矿，消耗的资源数量为基础消耗量。到达矿山当天不能挖矿，沙暴日也可挖矿。

2.8 玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2 倍。

参数设定

天气状况

地图

3 问题的分析

对于多人游戏，在分析机制后建立了静态博弈模型。首先对卡关的几种较优单人决策进行分析，建立起两两间的博弈收益函数表，根据收益表分别进行纯决策和混合决策分析。然后得出均衡的解为双方采用3 天到达终点的决策并会选择在起点购买足够生存的物资。最后我们分析了模型的优缺点和灵敏度，结果显示模型对于这一类问题具有比较好的适应性，提炼出的规则可以有效指导玩家决策。

4 模型的假设

4.1 不存在半路丢掉食物或将食物暂时放到路上的情况。

4.2 保证补给点有足够的食物补给，不存在断货缺货的问题。

4.3 不考虑玩家其他时间消耗，只考虑题目中所提及的时间消耗。

5 符号说明

?

6 模型的建立与求解

由于有不止一个玩家，并且玩家在游戏中的状态更新会受到对方情况的影响，因此每个玩家为了实现自己的游戏目标，必须考虑对方的行动决策。因此用博弈的模型来考虑，双方同时进行一次决策，为单阶段静态博弈。

6.1 两人单阶段博弈

6.1.1 博弈设定与求解目标

有两位玩家A、B。我们假设两个玩家都是具有充分思维能力的理性玩家，可以依据情况进行判断。设计的目标是使A 能够在B 按照符合B 利益前提下行动时让自己获得最大的期望收益。

因为A、B 玩家角色地位是平等的，拥有相同的资金，即两个玩家的决策集是完全一致，因此我们为A 设定的决策对B 也是同样适用的。

6.1.2 思路分析

可行的方案大致有两类：第一类为纯决策，两个玩家使用同一种固定决策，走同一条路径。第二类为混合决策，根据题目可知，一名玩家的决策会影响其他玩家的利益，也就是说每个人的决策方案会影响到其他人的决策方案。且题目要求，n 名玩家需在第0 天时把方案确定，之后不能更改，此时玩家所剩资金（包括资源折合的资金）要达到最大值。因此我们查阅了博弈论有关的资料，针对题目要求建立相关博弈论模型。

6.2 题目一般决策

天气情况全部已知且存在多个玩家的单阶段博弈：

由于中途失败造成的损失巨大，玩家的首要目的是生存，因此要在起点处购买足够多的食物和水，然后猜测其他玩家可能会采取的行走路线，这些路线是天气已知的单玩家模式下的较优行走决策，运用博弈论的方法寻找纳什平衡，纳什平衡给出的决策就是玩家们的行动决策。

6.3 单阶段博弈模型的建立

6.3.1 对于玩家的资源

设共有n 名玩家，由题意可知，当有多名玩家走相同路线时，消耗的资源量会增加，挖矿获得的收益会减少，购买补给所需的资源也会翻倍。所以为了获取最大利益，我们应尽量安排各位玩家不同的路线，即进行两两比较。

在一个博弈过程中，无论对方的决策选择如何，当事人一方都会选择某个确定的决策，则该决策被称作支配性决策。如果任意一位参与者在其他所有参与者的决策确定的情况下，其选择的决策是最优的，那么这个组合就被定义为纳什平衡。

根据纳什平衡，我们进行模型建立：

以玩家1，2 为例，不妨设他们各有n1,n2 种决策方案，则他们在同一地图中所用方案的集合为：

对于各名玩家来说，当一名玩家决定其路线时，其他玩家应避免相同路径，并从其他剩余路径中选择最适路径。这一规则也符合纳什平衡。由于各位玩家选择的路径决定了他们资金的多少。

则玩家1，2 所用资金可由下列矩阵表示：

该矩阵中，aij（i=1,2……，j=1,2……）表示，玩家1 在玩家2选择路径之后选择的其他最优路径数目。

6.3.2 对于两名玩家的数值期望

设玩家1 选择第i 条路的概率为Pi(i=1,2……)，玩家2 选择第j 条路的概率为Qj(j=1,2……)

则其数学期望分别为：

6.3.3 基于静态博弈论所设计的决策模型

对于玩家1 和玩家2，他们选择的决策应使其数学期望最大，即

在博弈论中，我们由纳什平衡可知，无论对方的决策选择如何，当事人一方都会选择某个确定的决策，则该决策被称作支配性决策。如果任意一位参与者在其他所有参与者的决策确定的情况下，其选择的决策是最优的。此时，总存在各玩家获利达到最大值与其他玩家获利达到最小值的情况。所以，该模型可转化为：

由于本卡关只有两名玩家，情况较少，所以可以用Lingo 编程求解。为获得最佳决策，玩家一定会从我们之前制定的路径进行选择。因此我们首先确定几条较好路径，两名玩家到达终点时剩余资金（包括剩余资源折合的资金）较多。

7 模型的总结与优缺点分析

7.1 优点分析

7.1.1 本关卡的最终结果可猜证

由于玩家人数少且天气情况已知，所以结果具有可猜证性，但能给出充分的思想来源和令人信服的论证并不容易。我们从统计结果抽取决策，并利用随机模拟较为完整地论证了该方案确实优于其他合理方案。

7.1.2 本关卡问题的二人博弈模型给出一系列有效的局部决策

由于多人游戏的复杂性使得一些规律性结论比确定性的计算机算法更有意义。因此这一部分我们用数学推导给出的可靠决策结论能够更有效地帮助实际游戏。

7.2 缺点分析

7.2.1 利用确定天气情况下求解结果后本问题时没有定量分析产生的偏差

尽管我们可以通过动态规划回溯出优秀解，但在天气未知的情况下这些解具有偶然性。虽然天气已知，但最高收益和存活率二者是相互制衡的，而我们在分析一些优秀解的时候虽然也重点考虑了存活率，但无法给出描述幸存者偏差的量并加以讨论。

7.2.2 给出的决策更加客观合理

我们给出的有些决策难以通过直觉或人工计算快速得到验证，都需要一定的程序，所以这些结果可能不易于从直观上理解。

7.2.3 对于多人玩家的情况没有给出完全最优解

虽然我们给出了最优决策，但对于多人的多阶段静态博弈没有给出完全最优解。由于博弈的过程难以由程序体现，最后的博弈过程没有进行模拟和全局计算。

8 结论

本文我们对“穿越沙漠”游戏的决策进行了由浅入深的分析，对于越来越复杂的问题也有确定性决策求解转化为带有随机性、局部性优化，并利用各种评价方法进行讨论分析。