基于属性的计算机兵棋规则模型研究

贺德富，涂 睿，苏喜生

(1.湖北第二师范学院， 武汉 430205； 2.海军工程大学， 武汉 430032；3.陆军勤务学院, 重庆 400000)

兵棋推演是军事指挥人员在作战前评估战略战术可行性、人员和装备损害程度的重要手段[1-2]。世界各军事强国普遍采用兵棋推演来进行军事行动的决策分析以及指挥训练工作[3-4]。例如，在美军作战部队中普遍使用的战场手册(field manual 5-0)规定的军事决策制定过程模型(military decision making process，MDMP)中，共包括7个阶段，其中兵棋推演是最重要、最耗时的阶段[5]。

计算机兵棋系统的研制是一个系统工程，主要包括模型构建、软件设计和实现等[10]。模型构建主要涉及兵棋规则的设计、验证和形式化，是软件开发的基础，也是最为核心的内容[11]。本文提出了基于属性的计算机兵棋规则模型：ABCWR(attribute based computer wargaming rule)，为计算机兵棋规则库的设计提供一套通用的形式化描述和规则判定方法。ABCWR模型主要由规则、规则访问请求、规则判定方法3部分构成。模型以算子实体的属性为基础定义规则，并进行规则判定，以简化规则库软件实现和管理的难度，增加规则判定的灵活性。

1 ABCWR模型定义

1.1 规则组成

ABCWR模型基于规则关联的主、客体等属性进行规则判定，属性指与实体相关的一些特征。一条规则由主体、客体、条件、行动、结果5部分构成[12]。

1) 主体对应的实体主要是兵棋算子，其属性包括：归属、算子类型、攻击力、防御力、维持力、机动力、当前状态(交战、撤退、机动等)、当前位置坐标等。

2) 客体可以认为是一种资源，包括算子、地图坐标等，其属性包括：归属、算子类型、攻击力、防御力、维持力、机动力、当前状态(交战、撤退、机动等)、当前位置坐标、六角格坐标、地形(山地、平原、河流等)、占据者等。

3) 环境属性是规则判定涉及的战场环境属性，例如回合数、天气、昼夜变化等。

4) 行动属性是主体对客体进行的行动相关的属性，例如：攻击、补给、支援、进入、离开、堆叠等。

5) 结果属性是规则执行的结果，例如:允许、禁止、修改主客体属性值(攻击力、当前状态、当前位置等)、导致连锁反应(自动转入防御等)被启动等。

例如，对于兵棋规则“前两回合，算子机动路径不可延伸至敌军所在格”，主体是机动算子，其归属属性是本方归属标识；客体是地图六角格，其占据者属性为敌方归属标识；环境属性是回合数为1或2；行动属性是进入；结果属性是禁止。

兵棋规则与计算机网络访问控制规则类似，但网络访问控制规则的客体基本是固定的，而在兵棋规则中客体则是多变的，甚至主客体会经常换位[13]。此外，兵棋规则的判定结果更为复杂，除了允许/禁止外，还包括对主客体属性的修改，例如修改攻击力值、当前状态等。

兵棋用户对算子的每一步操作首先转换为规则访问请求消息。规则模型会将规则请求中的属性与包含在兵棋规则中的属性进行匹配，从而生成规则执行结果，并导致某些连锁反应被启动。规则集的访问请求包括查询请求(request message)和查询响应(response message)2种消息格式。查询请求消息包含了主体、客体、行动、环境的属性赋值关系,查询响应消息包含了返回结果的属性赋值。

1.2 模型形式化定义

ABCWR规则的描述语言包括5个元素：subject(主体)、object(客体)、environment(环境)、action(行动)、result(结果)。形式化为五元组Rule(s,o,e,a,r)。

模型为S,O,E,A定义了若干预定义属性集(Pre-Attribute)，分别表示为:SPAk(1≤k≤K)，OPAk(1≤k≤K),EPAk(1≤k≤K)，APAk(1≤k≤K)。例如，S定义了2个预定义集合SPA1、SPA2，其中，SPA1表示算子类型、SPA2表示当前状态，则有SPA1={步兵,装甲部队,空军}，SPA2={交战,撤退,机动,驻扎}。用Result表示规则的判定结果，例如Result={允许,禁止,攻击力-1,撤退}。

