双人版《Halite III》游戏

使用强化学习掌握《Halite》

摘要

本文运用机器学习技术，为资源管理类游戏《Halite III》开发计算机智能机器人。我们聚焦于单人单船模式，分别构建了两种分类器：一种基于监督学习的支持向量机模型，另一种则采用强化学习的深度神经网络模型。我们将这两种机器学习机器人与两个基准机器人进行对比评估，其中一个为简单的规则驱动型机器人，另一个则是经过遗传算法优化的规则驱动型机器人。实验结果表明，机器学习机器人能够成功学习游戏策略，并在性能上介于这两个基准之间。

1 引言

《Halite》是由Two Sigma公司每年举办的开源人工智能挑战赛。今年的比赛版本《Halite III》是一款资源管理类游戏，玩家需要编写机器人程序，控制船只探索游戏地图并收集“halite”——一种散布在地图各处的能量资源。船只以“halite”作为能量来源，比赛结束时拥有最多“halite”的玩家将获胜。

1.1 游戏规则

每位玩家在《Halite III》开始时都拥有一座船厂，船只在此出生并储存“halite”。玩家消耗“halite”来建造新船、移动现有船只或将船只转换为卸货点。此外，玩家还可以通过良性竞争相互激励，或故意让船只相撞，使双方一同沉入海底。

每位玩家初始拥有5,000单位的“halite”储备、一座船厂以及对游戏地图的了解。每局游戏由两至四名玩家参与，在一个具有独特对称图案的二维地图上进行。船只每回合只能执行一项操作：向任意一个基本方向移动一格、在当前位置采集“halite”，或转换为卸货点。当船只位于己方船厂或卸货点上方时，会自动卸下所携带的“halite”，从而增加玩家的总储量。

每回合开始时，游戏引擎会向所有玩家发送当前所有船只和卸货点的位置信息，以及更新后的游戏地图。玩家有最多两秒钟的时间下达本轮指令。游戏引擎会解析并执行这些指令，计算每位玩家的“halite”得分，并处理所有移动动作。游戏通常持续400至500回合，具体时长取决于地图大小。最终，“halite”储量最多的玩家即为胜者。

图1：《Halite III》游戏棋盘

图1展示了一个具体的《Halite》游戏状态示例。更多关于《Halite III》规则及比赛录像的信息，请访问官网halite.io。

1.2 本课题的重要性

近年来，机器学习在游戏领域的快速发展，很大程度上得益于一系列新方法和算法的发现与应用。其中一种名为“极小化极大算法”的技术，旨在最小化可能的最大损失风险。该算法广泛应用于国际象棋引擎中，也可用于存在不确定性因素的一般决策问题。这类算法的发展极大地提升了我们解决问题的能力（Ontanon, 2012）。因此，研究机器学习如何玩好游戏具有重要意义。

2 问题与方法

2.1 问题陈述

我们的目标是为《Halite III》开发一款机器学习机器人，使其能够在固定大小的地图上实现单人模式下的资源收集最优化。该机器人每回合的主要决策将围绕船只的导航展开。在解决这一问题之后，我们可以进一步探讨该机器人在多人模式或不同尺寸地图上的泛化能力；然而，这并非本项目的重点。尽管如此，值得注意的是，我们所采用的方法其实可以简单地扩展到多人模式，只需为每个玩家单独训练一个单人分类器即可。

为了简化问题，我们在本地搭建了一个新的游戏引擎，并设置了一个环境，使得每次仅允许一名玩家参与游戏，同时保持32×32的地图尺寸不变。此外，我们还将船只的建造时机交由规则决定。若要准确判断何时建造船只，需要生成大量数据，因为在游戏中大多数情况下，玩家并不具备足够的资源。而且，船只建造决策本身也需要单独建模，这意味着必须使用另一套分类器。然而，引入额外的分类器会导致实验结果混淆，难以得出明确结论。因此，我们决定将船只建造决策设定为规则驱动型。

最后，我们还简化了训练过程，只使用一艘船只进行训练。这样做可以使训练更加容易，因为如果有多艘船只参与，那么每回合的游戏环境都会变得非确定性，导致我们无法将船只视为一个完整的智能体。此时，我们需要对地图状态中的随机因素进行模拟，整体模型也会变得更加复杂。

