作者：尹奇躍，趙美靜，倪晚成，張俊格，黃凱奇

摘要:

近年來, 以人機對抗為途徑的智能決策技術取得了飛速發展, 人工智能技術AlphaGo、AlphaStar等分別在圍棋、星際爭霸等游戲環境中戰勝了頂尖人類選手. 兵棋推演, 作為一種人機對抗策略驗證環境, 由于其非對稱環境決策、更接近真實環境的隨機性與高風險決策等特點受到智能決策技術研究者的廣泛關注. 本文將梳理兵棋推演與目前主流人機對抗環境如圍棋、德撲、星際爭霸等對抗環境的區別, 闡述兵棋推演智能決策技術的發展現狀, 并分析當前主流技術的局限與瓶頸, 對兵棋推演中的智能決策技術研究進行了思考, 期望能對兵棋推演相關研究人員的智能決策技術研究帶來啟發.

人機對抗, 作為人工智能技術的試金石, 近年來獲得了舉世矚目的進展. 隨著Deep Blue[1]、AlphaGo[2]、Libratus[3]、AlphaStar[4]等智能體分別在國際象棋、圍棋、二人無限注德州撲克以及星際爭霸中戰勝頂尖職業人類選手, 其背后的智能決策技術獲得了廣泛的關注, 也代表了智能決策技術在中等復雜度完美信息博弈、高復雜度完美信息博弈再到高復雜度不完美信息博弈中的技術突破.

國際象棋、圍棋代表了完美信息博弈, 其狀態空間復雜度由1047增至10360, 后者更是被譽為人工智能技術的阿波羅. 相比于上述兩種博弈環境, 二人無限注德州撲克, 盡管狀態空間復雜度僅有10160, 但其為不完美信息博弈, 相比于國際象棋與圍棋信息集大小僅為1, 其信息集平均大小達到103. 而星際爭霸, 作為高復雜度不完美信息博弈的代表, 因其相比于上述游戲的即時制、長時決策等特性[4, 5], 對智能決策技術提出了更高的要求.

星際爭霸突破之后, 研究人員迫切需要新的人機對抗環境實現智能技術的前沿探索. 兵棋推演是一款經典策略游戲[6-8], 也被稱為戰爭游戲, 作為一種人機對抗策略驗證環境, 由于其具有不對稱環境決策、更接近真實環境的隨機性與高風險決策等特點, 受到智能決策技術研究者的廣泛關注. 近些年來, 研究者投入了大量的精力進行兵棋推演智能體研發以及兵棋推演子問題求解, 試圖解決兵棋推演的人機對抗挑戰[9-14].

兵棋推演, 一直以來都是戰爭研究和訓練的手段, 分為早期的手工兵棋與20世紀80年代后期普及的計算機兵棋[15-17]. 胡曉峰等人[6]全面綜述了兵棋推演的基本要素(參演人員、兵棋系統模擬的戰場環境和作戰部隊、導演部及導調機構), 指出“兵棋推演的難點在于模擬人的智能行為”, 進而得出“兵棋推演需要突破作戰態勢智能認知瓶頸”, 最后給出了如何實現態勢理解與自主決策可能的路徑. 和目前兵棋推演關注的重點不同, 本文關注的是兵棋推演中的智能體研究, 針對通用性的智能決策技術與挑戰展開. 另外, 需要闡明的是, 本文中的兵棋推演, 如非特別闡述, 在不引起歧義的前提下統一指雙方計算機兵棋推演(紅藍兩方).

本文內容組織如下: 第二章將梳理兵棋推演與目前主流人機對抗環境如星際爭霸等的區別, 以及為什么其潛在是人機對抗的下一個挑戰; 第三章將介紹兵棋推演智能技術的研究現狀; 之后在第四章闡述當前主流技術的瓶頸; 第五章對兵棋推演的智能決策技術進行展望與思考, 希望啟發新的研究方向; 最后對全文進行總結.

1.兵棋智能決策問題的挑戰

本章首先簡要介紹兵棋推演問題以及與手工兵棋的比較. 在此基礎上, 以人機對抗發展脈絡為主線, 以兵棋推演中的智能體研究為核心, 介紹兵棋推演與其他主流策略游戲的通用挑戰, 之后重點闡述兵棋推演的獨特挑戰. 前者為實現兵棋推演人機對抗的成功提供了技術基礎, 后者則對當下人機對抗智能體決策技術提出了新的挑戰.

1.1 兵棋推演問題

早期的兵棋推演一般指手工兵棋, 具有200年的研究歷史, 而隨著信息技術與計算機性能的不斷發展, 計算機兵棋, 因其簡便、快速、逼真等特點成為目前兵棋推演的主流方向[18]. 王桂起等人[15]在2012年概述了兵棋的概念、發展、分類以及應用, 并分析了兵棋的各組成要素以及國內外兵棋的研究現狀. 彭春光等人[16]在2009年對兵棋推演技術進行了綜述, 指出兵棋主要研究人員決策與兵棋事件之間的因果關系.

2017年, 胡曉峰等人[6]對兵棋推演進行了全面的綜述, 描述了兵棋推演的基本要素, 重點闡述了兵棋推演的關鍵在于模擬人的智能行為, 面臨的難點為“假變真”、“粗變細”、“死變活”、“靜變動”、“無變有”, 歸結起來為“對戰場態勢的判斷理解”以及“對未來行動的正確決策處置”, 在此基礎上, 作者展望了AlphaGo等技術對兵棋推演帶來的新機遇. 不同于上述工作, 本文以人機對抗智能決策切入, 針對通用性的智能決策技術與挑戰展開對兵棋推演中的智能體研究.

1.2 策略游戲普遍挑戰問題

