图论在策略图版游戏“穿越沙漠”中的应用

The Application of Graph Theory in the Strategy Board Game “Crossing the Desert”

摘要: 针对“穿越沙漠”游戏的策略求解问题，本文从玩家角度出发，利用数学语言对“穿越沙漠”游戏规则进行详细刻画，以玩家最终抵达终点所剩的资金最多为目标，建立优化模型，并结合Floyd算法对游戏地图进行简化，最终通过随机化贪心算法求解既定条件下的最优游戏策略。

Abstract: In order to find out the strategy of “Crossing Desert” game, from the point of view of the players, we described the rules of the game “crossing the desert” in detail by using mathematical language. Then, we took the maximum amount of funds left at the final destination as the goal, established an optimization model, and simplified the game map with Floyd algorithm, and finally we used randomized greedy algorithm (RGA) to solve the optimal game strategy under the given conditions.

1. 引言

策略图版游戏是现实情况的抽象和缩影，策略图版游戏求解有利于更复杂现实情况的研究 [1]。“穿越沙漠”是一款经典的策略图版游戏，游戏中，在起点获得初始资金的玩家通过购买物资、挖矿及合理安排每日行进策略，最终达到成功穿越沙漠并剩余资金较多的目标。由于游戏目标多且涉及领域较多，该游戏一直被众多公司企业用来培养团队在复杂情况下的分析决策能力，以及用在高校以培养学生的战略管理能力，具有很强的教育意义 [2] [3]。对于该游戏的研究目前仍停留在教学培训意义层面，游戏攻略一般由人工计算得出，鲜有相关专家学者对其策略的计算机求解进行研究。本文在详细刻画游戏规则和设定游戏获胜策略的基础上，利用计算机编程求解最优策略，有利于为现实复杂情况的策略求解提供思路。

2. “穿越沙漠”游戏规则的数学刻画

沙漠掘金游戏中，玩家在起点获得用于购买水、食物等物资的初始资金，备足物资后从起点出发，深入沙漠。若在行走途中经过矿山，玩家可以考虑挖矿以补充资金，经过村庄时玩家可以购买食物和水以满足行走、停留或挖矿的消耗。在游戏时段内，玩家每天都面临着晴天、高温、沙暴等天气变化造成的物资消耗不等的考验。在规定的游戏时间内，玩家可能剩余一定资金顺利抵达终点，也可能因物资耗尽以失败告终，这一切取决于玩家的行进策略。因此，“沙漠掘金”游戏的规则可以从玩家存活、天气影响、物资消耗、物资携带以及资金规则五个方面进行详细刻画：

1) 玩家存活：玩家必须在游戏规定天数内抵达终点。游戏规定玩家共有n天的探险时间，地图上分布着k个落脚点，仅相邻落脚点之间存在通路，其中村庄、矿山与终点分别用 $k_c,k_s,k_z$ 来表示。用0-1变量 $x_{ij}$ 表示第 $i\left(i=\text{1},\text{2},\cdots ,n\right)$ 天到达 $j\left(j=\text{1},\cdots ,k\right)$ 地，若第i天玩家在j处，记 $x_{ij}=1$。玩家存活即在规定的n天中的某一天到达终点，即：

$x_{i,k_z}=1,i=1,2,\cdots ,n$ (1)

2) 天气影响：天气是决定该天行进方案以及物资消耗的重要因素，某一天不同的天气状况影响着玩家整体的行进策略。假设游戏中只有“晴朗”、“高温”及“沙暴”三种天气，而且游戏地图上的所有区域都处于同一种天气，用1代表晴朗，2代表高温，3代表沙暴，第i天的天气记为 $t_i$，则玩家全部游戏时段的天气向量组T可表示为：

$T=\left(t_1,t_2,\cdots ,t_i,\cdots ,t_n\right),t_i=1,2,3$ (2)

在沙暴天气下，玩家只能原地停留而不能移动，若第i天碰上沙暴天气，则玩家有：

$x_{i,j}=x_{i-1,j}=1,t_i=3$ (3)

3) 物资消耗：水和食物是玩家穿越沙漠必需的两种资源，将玩家停留一天消耗的水和食物记为基础消耗量 $j_{wi}$ 、 $j_{fi}$，根据游戏规则，不同的天气状况下基础消耗量的取值也不相同。

玩家行走一天消耗基础物资消耗量的2倍，采矿一天需要3倍，因此每天的物资消耗可以分为两部分表示，基础物资消耗量 $j_{wi}$ 或 $j_{fi}$ 乘以消耗倍数 $B_i$。规定0-1变量 $y_{i,k_s}$ 表示第i天玩家在矿山 $k_s$ 是否选择采矿，则消耗倍数 $B_i$ 可表示为：

