基于屬性的計算機(jī)兵棋規(guī)則模型研究

賀德富，涂 睿，蘇喜生

(1.湖北第二師范學(xué)院， 武漢 430205； 2.海軍工程大學(xué)， 武漢 430032；3.陸軍勤務(wù)學(xué)院, 重慶 400000)

兵棋推演是軍事指揮人員在作戰(zhàn)前評估戰(zhàn)略戰(zhàn)術(shù)可行性、人員和裝備損害程度的重要手段[1-2]。世界各軍事強(qiáng)國普遍采用兵棋推演來進(jìn)行軍事行動的決策分析以及指揮訓(xùn)練工作[3-4]。例如，在美軍作戰(zhàn)部隊(duì)中普遍使用的戰(zhàn)場手冊(field manual 5-0)規(guī)定的軍事決策制定過程模型(military decision making process，MDMP)中，共包括7個階段，其中兵棋推演是最重要、最耗時的階段[5]。

計算機(jī)兵棋系統(tǒng)的研制是一個系統(tǒng)工程，主要包括模型構(gòu)建、軟件設(shè)計和實(shí)現(xiàn)等[10]。模型構(gòu)建主要涉及兵棋規(guī)則的設(shè)計、驗(yàn)證和形式化，是軟件開發(fā)的基礎(chǔ)，也是最為核心的內(nèi)容[11]。本文提出了基于屬性的計算機(jī)兵棋規(guī)則模型：ABCWR(attribute based computer wargaming rule)，為計算機(jī)兵棋規(guī)則庫的設(shè)計提供一套通用的形式化描述和規(guī)則判定方法。ABCWR模型主要由規(guī)則、規(guī)則訪問請求、規(guī)則判定方法3部分構(gòu)成。模型以算子實(shí)體的屬性為基礎(chǔ)定義規(guī)則，并進(jìn)行規(guī)則判定，以簡化規(guī)則庫軟件實(shí)現(xiàn)和管理的難度，增加規(guī)則判定的靈活性。

1 ABCWR模型定義

1.1 規(guī)則組成

ABCWR模型基于規(guī)則關(guān)聯(lián)的主、客體等屬性進(jìn)行規(guī)則判定，屬性指與實(shí)體相關(guān)的一些特征。一條規(guī)則由主體、客體、條件、行動、結(jié)果5部分構(gòu)成[12]。

1) 主體對應(yīng)的實(shí)體主要是兵棋算子，其屬性包括：歸屬、算子類型、攻擊力、防御力、維持力、機(jī)動力、當(dāng)前狀態(tài)(交戰(zhàn)、撤退、機(jī)動等)、當(dāng)前位置坐標(biāo)等。

2) 客體可以認(rèn)為是一種資源，包括算子、地圖坐標(biāo)等，其屬性包括：歸屬、算子類型、攻擊力、防御力、維持力、機(jī)動力、當(dāng)前狀態(tài)(交戰(zhàn)、撤退、機(jī)動等)、當(dāng)前位置坐標(biāo)、六角格坐標(biāo)、地形(山地、平原、河流等)、占據(jù)者等。

3) 環(huán)境屬性是規(guī)則判定涉及的戰(zhàn)場環(huán)境屬性，例如回合數(shù)、天氣、晝夜變化等。

4) 行動屬性是主體對客體進(jìn)行的行動相關(guān)的屬性，例如：攻擊、補(bǔ)給、支援、進(jìn)入、離開、堆疊等。

5) 結(jié)果屬性是規(guī)則執(zhí)行的結(jié)果，例如:允許、禁止、修改主客體屬性值(攻擊力、當(dāng)前狀態(tài)、當(dāng)前位置等)、導(dǎo)致連鎖反應(yīng)(自動轉(zhuǎn)入防御等)被啟動等。

例如，對于兵棋規(guī)則“前兩回合，算子機(jī)動路徑不可延伸至敵軍所在格”，主體是機(jī)動算子，其歸屬屬性是本方歸屬標(biāo)識；客體是地圖六角格，其占據(jù)者屬性為敵方歸屬標(biāo)識；環(huán)境屬性是回合數(shù)為1或2；行動屬性是進(jìn)入；結(jié)果屬性是禁止。

兵棋規(guī)則與計算機(jī)網(wǎng)絡(luò)訪問控制規(guī)則類似，但網(wǎng)絡(luò)訪問控制規(guī)則的客體基本是固定的，而在兵棋規(guī)則中客體則是多變的，甚至主客體會經(jīng)常換位[13]。此外，兵棋規(guī)則的判定結(jié)果更為復(fù)雜，除了允許/禁止外，還包括對主客體屬性的修改，例如修改攻擊力值、當(dāng)前狀態(tài)等。