回顧當前典型的已獲得一定人機對抗突破的決策環境如雅達利、圍棋、德州撲克以及星際爭霸, 可以得出一些基本的結論. 人機對抗研究的重心已經從早期的單智能體決策環境如雅達利過渡到了多智能體決策環境如圍棋與星際爭霸; 從回合制決策環境如圍棋逐漸過渡到更貼近現實應用的復雜即時戰略類決策環境如星際爭霸; 從完美信息博弈如圍棋逐漸過渡到非完美信息博弈如德撲與星際爭霸; 從以樹為基礎的博弈算法如圍棋與德撲過渡到以深度強化學習為基礎的大規模機器學習算法. 針對上述轉變與各自博弈對抗環境的特點, 可以凝練抽取一些影響智能體設計與訓練的關鍵因素, 如表1所述. 典型的兵棋推演仿真環境一般由算子、地圖、想定以及規則要素組成, 展現了紅藍雙方之間的博弈對抗. 與代表性策略游戲如雅達利、圍棋、德州撲克以及星際爭霸等類似, 兵棋推演的智能體研究表現出策略游戲中智能體研究的普遍挑戰性問題.

表 1 對決策帶來挑戰的代表性因素

不完美信息博弈. 不完美信息博弈是指沒有參與者能夠獲得其他參與者的行動信息[19], 即參與者做決策時不知道或者不完全知道自己所處的決策位置. 相比于完美信息博弈, 不完信息博弈挑戰更大, 因為對于給定決策點, 最優策略的制定不僅僅與當下所處的子博弈相關. 與德州撲克、星際爭霸相似, 兵棋推演同樣是不完美信息博弈, 紅方或者藍方受限于算子視野范圍、通視規則、掩蔽規則等, 需要推斷對手的決策進而制定自己的策略.

長時決策. 相比于決策者僅做一次決策的單階段決策游戲, 上述游戲屬于序貫決策游戲[20]. 以圍棋為例, 決策者平均決策次數在150次, 相比于圍棋, 星際爭霸與兵棋推演的決策次數以千為單位. 長時決策往往導致決策點數量指數級的增加, 使得策略空間復雜度變大, 過高的策略空間復雜度將帶來探索與利用等一系列難題, 這對決策制定帶來了極大的挑戰.

策略非傳遞性. 對于任何策略vt可戰勝vt?1, vt+1可戰勝vt, 有vt+1可戰勝vt?1, 則認為策略之間存在傳遞性. 一般情況下, 盡管部分決策環境存在必勝策略, 但在整個策略空間下都或多或少存在非傳遞性的部分, 即大多數博弈的策略不具備傳遞性[21]. 例如, 星際爭霸與兵棋推演環境, 策略難以枚舉且存在一定的相互克制關系. 策略非傳遞性會導致標準自博弈等技術手段難以實現智能體能力的迭代提升, 而當前經典的博弈算法如Double Oracle[58]等又往往難以處理大規模的博弈問題, 使得逼近納什均衡策略極其困難.

智能體協作. 在多智能體合作環境中, 智能體間的協作將提升單個智能體的能力, 增加系統的魯棒性, 適用于現實復雜的應用場景[22-24]. 圍棋與兩人德州撲克參與方屬于純競爭博弈環境, 因此不存在多個智能體之間的協作. 星際爭霸與兵棋雖然也屬于競爭博弈環境, 但是需要多兵力/算子之間配合獲得多樣化且高水平策略. 將上述問題看作是單個智能體進行建模對求解是困難的, 可以建模為組隊零和博弈, 隊伍之間智能體相互協作, 最大化集體收益. 針對組隊零和博弈問題, 相比于二人零和博弈問題, 理論相對匱乏.

為應對上述挑戰, 研究人員進行了大量的技術創新. 例如, 在蒙特卡洛樹搜索基礎上引入深度神經網絡實現博弈樹剪枝、通過自博弈實現強化學習的圍棋AI AlphaGo系列[2], 在虛擬遺憾最小化算法基礎上引入安全嵌套子博弈求解以及問題約簡等技術的二人無限注德州撲克AI Libratus[3], 采用改進自博弈以及分布式強化學習的星際爭霸AI AlphaStar[4]. 上述技術為相應決策問題的挑戰性因素提出了可行的解決方案, 盡管兵棋推演存在上述挑戰, 但相關技術基礎已經具備, 可以指導兵棋推演的研究方向.

1.3 兵棋推演獨特挑戰問題

1.3.1 非對稱環境決策

傳統的非對稱信息指某些行為人擁有但另一些行為人不擁有的信息, 本文的非對稱以學習的角度考慮, 指的是游戲雙方的能力水平或游戲平衡性. 以圍棋、星際爭霸以及絕大多數游戲環境為例, 游戲設計者為保證游戲的體驗以及促進人類選手競技水平的提升, 往往保證游戲不同方具有相對均衡的能力. 例如, 星際爭霸游戲中包含了三個種族, 即人族、蟲族以及神族, 盡管不同種族具有截然不同的科技樹、兵力類型等, 但是三個種族在能力上處于大致均衡的狀態.

相比于星際爭霸等, 兵棋推演中游戲是不平衡的. 這不僅體現在紅方與藍方在兵力配備上的不同, 也體現在不同任務/想定下紅方和藍方的現實需要. 以部分奪控戰為例, 紅方兵力水平一般弱于藍方, 同時紅方往往具有更好的視野能力(如紅方配備巡飛彈算子), 而藍方往往具有更強的進攻能力(如配備更多的坦克算子). 這種嚴重的非對稱性, 對于目前的學習算法提出了極大的挑戰.

當前主流的或改進的自博弈技術, 在智能體迭代過程中往往對每個參與智能體以對稱的方式進行訓練, 進而保證智能體能力在相互對抗的迭代過程中持續增長. 但是, 在兵棋推演中, 紅方與藍方嚴重的非對稱性, 使得直接采用相似的設計難以保證弱勢方的訓練, 需要設計更合理的迭代方式(如啟發式迭代)保證相對較弱勢方的訓練. 另一方面, 在二人零和博弈中, 雖然弱勢方的納什均衡策略可取, 但是如何根據對手的情況調整自己的策略以最大可能剝削或者發現對手的漏洞并加以利用, 可能是要考慮的重點問題.

1.3.2 隨機性與高風險決策

隨機性與高風險主要體現在游戲的裁決中, 泛指交戰規則中隨機影響因素以及對交戰結果產生的影響. 裁決是游戲的重要組成部分, 在決定游戲的勝負規則之外, 明確定義了參與方在對抗過程中的交戰結果. 例如, 在圍棋中, 黑子包圍白子之后, 需要將白子從棋盤中拿下, 即吃子. 在星際爭霸環境中, 兩隊兵力對抗中, 血量為零的兵力將直接消失. 一般來說, 在圍棋等棋類游戲中, 裁決不受隨機因素的干擾, 即不具有隨機性. 而在星際爭霸環境中, 盡管不同兵力攻擊產生的傷害數值是固定的, 但仍然受到少量隨機因素的影響, 例如具有一定概率觸發某項技能(如閃避).

