一種用于兩人零和博弈對手適應的元策略演化學習算法

吳哲 李凱 徐航 興軍亮,

兩人零和博弈作為博弈論中的一種基礎模型,由于其兼具理論性完備、適應性廣泛的特點,一直是人工智能領域所關注的重要問題.近年來,得益于以深度學習[1?2]為代表的一系列新技術的發展與應用以及計算能力的飛速提升,兩人零和博弈中的一些比較困難的問題諸如圍棋[3?7]、德州撲克[8?9]等已經取得了突破性的進展[10].

圍繞納什均衡解概念[11]進行求解是目前解決兩人零和博弈問題主流的研究思路,由此產生的一系列均衡求解算法也得到了廣泛的研究與發展.但是隨著人們研究的進一步深入以及現實世界關于對抗問題的廣泛關注[12],這種均衡求解方法暴露出越來越多的局限性.首先,對于狀態空間較大的復雜博弈,尋找納什均衡解的計算成本很高[13].例如求解德州撲克中的納什均衡策略需要在整個博弈樹上不斷迭代求解,該過程需要計算集群巨大的算力支持和TB 級別的存儲空間[14].同時,近似納什均衡解的質量并不理想[14],在兩人無限注德州撲克中的近似納什均衡解可以被簡單的局部最佳響應策略剝削.其次,求解納什均衡解的前提條件是假設玩家雙方是完全理性的,但是現實世界中更多面對的是非完全理性的競爭對手.這也就意味著采取均衡解要放棄剝削非理性對手帶來的巨大潛在收益[15].

對手建模是均衡求解法之外的另一種在兩人零和博弈中被廣泛研究與使用的方法[16?18].與逼近納什均衡解來保證最壞情況下的收益不同,對手建模方法通常需要基于歷史數據來為當前的對手策略擬合一個顯式模型,再根據該模型預測對手下一步的動作,以此作出更有針對性的決策來獲取超額收益.但這種方法也有明顯的局限性: 一方面,對手建模類方法由于需要歷史交互數據來刻畫一個顯式的對手模型,因此交互數據的質量和規模都會影響模型刻畫的準確性和時效性;另一方面,對手建模類方法所刻畫的對手模型具有很強的針對性,一旦對手策略發生了改變,往往需要從零開始重新建立一個模型.

正是考慮到兩人零和博弈領域內現有方法的局限性,本文創新性地提出一種在博弈過程中可以快速適應未知風格對手的元策略演化學習算法.本方法不以納什均衡為求解目標,因此可以獲取遠超均衡解的收益,同時又避免了對手建模類方法對大量交互數據的需求.圖1 展示了本方法的訓練流程.

圖1 本文提出的元模型訓練方法Fig.1 The meta-model＇s training process

本文的研究重點和貢獻可以被總結為三點.1)將元學習思想引入兩人零和博弈過程,訓練一個元模型用于未知風格對手的快速適應.這種快速適應的能力得益于元學習的策略更新方式,經過訓練后的元模型收斂于參數空間內的一類初始點.該類初始點具有快速更新至目標參數空間的良好性質.2)提出了一種基于進化算法的種群訓練方法用于提升元模型的泛化能力.由于元模型需要在參數空間內充分探索以尋找到最佳的初始點,因此本文提出一種基于進化算法的種群訓練方式來為元模型的訓練不斷提供對手.一方面,該種群可以借助進化算法中的交叉(Crossover)、變異(Mutation)算子來不斷探索更大的參數空間.另一方面,進化算法中的選擇(Selection)算子通過不斷篩選出優質對手來進一步提升元模型的博弈水平.3) 提高了種群演化算法的訓練效率.元模型在訓練期間會周期性地補充到種群中去,實現了進化算法多樣性和梯度算法高效性的充分結合.

1 相關工作

1.1 均衡解求解

在兩人零和博弈中,若存在這樣的一個策略組合: 每個策略都是其他策略的最佳響應,那么這一策略組合便被稱為納什均衡策略組[19].在這個策略組中,每一個玩家都不可能因為單方面改變自身策略而增加收益.而且在任何一個有限兩人零和博弈中都必然存在納什均衡[19?20].因此,求取近似納什均衡解來保證最壞情況下的收益,成為了目前兩人零和博弈問題下主流的解決方案.

