548. Lux AI Season 2 | lux-ai-season-2
这是我第一次参加此类竞赛并构建逻辑机器人。我发现竞争非常有趣，并向那些犹豫是否参加今年比赛的人们推荐。编写机器人代码并直观地看到它与其他机器人对战是一种很棒的体验。游戏设计非常出色，创造了一些新型挑战。在这次比赛中我遇到了一些陷阱，我想与大家分享。希望能帮助一些人避免它们。
在这篇文章中，我将首先快速介绍游戏。然后讲解我的设计，接着分析我遇到的陷阱，最后说明如果我有更多时间想要改进的地方。
对于任何对代码感兴趣的人，它存储在GitHub上。
LuxAI 2挑战是一场2人零和游戏，两名玩家竞争在1000个时间步内通过建造最多的地衣来改造火星。他们从几个工厂开始，拥有足够的资源建造一些单位。在游戏中，单位可以收集两种资源——用于建造新单位的矿石，以及用于维持工厂运转和浇灌地衣的冰。地衣除了在游戏结束时计入分数外，还会产生单位执行动作所需的能量。总的来说，能量在这个游戏中是非常稀缺的资源，因此高效的能量使用至关重要。
有两种类型的单位：轻量单位更节能，而重型单位每回合能挖掘更多资源，因此具有更高的资源利用率。单位执行动作并需要能量来执行这些动作。
如果两个单位相撞，较强的一方会存活。如果它们是同一类型且一个单位静止不动，那个静止的单位会损失。如果两者都在移动，能量最多的单位会存活。当你的单位相互碰撞时，适用同样的规则。因此避免单位之间的碰撞极其重要。这并不容易，因为你不是通过发送下一个动作来控制单位，而是通过更新一个可以轻松包含50个动作的动作队列。可以在每一步为每个单位更新动作队列，但这代价很高，因为每次更新队列都会消耗能量。
在比赛期间我多次更改设计，但最终得到了以下设计。
每个单位都被分配给他们生成的工厂，工厂将根据其当前资源、游戏时间步以及已安排的目标，决定其单位当前应关注的最优先战略。这些战略的一些例子包括增加地衣、收集矿石、攻击对手或保卫地衣地块。基于这些战略，尝试安排最适合此任务的单位。单位选择会选择那些乍一看每一步似乎具有最高价值的单位（在get_best_case_value_per_step部分有更详细的解释）。如果工厂的单位都无法安排来协助此战略，将尝试在次高优先级的战略上安排单位。工厂安排一个单位后，会重新计算战略的优先级，以决定下一个单位应安排在哪里。这个循环持续进行，直到所有单位都被安排，或没有任何单位可以安排在任何相关战略上。
我最终为单位设定了11个不同的目标。这些目标要么直接有助于完成战略，要么帮助单位生存（例如逃离对手）。例如，这些目标包括在特定坐标(x, y)收集冰、在特定坐标清除瓦砾或摧毁对手特定的地衣地块。这些目标的抽象基类具有以下方法：get_best_case_value_per_step、generate_action_plan和get_value_per_step_of_action_plan。
为了评估目标，我使用了以下简单公式：
value_per_step = (power_benefit – power_cost) / nr_steps
这个方法乍一看是在不计算精确行动计划的情况下，估计在最佳情况下安排单位到目标时的该公式。为了估计每个目标的能量收益，我创建了一个包含一些可调参数的公式。然后为了确定参数，我根据排行榜上的表现对它们进行了调整。
为了快速计算最佳情况，我们假设一切都很理想。例如，为单位收集冰时，我们会计算到达那里所需的距离（假设没有任何单位阻碍），路上没有瓦砾，并且单位挖掘冰的最大数量基于白天的状态，意味着每一步都会产生能量，然后返回工厂归还能量。
这些目标的最佳值用于选择最适合某战略的单位。例如，如果我们想增加矿石来建造单位，所有属于工厂且尚未安排目标的单位都会被要求计算他们在周围矿石地块采矿的最佳值。具有最佳值的单位会被选中，对于这个单位，我们将执行代价较高的方法generate_action_plan。
要从目标获得行动计划（一组特定的动作），你需要某种规划算法。我以A*为基础。A*是一种类似于更著名的Dijkstra算法的算法，但如果你能对在到达终点前剩余成本设定准确的较低边界，它可以更好地优先考虑最有希望的节点。在这个游戏的网格世界中，可以根据到最终节点的距离获得合理的较低边界。目标被分解为一些子目标（例如移动到工厂并获取能量、收集冰并将冰转移到工厂）以减少规划范围，这显著提高了计算性能。然而，找到的解决方案可能比最优解稍差。
另一个要解决的关键任务是确保你的单位不会碰撞。在这个游戏中这尤其困难，因为我们不是每次为单位规划一步，而是更新包含多个动作的动作队列。对于我们的规划算法，这意味着我们还必须考虑其他单位的行动计划。最终，我为此使用了预约表。它采用先到先得的方式。第一个被安排的单位将预约其行动计划对应的时间坐标（x, y和t=时间）。然后任何未来的单位规划都不被允许出现在这些坐标上，并会相应地生成其行动计划。
鉴于我们现在有了单位的精确行动计划，我们可以准确地计算该计划每一步的价值。这样做至关重要，因为在游戏中期，通常单位数量多于值得执行的目标。如果你总是将单位安排在目标上，最终会消耗过多能量，然后你的单位将没有足够的能量用于最重要的目标。因此，具有负值的目标永远不会被安排。
一开始，每个单位都自己思考最有价值的目标是什么，并且没有被分配到工厂。使用sum-assignment problem solver，单位被分配到特定目标。这有一个很大的缺点。通常所有单位最终都执行相同的目标。例如，如果冰矿开采的参数比矿石开采稍微有利一些，并且工厂周围有很多冰资源，单位就只会收集冰，完全忽略矿石资源。这样我最终会有很多冰但没有矿石来建造新单位。同样地，如果矿石开采稍微有利，我可能会有很多单位但没有冰，因此也没有地衣为这些单位产生能量。
因此，规划算法中需要一些自平衡规则。我最终根据工厂的需要安排单位执行目标。工厂在目标上安排一个单位后，会使用上一个安排的单位的目标重新计算其最重要的战略。例如，假设工厂安排上一个单位收集矿石。那样的话，它很快会建造新单位，因此现在会优先考虑为这些未来单位产生能量的战略。
一开始我花了很多时间解决的最大陷阱是试图在每一步计算完美的联合计划。我为此使用了基于冲突的规划。这个算法的思路是，首先每个单位独立提出完成其目标的行动计划。之后，我们验证联合计划是否有效，即是否不包含任何碰撞？如果任何单位的路径发生碰撞，我们将问题分成两个子问题，一个第一个单位获得时间坐标，另一个则没有。然后，在我的实现中，我会重新考虑在此限制下的最佳目标分布（如果一个单位未获得其最优路径，让它执行在未阻塞路径上的类似目标可能更好）。然后未获得最优路径的单位将生成新的行动计划。如果这再次无效，我们再次将问题一分为二。以分支限界风格，我们关注最优值最有希望的子问题，并重复此过程，直到找到具有最佳联合值且无碰撞的节点。
一开始，这效果很好，创建的联合行动计划总是最优的。但随着我开始建立更高效的经济体系，我的单位规模增加，碰撞也随之增加，无法及时找到无碰撞的联合计划。为了解决这个问题，我花了大量时间优化代码，以在时间限制内生成行动计划。但这似乎无法实现。因此，最终我改用预约表，虽然它可能无法给出完美解决方案，但速度要快得多，让我能够将计算资源，更重要的是我为此项目可用的编程时间集中在更重要的部分。
我低估了构建控制100多个单位的机器人的复杂性。一开始，当出现错误时，我使用调试器找出问题并继续。但主要使用调试器与日志记录相比有两个很大的缺点。一个是比赛通常需要20多分钟，因此在调试模式下复制此状态很耗时。此外，有些反复出现的问题在调试模式下更难检测。例如，我遇到一些情况，一些单位被安排到某个目标，但随后另一个单位也被安排到同一目标。原始单位会被取消安排，但之后又会自行安排到这个目标。使用调试器检测这一点需要相当多的努力，尤其是当其他单位也被穿插安排时。但通过记录每次安排和取消安排的决定，这很容易检测。
了解你的机器人是否改进的最佳方法是通过与排行榜上的对手进行比较。因此充分利用每天的五次提交至关重要。不幸的是，我过于专注于为机器人添加所有需要的功能，计划在最后专注于优化参数。但最终，我意识到我想测试的东西比我剩下的上传次数要多得多。回想起来，我应该从一开始就使用所有上传次数，因为每天调整几个参数并不费力。
为了充分利用这些上传，帮助尽可能准确地评估它们。Kaggle的评分系统波动很大，尤其是在提交截止日期之前。出于排行榜的原因，这可能是最优的，但要在一系列比赛中准确评估性能，可能有更好的选择。我没有找到很多关于Kaggle评分系统的信息，但我相信它的工作原理类似于Elo和Glicko评分系统。在这些系统中，最近比赛的影响比旧比赛更重要。这对于这些方法的原始领域（体育）来说很有意义。但对于静态机器人，你可以通过使用假设竞争者水平固定的方法来获得更准确的评估。
在比赛期间，我用两种不同的方式设置了安排，每种都有其缺点。当单位完全自行安排时，他们最终可能会执行与工厂无关的目标。另一方面，当工厂只关注最关键的战略时，这可能会导致最重要战略完成得很差，而不是高效地完成第二重要的战略。我本希望将两种方法结合起来，将目标价值乘以战略重要性。战略重要性应该是一个平均值约为1的数字。
最初，我大部分时间都花在让规划算法正确、快速且无碰撞地运行上。后来，我在平衡经济方面遇到了困难。还有很多小功能需要构建，例如区分单位的私人行动计划和它发送给环境的动作队列，并精确计算该行动计划的能量，包括它会更新动作队列的时刻。
最后，我没有时间正确实现防御目标以及一些攻击目标。我确实很好地实现了清除对手地衣的功能，但保卫基地附近的冰地块或保卫我的地衣则很仓促，无法正常工作，也没有被工厂适当地优先处理。我也没有时间实现蹲守重要对手资源或捕获远离工厂且能量低的对手单位（在那里他们是安全的）。缺乏这些能力严重阻碍了我的机器人性能。
总之，这是一次很棒的经历。我要感谢Stone Tao创造了如此丰富的竞赛环境。通过在这里竞争，我学到了很多。希望这份总结能帮助一些人避免我下次挑战中的陷阱。最后，我迫不及待想看看LuxAI挑战赛3会带来什么！