$B_i=\{\begin{array}{l}0x_{ij}-x_{i-1,j}=0\\ 2\left|x_{ij}-x_{i-1,j}\right|=1\\ 3x_{i,k_s}-x_{i-1,k_s}=1,y_{i,k_s}=1\\ 1其他情况\end{array}$ (4)

基于此，第i天在j处水的消耗量 $w_{ij}$，以及第i天在j处食物的消耗量 $f_{ij}$ 可分别表示为：

$w_{ij}=j_{wj}\times B_i$ (5)

$f_{ij}=j_{fj}\times B_i$ (6)

4) 物资携带：玩家只能携带有限重量的物资，用 $z_w$ 、 $z_f$ 分别表示单位水和食物的重量， $W_0$ 、 $F_0$ 分别表示玩家在起点时水和食物的初始量，为充分发挥α kg的有限携带能力，在起点玩家购入物资可表示为：

$z_w{W}_0+z_f{F}_0\le \alpha$ (7)

在穿越沙漠的过程中，玩家第i天剩下的水 $W_i$ 可由前一天剩下的水 $W_{i-1}$ 、第i天在j处水的消耗量 $w_{ij}$ 以及第i天购买的水的数量 $g_{wi}$ 表示：

$W_i=W_{i-1}-w_{ij}+g_{wi}$ (8)

同样地，玩家第i天剩下的食物 $F_i$ 为：

$F_i=F_{i-1}-f_{ij}+g_{fi}$ (9)

确保玩家每天存活的另一重要条件是每天均有剩余的水和食物，即：

$\{\begin{array}{l}{W}_i+F_i\le \alpha \\ W_i\ge 0,F_i\ge 0\end{array}$ (10)

5) 资金规则：玩家的初始资金为 $M_0$ 元，在起点时分别以水和食物的基准价格 $P_w$ 、 $P_f$ 购进水和食物的初始量 $W_0$ 和 $F_0$，需满足资金条件：

$P_w{W}_0+P_f{F}_0\le M_0$ (11)

在矿山时玩家可以通过采矿获得基础收益 $M_{ij}$，游戏规定玩家到达矿山当天不能直接采矿，从停留的第一天开始才能赚取收益：