相比于上述游戲, 兵棋推演在所有攻擊裁決過程中均受到隨機因素的影響, 即隨機性較高, 這主要是因為兵棋裁決一般遵循著“攻擊等級確定、攻擊等級修正、原始戰果查詢、最終戰果修正”的基本流程. 在原始戰果查詢與最終戰果修正中, 將基于骰子產生的隨機數值(兩個骰子1?12點)分別進行修正, 上述修正的結果差距較大, 可能產生壓制甚至消滅對方班組的戰果, 也有可能不產生任何效果. 更重要的是, 相比于其他即時戰略類游戲(如星際爭霸), 兵力一旦消失, 將不能重新生成, 因此會造成極高的風險, 對于專業級選手, 兵力的消失往往意味著游戲的失敗.

兵棋推演的隨機性與高風險決策對于智能體的訓練提出了極高的挑戰. 反映在數據上, 環境的狀態轉移不僅受到其他算子以及不可見信息的影響, 也受到裁決的影響, 即狀態轉移高度不確定. 另一方面, 決策的高風險使得算子所處狀態的值估計等具有高方差特性, 難以引導智能體的訓練, 尤其是在評估上難以消除該隨機性的情況下訓練更加困難.

總的來說, 兵棋推演, 作為一種人機對抗策略驗證環境, 由于其具備目前主流對抗環境的挑戰性問題, 使得完成兵棋推演的人機對抗挑戰具備一定的技術基礎. 同時, 由于其不對稱信息決策、更接近于真實環境的隨機性與高風險決策特點, 對當前人機對抗技術提出了新的挑戰, 也使得兵棋推演成為人機對抗的下一個挑戰.

2. 兵棋智能決策技術研究現狀

為應對兵棋推演的挑戰性問題, 研究者提出了多種智能體研發與評測方法. 與圍棋、星際爭霸等主流游戲人機對抗智能體研發脈絡類似(如星際爭霸從早期知識規則為主, 中期以數據學習為主, 后期以聯合知識與強化學習完成突破), 兵棋推演也經歷了以知識驅動為主、以數據驅動為主以及以知識與數據混合驅動的研發歷程. 兵棋的評測技術包含了智能體的定量與定性分析方法. 在本節中, 將重點闡述兵棋智能體研發的技術與框架, 同時對智能體的評估評測進行簡述.

2.1 兵棋智能體研發技術與框架

當前智能體的研發技術與框架主要包含三類, 即知識驅動、數據驅動以及知識與數據混合驅動的兵棋推演智能體, 本節將分別闡述各個技術框架的研究進展.

2.1.1 知識驅動的兵棋推演智能體

知識驅動的兵棋推演智能體研發利用人類推演經驗形成知識庫, 進而實現給定狀態下的智能體決策[25]. 代表性的知識驅動框架為包以德循環(OODA[26]), 其基本觀點是通過觀察(Observation)、判斷(Orientation)、決策(Decision)以及執行(Action)的循環過程實現決策, 如圖1所示. 具體來說, 觀察包括觀察自己、環境以及對手實現信息的收集; 判斷對應態勢感知, 即對收集的數據進行分析、歸納以及總結獲得當前的態與勢; 決策對應策略的制定, 利用前面兩步的結果實現最優策略的制定; 執行對應于具體的行動.

圖 1 包以德循環

通過引入高水平人類選手的經驗形成知識庫, 可以一定程度規避前面所述的挑戰性問題, 實現態勢到決策的規則制定與編碼. 自2017年國內各類兵棋大賽舉辦以來, 每年都有數十甚至上百個參賽隊伍進行機機對抗, 角逐的精英智能體將參與人機對抗以及人機混合對抗. 為適應不同的想定以及進行人機協同, 目前絕大多數智能體為知識驅動型, 即依據人類選手的經驗進行戰法總結, 以行為樹[27]、自動機[28]等框架實現智能體決策執行邏輯的編程實現. 總的來說, 知識驅動型智能體研發依賴于人類推演經驗與規律的總結, 實現相對簡單, 不需要借助于大量的數據進行策略的訓練與學習.

近些年來, 通過編碼高水平選手的決策, 涌現出了一系列高水平知識驅動型智能體并開放對抗①, 例如, 信息工程大學的“兵棋分隊級AI-微風1.0”, 該智能體基于動態行為樹框架, 在不同想定下實現了不同的戰法戰術庫. 中國科學院自動化研究所的“兵棋群隊級AI-紫冬智劍2.0”, 該智能體以OODA環為基本體系架構, 以敵情、我情以及地形等通用態勢認識抽象狀態空間, 以多層級任務行為認知抽象決策空間, 可以快速適應不同的任務/想定. 目前部分智能體可以支撐人機混合對抗, 甚至在特定想定下達到了專業級選手水平.

2.1.2 數據驅動的兵棋推演智能體

隨著AlphaGo、AlphaStar等智能體取得巨大成功, 以深度強化學習為基礎進行策略自主迭代(如自博弈中每一輪的策略學習)成為當前的主流決策技術[29]并被成功應用于兵棋推演[30, 31]. 其基本框架如圖2所示, 智能體以自博弈或改進的自博弈方式進行每一代智能體的迭代, 而每一代智能體采用強化學習的方式進行訓練. 對于強化學習來說, 智能體與環境進行交互收集狀態、動作與獎賞等序列數據進行訓練, 直至學習得到可以適應特定任務的策略. 由于兵棋推演環境沒有顯式定義狀態、動作與獎賞等的具體表現形式, 因此在應用于強化學習的過程中, 首要的任務是進行上述基本要素的封裝, 在此基礎上便可以進行基本的強化學習訓練.

圖 2 自博弈+強化學習訓練

