Frog Parade 的解决方案

引言

首先，我要感谢 Lux 和 Kaggle 的比赛组织者，特别是 Stone 和 Bovard，感谢他们在比赛前后为使本次比赛成为可能所做的所有工作。我还要感谢我的队友 Garrett，感谢他在头脑风暴中的协助，以及他学习 Rust 和深度强化学习的意愿和热情。

我参加这次比赛的方法是由以下几个关键因素驱动的：

1. 我认为我无法有效地以无 bug 且高效的方式用 Jax 编写特征工程代码。
2. 我想变得更擅长 Rust，并学习如何从 Python 运行 Rust 代码。
3. 与之前的比赛相比，我花费的时间要少得多，所以我需要高效地编写代码。

考虑到前两个因素，解决方案很明显，虽然起初有点令人生畏：我将用 Rust 重写环境并执行所有特征工程。此外，为了解决时间限制问题，我计划使用严格的测试驱动方法来编写所有涉及/困难的代码，这样我 hopefully 花费在调试上的时间会尽可能少。

最终系统由三个主要部分组成：用 Rust 重写的规则引擎，同样用 Rust 编写的特征工程代码，以及用 Python 编写的模型和强化学习代码。我已在 GitHub 上发布了完整的开源代码：https://github.com/IsaiahPressman/kaggle-lux-2024

规则引擎

对于那些不熟悉的人，我建议查看完整规则，但我也在这里简要总结一下：

• 每个玩家控制一支（最多）16 艘飞船的舰队，在 24x24 的地图上驾驶它们寻找生成点数的遗迹节点。
• 游戏的目标是率先赢得 3 场比赛，每场比赛的获胜者是 100 步后从遗迹节点得分最多的人。
• 飞船还必须通过寻找高价值能量块来收集能量，避开小行星和危险的星云，并与 opposing 飞船进行激光战斗。
• 存在战争迷雾，意味着玩家无法看到每艘飞船周围小区域之外的地方，所以你不知道对手在做什么，除非就在你的飞船附近。
• 地图是程序生成的，所以点数、障碍物和能量场的位置每场比赛都不同。
• 某些规则本身每场比赛都不同，尽管在给定的 5 场匹配集中永远不会变化。
  例如，移动成本或激光的有效性（游戏中称为吸取（sap）动作）可能因游戏而异，但在该游戏的匹配中是固定的。玩家必须在游戏过程中弄清楚他们确切使用的是哪些参数。

在 Rust 中运行模拟的大部分代码都很直接，但有趣的部分是确保其正确性。由于规则引擎在比赛过程中发生了一些变化，主要是由于比赛中期的一次大型规则变更，这使得这一点变得更加困难。为了尽可能确保我的模拟与真实的模拟相匹配，我编写了两种类型的测试：较小的单元测试以检查模拟的各个组件是否按预期工作，以及较大的集成测试，我在其中检查我的模拟是否在一系列种子上与真实模拟相匹配。这样，当规则发生变化时，如果我错过了任何变化，测试就会失败并提醒我注意该问题。

我认为测试驱动方法会有所帮助，但它大大超出了我的预期。我不仅在测试通过后没有花费任何时间调试模拟，而且还发现并能够快速帮助修复比赛规则引擎本身的一些 bug。虽然以这种有条不紊的方式编写代码起初减慢了我的速度，但从长远来看，所花费的时间绝对物有所值。

特征工程与动作掩码

我也用 Rust 编写了所有特征工程代码，这样它就不会成为瓶颈。我将特征分为四种类型，沿两条线划分：全局与空间，以及时间与非时间。

• 全局特征包括与地图上任何特定位置无关的特征，例如我和对手的分数、已知规则、推断规则和当前步骤。
• 空间特征包括诸如我的飞船、对手飞船、遗迹节点、已知点数块和能量场值等特征。
• 时间特征是随时间变化的特征，例如我和对手的飞船，或我和对手的分数。
• 非时间特征是指那些不随时间变化的特征，例如遗迹节点位置和已知规则，或者我觉得没有必要提供历史记录的特征，例如能量场或小行星和星云的移动。
  我在这里指出，虽然我没有提供小行星和星云位置的历史记录，但我确实向模型提供了预测的未来位置，一旦它们已知。

对于所有时间特征，我跟踪了最后 10 次观察的历史记录，并将其与它们的非时间对应物结合起来。关于特征如何输入模型的更多详细信息可以在模型架构部分找到。总的来说，包括时间特征的历史记录在内，共有 80 个全局特征和大约 100 个空间特征。对于那些好奇想查看完整特征列表的人，可以在代码中的 basic_obs_space.rs 中找到。

虽然某些特征（例如我单位的当前位置）是现成的，但战争迷雾和隐藏规则意味着大多数特征必须独立于每一步提供的观察结果进行跟踪。此外，有很多信息从未在观察中明确提供，但可以推断出来。关于特征推断，有很多工作要做，这突出了重写模拟代码的另一个好处——它让我非常熟悉规则的怪癖和边缘情况，这在处理特征工程中的相同边缘情况时非常有帮助。

一些推断特征的例子包括：