該類方法目前大多以自博弈 (Self-play)框架為基礎[11],其中比較典型的做法是神經虛擬自博弈算法 (Neural fictitious self-play,NFSP)[21].Deep-Mind 的Lanctot等[22]基于Double oracle 算法提出一種更加通用的均衡求解框架PSRO (Policyspace response oracles),該算法可以看作是NFSP思想的進一步拓展.Zinkevich等[23]則創新性地提出了一種同樣具有良好理論保證的近似均衡求解算法: 反事實遺憾最小化算法(Counterfactual regret minimization,CFR),其成為此后構建德州撲克智能體的主流算法[24?26].MCCFR[27]和DeepCFR[28]則分別結合了蒙特卡洛采樣和深度神經網絡近似的方法來克服傳統CFR 方法中采樣效率低、存儲空間大的問題.但目前這一系列方法仍然面臨以求解均衡策略為目標所帶來的計算成本高和策略保守無法最大化剝削非理性對手的固有缺點.

1.2 對手建模

與追求納什均衡的目標不同,對手建模方法旨在通過為對手建立模型來推測其意圖,從而作出針對性決策以獲取更高收益.常用的對手建模方法可分為顯式建模、策略匹配、遞歸推理等幾大類[16].

顯式建模類方法[17]通常基于與對手的大量交互數據針對性地構建一個模型,以推測對手的決策意圖.這類方法的缺點是對交互數據的需求量大,且需要不斷更新當前的對手模型.策略匹配類方法[29?30]通常會建立一個離線數據庫,在與對手的交互過程中為其匹配策略庫中的相似模型,來預測對手的動作.這類方法雖然省去了從頭建立對手模型的步驟,但是受限于離線數據庫的規模,只針對特定對手有效.遞歸推理類方法[31]考慮的是嵌套推斷這類更復雜的決策過程 (即我讓你以為我在思考什么).這類方法的隱患是在詐唬對手的同時可能會被更狡猾的對手反利用.與以上這些需要大量交互數據來建立對手模型的方法不同,本文提出的方法并沒有顯式建立對手模型,而是通過不斷采樣不同風格的對手進行訓練,以此獲得快速適應的能力.

1.3 元學習

元學習目前已逐漸成為機器學習領域內一個新的研究熱潮,解決的是讓智能體學會去學習(Learning to learn) 的問題.該方法在訓練過程中充分利用各個采樣任務中獲得的經驗,將其泛化到新環境或新任務.元學習目前已經在監督學習領域中的分類和回歸任務以及強化學習領域的新任務適應問題中取得了一系列進展[32?33].本文借助元學習快速適應的特點來克服傳統博弈求解方法中存在的策略適應性差、交互數據需求量大等弊端.

目前針對元學習的研究主要集中于以下三類:1)距離度量類方法[34],通過學習不同任務之間的距離度量,從而達到在距離空間內快速適應新任務的目標;2)基于循環神經網絡的元學習類方法[35],通過建立記憶系統來匹配面對新任務的決策模式;3)與模型無關的元學習類方法[32],主要通過訓練得到一個比較好的網絡初始化參數來加速適應過程.本文主要結合第三類元學習方法試圖在決策空間內找到一組比較好的網絡初始化權重,從而在面對未知對手時可以進行快速適應.

1.4 演化算法

演化算法 (Evolutionary algorithm,EA)[36]作為一類通用的搜索優化算法,在人工智能領域得到了廣泛應用.該算法的一大優點是可以在不掌握目標函數及其梯度信息的情況下,僅依靠迭代評估可行解的好壞來逼近全局最優解.一些最新的群體智能算法通過引入演化算法的思想,已經解決了多類博弈問題[37?39].Jaderberg等[38]于2019 年發表在Science 上的工作就是借助種群訓練(Populationbased training)[37]的思想對博弈過程中的群體模型進行超參數優化.它使用選擇算子將當前模型權重替換為種群中表現最好的模型權重,并使用變異算子對模型超參數進行隨機擾動.DeepMind 的Liu等[39]將演化算法應用到了合作類型的多智能體足球博弈場景中,通過配合使用選擇、交叉、變異算子,使智能體在足球博弈場景中學會了復雜的合作策略.