模型使用四元组Request(s,o,e,a)表示一条规则查询请求。使用ATTR(s)、ATTR(o)、ATTR(e)、ATTR(a)分别表示主体、客体、环境和行动的属性赋值关系，均为各自预定义属性的笛卡尔集子集，其取值与特定的s,o,e,a相关。

ATTR(s)⊆SPA1×SPA2×…SPAk

ATTR(o)⊆OPA1×OPA2×…OPAk

ATTR(e)⊆EPA1×EPA2×…EPAk

ATTR(a)⊆APA1×APA2×…APAk

(1)

兵棋规则本质上是从实体属性集到规则判定结果集的映射，其函数定义如下：

Rule(ATTR(s),ATTR(o),ATTR(e),

ATTR(a))→Result

(2)

在一个特定的兵棋系统中，实体的预定义属性集是固定的。对于一个规则查询请求：

Request(ATTR(s),ATTR(o),

ATTR(e),ATTR(a))

(3)

规则判定函数通过比较某条规则和规则查询请求中实体属性的包含关系，将其映射到判定结果集，其函数映射定义如下：

(4)

其中：RuleAttr表示规则中的实体属性集；ReqAttr为查询请求中的实体属性集；Unsatisfy表示该规则无法匹配。Rule∈RuleSet，RuleSet表示基于每个请求所包含客体的属性搜索得到的关联规则集。兵棋系统中，每个客体实体(算子、六角格)都可能绑定若干条规则。

为了提高规则匹配的效率，模型首先对规则库的所有规则进行预处理，即首先对请求中主体、客体，或行动属性所关联的规则集进行搜索和匹配。用函数(5)表示对于具有特定属性查找的绑定规则或无规则。

RuleBinAttrbute(ATTR(s)|ATTR(o)|ATTR(a))→Rule∪φ

(5)

2 基于XML描述的ABCWR规则集

兵棋规则的描述应具有可读性和可维护性。兵棋规则设计者或用户一方面可以方便地识读、修改规则文档；另一方面描述文档自身可以有效地管理、存储、传输和转换，并能将规则数据动态地展现出来。XML语言具有自描述性、可扩展性、跨平台性以及严格的语法和逻辑，提供了较高效的数据管理能力。因此，XML比数据库更适合兵棋规则库的实现。

在ABCWR规则库的实现中，借鉴了网络访问控制的思想，使用XACML策略描述语言来定义兵棋规则。XACML(eXtensible access control markup language)[14-15]是一种用于保护资源的基于XML的通用访问策略描述语言。该语言基于实体的属性进行决策，适合于描述ABCWR模型。此外，XACML还提供策略管理的工具，简化了兵棋规则库的工程实现。例如，对于规则“夜晚装甲部队机动路径不可延伸至沼泽区”，其XACML语言描述如图1所示。

图1 规则的XACML语言描述

3 ABCWR规则判定机制

ABCWR模型的模块组成如图2所示，模型主要包括4部分：规则决策点( rule decision point，RDP)、规则执行点(rule execute point，REP)、规则信息点(rule information point，RIP)、规则管理点(rule management point，RMP)。

在工程实现中，首先依据兵棋剧本和规则说明书生成预定义属性集，再将兵棋规则转换为函数(2)的映射关系(规则)，并将规则体以XML的形式存储于RMP的规则库。RMP规则库中的规则XML文件能够以Web页面的形式展现给用户，从而方便用户查看和修改规则。

图2 ABCWR模型模块组成

针对算子的每次行动，REP依据函数(3)将兵棋用户的操作转化为原始查询请求消息(包含主体、客体、行动属性)，并发送给RDP。RDP将查询结果以查询响应消息的形式回传给REP。请求和响应消息采用XML的形式进行描述，定义了RDP和REP之间的接口。RIP为RDP提供匹配规则过程中需要的环境属性信息。上下文处理器(context handler)负责各模块之间的消息传递。

RDP 模块负责对规则查询请求进行规则判定。RDP基于查询请求中的主体、客体或行动属性从RAP 中获取关联规则集，然后根据查询请求中的主体、客体或行动属性以及RIP中的环境属性，对关联规则集中的所有规则进行目标匹配，最后对这些结果进行合并得到最终结果。RDP 对应ABCWR模型中的RuleDecision 函数。

