0 概述

机器博弈^[1]又称为计算机博弈, 主要研究如何使计算机模拟人类进行游戏对抗, 是人工智能领域最具挑战性的研究方向之一。继以围棋^[2-4]、五子棋^[5]、亚马逊棋^[6]、兵棋^[7]等棋类游戏为代表的序贯博弈问题得以解决后, 以实时策略(Real-Time Strategy, RTS)游戏^[8]为代表的同步博弈问题成为机器博弈领域的研究热点, 如星际争霸(StarCarft)^[9-11]、Dota 2、王者荣耀^[12]等。通常, RTS游戏职业玩家或RTS AI程序(Bot)的操作可划分为宏观操作和微观操作两部分^[8], 分别称为宏操、微操。宏操侧重于对整个战局的调控, 用于保证玩家占有经济和科技优势; 微操侧重于遭遇战中作战单元的控制, 用于保证玩家占有军事优势。可见, RTS游戏微操是RTS游戏AI研究的基础问题, 也是RTS AI Bot的核心模块。

相较于棋类游戏中参与者轮流行动, RTS游戏微操要求参与者同时采取行动, 实时性更强, 且双方作战单元数目不定, 导致动作空间规模随作战单元数量的增加而呈指数级增长。目前, 常见的解决思路分为搜索方法和强化学习方法两种, 两者相互独立。但在面对大规模战斗场景时, 搜索方法存在搜索速率下降和搜索空间有限的问题, 难以保证求解的最优性, 而强化学习^[13-15]方法存在学习困难的问题, 且训练好的强化学习模型往往局限于固定的战斗场景。因此, 现有方法难以解决大规模战斗场景下的RTS游戏微操问题。

采用深度学习与搜索相结合的思路, 可以实现学习模型对搜索方法的合理指导, 使得在实时性约束下, 尽可能地搜索大概率存在最优解的动作空间, 如AlphaGo^[3]、AlphaGoZero^[4]在围棋上取得的巨大成功, 为解决RTS微操问题提供可能。考虑到采用强化学习方式, 难以训练适用于多变战斗场景的学习模型, 参考AlphaGo^[3]的思路, 采用监督学习方式训练深度学习模型。基于此, 本文提出融合深度学习与搜索的RTS游戏微操方法。根据作战状态表达方法, 将游戏状态映射为多通道特征图, 给出一种基于卷积神经网络的联合策略网络(Joint Policy Network, JPN), 不同于大多数模型仅能学习游戏状态至个体动作映射的策略模型, JPN可以实现多智能体联合动作的端到端学习, 并将JPN与组合贪婪搜索(PGS)^[16]、组合在线演化(POE)^[17]、自适应分层策略选择(SSS+)^[18]相结合, 提出了3种改进方法, 分别为PGS w/JPN、POE w/JPN、SSS+w/JPN。

1 相关工作

现有的RTS游戏微操方法分为搜索方法和强化学习方法两类, 搜索方法是在有限时间内进行在线搜索, 由搜索到的局部最优解决定最终行动; 强化学习是通过环境交互完成模型学习, 使用时由模型决定最终行动。

搜索方法应用于RTS游戏微操始于Churchill等人提出的ABCD^[19]和UCTCD^[16], 这两种算法由广泛应用于棋类游戏的Alpha-Beta搜索和UCT算法演变而来。后来的研究工作主要围绕如何在搜索方法中引入精炼机制, 包括动作精炼和状态精炼两类, 即通过减小动作空间或状态空间的规模来加快搜索效率。动作精炼一般将原始动作替换为固定规则(Script)动作, 如组合贪婪搜索(PGS)^[16]、基于Script的UCT^[20]、组合在线演化(POE)^[17]等; 状态精炼则是合并相似状态的作战单元, 如基于空间聚类的UCT^[20]、基于类型系统的分层策略选择(SSS)^[18]、自适应分层策略选择(SSS+)^[18]等。然而, 动作空间规模随作战单元数量的增加而呈指数级增长, 当作战单元数量较多时, 实时性约束(一般为42 ms)下的精炼机制也只能搜索有限的动作空间, 所求解的最优性仍不足。