深度強化學習通過改進神經網絡的設計可以一定程度緩解非完美信息與長時決策帶來的挑戰. 例如, 通過增加認知網絡結構如記憶單元[32, 33]可以有效使用歷史信息, 一定程度解決部分可觀測狀態下的決策問題; 通過增加內在獎勵驅動的環境建模網絡[34], 可以緩解長時決策尤其是獎勵稀疏情況下強化學習的訓練. 自博弈尤其是改進的自博弈框架, 如星際爭霸提出的帶有優先級的虛擬自我對局與聯盟博弈有效緩解了策略非傳遞性的挑戰, 并通過初期的強化學習網絡監督訓練初始化實現了對策略非傳遞性的進一步緩解. 針對智能體協作, 研究者提出了大量的多智能體協同算法, 并通過獎勵共享、獎勵分配等實現了不同智能體的有效訓練. 關于非對稱性與高隨機性, 據本文作者所了解, 尚未有相關文獻解決兵棋推演的上述挑戰.

近些年來部分研究者將其他數據學習方式與強化學習進行結合以緩解端到端強化學習的困難. 例如, 李琛等[30]將Actor-Critic框架引入兵棋推演并與規則結合進行智能體開發, 在簡化想定(對稱的坦克加步戰車對抗)上進行了驗證. 張振等[31]將近端策略優化技術應用于智能體開發, 并與監督學習結合在智能體預訓練基礎上進行優化, 在簡化想定(對稱的兩個坦克對抗)驗證了策略的快速收斂. 中國科學院自動化研究所提出的AlphaWar②引入監督學習與自博弈技術手段實現聯合策略的學習, 保證了智能體策略的多樣性, 一定程度緩解了兵棋推演的策略非傳遞性問題. 2020年, AlphaWar在與專業級選手對抗過程中通過了圖靈測試, 展現了強化學習驅動型兵棋推演智能體的技術優勢.

另一方面, 分布式強化學習作為一種能夠有效利用大規模計算資源加速強化學習訓練的手段, 目前已成為數據驅動智能體研發的關鍵技術, 研究者提出了一系列算法在保證數據高效利用的同時也保證了策略訓練的穩定性. 例如, Mnih等人[35]在2016年提出異步優勢動作評價算法(Asynchronous advantage actor-critic), 實現了策略梯度算法的有效分布式訓練. Horgan等人[36]在2018年提出APE-X分布式強化學習算法, 對生成數據進行有效加權, 提升分布式深度Q網絡(Deep Q Network)訓練效果. Mnih等人[37]在2018年提出IMPALA算法實現了離策略分布式強化學習, 在高效數據產生的同時也可以通過V-Trace算法進行離策略(off-policy)修正, 該技術被成功用于奪旗對抗[38]. Espeholt等人[39]在2019年引入中心化模型統一前向, 進一步提升了IMAPLA的分布式訓練能力, 并被應用于星際爭霸AlphaStar的訓練中. 考慮到IMPALA的高效以及方便部署, 以IMPALA為代表的分布式強化學習已經成為兵棋智能體訓練的常用算法. IMPALA的結構如下圖3所示, 其實現可以方便地通過TensorFlow③、Pytorch④或伯克利近期提出的Ray[40] 框架完成.

圖 3 IMAPLA用于兵棋推演AI訓練

2.1.3 知識與數據混合驅動的兵棋推演智能體

知識驅動智能體具有較強的可解釋性, 但是受限于人類的推演水平. 與之相反, 基于數據驅動的兵棋智能體較少依賴人類推演經驗, 可以通過自主學習的方式得到不同態勢下的決策策略, 具有超越專業人類水平的潛力, 但是由于數據驅動的兵棋推演智能體依賴數據以及深度神經網絡, 其訓練往往較為困難且決策算法缺乏可解釋性.

為了有效融合知識驅動與數據驅動框架的優點, 避免各自的局限性, 目前越來越多的研究者試圖將兩者進行結合[41]. 其中關注較多的工作為將先驗信息加入到學習過程中進而實現對機器學習模型的增強[42-44]. 在該類工作中, 知識或稱為先驗信息作為約束、損失函數等加入到學習的目標函數中實現一定程度的可解釋性以及模型的增強. 近年來, Laura von Rueden等人[42]進行了將知識融合到學習系統的綜述并提出了知信機器學習的概念(informed machine learning), 從知識的來源、表示以及知識與機器學習管道的集成對現有方法進行了分類.

知識與數據混合驅動框架結合了兩者的優勢, 可以更好應對兵棋推演環境的挑戰, 目前代表性的融合方式包括“加性融合”, 如圖4所示, 即知識驅動與數據驅動各自做擅長的部分, 將其整合形成完整的智能體. 一般來說, 知識驅動善于處理兵棋推演前期排兵布陣問題, 因為該階段往往缺乏環境的有效獎勵設計. 另一方面, 緊急態勢下的決策以及相對常識性的決策也可以由知識驅動完成, 以減少模型訓練的探索空間. 數據驅動善于自動分析態勢并作出決策, 更適用于進行兵棋推演中后期多樣性策略的探索與學習. 此外, 一些難以用相對有限的知識規則刻畫的態勢-決策也可由數據驅動完成. 黃凱奇等人[45] 提出了一種融合知識與數據的人機對抗框架, 如圖5所示, 該框架以OODA為基礎, 刻畫了決策不同階段的關鍵問題, 不同問題可以通過數據驅動或知識驅動的方式進行求解.

圖 4 知識與數據驅動“加性融合”框架

圖 5 人機對抗框架[45]

另一種代表性融合方式為“主從融合”, 如圖6所示, 即以一方為主要框架, 另一方為輔助的融合方式. 在以知識驅動為主的框架中, 整體設計遵循知識驅動的方式, 在部分子問題或者子模塊上采用如監督學習、進化學習等方式實現優化. 例如, 武警警官學院開發的分隊/群隊AI“破曉星辰2.0”⑤在較為完善的人類策略庫基礎上結合蟻群或狼群等算法進行策略庫優化, 以提升智能體的適應性. 在以數據驅動為主的框架下, 則采用如數據驅動的改進自博弈加強化學習的方式進行整體策略學習, 同時增加先驗尤其是常識性約束. 例如, 將常識或人類經驗作為神經網絡選擇動作的二次過濾以減少整體探索空間.

圖 6 知識與數據驅動“主從融合”框架

