基于动态规划和运筹学的游戏策略优化问题 2020年9月17日 星期四 18:00 目录 原题 考虑如下的小游戏：玩家凭借一张地图，利用初始资金购买一定数量的水和食物（包括食品和其他日常用品），从起点出发，在沙漠中行走。途中会遇到不同的天气，也可在 矿山、村庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。 游戏的基本规则如下： （1）以天为基本时间单位，游戏的开始时间为第0天，玩家位于起点。玩家必须在截止日期或之前到达终点，到达终点后该玩家的游戏结束。 （2）穿越沙漠需水和食物两种资源，它们的最小计量单位均为箱。每天玩家拥有的水和食物质量之和不能超过负重上限。若未到达终点而水或食物已耗尽，视为游戏失败。 （3）每天的天气为“晴朗”、“高温”、“沙暴”三种状况之一，沙漠中所有区域的天气相同。 （4）每天玩家可从地图中的某个区域到达与之相邻的另一个区域，也可在原地停留。沙暴日必须在原地停留。 （5）玩家在原地停留一天消耗的资源数量称为基础消耗量，行走一天消耗的资源数量为基础消耗量的2倍。 （6）玩家第0天可在起点处用初始资金以基准价格购买水和食物。玩家可在起点停留或回到起点，但不能多次在起点购买资源。玩家到达终点后可退回剩余的水和食物，每箱 退回价格为基准价格的一半。 （7）玩家在矿山停留时，可通过挖矿获得资金，挖矿一天获得的资金量称为基础收益。如果挖矿，消耗的资源数量为基础消耗量的3倍；如果不挖矿，消耗的资源数量为基础 消耗量。到达矿山当天不能挖矿。沙暴日也可挖矿。 （8）玩家经过或在村庄停留时可用剩余的初始资金或挖矿获得的资金随时购买水和食物，每箱价格为基准价格的2倍。 请根据游戏的不同设定，建立数学模型，解决以下问题。 1. 假设只有一名玩家，在整个游戏时段内每天天气状况事先全部已知，试给出一般情况下玩家的最优策略。求解附件中的“第一关”和“第二关”，并将相应结果分别填入 Result.xlsx。 2. 假设只有一名玩家，玩家仅知道当天的天气状况，可据此决定当天的行动方案，试给出一般情况下玩家的最佳策略，并对附件中的“第三关”和“第四关”进行具体讨论。 3. 现有n 名玩家，他们有相同的初始资金，且同时从起点出发。若某天其中的任意 名玩家均从区域A行走到区域B( )，则他们中的任一位消耗的资源数量均为基础消耗量的 倍；若某天其中的任意 名玩家在同一矿山挖矿，则他们中的任一位消耗的资源数量均为基础消耗量的 倍，且每名玩家一天可通过挖矿获得的资金是基础收益的 ；若某天其中的任意 名玩家在同一村庄购买资源，每箱价格均为基准价格的4 倍。其他情况下消耗资源数量与资源价格与单人游戏相同。 （1）假设在整个游戏时段内每天天气状况事先全部已知，每名玩家的行动方案需在第0天确定且此后不能更改。试给出一般情况下玩家应采取的策略，并对附件中的“第五 关”进行具体讨论。 （2）假设所有玩家仅知道当天的天气状况，从第1天起，每名玩家在当天行动结束后均知道其余玩家当天的行动方案和剩余的资源数量，随后确定各自第二天的行动方案。试 给出一般情况下玩家应采取的策略，并对附件中的“第六关”进行具体讨论。 注1：附件所给地图中，有公共边界的两个区域称为相邻，仅有公共顶点而没有公共边界的两个区域不视作相邻。 注2：Result.xlsx中剩余资金数（剩余水量、剩余食物量）指当日所需资源全部消耗完毕后的资金数（水量、食物量）。若当日还有购买行为，则指完成购买后的资金数（水 量、食物量）。 缺憾与错误 1. maxM居然打成minM，第三问全高温打成全沙暴……（什么鬼手误啊啊啊啊啊） 2. 3. 4. 5. 没给最短路径shortcut的表作为不挖矿纯消耗的对比（尤其是第1,2,4问，第五问在第四问的基础上有结论可以省去） 标题与论文不符，“人工智能”着实不该作为标题，应改为运筹学（当时队内调侃真。人工。智能，就给写上去了，很煞笔，应该写个运筹学，所以本文所有“人工智 能”都应该是运筹学） 得到的结果正确性有待确认。 最大的缺憾是确实做不出第六问，构造一个游戏世界的模拟器，不过听说别的队也是手算辅助出一二问，老师说这次可能就是手算比机算来的现实，一时间各队都在讲自 己最优xxx，为此队里负责精益求精表格结果的小哥都已经成老抠搜了……最后比身边听说的还是要差点的，就酱吧。 6. 论文要是有空余时间还能精益求精，有多处内容错误。 摘要 在给定的一个游戏背景下：玩家凭借每关不同的地图，利用初始资金购买一定数量的水和食物，从起点出发，途径各种不同的天气，消耗不同数量的物资。中途可在矿山、村 庄补充资金或资源，目标是在规定时间内到达终点，并保留尽可能多的资金。 问题1：首先对整个基于地图的营生行走过程建立一个优化模型，确立总目标函数是使到达终点时资金数目最大。玩家的走法为两大途径，即挖矿和不挖矿，于是寻求损耗物资 最少和综合收益最大是相应两种优化方向。基于此建立两大贯穿全文的基本模型——一是最短路径规划模型，二是矿山-村庄体系往返决策模型。前者的实现算法是Dijkstra算 法，后者则采用人工智能决策。 分区 博客草稿 的第 1 页 