2.2 SVM 机器人

我们考虑的首个用于解决该问题的机器学习方法是监督学习，即通过回放录像生成训练数据。Halite 官网上有一个存储库，包含了每位玩家所有对局的完整回放记录。因此，我们用来训练机器人的数据便取自排名前50位的玩家的比赛。

其核心思想是：在竞技游戏中表现最出色的玩家的舰船行为，应当能够泛化到单人模式下最大化资源收集的目标。不过，这一假设确实存在一定的跳跃性，因为我们试图从一个更为复杂的问题中学习解决另一个问题的方法。为此，我们决定仅选取每场比赛前150步的数据，因为这一阶段与其他玩家的交互最少。这样一来，总共可获得750步可供学习的数据。然而，对于每一步，都会产生来自多艘舰船的数据。

在每一步、针对每一艘舰船，我们都会解析并提取相关信息：该舰船当前携带的卤石数量、船坞的位置，以及附近可用卤石的位置与数量。这些信息共同构成了我们的特征空间。而标签则是“优秀”玩家机器人所作出的导航决策。训练过程则简单地将这些带标签的数据输入模型即可。

我们选用的模型是带有径向基函数（RBF）核的加权支持向量机分类器。之所以选择它，是因为这是一种广为人知且在众多实际场景中广泛应用的核函数，能够确保数据在高维空间中线性可分；同时，它也易于在许多标准库中实现。

这种监督学习方法的一个潜在问题在于，它仅基于单一玩家的数据进行训练。因此，当机器人完全模仿该玩家的行为时，它的表现会达到最佳状态；但这也意味着它永远无法超越所学习的那个机器人。基于此，或许可以通过训练多个不同风格的机器人来提升性能，然而这又会带来另一个问题：如果这些机器人采用不同的策略，我们就无法保证最终训练出的 SVM 机器人能够真正学到有价值的知识。

此外，这种监督学习方法还可能限制 SVM 机器人持续改进的能力，原因在于：SVM 机器人只会机械地模仿训练数据中的动作，而不会深入理解这些动作背后的策略意图。

2.3 深度Q学习机器人

第二个目标是尝试构建一个更复杂、更鲁棒的算法，以提升机器人的性能。为此，我们考虑训练一个神经网络，该网络能够综合当前的游戏状态，并预测应采取的最佳行动。

尽管这是一个合理的模型选择，但其中面临的一个关键挑战是如何判断在特定游戏状态下，某一具体行动是否为“好棋”。因为我们唯一的评价指标是在游戏结束后才能知道机器人最终的表现如何。因此，解决这一问题的一种自然方法是采用强化学习。从高层次来看，我们希望做出能够最大化长期预期奖励的决策。为了进行训练，我们会根据每局游戏的最终结果，为游戏中每一步行动事后赋予相应的奖励。

用于此方法的数据将来自机器人自身对弈的游戏记录，这些数据将作为特征来源。我们的特征将构成神经网络的各层：共三层，每一层都是以飞船为中心的33×33网格。第一层包含飞船周围每个位置上的可用哈立特资源；第二层则编码附近其他飞船的信息——在网格中对应于每艘飞船位置上填入其持有的哈立特数量。这样，没有飞船的位置将被编码为零，而网格中心（即我们所训练的飞船所在位置）始终会显示该飞船当前持有的哈立特总量。需要注意的是，由于简化处理，这一中心位置将是该层中唯一可能非零的单元格。最后一层同样是网格形式，仅在船坞所在位置填入数字1，其余均为0，从而确保飞船能够明确前往何处卸载收集到的哈立特。

具体而言，我们选择深度Q学习作为训练分类器的模型。Q学习是强化学习的一种实现方式，特别适用于我们的场景，因为它使用离散的动作空间和连续的状态空间。虽然理论上我们的状态空间是离散的，但可能的状态组合极其庞大，若将其视为离散空间，则对于学习算法来说将难以有效训练。深度Q学习已在类似的应用中得到验证并取得成功，例如应用于Atari游戏——这些计算机化游戏机器人同样面临与我们相似的问题，包括高维视觉输入（Mnih, 2013）。

