基于屬性的計算機兵棋規則模型研究

賀德富，涂 睿，蘇喜生

(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模型的規則判定時間與規則數目呈正比關系，在現有商業兵棋規則庫規模下具有實用性。