• 反射特征 - 地图总是完全对称的，所以飞船在我这边地图上发现的任何东西，如遗迹节点、小行星和星云，都可以提供给模型，就好像它们在反射位置也被看到一样。
• 点数块位置 - 虽然从未告诉您点数块在哪里，但您可以发现点数块将附近的遗迹节点，并且您知道您的分数、您的飞船在哪里以及它们去过哪里。因此，您可以推断，任何时候您的分数保持不变，您的飞船所在的位置都不包含点数。同样，每当您的分数增加某些点数时，您的飞船必须正好位于那么多点数块上。通过结合这两个推断，您可以快速准确地推断出地图两侧的点数块确切位置。（点数块也是对称的）
• 隐藏规则以及小行星和星云移动 - 所有隐藏参数，包括小行星和星云块移动的速度和方向，都是从已知的离散数量的可能性中采样的。因此，所有这些最初隐藏的信息都可以通过仔细观察观察结果如何一步步变化，并将其与给定特定规则组合的观察结果应该是什么样子的预期进行比较来推断。例如，一旦您观察到星云在第 7 步没有移动，您就可以安全地推断 nebula_tile_drift_speed 参数必须处于其他较慢的速度。
• 能量场缓存 - 只有两个相关的隐藏能量节点对称移动以构成能量场。我利用了这一点并预计算了所有可能的能量场配置。在仅观察到几个能量场值后，我可以填充其余未观察到的能量场，因为给定观察结果只剩下一种可能的配置。通常，我可以在第一艘飞船生成后尽快推断出整个能量场。

对于所有推断特征，我编写了单元测试来检查各个组件。此外，我编写了更大的集成测试，断言有关隐藏特征推断的以下内容：

• 它绝不应提供虚假信息。它要么提供与未观察到的现实一致的信息，要么未能提供超出观察内容的任何信息。
• 它绝不应提供少于观察到的信息。花大量精力处理复杂的特征推断却忘记存储可以直接观察到的信息会很可惜。
• 当相关时，它应始终提供对称信息。
• 到游戏结束时，它应该已经解决了大部分事情，尽管“大部分”的定义因特征而异。例如，我断言在 >99% 的观察中，我可以准确推断出完整的能量场。

动作掩码要简单得多。我不允许无关的动作，例如移出地图或进入小行星。同样，如果飞船没有足够的能量来支付动作，我也不允许该动作。最后，我也不允许盲目吸取，除非它针对的是已知点数块上或旁边的方块。然而，这可能是一个错误，因为 Flat Neurons 团队在 otherwise 看似无关的方块上出色地使用了这种盲目吸取。出于这个原因，下次我会使用限制较少的动作掩码，只禁止肯定无用或毫无意义的动作，例如移出地图。

深度强化学习

我解决方案的核心决策组件使用了深度强化学习。虽然上面的所有特征工程对于从可用观察中提取信息很有用，但就其本身而言，它仍然无法回答最重要的问题：鉴于可用信息，我应该采取哪些动作？深度强化学习旨在通过使用深度神经网络参数化策略来回答这个问题，使用该策略在环境中采取动作，接收奖励（或惩罚），然后使用梯度下降逐渐更新策略以最大化预期累积奖励。给定足够的时间在模拟中训练、正确的超参数和适当的奖励函数，模型可以自行学习强大的策略。此外，深度强化学习代理通常以令人惊讶的微妙战术和战略方式玩耍，这是使用传统的基于手工编码启发式的方法难以或不可能模仿的。

模型架构

我为这次比赛尝试了两种模型架构。两者都使用相同的输入和输出结构，但具有不同的模型核心。我最成功的是带有 squeeze-excitation 层的残差卷积神经网络（CNN），所以我将其提交为最终代理。我还尝试使用带有旋转位置嵌入的视觉 transformer 基础，但我只是在最后一个月才开始研究它，并且正在努力稳定足够大模型的训练。尽管我的最终解决方案使用了 CNN，但我对 transformer 在模仿教师时学习速度之快印象深刻，并且它能够以更少的参数达到可比的性能。未来，我可能会首先尝试 transformer 架构，因为它感觉离超越 CNN 只差一两个小技巧或超参数调整。

模型有两个输入层，一个用于空间特征，一个用于全局特征。对于空间输入，我将 10 帧堆叠的时间空间特征与非时间空间特征连接起来，然后使用 2 层 CNN 将其投影到模型的维度。对于全局输入，我同样连接了时间和非时间特征，然后使用 2 层 MLP 将其投影到模型的维度。最后，我广播全局特征以匹配空间特征的形状，并将两个信息流相加。我将这个组合张量输入到核心模型中——一个具有 256 大小隐藏维度（d_model）的 8 块 3x3 CNN。在核心模型之后，我将输出张量输入到价值和策略头中。