为了构建我们的强化学习机器人，我们采用了OpenAI开发的DQN基准框架。然而，鉴于哈立特游戏由引擎实例化的方式，同时进行对局并应用Q学习需要对游戏引擎进行大量修改。因此，我们选择通过OpenAI Gym环境构建单舰场景的模拟环境，并在此全新环境中进行学习。值得注意的是，尽管我们在模拟环境中训练了机器人，但学习问题的本质并未改变。在参数选择方面，我们主要参考了在Atari游戏中训练DQN时所使用的配置。

我们为DQN设计了两种奖励函数：即时奖励和延迟奖励。即时奖励会在飞船完成哈立特投放时立即给予奖励；而延迟奖励则根据整场比赛中累计收集的哈立特总量，在游戏结束后统一发放。我们将评估哪种奖励函数更为有效，若两者均可行，则进一步比较其表现优劣。

该模型在Q学习中的训练过程主要依赖于探索与利用两个阶段。在每一轮迭代中，模型会根据当前情况随机猜测（探索）或基于Q表中的已有信息作出决策（利用），以确定下一步行动。模型依据ε-贪心策略来决定执行哪一种操作：以1-ε的概率进行探索，以ε的概率进行利用。初始时，ε值较小，随着迭代次数的增加，ε值逐渐增大。根据每轮迭代中选定的参数值，Q表中的数值会相应更新（Mnih, 2013）。

此外，该算法还采用了对决式增强机制，这是一种多组神经网络相互竞争的学习方式，类似于人类的想象力（Wang, 2016）。

2.4 预期

我们预计，采用强化学习的第二种方法将在多个方面优于监督学习方法。如前所述，监督学习是从较为复杂的问题中提取数据，并倾向于模仿既定模式；而强化学习则专门针对我们的问题进行了优化，因为我们的动作空间是离散的，可供选择的选项有限。尽管我们可能在调整DQN参数时遇到一定困难，但我们仍预测它将超越支持向量机的表现。

总体而言，我们预计基于遗传算法的基准机器人和强化学习机器人将取得最佳性能，因为它们是专门为单舰、300回合的场景量身定制的。

3 结果与评估

为评估DQN和SVM机器人的性能，我们将其与两个基准进行了对比：一个简单的规则驱动机器人，以及一个经过遗传优化的规则驱动机器人。

具体而言，我们让每种机器人在32×32的地图上分别进行500局对战，每局设定300个回合。所有四款机器人均在相同的500组地图种子上进行了测试。

3.1 规则驱动机器人

作为第一个基准，我们创建了一个简单的规则驱动机器人，其行为基于贪婪策略。该机器人会持续从当前位置采集哈立特，直到该格子内的哈立特低于100点，随后移动到相邻哈立特最多的格子。当货物达到最大容量1000点时，它便会返回船坞进行投放。

3.2 遗传机器人

对于我们的第二个基准测试，我们开发了一款高性能的基于规则的机器人，并使用自定义的遗传算法来优化各项参数。该机器人会扫描周围单元格，寻找距离最近且高于某一阈值的单元格。扫描距离和阈值大小均通过遗传算法进行调优。在采集资源时，机器人会持续采集当前单元格中的资源，直到该单元格被认为“稀缺”。所谓“稀缺”的判断标准取决于周围平均卤石含量的一个倍数因子以及一个绝对最小值，这两者同样经过遗传优化。最后，机器人返回船厂的载货量阈值也进行了调优。

我们的遗传算法初始种群包含20个个体，每个个体的各项参数都由随机生成的“基因”决定。每一代中，每个个体都会参与五场比赛。根据适应度函数——即五场比赛中累计采集的卤石占比——采用锦标赛选择法选出适应度最高的个体。子代的参数则通过交叉和变异产生。

我们运行了这一自定义算法200代，每代保持20个个体，直到性能趋于稳定，最终构建了一个强大的基准模型。

3.3 结果

图2

图3

