2024华为软件精英挑战赛季军赛队心路历程分享

日前，2024第十届华为软件精英挑战赛-“普朗克计划”全球总决赛及颁奖典礼圆满落幕。11支优秀队伍凭借优异表现分享了68万元总奖金池。

其中，武长赛区来自华中科技大学的“明天组会吃烧烤还是火锅”队获得全球总决赛季军。来自华中科技大学的优秀选手陈梦雷撰文分享其赛队参赛体验，包括参赛初衷、解题思路及方案、比赛收获等。

一、参赛初衷

今年决定参加软挑主要是想找个有趣的事情做做，重新找回写代码的动力。平时做研究比较枯燥，也很难有正反馈，甚至反馈都很慢。看了下今年赛题，感觉很有意思，就决定来参与下。

二、初赛阶段思路

初赛阶段地图属性相对简单（只有空地、海洋、障碍物、以及港口），且不需要考虑船的路径规划。主要的设计可以分为如下几个模块：（a）机器人路径规划（b）机器人碰撞避免机制（c）机器人运货策略（d）船运货策略。

机器人路径规划。我们采用简单的bfs来实现机器人路径规划。dis(x,y,tx,ty)和direct(x,y,tx,ty)分别表示某点(x,y)到目标点(tx, ty)的距离和下一步应走的方向。为了减少空间开销，我们要求起点(x,y)是有效点（即空地和港口），同时要求终点(tx,ty)是港口或者货物生成点。为了减少时间开销，我们只在选择物品后，才以该货物生产点为(tx,ty)进行一次bfs。

机器人碰撞避免机制。具体而言，每个机器人生成detect_time长度的未来路径，这个路径就是没有碰撞情况下这个机器人预计走的路径。根据这个未来路径，可以判断机器人A和B是否会碰撞。这样可以得到若干机器人集合，任意集合内的机器人会至少和另一个集合内机器人碰撞。我们分别对于每个集合进行碰撞避免处理。对于某个集合，我们对集合内每个机器人生成handle_time长度的合法路径（即不与障碍物或者海洋发生碰撞）。然后采样若干次，每次采样对集合内每个机器人随机选取一条刚刚生成的合法路径，然后对这一次采样选取的路径集合进行估值。估值函数需要满足：（a）碰撞惩罚很大（b）对于机器人和目标点距离，根据机器人优先级加权求和。最后，选取估值小的路径集合，强制机器人在后续handle_time步按照所生成的路径行进。注意我们每一帧都可以检测碰撞和处理碰撞，所以这种处理方式其实是比较动态的。下列代码展示了碰撞处理函数：

机器人运货策略。初赛阶段我们尝试了很多种运货策略，这里介绍我们最终初赛正式赛所采用的策略。我们先将每个货物归属到最近的那个港口，然后按照value/send_time排序，这里send_time指货物生产点到所归属港口的距离。然后对于每个机器人，我们也会将其归到一个港口。处于空闲状态的机器人就会选取对应港口优先级最高的货物去搬运。每个机器人会存储一个plan_to_work_time，表示会在plan_to_work_time之前都归属在当前港口。当过了plan_to_work_time，就要重新选择一次工作港口。我们定义港口吞吐率，即该港口总货物价值除以当前时间。我们枚举每个港口，三分枚举机器人在这个港口预计归属时间t，分别计算加入这个机器人和不加入这个机器人两种情况下港口在t时刻的吞吐率，选取吞吐率差值最高的港口以及归属时间。因为我们某个港口的机器人选取货物是固定顺序的，吞吐率的计算就是模拟即可。

船运货策略。我们定义船的吞吐率，即最终船运输的货物总价值除以这一趟运输的总耗时（从虚拟点出发到回到虚拟点的时间）。和机器人类似，我们也为每个船存储一个plan_to_load_time，表示在plan_to_load_time之前都会前往并停留在目标港口。每当一艘船到达plan_to_load_time时，有如下方案：（a）回虚拟点（b）前往另一个港口并停留若干时间。我们会选择使船吞吐率最高的方案。选择港口时，我们会假设前往这个港口后就会直接回虚拟点，从而计算对应船的吞吐率。

