《探索多行动回合制兵棋的学习分类系统行为》美国空军学院2022最新102页论文

2022 年 9 月 28 日 专知

I. 引言

1.1 问题背景

自人工智能（AI）诞生以来，复杂的游戏为测试和探索搜索技术提供了一个具有挑战性的领域。甚至阿兰-图灵也提出将国际象棋游戏作为人工智能的基准，提出了一种他亲手执行的游戏算法[1]。游戏在搜索算法中的重要性后来在1958年得到了扩展，当时阿瑟-塞缪尔使用早期版本的强化学习创造了一个跳棋游戏程序[2]。自20世纪70年代以来，重点是国际象棋比赛，最终为IBM深蓝程序在1996年击败世界国际象棋冠军加里-卡斯帕罗夫铺平了道路[3]。在最近几年，玩游戏的人工智能仍然处于该领域的前沿。2016年，谷歌DeepMind的经典大状态空间游戏Go的智能体在比赛中击败了世界冠军[4]，标志着人工智能发展的一个里程碑。

游戏有很大的搜索空间，很难完全探索。尽管一个人可以采取的状态和行动组合的数量很多，但人类在为复杂的游戏制定策略方面却异常出色。然而，随着计算能力和算法理论的进步，人工智能Agent现在能够在复杂游戏中击败世界冠军人类。这些现代游戏算法往往摆脱了人类的理解能力，并试图取代人类的决策，而不是增强它。

在整个人工智能领域，存在着使人工智能更加透明、可解释和可说明的普遍工作[5]。然而，在玩游戏的人工智能领域，这种努力对学习Agent来说是稀疏的，因为现代Agent传统上使用非符号方法。符号Agent通过使用所学概念的符号描述来表示其知识，而非符号Agent则以内部格式表示其知识，如加权突触、逻辑单元或连接网络[6]。游戏可以特别受益于符号方法的可解释性，以帮助人类用户理解游戏，并在人工智能的辅助推理被移除后提高他们的表现[7]。

符号化人工智能用于游戏的一个例子是学习分类器系统（LCS）算法家族。LCS是基于规则的学习机器，采用遗传算法（GA）来发现新的规则[8]。LCS的实现分为两个系列，即密歇根式和匹兹堡式。密歇根式LCS评估单个规则的适用性，而匹兹堡式LCS则评估规则集的适用性。最近的研究工作绝大部分集中在密歇根式的实现上[8]。此外，由于较小的评估时间和在线学习能力，密歇根式的LCS实现在游戏中比匹兹堡式的对应系统受到广泛青睐。然而，由于规则数量众多，它们的推理能力较低[7]。虽然匹兹堡式的LCS在实时战略游戏中经常拥有局限性[9]，但它们在其他游戏环境中显示出了前景，因为在这些环境中可以进行离线学习[10]，同时保持可解释性[11] 。

本论文探讨了LCS在一类特殊游戏中的应用：兵棋推演。兵棋推演并没有一个标准的定义。2020年版的《联合出版物5-0》将兵棋推演定义为 "在合成环境中的冲突或竞争的表现，其中人们做出决定并对这些决定的后果做出反应"。[12] 相比之下，国防建模与仿真协调办公室（DMSCO）使用现已失效的电气和电子工程师协会（IEEE）610.3-1989的兵棋推演定义，将其定义为 "一种模拟游戏，参与者在预先确定的资源和约束条件下寻求实现特定的军事目标；例如，模拟参与者做出战场决策，计算机决定这些决策的结果。" [13] 在本论文中，我们将兵棋推演定义为以现实世界的逻辑为模型的战场模拟，其中参与者做出决定以完成一个或多个目标，并由计算机决定结果和互动。

这篇论文的重点是LCS在回合制、同时移动和多行动游戏Stratagem MIST中的实现。Stratagem MIST是空军研究实验室（AFRL）正在开发的一个游戏，作为战时冲突的多域模拟器。据作者所知，专门用于军事战争游戏的LCS Agent目前还没有被探索。此外，在一般的游戏中缺乏涉及匹兹堡式的LCS的研究，这也提供了一个兴趣点和未开发的领域。我们的假设是，LCS，特别是匹兹堡式LCS，除了产生可解释的输出，可以让外部观察者理解其决策过程外，还可以成为Stratagem MIST的有效的符号游戏Agent。

1.2 动机

兵棋推演对于军事科学领域尤其重要，因为它们可以用于发展作战理论[14]。现代兵棋推演的概念是1780年在普鲁士发明的，记录显示，年轻的军官通过玩桌面兵棋推演来学习军事战略。从历史上看，从兵棋推演中学到的经验往往能转化为现实世界的场景。在第一次世界大战中，每个主要作战国都采用了兵棋推演来帮助战争计划[15]。在第二次世界大战中，美国和英国皇家海军利用分析后的兵棋推演结果来制定更好的战术，而轴心国部队则利用兵棋推演来预测盟军的战略[14]。近年来，一些项目证明了应用人工智能技术解决复杂兵棋推演的成功[16]。然而，解决游戏或开发先进的搜索技术以胜过人类的目标可能与兵棋推演的既定目的相冲突。如果兵棋推演的目的是通过模拟为人类玩家准备实际的冲突，那么非符号Agent的行动可能无法转移到现实世界的表现。相反，一个能够很好地发挥兵棋能力，并以可解释的形式呈现其理由的Agent有可能帮助发现新的战略和战术，从而转化为现实世界的场景。

战略MIST是探索兵棋推演中使用LCS的一个主要领域。其巨大的复杂性、一般的兵棋结构以及对多个多领域场景的适应性，促使人们在多个方面产生研究兴趣。由于在兵棋和Stratagem MIST中没有其他LCS的实现，因此跟踪LCS规则在条件分布、行动分布和行动选择倾向方面的内部构成是很重要的。这些数据可以回答关于LCS在保持可解释性和性能的同时做出复杂决策的能力的问题。