兵棋用戶對算子的每一步操作首先轉(zhuǎn)換為規(guī)則訪問請求消息。規(guī)則模型會將規(guī)則請求中的屬性與包含在兵棋規(guī)則中的屬性進(jìn)行匹配，從而生成規(guī)則執(zhí)行結(jié)果，并導(dǎo)致某些連鎖反應(yīng)被啟動。規(guī)則集的訪問請求包括查詢請求(request message)和查詢響應(yīng)(response message)2種消息格式。查詢請求消息包含了主體、客體、行動、環(huán)境的屬性賦值關(guān)系,查詢響應(yīng)消息包含了返回結(jié)果的屬性賦值。

1.2 模型形式化定義

ABCWR規(guī)則的描述語言包括5個元素：subject(主體)、object(客體)、environment(環(huán)境)、action(行動)、result(結(jié)果)。形式化為五元組Rule(s,o,e,a,r)。

模型為S,O,E,A定義了若干預(yù)定義屬性集(Pre-Attribute)，分別表示為:SPAk(1≤k≤K)，OPAk(1≤k≤K),EPAk(1≤k≤K)，APAk(1≤k≤K)。例如，S定義了2個預(yù)定義集合SPA1、SPA2，其中，SPA1表示算子類型、SPA2表示當(dāng)前狀態(tài)，則有SPA1={步兵,裝甲部隊(duì),空軍}，SPA2={交戰(zhàn),撤退,機(jī)動,駐扎}。用Result表示規(guī)則的判定結(jié)果，例如Result={允許,禁止,攻擊力-1,撤退}。

模型使用四元組Request(s,o,e,a)表示一條規(guī)則查詢請求。使用ATTR(s)、ATTR(o)、ATTR(e)、ATTR(a)分別表示主體、客體、環(huán)境和行動的屬性賦值關(guān)系，均為各自預(yù)定義屬性的笛卡爾集子集，其取值與特定的s,o,e,a相關(guān)。

ATTR(s)?SPA1×SPA2×…SPAk

ATTR(o)?OPA1×OPA2×…OPAk

ATTR(e)?EPA1×EPA2×…EPAk

ATTR(a)?APA1×APA2×…APAk

(1)

兵棋規(guī)則本質(zhì)上是從實(shí)體屬性集到規(guī)則判定結(jié)果集的映射，其函數(shù)定義如下：

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

ATTR(a))→Result

(2)

在一個特定的兵棋系統(tǒng)中，實(shí)體的預(yù)定義屬性集是固定的。對于一個規(guī)則查詢請求：

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

ATTR(e),ATTR(a))

(3)

規(guī)則判定函數(shù)通過比較某條規(guī)則和規(guī)則查詢請求中實(shí)體屬性的包含關(guān)系，將其映射到判定結(jié)果集，其函數(shù)映射定義如下：

(4)

其中：RuleAttr表示規(guī)則中的實(shí)體屬性集；ReqAttr為查詢請求中的實(shí)體屬性集；Unsatisfy表示該規(guī)則無法匹配。Rule∈RuleSet，RuleSet表示基于每個請求所包含客體的屬性搜索得到的關(guān)聯(lián)規(guī)則集。兵棋系統(tǒng)中，每個客體實(shí)體(算子、六角格)都可能綁定若干條規(guī)則。

為了提高規(guī)則匹配的效率，模型首先對規(guī)則庫的所有規(guī)則進(jìn)行預(yù)處理，即首先對請求中主體、客體，或行動屬性所關(guān)聯(lián)的規(guī)則集進(jìn)行搜索和匹配。用函數(shù)(5)表示對于具有特定屬性查找的綁定規(guī)則或無規(guī)則。

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

(5)

2 基于XML描述的ABCWR規(guī)則集

兵棋規(guī)則的描述應(yīng)具有可讀性和可維護(hù)性。兵棋規(guī)則設(shè)計者或用戶一方面可以方便地識讀、修改規(guī)則文檔；另一方面描述文檔自身可以有效地管理、存儲、傳輸和轉(zhuǎn)換，并能將規(guī)則數(shù)據(jù)動態(tài)地展現(xiàn)出來。XML語言具有自描述性、可擴(kuò)展性、跨平臺性以及嚴(yán)格的語法和邏輯，提供了較高效的數(shù)據(jù)管理能力。因此，XML比數(shù)據(jù)庫更適合兵棋規(guī)則庫的實(shí)現(xiàn)。