强化学习^[13-15]方法通常将RTS游戏微操问题建模为多智能体马尔科夫决策过程, 其目标是让多智能体学会合作式行动。主流方法是将多智能体强化学习与深度学习相结合, 研究方向包括学习架构、学习策略及多智能体沟通机制。学习架构涉及多智能体强化学习框架的设计, 主要围绕传统强化学习中的行动家-评判家框架, 如相互独立的行动家-评判家^[21-23]框架、分布式行动家-集中式评论家^[24]框架等。学习策略主要用于提升强化学习的学习效率, 如文献[22]采用课程学习逐步将强化学习模型由简单场景迁移至复杂场景, 文献[23]利用职业玩家先验知识预训练强化学习模型。多智能体沟通机制涉及多智能体信息传递的显性建模, 如文献[25]由单个沟通网络实现多智能体间信息传递、文献[26]采用双向递归神经网络实现各个智能体的信息传递。强化学习模型的训练难度正比于状态空间、动作空间规模, 导致现有方法难以应对大规模场景。另外, 现有强化学习方法往往局限于单一场景, 双方作战单元的种类、数目固定, 难以应对多变的复杂场景。

综上, 搜索方法和强化学习方法相互独立, 均难以解决大规模战斗场景下的RTS游戏微操问题。本文方法融合了搜索方法、学习方法的优势, 有利于拓展RTS游戏微操的研究思路。

2 问题描述

RTS游戏微操问题涉及作战环境、敌我双方控制的作战单元, 参与者要求控制各自的作战单元进行实时对抗, 直至一方所有作战单元消灭殆尽, 属于零和同步博弈问题。本文关注二人零和的RTS游戏微操问题, 假设参与者为P={i, －j}, 己方i控制m(m≥1)个作战单元, 敌方－j控制n(n≥1)个作战单元, 分别对应作战单元集合U_i=(u₁, u₂, …, u_m)、U_－j=(u_－1, u_－2, …, u_－n)。由此, RTS游戏微操问题可以被建模为包含m+n个智能体的马尔科夫决策过程, 该问题可以表示为一个四元组G={S, A, Γ, R}, S表示所有作战单元U=U_i∪U_－j可能经历的状态, A表示作战单元的所有可行动作。在任意状态s∈S下, 待命单元选取各自动作α∈A构成联合动作$\left\{ {{{\left\{ {{\alpha _i}} \right\}}_{i = 1, 2, \ldots, m}}, {{\left\{ {{\alpha _{ - j}}} \right\}}_{j = 1, 2, \ldots, n}}} \right\}$, 依据状态转移函数Γ:S×A^m+n×S→[0, 1]可以实现作战场景的状态转移, 并依据奖励函数R:S×A^m+n→[0, 1]获得即时回报。本文采用监督学习方式训练策略模型, 在此忽略奖励函数的定义及使用。

固定规则常被用于输出智能体的个体行动, 可将其定义为σ:S×U→A, 在任意状态s∈S下, 依据固定规则输出单元u∈U的动作决策α∈A。通常以UCTCD为代表的树搜索方法事先建立博弈树, 搜索树根节点(Root)至叶子节点的最佳路径对应局部最优解。博弈树中各个节点对应S中各个可能状态, 若状态s_i与状态s_j间存在边, 则两状态间存在状态转移。不同于树搜索方法, PGS、POE、SSS+不要求建立博弈树, 基本思想是在初始解的基础上, 采用不同的迭代策略使得初始解朝最优解方向演变。搜索方法结合固定规则σ和静态评估函数ψ来评估出现状态s∈S的价值, 前者用于模拟状态转移, 后者用于评估终局局势, 典型的LTD2函数如式(1)所示:

$ \begin{array}{l} {\rm{LTD}}2\left( s \right) = \sum\limits_{{u_i} \in {U_i}} {\sqrt {{\rm{hp}}({u_i})} } {\rm{dpf}}\left( {{u_i}} \right) - {\rm{ }}\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{{u_{ - j}} \in {U_{ - j}}} {\sqrt {{\rm{hp}}({u_{ - j}})} } {\rm{dpf}}({u_{ - j}}) \end{array} $

(1)

其中, hp(u_i)、dpf(u_i)表示单元u_i∈U_i的当前生命、单帧可造成的伤害。