2 兩人零和博弈中的快速適應算法

本文所提出的適用于兩人零和博弈的快速適應算法會在本節內進行詳細介紹.本算法的目標在于,克服傳統兩人零和博弈中均衡求解法不具備策略適應性和對手建模方法對數據量要求大的固有缺陷.本算法創新性地將元學習方法引入博弈求解過程,并使用種群演化算法[40?41]為元模型的訓練提供對手模型,克服了元學習方法依賴手工設計訓練任務的弊端.

算法整體架構如圖1 所示.本算法主要包含元模型訓練器 (見第2.2 節)和對手種群演化池 (見第2.3 節) 兩個模塊.元模型訓練器的目標是優化得到一個元模型,該元模型在決策空間內擁有良好的策略初始化.在面對未知風格對手時,能夠通過少量交互來快速適應其策略,使得元模型收益盡可能大.為了提升元模型的泛化性,對手種群演化池在訓練過程中不斷提供訓練樣本給元模型.與傳統元學習方法在圖像分類、檢測等任務中需要手工設計任務集不同,對手種群通過進化算法為元模型的訓練提供了一套自動的課程學習[42]方案.

2.1 問題建模

為確保整個算法的通用性和可拓展性,元模型M使用深度神經網絡πθ進行建模,用于訓練的對手P被建模為π?.由此元模型與對手交互的過程可以建模為兩人馬爾科夫博弈[5]過程:

其中,S為狀態空間,AM和AP分別代表雙方玩家的動作空間,系統的狀態轉移方程定義為T:S ×AM ×AP →?(S′),玩家的獎勵函數Ri:S×AM×AP ×S′ →R 取決于當前狀態S、下一個狀態S′以及雙方玩家的動作.在給定一個策略已知且固定的對手P的情況下,上述定義的兩人馬爾科夫博弈G就會退化為單人馬爾科夫決策過程 (Markov decision process,MDP)[43]:

2.2 元模型訓練算法

其中,α代表學習率,代表元模型πθ面對固定對手Pi的損失函數,γ代表折扣因子,MPi用于表示更新后的元模型.為了提升元模型的泛化能力,中的對手策略不斷被采樣并完成上述梯度更新過程.算法最終的目標是使得元模型可以快速適應每一個當前對手Pi并最大化平均獎勵,即目標函數為:

其中,β代表元模型參數更新的步長.

針對該優化目標進行求導后得到:

其中,τ′代表適應性參數θ′采集的軌跡.該優化形式與MAML (Model-agnostic meta-learning)類元學習算法[32]的優化目標一致.結合Finn 給出的理論保證[45],只需選用任意一個可進行自動微分的機器學習框架(例如PyTorch[46])對上述優化形式進行實現,訓練后的元模型理論上就可以獲得快速適應新對手的能力.由于式(7)中二階梯度項的存在,算法整體的計算復雜度約為 O (d2),d代表博弈空間的問題維度.為了降低算法復雜度,本算法可采取MAML類元學習算法的通用實現方式,將二階梯度項忽略,此時算法復雜度降低為 O (d),且整體效果不會受到較大影響[32].

總結來看,使用上述目標函數進行梯度更新的訓練算法旨在找到這樣一個元模型: 僅需與對手進行少量交互(即只進行幾次梯度更新)就可以學會如何適應對手策略并剝削(獎勵最大化).元模型訓練算法的具體步驟詳見算法1.種群演化對手策略生成(Opponent strategy generation,OSG)模塊將在第2.3 節進行詳細闡述.

算法1.元模型訓練算法

該算法主要包含兩個階段,首先通過種群演化算法得到訓練用的對手策略集合,然后再通過元模型訓練算法得到快速適應性.第2.3 節對種群演化算法進行描述.

2.3 種群演化對手生成

在迭代開始前,首先隨機初始化一個對手策略的種群B={P1,P2,···,PN},此時元模型策略M也會被補充到對手種群中,用于引導對手策略在演化初期快速提升博弈水平,提高訓練效率.

種群策略的初始化完成以后,使用元模型來評估當前種群中每一個對手策略的適應度.適應度F被形式化為對手策略Pi與元模型在一個對局步長內獲得的累計獎勵總和:

評估結束后,選擇 (Selection) 算子基于當前種群策略的適應度,以?的比例挑選出適應度靠前的部分個體組成精英團體E.對手種群池中剩余部分的策略 (B ?E) 通過與精英團體E內的策略進行交叉 (Crossover) 以及自身策略的變異 (Mutation),來獲得提升策略適應度的機會.精英團體E內策略的基因會完整保留到下一代種群中,不會受到交叉和變異算子的影響,這使得種群內部表現優異的基因(網絡權重)可以不斷延續下去.

本節所提出的種群演化算法通過不斷自動生成對手策略來為元模型提供訓練數據.選擇算子的應用使得對手種群的博弈水平逐步提升,從而為元模型的訓練構建了一個課程學習的范式.同時,交叉和變異算子的應用豐富了種群策略的多樣性.用于訓練的對手策略風格越多樣,元模型的泛化能力就越強.算法2 詳細描述了種群演化對手生成的具體步驟.

算法2.種群演化對手生成算法

本文中種群策略池的規模設定主要考慮了環境復雜度和算法收斂速度兩個方面,統一設置為10.精英團體E占種群策略的比例?根據不同問題在0.2～0.5 內取值.變異率m utprob根據不同問題在0.1～0.3 內取值.變異強度 m utstrength設置為0.1,即對應10%的高斯噪聲.

3 實驗評估

本節通過構建一系列對比實驗,來驗證本文所提出的元模型訓練算法在兩人零和博弈中的有效性.第3.1 節給出了用于實驗評估的仿真環境和基線算法介紹.第3.2 節給出了算法訓練及測試過程中的詳細參數設置.第3.3 節對實驗結果進行對比分析.

3.1 評估環境與基線算法

3.1.1 評估環境

本文所提出的算法在Leduc 撲克、兩人有限注德州撲克 (Heads-up limit Texas Hold＇em,LHE)以及復雜連續空間下的仿真器RoboSumo[33]上都進行了實驗驗證.這些環境是目前兩人零和博弈研究中被廣泛使用的驗證平臺,其中兩人有限注德州撲克和RoboSumo 均具有較高的環境復雜度,同時又分別屬于離散和連續動作問題,因此能夠充分評估算法的適應性和可拓展性.

環境具體介紹如下: Leduc 撲克通常包含兩種花色(紅桃、黑桃),每種花色有三個牌型(J,Q,K),共計6 張牌組成.整個游戲分為兩輪,每個玩家在第一輪分別會得到一張私有牌,第二輪則只發一張公共牌.當有一方玩家的私有牌與公共牌組成對子時,則獲得勝利;若無人組成對子,牌力高的一方獲得勝利.勝利的一方贏取所有籌碼,牌力相同時平分場上所有籌碼.在發牌前,每個玩家會被強制下注1 個籌碼,接下來的兩輪下注中,每輪最多允許有兩次加注,籌碼量被分別固定為2和4.

兩人有限注德州撲克是現實世界德撲玩家常用的一種撲克玩法.LHE 共包含52 張牌,游戲總共有4 個階段,每個玩家在翻牌前階段 (Pre-flop) 會得到2 張私有牌,在后續的翻牌階段 (Flop)、轉牌階段 (Turn)、河牌階段 (River) 會分別發出3 張、1 張、1 張,總共5 張公共牌.玩家在每個階段的可選動作包括 “過牌 (Check)”、“加注 (Raise)”、“跟牌(Call)”、“棄牌 (Fold)”.若無人棄牌則牌力高的一方獲得游戲勝利.

RoboSumo 是一個高維連續狀態動作空間下的仿真機器人環境.本文中所用的RoboSumo-ants 仿真了兩只螞蟻在圓形擂臺上角力的競爭型博弈過程.游戲獲得勝利的條件是,將另一方推出擂臺或掀翻.如果達到時間限制,該局比賽則以平局結束.該環境中每個玩家的狀態空間由自身的可觀測信息和對手的部分可觀測信息組成.玩家自己的可觀測信息包括自身關節的位置、速度和接觸力,對手的部分可觀測信息主要包括對手關節的位置.

3.1.2 基線算法