2.2 兵棋智能體評估評測及平臺

智能體的評估涉及智能體整體能力與局部能力評估, 同時開放的智能體評估平臺將有效支撐智能體的能力測評與迭代. 本節將從智能體評估算法與智能體評估開放平臺展開介紹.

2.2.1 智能體評估算法

正確評估智能體策略的好壞對于智能體的訓練與能力迭代具有至關重要的作用. 考慮到兵棋推演中策略的非傳遞性以及其巨大的策略空間問題, 進行智能體的準確評估挑戰巨大. 近年來, 研究者們提出了一系列評估算法, 試圖對智能體能力進行準確描述. 經典的ELO算法[46]利用智能體之間的對抗結果, 通過極大似然估計得到反映智能體能力的分值. 例如, 圍棋、星際爭霸等對抗環境中的段位就是基于ELO算法計算獲得. Herbrich等人[47]提出TrueSkill算法, 通過將對抗過程建立為因子關系圖, 借助于貝葉斯理論實現了多個智能體對抗中單一智能體能力的評估. 考慮到ELO算法難以處理策略非傳遞性這一問題, Balduzzi等人[48]提出多維ELO算法, 通過對非傳遞維度進行顯式的近似改善了勝率的預測問題. 更進一步, Omidshafiei等人[49]提出α-rank算法, 基于Markov-Conley鏈, 使用種群策略進化的方法, 對多種群中的策略進行排序, 實現策略的有效評估.

定量評估之外, 也可以通過專家評判的方式進行定性評估, 實現對智能體單項能力的有效評估. 例如, 圖7是廟算杯測試賽 ⑥中對智能體AlphaWar的評估, 在人為抽象出的“武器使用”、“地形利用”、“兵力協同”、“策略高明”、“反應迅速”方面與測試賽排名第一位的人類選手進行了比較.

圖 7 智能體單項能力評估

2.2.2 智能體評估開放平臺