至此也奠定了每问寻求挖矿途径最优策略的思路，即将玩家决策分为两头行走的最短路径规划，和矿山-村庄的往返动作规划。 由于第一关和第二关均为天气排列情况给定的模式，根据上述两个模型确定路径规划和动作决策后，根据题目所给物资消耗规则，可求得玩家初始点最佳购买策略和最终最大 拥有资金数。 问题2：相较于问题1，Q2最大的特点就是天气的随机性，一方面可以利用穷举法将所有天气情况全排列，再对挖矿处挖矿天数进行从0至最大预留时间的穷举模拟，做出走挖矿 途径或者纯最短路的选择； 另一方面蒙特卡洛模拟可以随机生成特定概率比的天气序列。基于此可以获得具有统计学属性的物资消耗散点分布，据此可以解决因为停留机制带来的时间延迟与随机变化的 问题，最终确定玩家最佳停留机制。 问题3：多玩家游戏机制中引入博弈论的思想，采取正和博弈的准则，在特定天气情况下更新两玩家在尽量自身利益最大化基础上总利益最大化的优化模型。在前几问解决问题 的方法基础上给出两玩家应采取的最优策略。且在出现矿山-村庄体系时尝试建立一种随机模拟器，对整个游戏过程进行动态仿真。 关键词：最短路径规划问题、Dijkstra算法、人工智能决策模型、蒙特卡洛模拟、多目标决策优化、博弈论 问题分析 已知本游戏策略优化问题目的是：在负重上限和初始资金两个限定条件的基础上给予单人玩家最优的游戏策略，此策略包含多个决策，涉及物资购买、物资补给、挖矿天数选 择、玩家的停留与否以及各种行为发生时机的安排等等，以期在玩家能够生存的前提下到达终点时拥有资金最多（而不是尽快跑出沙漠哦！） 易知达到资金最多的途径一是不考虑收益（即不挖矿），尽量使物资损耗最少；二是考虑收益（即考虑挖矿和去村庄补给），尽量寻求一套综合决策规则使得到终点资金最大 化，然后再比较这两个途径优化的结果得到最佳选择，这一思路贯穿整个问题的解决。 沿着这一思路，途径一的解决可以归纳为最短路径规划问题，途径二的优化可以分割为两个基本模型来寻求解决，一是从起点到达村庄（或矿山）前以及最后从村庄（或矿 山）去终点两个阶段的最短路径规划模型；二是玩家在矿山-村庄往返体系中为了赚钱进行的一系列人工智能决策模型。尤其是第二个非常复杂，需要人脑进行贪心算法和计算 机搜索算法相结合完成。因此整篇文章的大思路可用如下思维导图来表明： 图1 求解思路思维导图 第一问展示的是30天天气状况及其排序全部已知的情况。玩家的走法可分为不挖矿和挖矿两大类，于是寻求损耗物资最少和综合收益最大是相应两种优化方向。我们应分别考 虑最短路径（即最少损耗）问题以及挖矿-补给综合决策问题两大优化问题，再将结果加以比较以寻求整个游戏策略的最优解。 第二问展示的是30天天气状况在玩家未经历前完全未知的情况。由于天气不同物资消耗不同，因此对于规定天数内每日天气状态的模拟十分必要。这一问题可以采用穷举排列 和蒙特卡洛模拟的方法实现。去除天气这一变化量外，再开始分别计算两种途径下的最优解。 第三问，由于是多名玩家，因此建立在博弈论的基础上对其建模。第五关中， 具体问题解决过程 关卡1 and 关卡2：（天气排列已知+最短路+运筹学）只是关卡2因为蜂巢型地图邻接矩阵维数变大，路径更多了。 关卡3：(天气排列随机+最短路+全排列+蒙特卡洛）走挖矿途径默认不停留，因为尽可能把时间留在赚钱上。通过全排列0,1,2,3,4,5天挖矿以及穷举2^10种天气判断挖矿与否； 而对shortcut即最短路部分采用蒙特卡洛模拟，原因是我们对这种傻瓜路线剩下考虑的就是是否停留，一旦出现停留和延迟情况，由于天气变化的随机性，对于天气状 态的模拟不应基于 的全排列。因此根据前一问天气高温和晴朗的比例产生容量为1000的随机排列样本，按照高温：晴朗=5:3的比例产生了天气序列，设置停留0天即不停 留、至多停留一天就走、至多停留两天就走三个模式，后两种是专为解决高温天连续出现一直停留的死胡同设置的，因为一共就四天的路。最后从1000组数据中统计结果，画 物资需求散点分布图，如下图：其中绿色表示最多停留2次，蓝色表示最多停留1次，红色表示停留0次。 分区 博客草稿 的第 2 页 

物资需求散点分布图，如下图：其中绿色表示最多停留2次，蓝色表示最多停留1次，红色表示停留0次。 经过对图表进行了统计分析后，我们得知1000次随机模拟中有821次0次停留的物资消耗量小于2次停留消耗；有746次0次停留的物资消耗量小于1次停留消耗，0次停留的消耗处 在整个消耗水平的最低位置，我们可以判断玩家一般情况下应选择不停留策略。 最佳决策敲定就好办，可以求出最短路的物资消耗，这里由于情况过多，论玩家的一般最佳策略我们给出了全晴朗和全高温两种极端情况的上下限需要准备的初始物资，如下 表： 表5 三种停留机制物资消耗表 食物/箱 水/箱 花费 终点拥有资金 上限 下限 54 24 54 18 810 330 9190 9670 表6 最差最好天气物资消耗表 关卡4：(天气排列随机+最短路+运筹学）延续第三关和前几关的方法，虽然又加上了沙暴天气并且为“已知30天内较少出现沙暴天气”这种模糊描述，但我们就想获取玩家在最 佳策略下准备物资的上下限范围，再有就是能力实在不济，天气随机+决策部分的模拟器没有做出来，做出来所有问都好办了……想尽可能将天气固定再讨论，因此在前题述的 基础上沙暴天最多设置6天，最少设置1天（即出现即满足要求。本着寻找最优预期和最坏打算的想法，讨论了先到村庄/矿山多种组合情况及两种极端天气情况：“第一段最短 路径为全高温、6天沙暴天全发生在挖矿时、第二段最短路径为全高温”的最差天气，和最佳天气排列即“全程全晴天”，结果是一系列天气日程排布和上下限物资需求表，这 里不加以展示了。 关卡5：（天气已知+最短路+正和博弈+全排列）题述是“假设在整个游戏时段内每天天气状况事先全部已知，每名玩家的行动方案需在第0天确定且此后不能更改。试出 一般情况下玩家应采取的策略。” 日期 1 2 3 4 5 6 7 8 9 10 天气 晴朗 高温 晴朗 晴朗 晴朗 晴朗 高温 高温 高温 高温 从玩家角度出发，每个人都本着自身利益最大化的策略出发会重复路径造成损人不利己的纳什平衡，根据题述由于天气已知，且每个人的方案事先都要给出来，那么我们就有 站在上帝视角的权利了。由于三四问我们队计算出的结论是不挖矿直接走最短路是最划算的，于是一个人走最短路，另一个人稍微妥协走次短路，至于你问为啥第二个人不等 一天再走最短路，因为经过计算利用等待等到全晴，这种情况比直接出发消耗还要稍高。 有了第三问，我们就直接做次短路关于停留机制讨论的全排列，在全排列1024的样本下统计最佳停留机制，结果依然是0次停留消耗物资最少，散点图分布展示如下： 分区 博客草稿 的第 3 页 

然后在对应的天气排列下寻找物资消耗，两玩家一般情况最佳策略下上下限资源消耗表如图： （当然现在看我们选择正和博弈可能也有不妥之处，网上看到有博文描述： “较大的变化是，游戏可以有多名玩家参与，而每个人的目标依然是使自己利益最大化，也就不存在牺牲小我，成就大我的那种情况，也不会干损人不利己的事。多玩家参与的游戏相对于一 名玩家参与的游戏而言，原来设定的最佳路径会因为该路径上有其它玩家而选择原地等待或改变路径。每名玩家需要根据博弈论的原理，以其他玩家剩余水和食物资源的数量以及离矿山或村 庄的位置为依据，来推测该名玩家下一步的行动方案。因为未来天气依然未知，这里使用蒙特卡洛仿真模型实现对不同比例天气的模拟，玩家在对应天气下依据博弈论原理进行选择。”，但 至少依据题意，事先给出的计划总是要趋于自身利益最大，但挖矿必亏这个结论已知，因为有竞争而合理避开路径冲突没有不妥。） 关卡6 （模拟器） 由于涉及到村庄-矿山往返补给部分没有具体的决策算法，“所有玩家仅知道当天的天气状况，从第1天起，每名玩家在当天行动结束后均知道其余玩家当天的行动方案和 剩余的资源数量，随后确定各自第二天的行动方案”，我们实在能力不济没有做出这个游戏的模拟器，也不大想再花时间人工+计算机给三人排日程，这一块请各位大佬有 办法的指教！ 附代码： 程序文件使用说明 ================ 邮箱：peratx@itxtech.org 运行环境 ================ 1. Java 11 2. Gradle 6.3 或更新版本 3. IntelliJ IDEA 依赖库 ================ 1. Jenetics (https://jenetics.io/manual/manual-6.0.0.pdf) 开源遗传算法实现库 程序文件说明 ================ 1. 1到6.kt分别对应关卡的程序 2. dijsktra.kt实现dijsktra算法 3. search.kt实现全路径搜索算法 4. simulator.kt实现游戏世界模拟器（未完成） 5. util.kt实现一些实用方法 资源文件说明 ================ 1. 2~4.txt分别为对应关卡的节点表 分区 博客草稿 的第 4 页 

分区 博客草稿 的第 5 页