假定φ(s, u_i)表示从单元u_i∈U_i视角出发, 状态s∈S对应特征图, 则多智能体强化学习方法依据π:φ(s, u_i)→α_i生成单元u_i∈U_i的动作决策。假定φ(s, U_i)表示从己方所有单元视角出发, 状态s∈S对应特征图, 本文提出方法的决策过程如下:1)JPN依据π:φ(s, U_i)→ρ(s, U_i)生成己方所有单元的动作概率分布; 2)由生成的概率分布指导搜索方法, 依据T:〈s, φ(s, U_i)〉→{α_i}_{i=1, 2, …, m}输出己方所有单元的最终行动。

3 RTS游戏微操方法

本节描述融合深度学习与搜索的RTS游戏微操方法, 给出整体解决方案描述各部分的逻辑关系, 介绍策略模型, 包括状态表达、动作表达、JPN等, 并对PGS w/JPN、POE w/JPN、SSS+ w/JPN 3种改进方法进行说明。

3.1 整体方案

梳理伤害机制密切相关的单元属性, 完成作战状态表达, 利用特征图表达原始状态; 采用动作精炼的思路, 完成作战单元的动作表达, 运用Script动作表达原始动作。RTS游戏微操的整体方案如图 1所示。对于当前游戏状态s∈S, 经状态表达生成特征图φ(s, U_i), 输入至JPN, 生成动作的概率分布; 搜索方法在此先验概率分布指导下, 循环执行搜索过程直至有限决策时间到达; 最后将Script动作转换为实际动作, 输出至RTS游戏实验平台, 作为最终决策。

3.2 状态表达

状态表达是将原始游戏状态转换为多通道特征图。鉴于RTS游戏涉及单元种类繁多, 本文参考之前搜索方法和多智能体强化学习方法的设置, 选取StarCarft中4种采用物理攻击的作战单元, 分别是Zergling、Zealot、Dragoon、Marine。在状态特征设计上, 主要考虑与空间分布、伤害机制密切相关的单元属性, 具体如表 1所示, 己方、敌方各对应一半。其中, 不同单元之间可造成的伤害由单元类型、攻击类型、体型共同决定, 单元生命按基数、比率、序数划分为3种特征, 基数、序数分别对应当前生命、生命排行, 比率表示当前生命与最大生命的比值。

特征编码采取one-hot编码方式, 每一种连续或离散特征对应多通道的0/1特征图, 共编码为56通道特征图。如图 2所示, 单元所属被编码为2通道特征图, 分别对应己方所属、敌方所属。考虑到实际游戏状态的稀疏性, 作战单元仅占据很小的空间, 特征编码在变化的作战场景尺度上进行。具体地, 若作战场景尺度为H×W, 则特征图尺度为λH×λW, λ≤1为缩放系数, 单元在作战场景中的真实坐标可以映射为特征图的像素坐标。

3.3 动作表达

与状态表达类似, 动作表达是编码作战单元的移动动作、攻击动作。本文采用PGS^[16]、POE^[17]、SSS+^[18]为基准搜索方法, 因此使用这3种算法的Script作为单位动作, 分别为NOK-AV、Kiter、BackFar、BackClose、Forward、ForwardFar及Cluster共计7种。通常, Script动作可分为攻击前移动、攻击时目标选择和攻击间隙移动3个阶段, 前6种Script动作在攻击前朝最近的敌方单元移动, 攻击时优先选择dpf/hp最高的敌方单元, 但它们在攻击间隙的移动动作有所不同^[16-17], 如NOK-AV在攻击间隙原地等待、Kiter在攻击间隙朝远离最近敌方单元的方向移动等。Cluster仅涉及移动动作, 表示朝友方单元的中心移动^[18]。与特征编码一致, 动作编码采用one-hot编码方式生成7通道的0/1动作图, 其动作图尺度为λH×λW, 单元在作战场景中的真实坐标可以映射为动作图中的像素坐标。

3.4 基于卷积神经网络的联合策略模型

策略模型的目标是在给定56通道特征图下, 计算己方所有单元的动作概率分布, 本节将描述具体的网络结构、损失函数。

3.4.1 网络结构