总的来说，初赛阶段我们并没有使用复杂算法，也并没有针对地图优化（除去调参），因此我们练习赛最终排名只有23名，正式赛也只排在15名。但正是因为我们所实现的策略比较通用，后续比赛阶段能比较好地利用初赛的各种策略，不需要进行太大的重构。

三、复赛阶段思路

复赛增加了船的路径规划，并且增加了许多地图属性（比如主干道、主航道）。但是我们的设计框架并不需要很大修改就能使用。相比初赛，复赛阶段我们只进行了如下修改：（a）船的路径规划（b）船的碰撞避免机制（c）修改船的运货策略(d)购买策略。

船的路径规划。和机器人的路径规划类似，我们使用bfs进行路径规划。sea_dis(x,y,d,tx,ty)和sea_direct(x,y,d,tx,ty)分别表示某点(x,y,d)到目标点(tx, ty)的距离和下一步应做的操作。同时只需实现港口间和港口到交货点之间的路径规划即可。

船的碰撞避免机制。和机器人一致，只需修改未来路径生成、合法路径生成以及估值函数部分。

船的运货策略。和初赛阶段大体一致，只不过每次可规划涉及多个港口的安排，称为一个trip。以涉及三个港口{A,B,C}的trip为例，其表示这样一个安排：(A,t_A)->(B,t_B)->(C,t_C)->交货点，t_A、t_B、t_C指对应的plan_to_load_time。这里我们也是基于采样的方法，来选取使船吞吐率最高的trip。

购买策略。我们只分别对机器人和船设置了最大购买数量，且一开始只买一艘船，等机器人买到最大数量时，才把后续船买完。这样静态的方法其实还可以，假设某个动态方法最后买了若干机器人和船，这些机器人和船肯定越早买越好。另外，购买地点我们只是选取过往购买次数最少的地点购买，尽可能使机器人平均分布。

复赛到最后前十名差距都不算大，能进入决赛说实在还是有些看运气的。

四、决赛阶段思路

决赛阶段所涉及的改动很大。所有队伍都在同一个地图上跑，这就自然而然引入博弈相关的策略涉及，同时需要处理对场面信息的更新。对于每个指令，都要保证其生效后才能进行相应状态更新。大模型问答也很有意思，不过我们认定大模型问答不是主要矛盾，可以后续再优化。这里先介绍决赛我们分析的博弈思路，然后介绍基于博弈思路的各项策略。

博弈思路

首先根据规则，分析观察得决赛有如下特点：

所有队伍都在一张地图上跑，由于各项资源有限，队伍之间是竞争关系。最直接的想法是保留复赛的各项策略，即机器人和船都会选择性价比高（对我们来说就是吞吐率高）的方案。但是复赛的各项策略都是含有对未来的预测和估算，这在决赛中是难以成立的，因为大部分机器人和船的行为都是不受自己控制的。同时，决赛机器人和船之间存在激烈竞争，比如对于高价值货物，一个高价值货物，必须派最近的机器人去抢，而这从全局调度来看，吞吐率可能不是最高的。同样地，由于泊位有限，船离港去交货点回来后，可能就无法占据到泊位了。

货物需要快速变现，前期积累的优势在后面有放大效应。所有队伍初始资金都是25000块，如果某个队伍A能在1000帧把货物变现并赚25000块，这个队伍相当于是两个1000帧才开始的队伍，对于前期没有取得这种优势的队伍B来说，这就是“正义的二打一”。假设后面A和B的行为相同，就仅仅因为前期这一优势，就能使A比B高出接近一倍的分数。

泊位的垄断会导致零和博弈。比赛最后阶段，自己处于装载状态的船可以一直占据泊位，不让别的船进入，到最后再离开，可以认为是一种对泊位资源的封锁。对于每艘船的最后一趟而言（即认为离港交货后无法占据到泊位），执行这样的封锁策略是基本不会有损失的。但是如果有多个队伍执行这种策略，队伍互相之间的博弈会导致封锁时间提前。具体而言，假设所有队伍都是17000帧开始封锁泊位，如果自己在17000帧之前没进行封锁，即离港去交货，那么回来时是占据不到泊位的。因此，自己必须提前进行封锁。所以，泊位封锁时间会越来越早，最终甚至可能一开始大家第一艘船占据港口后就不能离开，根本无法变现。