RMP 模块完成规则预处理功能，为RDP 提供特定属性的关联规则集。RMP根据RDP提交的特定属性，从规则库中查找特定属性所关联的规则集，并将关联规则集返回给RDP用于规则判定。RDP提交给RMP的特定属性类型可以是主体属性、客体属性或行动属性。RMP 对应ABCWR模型中的RuleBindAttribute函数。

4 ABCWR规则判定性能测试

判定1条规则需要匹配主体、客体、环境、行动4类属性。对于一个判定请求，若4个属性均相同，则该规则为真，否则为假。判定1条规则为真，需要运行4次；判定1条规则为假，至少需要运行1次；假定4类属性为假的概率相同，则需要平均运行2次。因此，每条规则的平均匹配次数为3次，假定规则库中有n条规则，共需要匹配3×n次，时间复杂度为O(n)。理论上，规则判定时间与规则库中的规则条数呈正比关系。

选择不同规模的规则库为标准对ABCWR模型的规则判定性能进行测试。其中，规则数目为5、10的规则库是设计的基准规则库，用于获得基准运行时间。将3款经典商业兵棋规则转换为规则库，分别对应大型、中型和小型兵棋规则库：《战争艺术Ⅲ》(647条规则)、《诺曼底1944》(353条规则)、《轴心国入侵萨拉热窝》(36条规则)[16-17]。

此外，为每个规则库设计与规则对应的查询请求，在每次测试中对所有的查询请求运行一遍。ABCWR模型基于Visual Studio2010实现，在测试过程中使用GetTickCount对规则匹配进程的运行时间进行计算。测试环境： Intel Core 2 P8700 2.53 GHz CPU，2 GB内存，Windows XP SP2操作系统。测试结果如表1所示。

表1 规则判定性能测试

表1中的实际运行时间为测试过程中运行时间。理论运行时间为运行时间与规则条数呈正比条件下的规则判定遍历理论运行值。为此，以10条规则的规则库的实际运行时间(1 ms)为基准值，计算出剩余3个商业兵棋规则库的规则判定遍历理论时间。如表1所示，后3个兵棋规则库的实际判定遍历时间与理论值十分接近。因此，ABCWR模型的规则判定时间与规则条数近似呈正比关系。

通过上述分析可以看出：为了提高ABCWR模型的规则判定性能，可以考虑减少判定规则为假的匹配次数。之前假定了4类属性为假的概率相同，但对于实际的兵棋规则库，基于不同的属性判定规则为假的概率是不同的。以商业手工兵棋《诺曼底1944》为例，转换了353条规则，分别依据行动属性和主体算子类型属性统计了不同属性的规则分布。

如图3、4所示，与依据主体算子类型的规则划分相比，依据行动属性的规则划分更为细致，兵棋规则的分布更为均衡。因此，如果首先根据行动属性对规则库进行匹配，则大部分“假”规则将在第1次匹配中被发现，从而整体上减少“假”规则的匹配次数，提高规则判定的效率。正是基于这个考虑，ABCWR模型的规则预处理按照函数(5)从规则库中提取了关联规则集。

图3 依据行动属性的规则分布

图4 依据主体算子类型属性的规则分布

分别对首先匹配主体算子类型属性规则和首先匹配行动属性规则2种情况的规则请求匹配时间进行测试。如表2所示，对于《诺曼底1944》的353条规则，首先匹配行动属性比首先匹配主体算子类型属性的匹配时间减少了20.58%。可见兵棋规则库中的规则依据属性的分布存在差异，需要对规则分布进行统计分析，从而比较得出最佳预处理属性类型。

表2 规则分布对匹配效率的影响

5 结束语

兵棋的本质是对作战指挥人员决策过程的推演，检验的是双方指挥人员的决策过程[18]。在兵棋推演过程中，推演双方必须熟练掌握兵棋的规则。如果规则库规模太大，虽然对战场的模拟更为逼真，但对推演者掌握兵棋规则带来巨大的困难。因此，实用的兵棋系统规则库规模不会太大。ABCWR模型的规则判定时间与规则数目呈正比关系，在现有商业兵棋规则库规模下具有实用性。