考虑到编码-解码卷积架构在图像分割^[27]领域的成功, 本文提出面向RTS游戏微操的联合策略网络。JPN的结构设计参考SegNet, 如图 3所示, 主要不同点是移除了大量卷积层, 以保证前向运算的速度。具体地, JPN的编码部分包含5层卷积层、4层最大池化层, 解码部分包含5层卷积层、4层上采样层, 最后一层接Softmax层。其中, 10层卷积层的卷积核大小都为3×3, 第1层、第10层卷积层的卷积核数量为64, 第2层、第9层卷积层的卷积核数量为128, 第3层、第8层卷积层的卷积核数量为256, 其余卷积层的卷积核数量都为512;4层最大池化层与4层上采样层一一对应, 采样步长都为2, 两部分分别实现输入特征图的16倍尺度缩小、放大, 使得输入、输出的尺度均为λH×λW。

3.4.2 损失函数

采用交叉熵损失函数作为JPN的目标函数, 考虑到不同类别动作之间的不均衡性, 构建一种加权交叉熵损失函数:

$ L(\theta ) = \sum\limits_{k = 0}^{K{\rm{ - }}1} {\sum\limits_{h = 0}^{\lambda H{\rm{ - }}1} {\sum\limits_{w = 0}^{\lambda W{\rm{ - }}1} {{\omega _k}} } } {y_{{\rm{khw}}}}{\rm{lo}}{{\rm{g}}_a}P\left( {{{\widehat y}_{{\rm{khw}}}}} \right) $

(2)

$ {\omega _k} = \left\{ \begin{array}{l} \frac{{\sum\limits_{i = 0, i \ne k}^{K - 2} {\left| {{N_i}} \right|} }}{{\sum\limits_{i = 0}^{K - 2} {\left| {{N_i}} \right|} }}, 0 \le k \le 6\\ 0, k = 7 \end{array} \right. $

(3)

其中, K表示类别数, |N_i|表示训练集中类别i的数, y_khw、$P\left({{{\widehat y}_{khw}}} \right)$分别表示坐标(h, w)处类别k的预测概率和one-hot编码标签。JPN负责己方单元的动作预测, 对应0≤k≤6;将敌方单元归类至背景, 忽略背景像素对损失函数计算的影响, 对应k=7。

3.5 改进搜索方法

本节将JPN与3种典型的搜索方法(PGS^[16]、POE^[17]、SSS+^[18])相结合, 提出3种改进方法, 即PGS w/JPN、POE w/JPN、SSS+ w/JPN。3种改进方法的思路类似。具体地, 由JPN输出己方单元在7种Script动作上的概率分布; 将最大概率Script动作设定为初始解; 由先验概率分布指导初始解的优化过程, 若采用状态精炼来合并相似状态的作战单元, 则面向群体展开搜索过程, 群体内单元共享相同的Script动作, 否则面向个体展开搜索过程, 直至决策时间消耗殆尽; 输出有限时间内搜索到的局部最优解。

3.5.1 PGS w/JPN方法

PGS w/JPN的算法流程如算法1所示, 主要分为设定初始解(第2行、第3行)、产生可能动作子集(第4行)、迭代优化(第5行~第12行)3个部分。

算法1  PGS w/JPN方法

输入 游戏状态s, 己方单元集合U_i={u₁, u₂, …, u_m}, 对方单元集合U_－j={u_－1, u_－2, …, u_－n}, 对方默认Script动作$\overline {{\sigma _d}} $, 动态评估方法ζ, 状态表达方法φ, 策略模型π, 模型参数θ, 可能动作集合大小M₁, 决策时间限制t

输出 己方单元联合动作A_i={α₁, α₂, …, α_m}

1.计算先验概率分布ρ_π(s, U_i)=π(φ(s, U_i); θ)

2.设定己方初始解{σ₁, σ₂, …, σ_m}←Max(ρ_π(s, U_i))

3.设定对方初始解{σ_－1, σ_－2, …, σ_－n}←$\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}} \} $

4.生成己方单元的可能动作子集${\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^1}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^2}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{{{\rm{M}}_{\rm{1}}}}} \} _{{\rm{i}} = 1, 2, \ldots, {\rm{m}}}}$←ρ_π(s, U_i)

5.While消耗时间小于t do

6.for i=1→m do

7.for j=1→M₁ do

8.己方当前解Σ={σ₁, σ₂, …, σ_m}

9.对方当前解Σ_－1={σ_－1, σ_－2, …, σ_－n}