為驗證元模型訓練算法的優越性,本文與前面所介紹的求解兩人零和博弈中的經典方法進行了實驗對比.具體使用的基線算法如下.

1) CFR[23].反事實遺憾最小化算法CFR 被廣泛應用于求解兩人零和博弈中的近似納什均衡解.2) DRON (Deep reinforcement opponent network)[17].DRON 方法將對手建模算法與深度強化學習相結合,在交互過程中推斷對手類型并進行剝削.3) EOM (Explicit opponent modeling)[16].EOM是一種顯式對手建模方法,通過收集大量對手交互數據來擬合對手模型并進行針對性求解.4) NFSP[21].NFSP 通過結合虛擬自博弈與深度強化學習算法,來求取兩人零和博弈中的近似均衡解.5) MAML[32].元學習算法MAML 已經被成功應用于各種回歸、分類以及單智能體強化學習任務.6) Oracle[17].Oracle 代表了在兩人零和博弈中針對當前對手的近似最佳響應.7) 本文算法 +PPO.“本文算法 +PPO”代表將元模型的求解器由TRPO (Trust region policy optimization)[47]替換為計算效率更高的近端策略優化算法 (Proximal policy optimization,PPO)[48].8) 本文算法 ?EA.“本文算法 ?EA”代表在本文所提出算法中移除掉種群演化模塊,僅使用元模型更新算法.9) EA.EA 算法僅使用種群演化算法[36],不使用元模型的更新方式.

上述基線算法中的1)和4)是兩人零和博弈中求取近似納什均衡解法的代表性方法,基線算法2)和3)是兩人零和博弈對手建模解法中隱式建模和顯式建模的代表性方法,基線算法5)是單智能體領域元學習解法的代表性方法.本文將MAML 訓練所需的任務分布替換為對手策略分布,在每次迭代中,從中采樣一批對手進行交互并完成元模型的更新.由于真實博弈過程中的對手策略分布并不會被玩家預先知曉,因此MAML 類算法僅能依靠隨機生成的對手進行訓練.基線算法6)代表了理想情況下的最佳響應.因此,使用上述基線算法與本文所提出的元模型訓練算法進行對比,可以充分驗證算法的有效性.

3.1.3 實驗參數設置

本文使用帶有GAE (Generalized advantage estimate)[49]的TRPO 算法[47]作為元模型的求解器,也可選用PPO[48]或其他任意梯度優化算法.模型架構為兩層全連接網絡,激活函數選擇ReLU[50].本文所有的訓練與評估都在一塊NVIDIA TITAN Xp GPU 上完成,算法通過PyTorch 框架[46]進行部署.詳細實驗參數見表1.本文中報告的所有實驗結果都是在設置3 個隨機種子運行后得到的平均值.表2和表3 中撲克類環境的結果在每個隨機種子下重復對打10 000 局后統計得出,代表的是該統計結果下的標準差.圖2 中RoboSumo 的實驗結果在每個隨機種子下重復對打500 局后統計得出.圖3內曲線部分的陰影代表了3 個隨機種子下統計結果95%的置信區間.圖 4 的實驗結果為對打10 000 局后統計得出.圖5 內曲線部分的陰影含義與圖3 相同.

圖2 本文算法與基線算法在RoboSumo 中的對比Fig.2 Comparison of our method with the baseline algorithm in RoboSumo

圖3 消融實驗Fig.3 Ablation study

表2 本文算法與基線算法在Leduc 環境中的對比Table 2 The average return of our method and baseline methods in Leduc

表3 本文算法與基線算法在LHE 環境中的對比Table 3 The average return of our method and baseline methods in LHE

3.2 實驗結果與分析

3.2.1 元模型有效性驗證

本節用于驗證元模型訓練算法的有效性.首先,對訓練得到的元模型的快速適應性進行驗證.模型的適應過程被限制為與當前對手只進行三步梯度更新,通過統計每步梯度更新后的平均收益來觀測當前元模型的適應能力.其次,快速適應后的元模型被進一步用于與各類基線算法進行對比,通過統計與各類對手10 000 局對戰的平均收益來觀測各類算法的表現情況.在不同任務上的具體實驗參數設置見表1.

表1 不同環境下的實驗參數設置Table 1 Hyperparameters settings