在ABCWR規(guī)則庫的實(shí)現(xiàn)中，借鑒了網(wǎng)絡(luò)訪問控制的思想，使用XACML策略描述語言來定義兵棋規(guī)則。XACML(eXtensible access control markup language)[14-15]是一種用于保護(hù)資源的基于XML的通用訪問策略描述語言。該語言基于實(shí)體的屬性進(jìn)行決策，適合于描述ABCWR模型。此外，XACML還提供策略管理的工具，簡化了兵棋規(guī)則庫的工程實(shí)現(xiàn)。例如，對于規(guī)則“夜晚裝甲部隊(duì)機(jī)動路徑不可延伸至沼澤區(qū)”，其XACML語言描述如圖1所示。

圖1 規(guī)則的XACML語言描述

3 ABCWR規(guī)則判定機(jī)制

ABCWR模型的模塊組成如圖2所示，模型主要包括4部分：規(guī)則決策點(diǎn)( rule decision point，RDP)、規(guī)則執(zhí)行點(diǎn)(rule execute point，REP)、規(guī)則信息點(diǎn)(rule information point，RIP)、規(guī)則管理點(diǎn)(rule management point，RMP)。

在工程實(shí)現(xiàn)中，首先依據(jù)兵棋劇本和規(guī)則說明書生成預(yù)定義屬性集，再將兵棋規(guī)則轉(zhuǎn)換為函數(shù)(2)的映射關(guān)系(規(guī)則)，并將規(guī)則體以XML的形式存儲于RMP的規(guī)則庫。RMP規(guī)則庫中的規(guī)則XML文件能夠以Web頁面的形式展現(xiàn)給用戶，從而方便用戶查看和修改規(guī)則。

圖2 ABCWR模型模塊組成

針對算子的每次行動，REP依據(jù)函數(shù)(3)將兵棋用戶的操作轉(zhuǎn)化為原始查詢請求消息(包含主體、客體、行動屬性)，并發(fā)送給RDP。RDP將查詢結(jié)果以查詢響應(yīng)消息的形式回傳給REP。請求和響應(yīng)消息采用XML的形式進(jìn)行描述，定義了RDP和REP之間的接口。RIP為RDP提供匹配規(guī)則過程中需要的環(huán)境屬性信息。上下文處理器(context handler)負(fù)責(zé)各模塊之間的消息傳遞。

RDP 模塊負(fù)責(zé)對規(guī)則查詢請求進(jìn)行規(guī)則判定。RDP基于查詢請求中的主體、客體或行動屬性從RAP 中獲取關(guān)聯(lián)規(guī)則集，然后根據(jù)查詢請求中的主體、客體或行動屬性以及RIP中的環(huán)境屬性，對關(guān)聯(lián)規(guī)則集中的所有規(guī)則進(jìn)行目標(biāo)匹配，最后對這些結(jié)果進(jìn)行合并得到最終結(jié)果。RDP 對應(yīng)ABCWR模型中的RuleDecision 函數(shù)。

RMP 模塊完成規(guī)則預(yù)處理功能，為RDP 提供特定屬性的關(guān)聯(lián)規(guī)則集。RMP根據(jù)RDP提交的特定屬性，從規(guī)則庫中查找特定屬性所關(guān)聯(lián)的規(guī)則集，并將關(guān)聯(lián)規(guī)則集返回給RDP用于規(guī)則判定。RDP提交給RMP的特定屬性類型可以是主體屬性、客體屬性或行動屬性。RMP 對應(yīng)ABCWR模型中的RuleBindAttribute函數(shù)。

4 ABCWR規(guī)則判定性能測試

判定1條規(guī)則需要匹配主體、客體、環(huán)境、行動4類屬性。對于一個判定請求，若4個屬性均相同，則該規(guī)則為真，否則為假。判定1條規(guī)則為真，需要運(yùn)行4次；判定1條規(guī)則為假，至少需要運(yùn)行1次；假定4類屬性為假的概率相同，則需要平均運(yùn)行2次。因此，每條規(guī)則的平均匹配次數(shù)為3次，假定規(guī)則庫中有n條規(guī)則，共需要匹配3×n次，時間復(fù)雜度為O(n)。理論上，規(guī)則判定時間與規(guī)則庫中的規(guī)則條數(shù)呈正比關(guān)系。