对于四款机器人各自进行的500场比赛，我们记录了每场比赛中总沉积的卤石数量以及地图上每个单元格的平均卤石含量。图2展示了这2000个数据点的散点图，其中X轴为每个单元格的平均卤石含量，Y轴为总采集的卤石数量。图3则呈现了同一组数据的16期移动平均线。我们选择这一指标，是因为卤石分布密集的地图自然会导致更高的总采集量，因此仅比较500场比赛的平均采集量并不足以全面评估表现。

我们的结果表明，两款机器学习机器人能够较好地学习卤石采集行为，其表现与两个基准机器人相当。此外，经过遗传优化的机器人在所有地图密度下均优于其他机器人。DQN机器人在低卤石密度的地图上表现优于基于规则的机器人，但在中高密度地图上则与之持平。而SVM机器人在低卤石密度的游戏场景中表现与基于规则的机器人相近，但在中高密度场景中则整体落后于其他机器人。

3.4 讨论

正如预期，强化学习机器人和遗传优化机器人取得了最高性能。这一结果在意料之中，因为DQN和遗传优化机器人是专门为单艘飞船、300回合的比赛场景训练和进化的。相比之下，SVM是在稍有不同的数据集上训练的，而基于规则的机器人则未接受任何专门训练。

我们观察到，DQN仅凭地图数据和每次沉积卤石时获得的即时奖励，便能迅速学会游戏策略。然而，在实验中，我们未能使用延迟奖励函数达到同样的效果。在这种奖励机制下，DQN只有在300回合比赛结束时才会根据总沉积的卤石量获得奖励。由于在此奖励机制下，DQN在99.66%的回合中都不会收到任何奖励，因此表现不佳也就不足为奇了。

尽管如此，我们发现当采用即时奖励机制时，DQN确实能够掌握复杂的卤石采集与返回船厂的任务。值得注意的是，这一任务颇具挑战性：DQN不能简单地在载货量达到某个阈值时就返回船厂，因为船只在移动过程中会消耗卤石，导致载货量低于该阈值，从而陷入无休止的循环。因此，DQN必须学习更为复杂的行为模式。

至于SVM，虽然其性能略逊于其他机器人，但仍然表现出相对接近的水平。考虑到SVM是在更复杂的多人多船场景下训练的，它仍能很好地泛化到我们简化后的单人单船场景中。

4 未来工作

通过本次实验及所得结果，我们证明了将机器学习应用于机器人算法的开发是一项有趣且实用的研究方向。然而，在这一领域仍有大量值得深入探索的空间。

值得注意的是，本研究中的实验是对Halite游戏的简化版本：我们将船只数量限制为一艘，固定了地图尺寸和迭代次数，并且仅针对单人优化目标进行测试。而在真实的游戏中，参数更加复杂，每一轮都需要考虑更多的变量和状态（尤其是其他玩家的状态）。

特别是将训练好的机器人适配到多人模式时，还会引发一些更有趣的问题和探索方向，例如可能需要引入博弈论的考量，让玩家通过预测对手的行为来优化自己的策略，以最大化获胜机会。

此外，还有许多不同类型的机器学习机器人值得进一步测试和评估其性能，同时也可以尝试调整各种参数，或改变游戏所用的地图尺寸。另一个有趣的探索方向是将这些方法推广到其他类型的游戏中，考察它们在不同环境下的适用性和迁移能力。

5 相关工作

将机器学习方法融入游戏算法的开发中，一直以来都得到了广泛的研究与实践。各类分类器及研究方向，尤其是神经网络和强化学习，已被应用于多种游戏的人工智能程序开发。其中，DeepMind的一项重要工作便是利用强化学习为国际象棋、将棋、围棋等多款游戏打造高性能AI（Silver, 2017）。特别地，作者采用了一种称为“白板式”强化学习的方法，训练出一种完全不依赖先验知识、仅基于游戏规则的算法，在每款游戏中均超越了当时已知的最佳算法，并且这种能力还能很好地迁移到计算复杂度更高的将棋等游戏中。

尽管已有许多基于机器学习的游戏AI被开发出来，但我们注意到，将这一方法应用于Halite这一特定游戏的问题仍具有一定创新性。实际上，运用机器学习原理来构建AI有多种可行的方式；而我们在算法中所采用的独特特征表示以及针对Halite简化版的具体策略，在现有文献中尚未见专门探讨。