策略设计

基于以上分析，我们修改了几乎所有策略，包括机器人货物选取和目标港口的选取、船选取港口、离港的策略、购买策略。

机器人和船的协同策略。机器人的货优先交给自己的船。我们会标记1-2艘自己的船，机器人的货优先交给这些被标记的船。虽然这样机器人可能需要多走几百帧的路才能把货物交到港口，但是这样能快速装满一些船，从而尽早变现。如果交给别人的船，就不确定别人何时交货，且货物价值要分一半给别人。

机器人货物选取策略。(a)优先选取高价值货物。当发现高价值货物时，安排最近的机器人去抢，这个我们是通过交换机器人目标货物来实现的。当没有高价值货物时，机器人会前往地图上预先设置好的巡逻点，到达巡逻点后，就可以按照优先级选择低价值货物。这可以让机器人在地图上游荡，更加可能抢到高价值货物，同时也会搬运少许低价值货物来保证基本的收益。(b)每一帧都重新选择目标港口，优先去最近的被标记的自己的船，如果没有，就优先送往有船且其loaded_num大的港口，争取尽早变现。

船选取港口策略。优先选取空港口，空港口就选最近的，能尽快抢到。另外，我们限制了船选取港口的距离，离船当前位置太远的港口就不考虑了，因为大概率抢不到。假设没有合适的空港口，就得排队等待。优先去自己船占据的港口等待，这样能尽量减少和别人船去抢泊位。如果当前港口都是别人的船，就去loaded_num大的港口，因为可能会更早离开。

船离港策略。对于第一艘船，我们限制其停留时间，且当装了足够价值货物时就让其交货，尽早变现。后续的船都是简单地装满了才离开。然后我们设置了封锁港口的时间，当过了这个时间，船即使装满了也不会离港。

购买策略。我们设置了机器人和船的购买比例（6：1），然后根据场上机器人数量限制自己的购买数量，避免边界效应。比如，当场上机器人数量超过1000个时，我们就停止购买。

尽管我们分析了很多博弈思路，并设计了基于博弈思路的各种策略，但正式赛的情况是我们未曾考虑到的。有很多队伍，基础的策略都没有调试好，也完全没考虑这些博弈，比如很多队伍机器人还是送到最近的港口。这就使得正式赛中，采用复赛中性价比策略的船能快速捡取空港口的高价值货物，进而飞快变现。我们了解到前期有采用这种策略的队伍就只有三只，而这三只队伍就是前三名的队伍。

五、总结

由于之前有参加软挑的经验，这次我们在设计上强调了策略的稳定性和鲁棒性，也确实效果不错。初赛和复赛阶段，我们只各花了一周左右的时间实现和修改，在取得不错效果和排名之后，没有进一步针对地图优化，因此练习赛排名都不在最前面。但是正式赛排名都轻松比练习赛高出一些，我们认为这归功于我们仅考虑通用策略，并没有对地图过拟合。

决赛过程其实并不顺利。我们练习赛上遇到字符串编码问题，查了很久bug才解决，这里也非常感谢赛题组老师们耐心解答我们的问题，这也使得我们最终能解决这个问题。另外在比赛前一天，我们才重新理清思路，重构了所有策略，并找出了之前的多个bug。决赛当天看到性价比策略具有重大优势时，试图重新加回去，但是一直没改好，有bug，最终选择提交了旧版本。发生这种情况也是因为版本管理没做好，之前觉得性价比策略在决赛博弈环境中作用有限，就去掉了，正式赛想重新启用就比较困难。我们后面和其他队伍交流发现很多队伍的情况也都和我们一样。还是应该多考虑可能发生的情况，把不同策略设置成可开关选项。

总的来说，这次软挑体验不错，赛程安排也合理，尽管还是有些久，但是确实没法再压缩了。非常感谢赛题组老师还有各个工作人员的付出，同时感谢武长赛区工作人员对我们的关心和鼓励，让我们能安心体验比赛，收获这次难忘的经历。