10.己方测试解Σ^′={σ₁, σ₂, …, $\overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{\rm{j}}} $, …, σ_m}

11.if ζ(S, Σ, Σ_－1) < ζ(S, Σ^′, Σ_－1) then

12.σ_i=$\overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{\rm{j}}} $

13.计算并返回己方单元联合动作A_i←{σ₁, σ₂, …, σ_m}

将最大概率Script动作设定为己方初始解(第2行), 将默认Script动作设定为对方初始解(第3行), 而原始的PGS采用迭代方式确定双方初始解。由先验概率分布产生可能动作子集(第4行), 在给定先验概率分布下, 采取排序方式, 按从大到小的原则确定不同Script动作对于各个单元的优先级, 若可能动作子集大小设定为M₁, 则按优先级从大到小选取前M₁个Script动作构成各个单元的可能动作子集。在给定可能动作子集下, 逐个优化己方单元的当前解(第10行), 类似PGS, 采用动态评估方法ζ来评价解的好坏, 先由当前解模拟状态转移, 再由静态评估函数评估终局局势, 选取评分最高的Script动作(第11行、第12行)。待决策时间消耗殆尽, 将局部最优解转换为具体的动作指令(第13行)。

3.5.2 POE w/JPN方法

POE w/JPN的算法流程如算法2所示, 类似演化算法, 主要分为初始化基因组(第2行~第5行)、产生可能动作子集(第6行、第7行)、突变(第9行~第12行)、交叉(第13行)和选择(第14行)5个部分。这里的改进主要集中在前3个部分, 后两部分与POE完全一致, 交叉对所有基因进行随机两两交换, 选择筛选优良基因。

算法2  POE w/JPN方法

输入 游戏状态s, 己方单元集合U_i={u₁, u₂, …, u_m}, 对方单元集合U_－j={u_－1, u_－2, …, u_－n}, 对方默认Script动作$\overline {{\sigma _d}} $, 动态评估方法ζ, 状态表达方法φ, 策略模型π, 模型参数θ, 可能动作集合大小M₂, 决策时间限制t, 基因数目size, 预先设定步长step, 变异率ε, 基因子代数目offsprings, 保留基因数目select

输出 己方单元联合动作A_i={α₁, α₂, …, α_m}

1.计算先验概率分布ρ_π(s, U_i)=π(φ(s, U_i); θ)

2.for i=1→size do

3.for j=1→step do

4.设定己方初始基因Σ_ij←Max(ρ_π(s, U_i))

5.设定对方初始基因Σ_－ij←$\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}} \} $

6.生成己方单元的可能动作子集${\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^1}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^2}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{{{\rm{M}}_2}}} \} _{{\rm{i}} = 1, 2, \ldots, {\rm{m}}}}$←ρ_π(s, U_i)

7.计算归一化概率分布ρ′_π(s, U_i)←ρ_π(s, U_i)

8.While消耗时间小于t do

9.for i=1→size do//执行突变步骤

10.for j=1→step do

11.ε′←ε*ρ′_π(s, U_i)

12.Σ_ij←Random(Σ_ij, offsprings, ε′)

13.执行交叉步骤Σ←Cross(Σ, select)

14.执行选择步骤Σ←Select(Σ, select, ψ)

15.计算并返回己方单元联合动作A_i←Σ₁₁

在初始化基因组阶段, 由最大概率Script动作设定为己方初始基因(第4行), 将默认Script动作设定为对方初始基因(第5行), 而原始的POE完全采取默认初始解, 其中基因对应己方单位或对方单位的Script动作组合。在产生可能动作子集阶段, 类似PGS w/JPN, 若可能动作子集大小设定为M₂, 按照优先级排序方式选取前M₂个Script动作构成各个单元的可能动作子集(第6行), 并计算这M₂个Script动作的归一化概率分布, 其他Script动作的概率取0(第7行)。在突变阶段, 在可能动作子集内执行基因变异操作, 朝向各个Script动作的变异率由默认变异率和归一化概率分布共同决定(第11行), 这意味着同一个基因朝不同动作的变异率可能不同。

3.5.3 SSS+ w/JPN方法

SSS+ w/JPN的算法流程如算法3所示, 主要分为设定初始解(第2行、第3行)、划分群体(第4行)、产生可能动作子集(第5行)和迭代优化(第6行~第13行)4个部分。