价值头使用 2 层 1x1 CNN 将输出投影到 1x24x24 形状，然后取其平均值以产生单个非标准化价值。该价值通过取决于所用奖励空间的标准化层。一旦训练稳定运行，并且在大多数比赛中，我使用了稀疏胜负（+1/-1）奖励，并在队伍达到 3 个匹配点后早期停止。价值标准化函数采用两个队伍价值的 softmax 来估计获胜可能性。值得注意的是，这种价值公式“作弊”，因为它能够同时看到两个队伍的视角以估计任一队伍的价值。然而，这有助于稳定训练，并且这样做没问题，因为价值不是在测试时计算的。

策略头由两部分组成：主策略头和吸取策略头。主策略头索引所有存活单位的位置以生成形状为 n_units x d_model 的矩阵。然后我将每个单位的标准化能量附加到此矩阵，然后将其传递给 2 层 MLP，将其投影到 n_units x n_actions 形状。请注意，能量在此步骤以及主输入中提供，以便同一方块上的单位可以学习基于其能量水平的独立策略。最后，为主动作独立采样每个单位，动作空间包含 10 个选项：NoOp，4 个移动动作，和 5 个吸取动作——每个可能的吸取范围一个。对于选择吸取动作的单位，吸取策略头使用 2 层 CNN 将核心输出投影到 1x24x24 形状，表示吸取该方块的非标准化概率，并在所有单位之间共享。非法吸取动作在每单位基础上被掩码，考虑到该单位的位置和吸取范围。

强化学习算法

我使用了相对普通的 PPO 实现，带有 clipping、非法动作掩码，以及额外的熵和教师-KL 损失项。我还使用 GAE-Lambda 来估计价值，具有高 gamma。(0.9999-1.0) 由于胜负奖励是在玩家级别分配的，我在计算策略损失时对所有单位跨主动作和吸取动作分布的 log 概率求和以获得联合 log 概率。我早期尝试过在每单位级别上分解价值函数，但无法弄清楚如何使其成功工作，所以我放弃了并专注于其他事情。我很想知道是否有人让每单位价值分解（和策略优化）方法工作！

测试时实现

与 Lux Season 1 不同，我在测试时使用了随机动作采样，因为随机策略的性能更好。我想这是因为混合策略有助于代理进行盲目吸取和躲避 opposing 盲目吸取。在测试时，我还使用了三种数据增强——两个对角线反射和 180 度旋转——并在采样前取平均策略。

其他工程笔记

训练系统

我在本地机器上运行所有实验，配备 16 核/32 线程 AMD Ryzen 9950X CPU，64GB RAM，以及两个 GPU：RTX 3090 和 RTX 2070 Super。使用带有全核多线程的自定义模拟器，当忽略计算所采取动作的时间时，我能够达到 110,000 步/秒的速度。因此，与将内存移动到 GPU 和从 GPU 移动内存以及运行推理和反向传播以训练模型所花费的时间相比，模拟和特征工程几乎是瞬时的。由于 GPU 计算是瓶颈，训练速度根据模型大小和架构而有很大差异。

模型大小

早期，我尝试了小型 420,000 参数模型，训练速度为 2800 步/秒。对于最终模型，我训练了一个具有 10,000,000 参数的卷积网络，训练速度为 430 步/秒。我本可以，而且可能应该，进一步扩大规模，因为我距离 100MB 提交文件大小限制还差 62MB，但我想尝试 transformer 架构，所以我在最后一个月改为这样做。我估计最终模型训练了大约 300,000,000 游戏步，总计 600,000,000 每玩家观察，对应大约 8 天的连续训练。它在大约 200,000,000 步时大部分已经 plateaued，但在那之后继续表现出小的逐渐改进。为了监控性能，我记录了许多指标，包括各种损失项、平均得分、动作频率和相对于之前最佳模型的胜率。

使用的工具

我使用 Wandb 记录所有性能指标并跟踪实验。我使用 Rye 进行 Python 包管理，并使用 Maturin 和 PyO3 为 Rust 代码添加 Python 绑定。最初，以与 Kaggle 服务器上竞争运行时环境跨兼容的方式编译代码和配置绑定很痛苦，但我最终发现问题是由于 GLIBC 版本不匹配。我能够通过在使用 Kaggle 镜像的 Docker 中编译和构建提交来解决这个问题，之后构建提交再也没有出现任何困难。

我使用的一些其他工具来帮助保持事情 organized 和无误包括：

• Rustfmt 和 Ruff 分别自动格式化 Rust 和 Python 代码
• Clippy 和 Ruff，再次，用于执行代码 linting
• Mypy 用于静态类型检查 Python 代码

结论

最后，包括测试在内的最终代码库由约 10,800 行 Rust 和约 6,500 行 Python 组成。虽然我为这个赛季编写的代码比第 1 季 considerably 更多且更复杂，但我觉得我能够更高效地这样做。这部分当然是由于经验，但我也归功于测试驱动方法节省了我在修复错误上的大量时间。这是一个谦卑的提醒，编写大量代码并不难，但编写正确的代码很难。

欢迎随时联系提出任何问题或在下面评论中发布，我会尽力回答。这次经历非常有趣，我想再次感谢组织者、我的队友 Garrett 和其他竞争对手进行了热烈的讨论和激动人心的比赛。我期待在接下来的几天里阅读和学习其他团队的解决方案，并热切等待 Lux 第 4 季！