選擇不同規(guī)模的規(guī)則庫為標(biāo)準(zhǔn)對ABCWR模型的規(guī)則判定性能進(jìn)行測試。其中，規(guī)則數(shù)目為5、10的規(guī)則庫是設(shè)計的基準(zhǔn)規(guī)則庫，用于獲得基準(zhǔn)運(yùn)行時間。將3款經(jīng)典商業(yè)兵棋規(guī)則轉(zhuǎn)換為規(guī)則庫，分別對應(yīng)大型、中型和小型兵棋規(guī)則庫：《戰(zhàn)爭藝術(shù)Ⅲ》(647條規(guī)則)、《諾曼底1944》(353條規(guī)則)、《軸心國入侵薩拉熱窩》(36條規(guī)則)[16-17]。

此外，為每個規(guī)則庫設(shè)計與規(guī)則對應(yīng)的查詢請求，在每次測試中對所有的查詢請求運(yùn)行一遍。ABCWR模型基于Visual Studio2010實(shí)現(xiàn)，在測試過程中使用GetTickCount對規(guī)則匹配進(jìn)程的運(yùn)行時間進(jìn)行計算。測試環(huán)境： Intel Core 2 P8700 2.53 GHz CPU，2 GB內(nèi)存，Windows XP SP2操作系統(tǒng)。測試結(jié)果如表1所示。

表1 規(guī)則判定性能測試

表1中的實(shí)際運(yùn)行時間為測試過程中運(yùn)行時間。理論運(yùn)行時間為運(yùn)行時間與規(guī)則條數(shù)呈正比條件下的規(guī)則判定遍歷理論運(yùn)行值。為此，以10條規(guī)則的規(guī)則庫的實(shí)際運(yùn)行時間(1 ms)為基準(zhǔn)值，計算出剩余3個商業(yè)兵棋規(guī)則庫的規(guī)則判定遍歷理論時間。如表1所示，后3個兵棋規(guī)則庫的實(shí)際判定遍歷時間與理論值十分接近。因此，ABCWR模型的規(guī)則判定時間與規(guī)則條數(shù)近似呈正比關(guān)系。

通過上述分析可以看出：為了提高ABCWR模型的規(guī)則判定性能，可以考慮減少判定規(guī)則為假的匹配次數(shù)。之前假定了4類屬性為假的概率相同，但對于實(shí)際的兵棋規(guī)則庫，基于不同的屬性判定規(guī)則為假的概率是不同的。以商業(yè)手工兵棋《諾曼底1944》為例，轉(zhuǎn)換了353條規(guī)則，分別依據(jù)行動屬性和主體算子類型屬性統(tǒng)計了不同屬性的規(guī)則分布。

如圖3、4所示，與依據(jù)主體算子類型的規(guī)則劃分相比，依據(jù)行動屬性的規(guī)則劃分更為細(xì)致，兵棋規(guī)則的分布更為均衡。因此，如果首先根據(jù)行動屬性對規(guī)則庫進(jìn)行匹配，則大部分“假”規(guī)則將在第1次匹配中被發(fā)現(xiàn)，從而整體上減少“假”規(guī)則的匹配次數(shù)，提高規(guī)則判定的效率。正是基于這個考慮，ABCWR模型的規(guī)則預(yù)處理按照函數(shù)(5)從規(guī)則庫中提取了關(guān)聯(lián)規(guī)則集。

圖3 依據(jù)行動屬性的規(guī)則分布

圖4 依據(jù)主體算子類型屬性的規(guī)則分布

分別對首先匹配主體算子類型屬性規(guī)則和首先匹配行動屬性規(guī)則2種情況的規(guī)則請求匹配時間進(jìn)行測試。如表2所示，對于《諾曼底1944》的353條規(guī)則，首先匹配行動屬性比首先匹配主體算子類型屬性的匹配時間減少了20.58%。可見兵棋規(guī)則庫中的規(guī)則依據(jù)屬性的分布存在差異，需要對規(guī)則分布進(jìn)行統(tǒng)計分析，從而比較得出最佳預(yù)處理屬性類型。

表2 規(guī)則分布對匹配效率的影響

5 結(jié)束語

兵棋的本質(zhì)是對作戰(zhàn)指揮人員決策過程的推演，檢驗(yàn)的是雙方指揮人員的決策過程[18]。在兵棋推演過程中，推演雙方必須熟練掌握兵棋的規(guī)則。如果規(guī)則庫規(guī)模太大，雖然對戰(zhàn)場的模擬更為逼真，但對推演者掌握兵棋規(guī)則帶來巨大的困難。因此，實(shí)用的兵棋系統(tǒng)規(guī)則庫規(guī)模不會太大。ABCWR模型的規(guī)則判定時間與規(guī)則數(shù)目呈正比關(guān)系，在現(xiàn)有商業(yè)兵棋規(guī)則庫規(guī)模下具有實(shí)用性。