算法3  SSS+ w/JPN方法

输入 游戏状态s, 己方单元集合U_i={u₁, u₂, …, u_m}, 对方单元集合U_－j={u_－1, u_－2, …, u_－n}, 对方默认Script动作$\overline {{\sigma _d}} $, 动态评估方法ζ, 状态表达方法φ, 策略模型π, 模型参数θ, 可能动作集合大小M₃, 决策时间限制t, 自适应类型系统types

输出 己方单元联合动作A_i={α₁, α₂, …, α_m}

1.计算先验概率分布ρ_π(s, U_i)=π(φ(s, U_i); θ)

2.设定己方初始解{σ₁, σ₂, …, σ_m}←Max(ρ_π(s, U_i))

3.设定对方初始解{σ_－1, σ_－2, …, σ_－n}←$\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{d}}}} \} $

4.己方单元划分群体{g₁, g₂, …, g_k}←types(U_i)

5.生成己方单元的可能动作子集${\{ \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^1}, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^2}, \ldots, \overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{{{\rm{M}}_3}}} \} _{{\rm{i}} = 1, 2, \ldots, {\rm{k}}}}$←ρ_π(s, U_i)

6.While消耗时间小于t do

7.for i=1→k do

8.for j=1→M₃ do

9.己方当前解Σ={σ₁, σ₂, …, σ_m}

10.对方当前解Σ_－1={σ_－1, σ_－2, …, σ_－n}

11.己方测试解Σ′={σ₁, σ₂, …, $\overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{\rm{j}}} $, …, σ_m}

12.if ζ(S, Σ, Σ_－1) < ζ(S, Σ′, Σ_－1) then

13.{σ₁, σ₂, …, σ_m}={σ₁, …, $\overline {{{\rm{ \mathsf{ σ} }}_{\rm{i}}}^{\rm{j}}} $, …, σ_m}

14.计算并返回己方单元联合动作A_i←{σ₁, σ₂, …, σ_m}

首先将最大概率Script动作设定为己方初始解(第2行), 将默认Script动作设定为对方初始解(第3行), 而原始的SSS+完全采取默认初始解。然后由当前类型系统归并相似状态的单元, 所采用的自适应类型系统types与SSS+一致, 包含5种类型系统, 分别是{T_{(c, 3)}, T_{(c, 2)}, T_{(c, 1)}, T_{(c, 0)}, T_RGD}, 前4种类型系统计算公式如下:

$ {T_{c, l}}\left( u \right) = \left( {r\left( u \right), d\left( u \right), \frac{{{\rm{hp}}(u)}}{{\left\lfloor {\frac{{{\rm{h}}{{\rm{p}}_m}\left( u \right)}}{l}} \right\rfloor }}} \right) $

(4)

其中, r(u)与d(u)分别表示单位u的攻击距离和伤害, hp(u)与hp_m(u)分别表示单位u的当前生命与最大生命, 若两单位的T_{c, l}(u)三要素完全一致, 则划分至一类, 否则划分至各自类别; 而T_RGD将单元分为近战单元、远战单元两类。另外, 自适应类型系统types依据运行情况自动调整所使用的类型系统, 若给定时间内可以遍历所有可能解, 则增大所使用类型系统的精细程度, 如T_{c, 2}(u)调整至T_{c, 3}(u); 否则, 降低所使用类型系统的精细程度, 如T_{c, 3}(u)调整至T_{c, 2}(u)。接着由先验概率分布产生可能动作子集(第5行), 采取排序、投票相结合的方式, 先排序确定不同动作对于各个单元的优先级, 再在各个群体内执行投票, 统计不同动作对于各个群体的优先级, 若可能动作子集大小设定为M₃, 则按优先级从大到小选取前M₃个Script动作构成各个群体的可能动作子集, 群体内单元共享相同的可能动作子集。最后在给定可能动作子集下, 逐个优化己方群体的当前解(第11行), 类似PGS w/JPN, 采用动态评估方法ζ来评价解的好坏, 选取评分最高的Script动作(第12行、第13行)。待决策时间消耗殆尽, 将局部最优解转换为具体的动作指令(第14行)。

4 实验评估