需要注意的是,適應過程中的各類對手都沒有用于元模型的訓練.同時,本文還提供了一系列涵蓋不同風格以及不同實力的博弈對手,用于元模型和各類基線算法的公平對比.Leduc 撲克中各類對手具體包括: 1) Random 對手會隨機采取各類動作,博弈水平相對較弱;2) Call 對手總是采取跟牌動作,具有明顯的博弈風格;3) Bluff 對手會根據手牌強弱進行動作并在一定概率內進行詐唬,博弈水平接近人類玩家;4) CFR 對手是通過基線方法中的CFR 訓練得到的,屬于近似納什均衡策略,很難被剝削;5) NFSP 對手是通過基線方法中的NFSP 算法訓練得到的.在規模更大的兩人有限注德州撲克LHE 中,本文提供了三類更加符合人類玩家特征的對手模型,分別為比較激進的LA 型對手,相對激進并有一定概率詐唬的TA 型對手,以及相對保守的LP 型對手.這三類對手策略基于專業牌手常用的德州撲克手牌計算器PokerStove 的緩存矩陣所計算出的獲勝概率進行決策.因此這三類對手策略的博弈水平更加貼近真實人類玩家.RoboSumo 中的對手策略 A gentZooN(N=1,2,3) 為Bansal等[51]使用PPO 算法訓練后開源的預訓練模型,其中N的不同取值代表了訓練時采用的不同隨機種子.這三類開源的預訓練對手模型的博弈水平較高且呈現出了不同博弈風格,已經被作為基線模型廣泛使用[33].

如表2 所示,元模型在面對Leduc 撲克中各類風格的對手時,都表現出了快速的適應性.在面對實力較弱或者表現出明顯博弈風格的對手 (比如Random、Call 等類型) 時,元模型可以快速更新到該類對手的近似最佳響應.在面對風格多變或者近似均衡這類很難去發現弱點進行剝削的對手時,元模型也可以快速提高對局中的平均收益.因此實驗表明,通過結合元學習的策略更新方式,元模型在策略空間內更新到了擁有快速適應性的初始化區域,從而在面對未知風格對手時可以快速提升自身博弈水平.表3 展示了元模型在LHE 中也具有類似的快速適應性.圖2 展示了適應后的元模型相比RoboSumo 中內置的基線算法的平均勝率,可以看出適應后的元模型相比于基線模型的勝率得到了大幅提升.

表2、表3 還展示了元模型與各類基線算法的實驗對比情況.可以看出,元模型相比于對手建模類算法DRON和EOM,在同樣的交互數據量以及更少的適應步驟 (三步梯度更新) 內獲取了更高的平均收益.需要注意的是,本實驗中的DRON和EOM 方法使用了與元模型相同的交互數據對對手進行建模,但是并沒有對梯度更新步驟進行限制.這也與本文前面提到的對手建模類算法需要大量交互數據擬合相對準確的對手模型的特點相一致.此外,元模型相比于近似均衡類求解方法 (NFSP和CFR),在面對實力較弱的對手時能夠大幅提升平均收益.而傳統的元學習類MAML 算法僅在面對Random 類對手時具有快速適應性,這是由于MAML類算法在訓練過程中缺乏高質量對手,僅依靠隨機生成的對手進行訓練,無法在參數空間內進行高效探索.

本文所提出的種群演化對手生成算法,正是通過選擇、交叉、變異算子實現了兼顧難度與風格的對手自動生成.元模型通過不斷與這些自動生成的對手進行訓練,逐步提升了自身策略的適應性.第3.2.2 節對該對手生成模塊的作用機制展開了詳細實驗驗證.最后,與基線算法 “本文算法 +PPO”的實驗結果對比也說明了本算法具有與模型無關(Model-agnostic) 的性質[32],可以與任何梯度優化算法兼容.

3.2.2 種群演化模塊驗證

本節主要針對第2.3 節中提出的種群演化對手生成算法的作用機制展開實驗驗證.主要包括: 1) 算法消融性實驗;2) 演化自動生成的對手策略是否具有多樣性;3) 超參數設置對實驗性能的影響.