6 结论

综上所述，我们通过机器学习训练了两款AI：一款基于支持向量机分类器的监督学习模型，另一款则基于神经网络的强化学习模型。经过与基准AI的性能对比，我们发现神经网络模型的表现显著优于SVM模型，但整体而言仍远逊于基于遗传算法训练的规则驱动型AI。不过，由于两款机器学习模型的性能均高于完全随机的行为，且与规则驱动型基准相当，因此可以认为它们确实能够做出具有一定意义的决策。

尽管我们的神经网络模型在与基准对比时表现尚可，但其效果仍未达到最初的预期。为进一步提升性能，一种可能的改进方案是引入一种奖励函数：每当完成固定数量的步数后，便根据该阶段内收集到的Halite总量给予相应奖励。换言之，奖励不再仅在采集资源或游戏结束时发放，而是以间隔方式分布在整个对局过程中。这样可以使AI学会识别某种行为模式的价值，而非单纯关注单个动作的好坏，从而更有效地学习并掌握策略。

Halite-III 快速上手指南

Halite-III 是一个由 Two Sigma 举办的开源人工智能挑战赛，玩家需编写机器人进行资源管理（收集卤素/能量）。本项目展示了如何利用机器学习（支持向量机 SVM 和深度强化学习 DQN）构建单船智能体来优化资源采集。

环境准备

在开始之前，请确保您的开发环境满足以下要求：

• 操作系统: Linux, macOS 或 Windows (推荐 Linux 以获得最佳兼容性)
• Python 版本: Python 3.6 或更高版本
• 前置依赖:
  • pip (Python 包管理工具)
  • git (版本控制工具)
  • 主要 Python 库：numpy, scikit-learn, tensorflow 或 pytorch (取决于具体实现), gym (用于强化学习环境)

提示：国内开发者建议使用清华源或阿里源加速 Python 包的安装。

安装步骤

1. 克隆项目仓库 将代码下载到本地：

   git clone https://github.com/lnmangione/Halite-III.git
   cd Halite-III
   

2. 创建虚拟环境（推荐） 为了避免依赖冲突，建议创建独立的虚拟环境：

   python3 -m venv venv
   source venv/bin/activate  # Windows 用户请使用: venv\Scripts\activate
   

3. 安装依赖包 使用国内镜像源安装所需依赖（以清华源为例）：

   pip install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple
   

   注：如果项目中没有 requirements.txt，请根据代码导入情况手动安装核心库，例如：

   pip install numpy scikit-learn tensorflow gym -i https://pypi.tuna.tsinghua.edu.cn/simple
   

4. 配置本地游戏引擎 该项目涉及对单船场景的简化模拟。确保您已按照项目说明初始化了本地的 OpenAI Gym 环境模拟接口（通常在首次运行脚本时会自动处理，或需运行特定的 setup 脚本）。

基本使用

本项目主要包含两种机器人实现：基于监督学习的 SVM 机器人和基于深度强化学习的 DQN 机器人。

1. 训练 SVM 机器人 (监督学习)

该模型通过分析顶级玩家的重放录像（Replays）来学习航行决策。

python train_svm_bot.py

执行后，脚本将解析前 50 名玩家的游戏数据（前 150 步），提取特征（卤素携带量、船坞位置、附近资源等），并训练一个带有 RBF 核的支持向量机分类器。

2. 训练 DQN 机器人 (强化学习)

该模型通过自我博弈在模拟环境中学习，旨在最大化长期奖励（收集的卤素总量）。

python train_dqn_bot.py

执行后，脚本将在自定义的 32x32 单船 Gym 环境中启动训练。模型会利用 $\epsilon$-greedy 策略平衡探索与利用，并通过即时奖励（沉积卤素）或延迟奖励（游戏结束总分）来更新网络权重。

3. 运行评估

训练完成后，您可以让机器人在本地模拟环境中运行，观察其表现：

python evaluate_bot.py --model_type svm
# 或者
python evaluate_bot.py --model_type dqn

系统将渲染游戏画面或输出日志，展示机器人在单船模式下的资源采集效率。