为评估JPN和改进方法(PGS w/JPN、POE w/JPN、SSS+ w/JPN)的性能, 本节一方面在SparCraft上展开原始方法(PGS^[16]、POE^[17]、SSS+^[18])和改进方法的对比实验, 测试改进方法的性能提升, 另一方面在StarCraft:BroodWar上展开内置AI和改进方法的对比实验, 测试改进方法的AI真实水平。两个实验平台的作战场景类似, 单元类型、单元属性也基本一致。其中, SparCraft显性建模了RTS游戏微操涉及的状态转移, 为搜索方法提供了极大的便捷; StarCraft:BroodWar提供了更加真实的作战场景, 更有利于鉴定改进方法的AI水准。考虑到目前尚无可用于训练JPN的数据集, 首先构建覆盖基准场景的学习用数据集; 然后将训练完成的模型接入改进方法, 在2个实验平台上分别开展验证实验。

4.1 场景设置

借鉴PGS^[16]、POE^[17]、SSS+^[18]的场景设置, 选取4种采取物理攻击的作战单元, 分别是Zergling(L)、Zealot(Z)、Dragoon(D)和Marine(M), 在多种作战基准场景中开展验证实验, 统计1 000场战斗中改进方法对抗原始方法或内置AI的胜率。具体地, 为评估改进方法的性能提升, 选取了5类基准场景, 各方控制单元的数量n选取自4, 8, 16, 32, 50, 分别为nD vs.nD、nL vs.nL、n/2Dn/2Z vs.n/2Dn/2Z、n/2Dn/2M vs.n/2Dn/2M、n/2Mn/2L vs.n/2Mn/2L, 共计25种基准场景。为评估改进方法的AI真实水平, 选取了BiCNet^[22]中的2种大尺度场景:即10 M vs.13 L、20M vs.30L, 并设计了8种变种场景:分别为6M vs.7L、8M vs.10L、12M vs.16L、14M vs.20L、16M vs.24L、18M vs.27L、22M vs.33L、24M vs.36L。由此, 共采用了35种作战基准场景。

4.2 基准算法设置

采用PGS^[16]、POE^[17]、SSS+^[18]作为基准搜索方法, 采用GMEZO^[21]、CommNet^[25]、BiCNet^[22]以及PS-MAGDS^[26]作为基准多智能体强化学习方法。为评估改进方法的性能提升, 实验对比了原始方法(PGS^[16]、POE^[17]、SSS+^[18])、改进方法(PGS w/JPN、POE w/JPN、SSS+ w/JPN), 以及结合随机先验概率分布的搜索方法(PGS w/RND、POE w/RND、SSS+ w/RND)。出于公平性, 借鉴SSS+^[18]中可能动作集合的大小, 三类搜索方法可能动作集合的大小均设置为3, 原始搜索方法默认为NOK-AV、Kiter、Cluster, 其他搜索方法依据各自的先验概率分布, 从7种Script动作中构建各自的可能动作集合。除此以外, 所有搜索方法的参数一致, 如决策时间限制为40 ms。

4.3 数据集构建

SSS+是所有开源搜索方法中的最佳方法, 因此将其分别接入SparCraft和StarCraft:BroodWar, 生成所设定基准场景的数据集。对于前25种基准场景, 为增强样本的质量和多样性, 采取了4点特殊设置:1)将SSS+的可能动作集合设定为7种Script动作; 2)将决策时间限制由40 ms延长至200 ms; 3)各方控制单元的数量n分别随机选取自1, 4、5, 8、9, 16、17, 32、33, 50, 每个基准场景进行100 000场战斗, 共进行了2 500 000场战斗; 4)合并相同规模场景中产生的数据集, 生成用于4v4、8v8、16v16、32v32、50v50五类场景的数据集。对于场景10 M vs.13 L、20M vs.30L, 鉴于StarCraft:BroodWar产生样本的速度远远低于SparCraft, 这里仅将可能动作集合设定为7种Script动作, 未采用其他3点特殊设置, 共进行了200 000场战斗。在上述设定下, 按50帧时间间隔来随机记录中间状态, 经状态表达、动作表达、数据打乱, 进一步地按4:1划分训练集、测试集, 生成的7组数据集分别称为I_4v4、I_8v8、I_16v16、I_32v32、I_50v50、I_10Mv13L、I_20Mv30L, 具体如表 2所示。