圖3 展示了種群演化模塊對元模型實驗性能的影響,三條曲線代表了不同模型在Leduc 撲克中面對Random 對手的表現.“本文算法”代表本文所提算法;“本文算法 ?EA”代表移除種群演化模塊后,僅使用元模型更新算法;“EA 算法”代表僅使用種群演化算法來生成對手,不使用元模型的更新方式.

由圖3 可以看出,元模型的更新方式和種群演化模塊對于實驗性能的提升都有顯著作用.僅使用種群演化算法的EA 模型性能提升緩慢,而且方差比較大,這是因為進化算法更新過程中并不使用梯度信息,采樣效率較低.當不使用種群演化模塊時,元模型只能通過自博弈的方式進行策略更新,會導致元模型在參數空間內探索受限,泛化性較差.當同時使用元模型更新方式和種群演化算法時,模型的性能大幅提升,而且表現更加穩定.這是因為種群演化算法通過選擇、交叉、變異算子的共同作用,自動生成了兼顧難度與風格的對手數據,從而提升了元模型的泛化性與適應性.同時,元模型通過與這些對手進行不斷交互,提升了自身快速適應性.在Leduc 撲克、兩人有限注德州撲克和RoboSumo中面對不同種類對手進行的消融實驗,更加充分地驗證了本文所提出的種群演化模塊和元模型更新算法的有效性,具體實驗結果見表2、表3和圖2.

圖4 可視化了種群演化算法自動生成的對手策略.這4 幅圖分別對應Leduc 撲克環境下對手策略種群里4 個對手模型的動作概率分布.每幅圖中的動作概率分布均由元模型與相應對手模型對打10 000局后統計得出.橫坐標代表了Leduc 中的不同牌型,縱坐標代表了持有該牌型時各個動作的概率.圖4下方的4 個圖例分別代表了Leduc 中4 個不同的可選動作.從圖4 中可以看出,自動生成的對手策略覆蓋了更大的策略空間,而且由于選擇、交叉、變異算子的共同作用,自動生成的對手策略并不僅僅關注策略上的差異性,還兼顧了模型的性能.例如,在拿到較強牌力的手牌時,棄牌的概率相應減小.

圖4 種群演化模塊生成的對手策略Fig.4 Visualization of the styles of the strategies

超參數的選擇對實驗性能也會造成一定影響,表1 中詳細展示了通過網格搜索確定的一組超參數.其中,“評估局數”的設置會對實驗性能產生較大影響.圖5 顯示了評估局數的不同取值對元模型性能的影響.當評估局數較少時,模型性能出現了劇烈震蕩;隨著評估局數的增加,模型的方差逐漸變小,性能也隨之提升.這是因為該參數代表了對手生成模塊中選擇算子評估對手模型性能的對局數量,這直接影響了子代種群的模型性能.通過實驗發現,評估局數較多時挑選出的子代種群有利于模型性能的提升,在本文的三類實驗場景中,50～100是一個比較合理的范圍,能夠兼顧評估速度與質量.

圖5 超參數設置對模型性能影響Fig.5 Effect of hyperparameter settings

4 結論

本文提出了一種針對兩人零和博弈的快速適應算法,該算法克服了均衡求解方法中策略過于保守以及對手建模方法泛化性差的弊端.本算法主要分為對手自動生成和元模型更新兩個階段.在對手生成階段,通過種群演化算法中的選擇、交叉和變異算子來自動生成兼具不同風格與博弈水平的對手策略.在元模型更新階段,模型通過不斷與這些對手進行交互并結合元學習的參數更新方式,來不斷提升模型面對不同博弈對手的泛化能力.

在Leduc 撲克、LHE 以及RoboSumo 中的實驗結果表明,本文算法在與對手進行少量交互的情況下,使用同一個元模型針對不同風格的對手都實現了快速適應.相比于均衡類算法,本文算法能夠實現對次優對手的剝削;相比于對手建模類算法,本文算法避免了顯式建模過程,提高了模型的泛化能力.消融實驗與可視化實驗的結果顯示了本文算法所使用的對手演化生成模塊與元模型更新算法的有效性.如何將本文算法應用到更大規模的游戲(例如,無限注德州撲克)以及如何結合均衡類算法的優點來保證元模型在適應過程中的安全性,是本文未來可以繼續研究的方向.