為促進兵棋推演智技術的發展, 構建標準的評估評測平臺至關重要, 其可以實現廣泛的兵棋智能體機機對抗、人機對抗甚至人機混合對抗[50], 這對兵棋推演評估評測平臺提出了較高的要求, 但也極大地促進了兵棋評估評測平臺的建設與標準化. 最近, 中國科學院自動化研究所構建了人機對抗智能門戶網站(//turingai.ia.ac.cn/), 如圖8所示. 該平臺以機器和人類對抗為途徑, 以博弈學習等為核心技術來實現機器智能快速學習進化的研究方向. 平臺提供兵棋推演智能體的機機對抗、人機對抗以及人機混合對抗測試, 并支持智能體的多種評估評測.

圖 8 “圖靈網”平臺

3.兵棋智能決策技術的挑戰

針對兵棋推演的智能技術研究現狀, 本節重點闡述不同技術框架存在的挑戰性問題, 引導研究者對相關問題的深入研究.

3.1 知識驅動型技術挑戰

知識驅動型作為智能體研發的主流技術之一, 其依賴人類推演經驗形成知識庫, 進而實現給定態勢下的智能體決策. 基于此, 知識驅動型智能體具有較強的可解釋性, 但同樣面臨不可避免的局限, 即受限于人類本身的推演水平, 同時環境遷移與適應能力較差, 造成上述局限的根本原因在于缺乏高質量的知識庫[51, 52]實現知識建模、表示與學習[53], 這也是目前知識驅動型技術的主要挑戰. 知識庫一般泛指專家系統設計所應用的規則集合, 其中規則所聯系的事實及數據的全體構成了知識庫, 其具有層次化基本結構.

對于兵棋推演來說, 知識庫最底層是“事實知識”, 如算子機動能力等; 中間層是用來控制“事實”的知識(規則、過程等表示), 對應于兵棋中的微操等; 最頂層是“策略”, 用于控制中間層知識, 一般可以認為是規則的規則, 如圖9所示. 兵棋推演中知識庫構建過程最大的挑戰便是頂層策略的建模, 面臨著通用態勢認知與推理困難的挑戰. 胡曉峰等人[6]指出兵棋推演需要突破作戰態勢智能認知瓶頸, 并提出戰場態勢層次不同, 對態勢認知的要求和內容也不同. 盡管部分學者嘗試從多尺度表達模型[54]、指揮決策智能體認知行為建模框架[55]以及基于OODA環框架下態勢認知概念模型[56]等進行態勢建模, 但是, 目前基于經典知識規劃的智能體受限于對環境的認識的正確性和完備程度, 表現相較呆板缺乏靈活應對能力, 不能很好地進行不確定環境邊界下的意圖估計與威脅評估等態勢理解.

圖 9 兵棋推演知識庫構建示例

3.2 數據驅動型技術挑戰

數據驅動型技術以深度強化學習為基礎進行策略自主迭代, 從該角度出發解決兵棋推演智能體研發, 訓練得到的智能體具有潛在的環境動態變化適應能力, 甚至有可能超越專業人類選手的水平, 涌現出新戰法. 同樣地, 為實現有效的智能體策略學習, 目前數據驅動型技術面臨以下技術挑戰: 自博弈與改進自博弈設計、多智能體有效協作、強化學習樣本效率較低. 其中, 自博弈與改進自博弈設計可以實現智能體能力的有效迭代提升, 多智能體有效協作將解決兵棋推演中的算子間協同(異步協同)問題, 而解決強化學習樣本效率較低問題可以實現在可控計算資源與時間下的智能體訓練.

自博弈與改進自博弈. 在兵棋推演這一二人零和博弈問題下, 傳統的博弈算法如虛擬自我對局[57]、Double Oracle[58]等難以適用于兵棋推演本身巨大的問題復雜度, 采用目前較為主流的自博弈或改進自博弈方式實現智能體能力的迭代成為一種可行的方案. 例如, 圍棋游戲的AlphaGo系列[2]采用結合蒙特卡洛樹搜索與深度神經網絡的自博弈強化學習實現智能體能力的迭代. 星際爭霸游戲的AlphaStar[4]則改進傳統的虛擬自我對局, 提出帶有優先級的虛擬自我對局并結合聯盟博弈進行智能體迭代. 具體來說, AlphaStar引入主智能體、主利用智能體以及聯盟利用智能體, 并對不同的智能體采用不同的自博弈進行以強化學習為基礎的參數更新. 總的來說, 盡管上述自博弈與一系列改進自博弈方法可以實現智能體的迭代, 但當前的設計多是啟發式迭代方式, 兵棋推演的非對稱環境等獨特挑戰是否適用有待驗證與開展深入研究.

多智能體協作. 協作環境下單個智能體的訓練受到環境非平穩性的影響而變得不穩定[59-62], 研究者提出了大量的學習范式以緩解該問題, 但仍然面臨著智能體信用分配這一核心挑戰, 即團隊智能體在和環境交互時產生的獎勵如何按照各個智能體的貢獻進行合理分配以促進協作[63-65]. 目前, 一類典型的算法為Q值分解類算法, 即在聯合Q值學習過程中按照單調性等基本假設將聯合Q值分解為智能體Q值的聯合, 進而實現信用隱式分配[66-68]. 例如, Sunehag等人[66] 率先提出此類算法將聯合Q值分解為各個智能體Q值的加和. 在此基礎上, Rashid等人[67]基于單調性假設提出了更為復雜的Q值聯合算法QMIX. 另外一類典型的信用分配算法借助于差異獎勵(difference reward)來實現顯式獎勵分配. 例如, Foster等人[69]通過引入反事實的方法提出COMA以評估智能體的動作對聯合智能體動作的貢獻程度. 通過將夏普利值引入Q學習過程中, Nguyen等人[70]提出了Shapley-Q方法以實現“公平”的信用分配. 在兵棋推演環境中, 不同智能體原子動作執行耗時是不一樣的, 導致智能體協作時的動作異步性, 如圖10所示. 這種異步性使得智能體間的信用分配算法要求的動作同步性假設難以滿足, 如何實現動作異步性下多智能體的有效協作仍然是相對開放的問題.

圖 10 兵棋推演中的異步多智能體協同

強化學習低樣本效率. 強化學習通過與環境交互試錯的方式進行模型訓練, 一般樣本效率較低, 因此在復雜環境下智能體訓練需要動用巨大的計算資源. 例如, AlphaZero[71] 采用了5000一代TPU與16二代TPU進行智能體學習; AlphaStar[4]采用192 TPU (8核)、12 TPU (128核)與50400 CPU實現群體博弈. 探索作為一種有效緩解樣本效率低的手段[72], 近些年來受到了研究者的廣泛關注, 并潛在適用具有巨大狀態空間、稀疏獎勵的兵棋推演環境中. 在單智能體強化學習中, 目前涌現了大量的探索類算法[72, 74], 如隨機網絡蒸餾(random network distillation)[34]、Go Explore[73] 等. 但多智能體的環境探索問題研究相對較少, 代表性方法包括MAVEN[75]、Deep-Q-DPP[76]、ROMA[77] 等. 其中MAVEN通過在QMIX的基礎上引入隱變量來實現多個聯合Q值的學習, 進而完成環境的有效探索. Deep-Q-DPP將量子物理中建模反費米子的行列式點過程(Determinantal Point Process)引入多智能體探索中, 通過增加智能體行為的多樣性來實現探索. 另一方面, ROMA通過考慮智能體的分工, 讓相同角色的單元完成相似的任務, 進而利用動作空間劃分來實現環境高效探索. 上述算法在星際爭霸微操等驗證環境中取得了有效的驗證, 但是兵棋推演環境擁有更加龐大的狀態空間, 如何實現智能體異步動作下的環境高效探索對當前技術提出了新的要求.

3.3 知識與數據混合驅動型技術挑戰

知識與數據混合驅動型相比于知識型與數據型, 可以有效融合兩者的優點, 既具備對環境的適用能力, 涌現出超越高水平人類玩家的策略, 同時又具備一定可解釋性, 實現可信決策. 在融合過程中面臨知識與數據驅動本身的技術挑戰之外, 另一個核心技術挑戰在于融合方式, 即如何實現兩者的有機融合[78]. 上一章節提到了代表性的 “加性融合”、“主從融合”, 可以實現知識與數據的一定程度融合, 但是何種融合方式更優目前并無定論, 另一方面, 探索更優的兵棋推演知識與數據融合思路是值得深入探索與研究的開放問題.

加性融合的挑戰. 在加性融合中, 知識驅動與數據驅動負責智能體不同的模塊, 兩者加和構成完整的智能體. 首先需要解決的問題是整個決策過程的模塊化或解耦合. 目前兵棋推演中較為簡單的一種做法是開局過程(算子前期布局/機動到中心戰場)采用知識驅動的方式, 中后期對抗(中心戰場對抗如消滅對手、奪控等)采用數據驅動的方式. 但是上述做法如何解耦合或者定義兩者的邊界是困難的, 這不可避免引入專家的領域知識, 也將受限于專家對問題認識的局限. 以OODA為基礎的人機對抗框架[45]雖然給出了較為一般化的框架, 但是如何在兵棋推演中具體實現存在較大的不確定性. 另一方面, 知識驅動與數據驅動部分相互制約, 在設計或訓練過程中勢必受到彼此的影響. 例如, 數據驅動的部分在迭代過程中受到知識驅動部分的限制. 這要求知識驅動或數據驅動部分在自我迭代的同時, 設計兩者的交替迭代進而實現完整智能體能力的迭代提升. 上述設計與研究目前仍然是相對開放的問題.

主從融合的挑戰. 在主從融合中, 以知識驅動或數據驅動為主, 部分子問題以另一種方式為手段進行解決. 在以數據驅動為主的框架中, 難點在于如何將知識或常識加入到深度學習或深度強化學習的訓練中. 例如, 如何引入領域知識設計狀態空間、動作空間以及獎賞. 相關設計將極大影響智能體的最終水平以及訓練效率, 因此需要對上述問題進行折中, 保證智能體能力的同時盡可能引入更多的知識以提升訓練效率. 在以知識為主的框架中, 難點在于尋找適宜用學習進行解決的子問題, 進而解決難以枚舉或難以制定策略的場景. 例如采用經典的尋路算法[79]實現臨機路障等環境下的智能體機動設計; 利用模糊系統方法實現兵棋進攻關鍵點推理[80]; 基于關聯分析模型進行兵棋推演武器效用挖掘[81]. 目前, 在星際爭霸、dota2等復雜即時戰略類游戲中的取得代表性成果的智能體多采用以數據驅動為主的方式, 即引入領域知識設計深度強化學習的各要素和訓練過程, 如何根據兵棋推演獨特的挑戰進行相關技術遷移與改進目前是相對開放的問題.

3.4 評估評測技術挑戰

當前智能體的評估主要借助機機對抗的勝率進行智能體綜合能力/段位的排名/估計. 除此之外, 兵棋推演一般建模為多智能體協作問題, 因此, 單個智能體的能力評估將量化不同智能體的能力, 在人機協作[82]中機的能力評估中占據重要的地位. 另一方面, 人機對抗中人對機的主觀評價正逐漸成為一種智能體能力評估的重要補充. 下面將分別介紹相關的挑戰性問題.

非傳遞性策略綜合評估. 多維ELO算法[48]在傳統ELO的基礎上通過對非傳遞維度進行顯式的近似, 可以緩解非傳遞性策略勝率的預測問題, 但是因為其依賴于ELO的計算方式, 也就存在ELO本身對于對抗順序依賴以及如何有效選取基準智能體等問題. 對于兵棋推演這一面臨嚴重策略非傳遞性的問題, 目前的評估技術基于ELO或者改進的ELO, 仍然具有較大的局限性.

智能體協作中的單個智能體評估. 基于經典的ELO算法, Jaderberg等人[38]提出啟發式的算法進行協作智能體中單個智能體的評估, 但是該算法依賴于智能體能力的可加和假設, 因此難以應用于兵棋推演環境, 即算子之間的能力并非線性可加和. 另一方面, TrueSkill算法通過引入貝葉斯理論, 實現了群體對抗中的某一選手的評估, 但是其對時間不敏感, 且往往會因為對抗選手的冗余出現評估偏差. 因此如何設計有效的評估算法實現協作智能體中的單個智能體的評估是當前的主要挑戰之一.

定性評估標準體系化. 當前一些評估評測平臺人為抽象了包括“武器使用”、“地形利用”等概念實現人機對抗中人對智能體的打分評測. 上述概念主要啟發于指揮決策中對指揮官能力的刻畫, 因此是面向現實應用下智能體能力評估的重要維度[83, 84]. 但是, 如何將智能體的評估體系與作戰指揮中的能力維度進行對齊仍然是開放的問題, 需要指揮控制領域的研究人員與博弈決策領域的研究人員共同協作.

4. 兵棋智能決策技術展望

為緩解兵棋推演智能決策技術存在的挑戰性問題, 部分研究者另辟蹊徑, 引入了新的理論、抽象約簡問題等以應對兵棋推演的人機對抗.

4.1 兵棋推演與博弈理論

博弈理論是研究多個利己個體之間的策略性交互而發展的數學理論, 作為個體之間決策的一般理論框架, 有望為兵棋人機對抗挑戰突破提供理論支撐[85-88]. 一般來說, 利用博弈理論解決兵棋推演挑戰, 需要為兵棋推演問題定義博弈解, 并對該解進行計算. 兵棋推演作為典型的兩人零和博弈, 可以采用納什均衡解. 但是, 納什均衡解作為一種相對保守的解, 并非在所有場合都適用. 考慮到兵棋推演的嚴重非對稱性, 納什均衡解對于較弱勢方可能并不合適. 因此, 如何改進納什均衡解(例如以納什均衡解為基礎進行對對手剝削解的遷移)是需要研究關鍵問題.

在博弈解求解這一問題上, 早期相對成熟的求解方法包括線性規劃、虛擬自我對局[57]、策略空間回應oracle (Policy space response oracle)[89]、Double oracle[58]、反事實遺憾最小化[90] 等. 但是, 上述納什均衡解(或近似納什均衡解)優化方法一般只能處理遠低于兵棋推演復雜度的博弈環境, 而目前主流的用于星際爭霸等問題的基于啟發式設計的改進自博弈迭代往往缺乏對納什均衡解逼近的理論保證. 因此, 針對兵棋推演這一具有高復雜度的不完美信息博弈問題, 如何將深度強化學習技術有效地納入可逼近納什均衡解的計算框架、或者提出更有效/易迭代的均衡逼近框架, 來實現兵棋推演解的計算仍然是開放性問題.

總的來說, 盡管博弈理論為兵棋推演的人機對抗挑戰提供了理論指導, 但是, 如何借助于該理論實現兵棋推演人機對抗的突破仍然是相對開放性的問題, 需要研究者們進行更深入的研究.

4.2 兵棋推演與大模型

近些年來, 大模型(預訓練模型)在自然語言處理領域獲得了飛速發展[91, 92]. 例如, OpenAI于2020年發布的GPT-3模型參數規模達到1750億[93], 可以作為有效的零樣本或小樣本學習器提升自然語言處理下游任務的性能, 如文本分類、對話生成、文本生成等. 中國科學院自動化研究所在2021世界人工智能大會上發布了三模態(視覺、文本、語音)大模型, 具備跨模態理解與生成能力⑦. 一般來說, 預訓練的大模型, 作為通用人工智能的一種有效探索路徑, 需要海量的數據支撐訓練, 但具有重要的學術研究價值與廣闊的應用前景.

兵棋推演提供多種任務/想定, 理論上可以有大量不同的訓練環境, 深度強化學習與環境交互試錯的學習機制使得大模型訓練的數據問題得以緩解. 但是, 如何針對兵棋推演訓練大模型, 使得其在不同的兵棋對抗任務中可以快速適應仍然面臨各種挑戰, 如圖11所示. 首先, 兵棋推演沒有如自然語言處理任務較為通用的訓練目標或優化目標, 尤其是不同規模的對抗任務差異較大, 因此如何設計該大模型的優化目標是需要解決的首要問題, 這涉及強化學習中動作空間、獎勵空間等多項要素的深入考慮.

圖 11 兵棋推演大模型訓練挑戰

另一方面, 兵棋推演包含異質且異步協同的智能體, 不同任務下需要協同的智能體在數量、類型上有所差距, 這就要求大模型在訓練過程中既能解耦合不同智能體之間的訓練, 同時可以建立有效的協同機制實現智能體之間的協同. 盡管, 可以采用智能體共享獎勵、神經網絡獨立訓練的框架, 但是該設計過于簡單, 難以有效實現智能體協同時的信用分配等挑戰性問題. 總的來說, 如何設計大模型下多智能體訓練以適應具有較大差異的兵棋推演任務是需要重點研究的問題之一.

最后, 在自博弈過程中進行大模型的訓練, 需要適應不同規模(兵棋推演天然存在連隊級、群隊級、旅隊級等規模)以及同規模下不同任務難度的對抗, 這對大模型的訓練提出了新的挑戰. 自步學習[94]的范式提供了智能體由易到難的逐步訓練框架, 但如何定義兵棋推演不同任務難度是啟發式的. 另一方面, 要求智能體在更難任務訓練時不能遺忘對已訓練任務的記憶, 這也需要持續學習[95]等前沿技術手段的引入.

4.3 兵棋推演關鍵問題抽象

星際爭霸完整游戲的人機對抗挑戰突破之前, 研究者們設計了包括敵方意圖識別[96]、微操控制(多智能體協同)[97, 98, 99]等在內的關鍵子任務以促進智能決策技術的發展. 針對兵棋推演問題, 為引領技術突破進而反饋解決兵棋人機對抗挑戰, 迫切需要對兵棋推演中的關鍵問題進行抽象、約簡, 在保證約簡的問題能夠表征原始問題的重要特征前提下, 在約簡的問題中進行求解.

基于上述考慮, 本文提出兩個約簡問題, 即排兵布陣與算子異步協同對抗. 需要指出的是, 問題約簡過程中不可避免對兵棋推演環境等要素的規則進行簡化, 甚至脫離兵棋推演本身的任務或者目的導向屬性, 但是相關問題的約簡與抽象一定程度反映了兵棋推演智能體決策的核心挑戰, 將極大促進研究者對相關問題的研究.

排兵布陣. 排兵布陣反映了決策者在未知對手如何決策的前提下采取何種規劃或者兵力選擇可以最大化自己的收益, 代表性環境如爐石傳說卡牌類游戲, 即如何布置自己的卡牌以在后期積累優勢獲得最大化利益. 其挑戰在于未知對手如何規劃的條件下實現己方規劃, 該問題因為缺乏驗證環境, 目前研究較少.

兵棋推演的前期, 紅方或者藍方基于未知的對手信息布局自己的兵力, 該布局一定程度決定了后期的對抗成敗. 該過程因為缺少環境的顯式反饋, 無法度量何種排兵布陣能夠最大限度利用地形、能夠最大化攻擊等, 也就難以評估何種兵力布置最優. 基于上述原因, 本文設計如圖12所示的排兵布陣簡化問題. 具體來說, 在一個簡化的地圖中, 紅方與藍方各占有一部分區域進行兵力放置, 同時紅方與藍方之間具有一定距離間隔, 考慮紅方與藍方不能移動且兵力放置之后自動進行裁決.

圖 12 排兵布陣問題示意圖

需要指出的是, 上述簡化環境對兵棋推演本身做了極大的簡化, 更多是從算法研究的角度出發. 在研究兵力放置過程中, 可以由簡單到復雜進行調整, 以契合兵棋推演問題本身, 包括兵棋推演的目的加入(如奪控)、地形設置(如高程)等.

算子異步協同對抗. 算子協同對抗是多智能體相關問題的重要組成部分, 目前相關領域已經開放了大量的智能體協同對抗環境, 如星際爭霸微操、捉迷藏等[22-24]. 值得注意的是, 目前絕大多數環境, 不同算子之間協同是同步的, 即智能體的動作執行周期一致. 以此為基礎, 研究者提出了大量的算法實現有效的算子間協同[100, 75, 101]. 但是當不同智能體的動作執行周期不一致時, 便導致異步協同問題, 兵棋推演的對抗便屬于異步協同對抗, 當前的研究因為相關環境的缺乏相對較少.

兵棋推演中后期, 紅方與藍方進行對抗, 為評估智能體的接敵能力實現算子之間異步動作的有效協同, 本文設計算子異步協同對抗簡化問題. 如圖13所示, 在一個簡化的相對較小的地圖上, 不考慮復雜地形、復雜交戰規則以及兵棋推演任務約束等因素, 紅方與藍方在各自的起始位置出發進行對抗, 算子可選動作包括機動(6個方向與停止)與射擊(對方算子). 由于不同算子機動能力的差異, 重點為領域提供多智能體異步協作的評估環境.

圖 13 算子異步協同問題示意圖

同排兵布陣問題, 簡化更多從驗證算法性能的角度入手. 在研究算子異步協同對抗過程中, 可以對任務的難度進行調整, 如對地圖進行調整, 包括設置高程、增加特殊地形等.

為了促進上述問題的深入研究, 在約簡問題設計上, 本文將陸續公開:

1)與OpenAI Gym⑧一致的領域認可的環境接口, 供智能體與環境交互進行策略的學習;

2)提供不同難度等級的內置智能體, 供算法研究人員進行算法驗證與算法間比較;

3)完全開放的底層源碼, 進而支持自博弈等主流技術以及人機對抗.

5. 結論

星際爭霸人機對抗挑戰的成功標志著智能決策技術在高復雜不完美信息博弈中的突破. 星際爭霸之后, 迫切需要新的人機對抗環境以牽引智能決策技術的發展. 兵棋推演, 因其非對稱信息決策以及隨機性與高風險決策等挑戰性問題, 潛在成為下一個人機對抗熱點. 本文詳細分析了兵棋推演智能體的研究挑戰尤其是其相比于其他博弈環境的獨特挑戰性問題, 在此基礎上了梳理了兵棋推演智能決策技術的研究現狀, 包括智能體研發技術框架以及智能體評估評測技術, 之后指出了當前技術的挑戰, 并展望兵棋推演智能決策技術的發展趨勢. 通過本文, 將啟發研究者對兵棋推演關鍵問題的研究, 進而產生實際應用價值.

致謝

中國科學院自動化研究所的周雷博士在“兵棋推演與博弈理論”章節給出了博弈理論解決兵棋推演問題的研究思路, 在此感謝周雷博士的建議.