4.4 结果分析

首先在7个数据集上训练并测试JPN, 然后将训练完成的学习模型接入各个搜索方法, 分别在2个实验平台上展开性能评估实验。

4.4.1 策略模型的预测性能评估

训练完成的JPN在7个测试集上的Top-1预测准确率如图 4所示, 此处类别总数为8(7类Script动作和1类背景)。由图 4可知, 前5个测试集上的最大准确率、最小准确率、平均准确率约为73.10%、69.66%、73.10%, 后2个测试集上的最大准确率、最小准确率、平均准确率约为57.30%、56.80%、57.05%。可见, JPN可以适应复杂的作战场景, 甚至是单元数量达到100的大规模作战场景。JPN在前5个测试集上的表现优于其在2个测试集上的表现, 这主要是由于前5组数据集在构建过程中所采用的特殊设置。

4.4.2 原始搜索方法与改进搜索方法的对比分析

改进方法(PGS w/JPN、POE w/JPN、SSS+w/JPN)、结合随机先验概率分布的搜索方法(PGS w/RND、POE w/RND、SSS+ w/RND)对抗原始方法(PGS、POE、SSS+)的实验结果如表 3所示, 其中, 第1列指定了场景设置, 第1行指定了测试的搜索方法。例如在场景4D4Z vs.4D4Z中, PGS w/RND vs.PGS的胜率是47%, PGS w/JPN vs.PGS的胜率是79%, 对应地, 两种搜索方法的增益分别是-3%和+29%。

由表 3可得出以下实验结论:1)在绝大多数场景中, 相比于改进方法, 结合随机先验概率分布的搜索方法取得较低的胜率, 这表示合适的先验概率分布对于引导搜索方法至关重要; 2)SSS+ w/RND总是存在增益, POE w/RND在一半场景中有增益, 而PGS w/RND在所有场景中无增益, 这表示随机先验概率分布带来的多样性对于PGS、POE、SSS+影响程度不等, SSS+受益最大; 3)在绝大多数场景中, 改进搜索方法对抗原始搜索方法的胜率大于50%, 其增益也总是大于结合随机先验概率分布的搜索方法, 这证实了JPN可以有效提升搜索方法; 4)PGS w/JPN、POE w/JPN的增益往往大于SSS+ w/JPN的增益, 相比于SSS+, JPN更有利于提升PGS、POE, 这主要由于采用了SSS+产生的训练集, SSS+的性能优于PGS、POE, 导致训练产生的学习模型更有利于提升PGS、POE。

4.4.3 内置AI与改进搜索方法的对比分析

改进方法(PGS w/JPN、POE w/JPN、SSS+w/JPN)对抗内置AI的实验结果如表 4和表 5所示, 其中, 表 4在2种基准场景中对比了改进方法、基准多智能体强化学习方法, 表 5在8种变种场景中评估了改进方法的泛化能力。例如在表 4场景10M vs.13L中, PGS w/JPN vs.内置AI的胜率和增益分别是95%和+8%。

由表 4和表 5可得出以下实验结论:1)在2种基准场景中, 改进方法可以击败内置AI, PGS w/JPN取得胜率接近最好的基准方法, 分别是95%、99%, 这证实了改进搜索方法对抗内置AI的优势, 同时, 改进方法的增益总大于0, 这再次表明了JPN可以有效提升搜索方法; 2)在8个变种场景中, 改进方法同样可以击败内置AI, 且增益同样大于0%, 这表明训练好的学习模型可以泛化至类似场景; 3)在绝大多数场景中, PGS w/JPN的表现好于POE w/JPN、SSS+ w/JPN, 但实际上PGS弱于POE、SSS+, 表明学习与搜索的结合机制对性能是至关重要的。

5 结束语

本文提出一种基于卷积神经网络的联合策略网络方法。该方法将所有智能体作为群体, 以实现多智能体联合动作的端到端学习。改进搜索方法由JPN输出的先验概率分布保证初始解, 以尽可能地搜索大概率存在最优解的动作空间。实验结果表明, JPN可以有效提升搜索方法。本文主要通过学习模型提升搜索方法, 后续将研究学习模型与搜索方法相结合的机制以进一步提升学习模型的性能。