$M_{ij}=\{\begin{array}{l}1000x_{i,k_s}=x_{i-1,k_s}=1,y_{i,k_s}=1\\ 0其他情况\end{array}$ (12)

在路途中玩家可能会因为天气突变等原因消耗大量的物资，从而导致不能顺利返回终点或无法使效益最大化，那么玩家可以选择通过地图中的村庄 $k_c$ 进行及时补给，但村庄的物资价格是基准价格的两倍。玩家第i天在村庄购买物资的花费 $g_i$ 可表示为：

$g_i=2P_w{g}_{wi}+2P_f{g}_{fi},x_{i,k_c}=x_{i-1,k_c}=1$ (13)

第i天的成本和采矿收入 $M_i$ 可表示为：

$M_i=M_{i-1}+M_{ij}-g_i$ (14)

若玩家最终返回终点时还有剩余物资，这部分剩余物资会以基准价格的一半进行回收，据此，最终返回终点时的所剩资金 $M_z$ 可以表示为：

$M_z=M_i+0.5\left(P_f{F}_i+P_w{W}_i\right),x_{i,k_z}=1$ (15)

“穿越沙漠”游戏胜利规则为：玩家在拥有充足物资抵达终点的前提下，保留的资金更多。由于游戏地图上落脚点数量及游戏天数有限，所以该游戏一定存在最优策略。为此，在游戏规则的约束下，以玩家最终抵达终点所剩的资金 $M_z$ 最多为目标，建立单目标优化模型，即可求解最佳游戏策略，则有“沙漠掘金”游戏的单目标优化模型：

$\begin{array}{l}目标函数:\max M_z\\ \{\begin{array}{l}T=\left\{t_1,t_2,\cdots ,t_i,\cdots ,t_n\right\},t_i=1,2,3\\ x_{i,j}=x_{i-1,j}=1,t_i=3\\ w_{ij}=j_{wj}\times B_i\\ f_{ij}=j_{fj}\times B_i\\ B_i=\{\begin{array}{l}0x_{ij}-x_{i-1,j}=0\\ 2\left|x_{ij}-x_{i-1,j}\right|=1\\ 3x_{i,k_s}-x_{i-1,k_s}=1,y_{i,k_s}=1\\ 1其他情况\end{array}\\ z_w{W}_0+z_f{F}_0\le \alpha \\ W_i=W_{i-1}-w_{ij}+g_{wi}\\ F_i=F_{i-1}-f_{ij}+g_{fi}\\ W_i+F_i\le \alpha \\ P_w{W}_0+P_f{F}_0\le M_0\\ M_i=M_{i-1}+M_{ij}-g_i\\ M_z=M_i+0.5\left(P_f{F}_i+P_w{W}_i\right),x_{i,k_z}=1\\ W_i\ge 0,F_i\ge 0\\ i=1,2,\cdots ,n\end{array}\end{array}$ (16)

3. 基于随机化贪心算法的模型求解

诸如此类约束条件复杂的优化模型最优解求解问题，一般采用剪枝优化的搜索算法对可能的最优解空间进行遍历得出最优解，但由于每天天气变化的影响，搜索过程中的剪枝优化效果不佳，时间复杂度极高，且容易发生组合爆炸。

考虑到随机化贪心算法(Randomized Greedy Algorithm, RGA)，即不直接取贪心策略的最优值而是从此最优值附近的一定区间内找到一个目标函数最优值 [4]，在贪心原则证明正确的前提下，通过足够次数的随机试验，即可得到最优解 [5]。随机化贪心算法适合动态规划类问题的求解，且其复杂度远小于搜索算法 [6]，故本文采用随机化贪心算法求解带天气变化因素的优化模型。基于随机化贪心算法的仿真模拟程序流程图：(如图1)

Figure 1. Flow chart of simulation program based on randomized greedy algorithm

图1. 基于随机化贪心算法的仿真模拟程序流程图

4. 实验结果和分析

现给出一套“沙漠掘金”游戏规则(如图2)，已知游戏时间段内全部的基础信息(如表1)和天气情况(如表2)，针对该实际案例对此展开分析。

Table 1. Table of basic parameters

表1. 参数设定表

Table 2. The profiles of weather conditions

表2. 天气状况表

首先结合实例给出具体的贪心算法及理论证明：

1) 起点和终点相同的最短路径经过村庄为最优。

证明1：起点到矿山的最短路径中，蓝色的等效路径经过村庄，可以提供玩家物资供给，而且等效路径与其他最短路径的路程相同，经过村庄的最短路径价值显然更大，因此认为经过村庄的两条最短路为最优(如图3)。

Figure 2. The map of the game “Crossing the Desert”

图2. “穿越沙漠”游戏地图

Figure 3. Equivalent graph of Floyd path optimization

图3. Floyd路径优化等效图

2) 除采矿、沙暴天气外，玩家不会在任何地方停留，一直处于移动状态。

证明2：给出游戏时段的天气序列 $d_1,\cdots ,d_{i-1},d_i,d_{i+1},d_{i+2},\cdots ,d_{end}$，其中 $d_i$ 表示第i天的天气，假设 $d_i$ 为高温天气， $d_{i+1}$ 为晴朗天气， $d_{i+2}~d_{end}$ 天气相同，假设 $d_i$ 天停留， $d_{i+1}$ 天移动，则其花费为：

$p_{21}\times pric{e}_{21}+p_{22}\times pric{e}_{22}+2\times \left(p_{11}\times pric{e}_{11}+p_{12}\times pric{e}_{12}\right)$

$d_i$ 天移动的花费为：

$2\times \left(p_{21}\times pric{e}_{21}+p_{22}\times pric{e}_{22}\right)$

因为后续天气全部相同，代入数值计算可得，停留的花费为18箱水，20箱食物，移动的花费为16箱水，12箱食物。显然，移动相同的距离，在无后效性的情况下，移动更优。

3) 若玩家不采矿，则直接走从起点至终点的最短路径；若玩家采矿，则玩家只会走两点间的最短路径。

证明3：若玩家不采矿，说明玩家的资金在穿越沙漠过程中，只有亏损而没有增加，以m (m > 0)代表玩家在穿越沙漠过程中的花费，用 $M_0$ 表示玩家的初始资金则有：

$M_0-m<M_0$

所以，玩家如果决定不采矿，直接走起点至终点的最短路径是最优选择。若玩家采矿，那么玩家在采矿路上的花费最低是其最终目标，结合贪心策略1)、2)，玩家不会停留且走规定的最短路径是路途花费最小且具有村庄补给机会的最优选择。

4) 玩家在起点尽可能多购买物资，且在满足当前方案约束下，尽可能多地购入食物。

证明4：游戏规定玩家在起点处购入物资，只需花费物资的基准价格，而玩家在补给村庄购买物资时，需花费物资两倍的基准价格。因此玩家在起点会尽可能多地购买物资，在满足当前方案约束的情况下，起点的剩余容量全部购入食物。

结合模型求解算法即可得出既定条件下的最优行进策略，总共用时24天，剩余资金最多为10,470元(如表3)。

Table 3. Results of the game “Crossing the Desert”

表3. 游戏求解结果表

5. 结语

在已知“穿越沙漠”游戏具有最优策略的前提下，本文将游戏细则进行数学刻画，由此建立起“穿越沙漠”游戏的单目标优化模型，将团队协作的管理领域游戏转化为运筹类数学模型，并使用随机化贪心算法对模型进行求解得到最终结果，具有一定的创新性和实际应用能力。此“穿越沙漠”游戏策略研究对有关社会学类、管理类案例的求解问题具有一定的参考价值。

基金项目

2019年度青岛理工大学教学改革项目(F2019-041)。

NOTES

^*通讯作者。