一種針對德州撲克AI 的對手建模與策略集成框架

張 蒙 李 凱 吳 哲 臧一凡 徐 航 興軍亮

計算機博弈與人工智能的發展一直相輔相成.自人工智能(Artificial intelligence,AI)學科誕生伊始,計算機博弈研究就是AI 技術發展創新的沃土,AI 領域的先驅圖靈和香農都曾研發過計算機博弈程序[1].用于測試機器是否具有 “智能”的圖靈測試,其實現形式就是通過人和機器之間博弈進行的.智能博弈一直都是衡量AI 技術發展水平的重要評價準則,AI 發展歷史上的主要里程碑事件都與計算機智能博弈游戲研究相關.1962 年6 月機器學習之父阿瑟·塞繆爾的西洋跳棋程序戰勝美國著名職業選手尼雷、1997 年5 月IBM 公司的超級電腦 “深藍”戰勝國際象棋大師卡斯帕羅夫等,都是AI 學科早期發展歷史上重要的里程碑事件.

近年來,計算機的存儲與計算能力不斷提升,以及各類數據的爆炸式增長與積累,以人工神經網絡為主要技術工具的深度學習方法[2-3],因其強大的數據擬合能力與泛化能力,使其在語音識別[4]、圖像識別[5]和自然語言處理[6-7]等領域都取得了突破性進展,成功推進了AI 領域由感知智能到認知智能的跨越.如今,AI 領域正在經歷從認知智能邁向決策智能的過程,以強化學習與深度學習相結合的深度強化學習方法[8-10],在圍棋博弈領域取得了重大突破并成功打敗人類頂尖選手[11-15],為完美信息場景下的博弈決策問題提供了有效的方法指導.而智能體如何在其所處狀態信息不完全已知的情況下做出準確的決策,是目前AI 領域面臨的核心問題.因此,不完美信息博弈場景下智能決策問題的研究和解決,是AI 取得突破的核心前沿領域和重要驅動力.

游戲是一種虛擬的實驗環境,具有可控損失的優點,實驗成本低且允許實驗失敗.博弈游戲本身又存在很多難點,具有決策空間復雜、實時高動態、信息不完美等特點[16-17],能夠為智能決策問題研究提供一種良好的算法實驗環境,是AI 技術絕佳的實驗研究平臺.不完美信息博弈游戲是指智能體在游戲中只能夠獲得自身的游戲狀態以及公共游戲信息,而無法掌握全部的局面信息[18],例如在德州撲克[19-20]、麻將[21]、斗地主[22]等游戲博弈過程中對手的手牌不可見,因此獲得的局面信息是不完美的,這也使此類博弈游戲的研究和解決更具挑戰性.

現實生活中,在軍事、經濟、商業、網絡安全等實際場景中的大多問題,均屬于不完美信息博弈問題.此類問題的研究和解決往往受到實際環境的成本制約,而將其轉化為對博弈游戲抽象模型的求解尋優問題可以大幅降低所需實驗成本.因此,以不完美信息博弈游戲為載體的研究,能夠為現實問題的解決提供有效的方法論.

本文選擇德州撲克游戲作為對不完美信息博弈的主要研究和實驗對象,以演化學習方法[23]和深度神經網絡相結合完成對智能體的訓練,通過在線的對手風格建模和種群策略集成的方法使智能體能夠適應對手策略變化,最終實現一種輕量高效并對解決不完美信息博弈問題具有通用性的博弈求解框架.

1 德州撲克游戲

德州撲克游戲規則明晰、玩法多樣且趣味性很強,是最受歡迎的撲克游戲之一.德州撲克游戲具有信息不完美、狀態和動作空間巨大、對手不確定等特性[24],是不完美信息博弈游戲的典型代表,集中反映人工智能領域的許多核心問題,其研究對于整個人工智能領域的發展有著極其關鍵的影響,得到國內外諸多研究團隊的極大關注并取得諸多進展.

1.1 游戲規則介紹

德州撲克游戲通常采用52 張撲克牌,參與游戲的玩家人數通常限制在2～ 9 人.游戲分為翻牌前、翻牌、轉牌和河牌4 個階段,在翻牌前階段開始時,每名玩家將獲得2 張只有自身能夠看到的 “底牌”,之后的3 個階段開始時桌面上會分別發出3 張、1 張和1 張 “公共牌”.在經過各階段游戲多次的 “加注/全壓”、“跟注/過牌”、“棄牌”等押注圈操作后,若牌局仍存在至少兩名玩家沒有棄牌,游戲進入 “攤牌”階段,該階段各玩家在自己的2 張底牌和5 張公共牌中挑選5 張形成牌組,按照圖1 所示的德州撲克游戲牌型大小規則分出勝負,贏家獲得桌面上全部籌碼.

圖1 德州撲克游戲牌型大小規則Fig.1 Texas Hold＇em card rules

本文主要針對兩人無限注的德州撲克游戲(Heads-up no-limit Texas Hold＇em,HUNL)進行方法的實驗和驗證.HUNL 是指只有兩個玩家參與的德州撲克游戲,游戲雙方按照游戲位置分為大盲位和小盲位.小盲位在翻牌前階段首先做動作,其余階段均為大盲位首先做動作.每局游戲結束時雙方交換游戲位置并且重置總籌碼量,然后開始下一局游戲.

1.2 相關解決方法介紹

HUNL 方面的研究主要經歷從博弈樹模型搜索優化逼近納什均衡策略,到深度神經網絡擬合納什均衡策略,再到深度強化學習自我博弈優化的發展過程.

Slumbot[25]是博弈樹模型搜索優化方法的典型代表,其核心是利用反事實遺憾最小化(Counterfactual regret minimization,CFR) 算法[26]在HUNL 中逼近納什均衡策略.Slumbot 主要算法流程為:首先根據HUNL 規則構建出游戲的博弈樹原始模型;然后利用抽象技術[27]將相似游戲狀態進行聚類,從而縮減博弈樹規模,降低算法計算規模;最后在縮減過的博弈樹上進行蒙特卡洛反事實遺憾最小化(Monte Carlo counterfactual regret minimization,MCCFR)算法[28]迭代,最終收斂得到近似的納什均衡策略.這種方法嚴重依賴于游戲博弈樹模型和人類專家知識進行抽象,并且CFR 算法需要對博弈樹上約6.31×10164個狀態結點進行不斷地采樣遍歷和迭代優化從而收斂得到納什均衡策略,即使經過模型縮減后該方法仍需要耗費大量的計算和存儲資源,例如Slumbot 在訓練階段需要耗費大于105個CPU 小時的計算資源和TB 級別的存儲資源來分別迭代優化和離線保存策略.此外,CFR 算法最終收斂得到的是一種靜態的離線策略,所以在對手策略變化時存在無法動態適應和剝削對手等問題.

DeepStack[29]是利用深度神經網絡擬合納什均衡策略方法的典型代表,其核心主要是利用CFR+算法[30]迭代計算出部分游戲狀態對應的納什均衡策略,然后使用神經網絡對采樣到的 “狀態-策略”樣本進行擬合,并利用神經網絡的泛化能力,估計得到沒有采樣過狀態的策略信息.此類方法的性能主要依賴于采樣到的樣本數量和神經網絡擬合精度,比如DeepStack 需要在每個階段游戲中至少采樣106種游戲狀態,并在博弈子樹上進行至少103輪算法迭代從而得到神經網絡訓練樣本,這至少需要耗費106個CPU 小時和103個GPU 小時的計算資源,因而該方法需要極其巨大算力支持,導致其運算經濟性較差,并且訓練樣本的存儲也需要耗費大量的存儲資源.此外,在與對手實際交互過程中,DeepStack 每次決策均需要在博弈子樹上進行算法迭代以求解均衡策略,存在決策速度和算法性能的矛盾性問題.

神經虛擬博弈(Neural fictitious play,NFSP)[31]是基于深度強化學習自我博弈優化方法的典型代表,其核心思想是通過自我博弈對戰提升策略性能,算法訓練過程中博弈雙方每次固定其中一方策略,利用強化學習算法通過在線博弈優化另一方策略,交替進行獲得策略提升.此類基于強化學習的方法需要不斷采樣大量的交互數據并保存到經驗回放池[32-33],從而給神經網絡的訓練優化提供樣本.NFSP 在訓練時需要至少采樣約3×107組交互樣本,并且強化學習訓練存在樣本利用率問題.此方法目前僅適用于小規模博弈問題和簡化的德州撲克游戲中,在大規模和多人博弈問題中存在算法穩定性差和無法快速收斂到納什均衡解等問題.

上述HUNL 的主流求解方法均是為得到近似的納什均衡策略,從而在理論上保證自己不輸.但是對于德州撲克這種具有巨大狀態和動作空間的不完美信息博弈游戲,求解近似的納什均衡策略不僅在計算層面是非常困難的,而且計算結果與真實納什均衡之間的差異也很難衡量.此外,由于在HUNL 中納什均衡策略的靜態特性,智能體只是根據已知信息使用固定響應作為自身策略,忽略了對手行為對自身策略的影響,所以無法根據對手的實際特點發現和利用對手弱點,進而實現自身收益最大化.

此外,演化學習在德州撲克游戲中得到過成功應用,ASHE[34]是此類方法的代表.ASHE 首先根據人類玩家知識定義具有特定策略規則的對手,然后通過智能體種群同時與不同對手進行對打和演化訓練,從而不斷提升種群對特定對手的適應度.由于ASHE 博弈水平與訓練對手的種類及策略水平相關性較強,因此智能體訓練時需要面對博弈類型盡量豐富的對手,而該方法中對手智能體是根據常見玩法策略經過人工精心設計得到,使該方法對人類專家知識的依賴較為嚴重.并且在博弈過程中,ASHE 需要依賴一種規則的決策算法得到其策略,無法端到端完成該過程.

2 方法框架

針對第1.2 節中各類HUNL 主流求解方案所存在的缺點,本文設計了不完美信息博弈求解框架流程圖(見圖2).本框架將演化學習方法和深度神經網絡相結合,通過在線的對手風格建模和種群策略集成使智能體能夠適應對手策略的變化.

圖2 不完美信息博弈求解框架整體流程Fig.2 Overall process of the imperfect information game solving framework

本框架整體分為智能體的離線訓練和在線博弈2 個階段,主要包含以下4 個步驟:

1)首先通過智能體與已知風格的對手博弈交互,完成智能體策略神經網絡參數的種群演化訓練,獲得能夠剝削不同風格對手的克制策略網絡;

2)然后利用不同克制策略網絡重新構建智能體,并分別與其對應克制對手博弈交互,通過在交互過程中收集對手信息來構建出對手特征庫;

3)在線博弈階段,首先對未知對手在線建模,并與對手特征庫進行博弈風格的相似度度量,得到博弈風格度量矩陣;

4)然后根據博弈風格度量矩陣對各種克制策略網絡的輸出進行加權集成,從而獲得集成策略與對手進行博弈交互.

2.1 離線訓練階段

智能體的離線訓練階段主要是為了獲得能夠剝削已知風格對手的策略網絡并構建對手特征庫.本階段首先設計含有不同博弈風格的對手池和能夠在線建模對手的智能體結構,然后通過智能體與對手池中的不同對手進行博弈交互,從而利用種群遺傳算法對智能體策略網絡參數進行演化訓練.

1)博弈風格建模與對手池設計

為保證集成策略在面對不同對手時均具有一定適應性,每種克制策略應盡量均勻分布在整個策略空間中,因此對手池應為策略網絡的種群演化訓練提供具有不同典型博弈風格的對手策略.

根據上述要求,首先對德州撲克游戲人類專業玩家的常見策略和博弈風格進行充分調研和總結,最終從德州撲克游戲代表性玩法的 “策略激進度”和 “手牌松緊度” 兩個維度出發,在整個策略空間中定義不同風格的對手策略從而構建對手池.“策略激進度”評價玩家在不同牌局狀態時動作的概率分布情況,激進類玩家即使在游戲局勢不足夠有利時,選擇加注動作的概率也比較高,而在相同情況下保守類玩家棄牌的概率較高.“手牌松緊度”評價玩家所玩手牌的牌力范圍,若玩家只在手牌牌力較大時繼續游戲,手牌較小時選擇棄牌,則表示其博弈風格比較 “緊”,如果玩家即使在手牌牌力相對較小時也將游戲進行下去,則表明其博弈風格比較 “松”.

根據上述博弈風格的度量方法得到了如圖3 所示的對手池策略空間,并將不同風格的玩家策略歸類為 “松-弱”、“松-兇”、“緊-弱”和 “緊-兇”四類博弈類型.“松-弱”和 “松-兇”型玩家具有較 “松”的手牌松緊度,其手牌牌力范圍一般大于40 %,“緊-弱”和 “緊-兇”型玩家則具有較 “緊”的手牌松緊度,其手牌牌力范圍一般小于40 %.“松-弱”和“緊-弱”型玩家具有偏保守的策略激進度,表現出跟注動作較多和加注動作較少等特點,“松-兇”和“緊-兇”型玩家的策略則偏激進,表現出加注動作較多和跟注動作較少等特點.

圖3 對手池策略空間與博弈風格類型定義Fig.3 The opponent strategy space and game styles definition

2)智能體結構設計

為獲得能在博弈交互過程中建模對手的智能體,本文設計了圖4 中右圖所示的智能體結構,該智能體主要由特征提取器和策略網絡2 個模塊組成.

圖4 離線訓練階段算法流程及智能體結構Fig.4 The offline training process and the agent structure

特征提取器主要在博弈交互過程中從游戲的游戲牌局上不斷收集與對手的歷史交互信息,然后統計獲得對手在不同牌局狀態時的特征信息,并作為對手特征輸入智能體策略網絡,從而完成對手建模任務.德州撲克是一種參與人之間動作具有先后順序的動態博弈過程,適合使用博弈樹對該類型的博弈進行表示.而特征提取器就是一種與博弈樹類似的樹形數據結構,樹中結點代表不同的游戲牌局狀態,結點之間連接的邊代表不同的動作,每個結點上都將維護對手歷史博弈交互信息的特征值.

牌局狀態主要是由兩名玩家交互的動作序列決定的.特征提取器的構建是根據游戲歷史動作序列進行動態 “擴充”和 “更新”的過程.例如:當特征提取器已經存在動作序列 “加注300/加注600/跟注”,如果另外兩局游戲的動作序列分別為 “加注300/加注600/跟注”和 “加注300/加注600/加注900”,那么對于已有的狀態結點 “跟注”,特征提取器將只對該路徑結點記錄的特征進行更新.而對于不存在的狀態結點 “加注900”,特征提取器將擴充自身結點.由于德州撲克游戲動作空間巨大,為了控制樹形結構的規模,對游戲雙方均進行了動作抽象,并按照底池倍數將加注的籌碼量映射到以下7 個范圍內:(0,0.125)、(0.125,0.375)、(0.375,0.75)、(0.75,1.25)、(1.25,2.0)、(2.0,4.0)、(＞4.0).

智能體策略網絡主要是完成 “狀態特征-動作策略”的端到端映射過程,結構如圖4 所示,由對手特征網絡、游戲特征網絡和策略輸出網絡三個模塊組成,其中對手和游戲特征網絡均是由多層長短期記憶網絡(Long short-term memory,LSTM)所構成,圖中每個LSTM 區塊均對應其中一層,而策略輸出網絡則是由包含多個隱含層的全連接神經網絡組成.

博弈過程中智能體每次做動作時,首先根據當前的游戲牌局提取出游戲特征,并根據牌局狀態得到在特征提取器中對應結點位置,從而讀取得到結點上維護的對手特征.然后將游戲特征和對手特征構建為特征向量,并分別輸入對應的特征網絡進行特征編碼.最后,2 種特征網絡輸出的編碼信息 “拼接”后輸入策略輸出網絡,策略輸出網絡輸出智能體策略并與對手博弈交互.詳細特征及編碼方式見第3.1 節特征定義部分.

3)種群遺傳算法

在德州撲克這種對抗性的回合制不完美信息博弈游戲中,由于對手策略未知并且動態變化,導致深度強化學習算法在這種具有較高隨機性環境中的訓練難以收斂.遺傳算法通過模擬生物界 “優勝劣汰,適者生存”的進化法則,在整個解空間內不斷搜索具有最高博弈性能的智能體策略并繁衍新的種群,使得種群適應度得到穩定的提高,最終以輕量化的算法框架獲得良好的收斂效果.本文基于遺傳算法的思想對智能體種群進行演化訓練,訓練核心算法流程如圖4 所示,主要包括以下3 個步驟:

a)選擇.選擇是為了篩選并 “淘汰”種群中適應度較低的個體,適應度較高的個體將存活至下一代種群.本步驟首先將種群每個智能體分別與所指定的對手進行博弈交互,然后對每個智能體的適應度進行評估,最后種群內所有智能體將根據其適應度高低進行排序,并按照一定的比例(生存率)淘汰部分智能體.智能體適應度函數為:

其中,f(i) 為智能體i的平均適應度,m為對手數量,eij為智能體i針對對手j的收益,nj為歸一化因子,當智能體的最大收益小于一個大盲注(BB)時,將nj設置為大盲注以避免歸一化錯誤.

b)交叉.交叉是為了將種群內的優勢基因(策略網絡參數)進行 “繁殖”得到下一代個體.為充分保留種群優勢基因,本文將經過選擇并生存的智能體進行分層,其中高于生存智能體平均適應度的部分個體將獲得 “繁殖權”進行交叉,其余智能體則直接進入下一代種群中并再次進行評估和選擇.這種分層方法在有效保留優勢基因的同時,能夠充分排除游戲隨機性因素對智能體性能的影響.按照適應度對具有 “繁殖權”的智能體進行排序,適應度較高的智能體分別與每個適應度較低的智能體 “配對”,“配對”雙方進行基因交叉過程,從而不斷得到子代智能體基因,直到種群恢復至原始規模.

進一步,提取出 “配對”智能體的策略網絡參數并分別將其拼接成參數向量作為交叉的2 種父代基因.基因交叉過程如圖5 所示.對于圖中2 組父代基因,將其分割成基因片段并按照其所屬位置對雙方的每組基因片段都按照智能體的適應度比例f(1)和f(2)進行隨機選擇,最終將所選擇的基因片段組合成為新的交叉基因.

圖5 智能體基因交叉變異示意圖Fig.5 Crossover and mutation

c)變異.變異為子代基因增加了一定的隨機性,從而提高對種群整體適應度的探索能力.變異過程遵循高斯分布,并且隨著種群演化的進行,突變率和突變強度(即高斯分布的均值和標準差)線性下降.具體操作步驟是,首先按照突變率對圖5中交叉基因的基因片段進行隨機選擇,所選中基因片段將加上服從該突變率和突變強度的高斯噪聲從而得到子代基因,進而最終獲得下一代種群.

上述步驟在訓練過程中反復進行.隨著不斷地種群演化迭代,種群的整體適應度將不斷提升,最終保存最后一代種群中適應度最高的基因作為智能體策略網絡的參數.算法詳細流程如算法1 所示.

4)對手特征庫構建

為了在線博弈階段實現對手博弈風格的度量識別,需要對不同對手的歷史交互信息進行收集,從而構建對手特征庫.對未知對手的博弈風格進行度量時,對手特征庫主要用作比對的 “模板”.為此,本文使用訓練得到的各類克制策略網絡重新構建智能體,并分別與所克制的對手再次進行博弈交互,最終分別保留其特征提取器構建對手特征庫.

2.2 在線博弈階段

本階段設計了一種對種群策略加權集成的博弈求解框架.該框架在對未知對手的博弈風格度量后,能夠根據對手的博弈風格及時調整自身的集成策略,并且在建模置信度較低時,智能體也能使用基礎策略網絡的輸出作為安全策略,從而避免智能體出現重大決策失誤.該框架主要分為以下2 個模塊:

1)對手博弈風格度量模塊

本模塊通過對未知風格對手與對手特征庫中已知風格對手的博弈風格特征進行相似度度量,從而估計未知風格對手的博弈類型相似度.該模塊具體結構如圖6 所示.

圖6 對手博弈風格度量模塊Fig.6 Measurement module of opponent＇s style

算法1.種群遺傳算法

具體地,智能體與未知風格對手博弈過程中不斷收集歷史交互信息并構建特征提取器,從而逐漸提高對手建模可信度.在當前牌局狀態對應的對手博弈風格特征達到置信度要求后,智能體將收集本游戲階段內歷史軌跡上所有結點的對手博弈風格特征向量序列,并與對手特征庫中不同的已知風格對手的特征向量序列進行 “距離”度量,從而得到未知風格對手與已知風格對手的博弈風格度量矩陣:,(i=1,2,···,8;p=1,2,···,k).其中,k表示已知風格對手的數量,i表示智能體分別位于8 種不同游戲階段(i=1,2,3,4 分別表示小盲位的4 個游戲押注階段,i=5,6,7,8 則表示大盲位的4 個游戲階段),表示未知風格對手在游戲階段i與已知風格對手p之間博弈風格特征向量的相似度.相似度度量函數為:

其中,m表示當前牌局狀態對應游戲歷史軌跡上的結點數量(即對手博弈風格特征向量數量),aij表示未知風格對手在游戲階段i的第j組博弈風格特征向量,表示已知風格對手p的對應博弈風格特征向量,n表示特征向量維度,fl(aij)表示未知風格對手特征向量aij的第l種特征,fl()表示已知風格對手p對應特征向量的第l種特征.

2)克制策略集成模塊

受到集成學習思想的啟發,本節設計了如圖7所示的種群策略集成模塊,該模塊中各個策略網絡的輸出是能夠剝削不同風格類型對手的策略,而這些策略只是整個策略空間的一些局部最優解,因此在面對未知對手時并不具備適用性.本文設計的策略集成方法可以將不同克制策略網絡的輸出通過博弈風格度量矩陣D進行加權集成,從而構建集成策略πint.策略加權集成方式:

圖7 種群策略集成模塊Fig.7 Integration module of population strategies

在與未知風格對手博弈交互的初始階段,由于對手的特征收集累積量較少,因此對手建模的置信度較差,此外對于從未經歷或者經歷次數較少的牌局狀態也會出現該問題.為避免因上述問題而導致決策失誤,本節訓練得到一個基礎策略網絡,該策略網絡是由智能體與對手池中所有已知風格對手對打和種群演化訓練得到的,其輸出作為在對手建模置信度較低情況下的安全策略,從而保證智能體博弈性能的 “下限”.

3 實驗與結果分析

3.1 實驗設置

1)游戲參數設置與性能評價方式

本文所有實驗均在2 人無限注德州撲克游戲環境中進行.其中,玩家每局總籌碼量為 2×104,小盲注和大盲注分為50 和100,每局游戲結束后籌碼重置并且雙方交換位置.為評判智能體策略好壞,游戲雙方對打 2×104局游戲并使用德州撲克AI 研究領域最為常見的平均每局千分之一個大盲注(Millesimal big blind per hand,mbb/h)作為智能體博弈性能的評價指標.

2)特征定義及編碼

本文收集了10 種特征作為策略網絡的輸入,具體的名稱、含義及編碼方式如下:

a)訪問頻率:游戲歷史中訪問特征提取器中結點的頻率,代表玩家在不同牌局狀態下所有動作的頻率分布信息;

b)棄牌率:特征提取器中當前結點為根的子樹上因對手棄牌使游戲結束的頻率;

c)攤牌率:特征提取器中當前結點為根的子樹上雙方玩家均未棄牌而使游戲進入攤牌階段的頻率;

d)期望牌力:特征提取器中當前結點為根的子樹上攤牌時對手的平均牌力;

e)同花或順子:當前公共牌對手同花或順子的概率;

f)對牌數量:當前公共牌中對牌的數量;

g)游戲輪次:當前游戲所處輪次;

h)手牌牌力:自身當前手牌期望牌力;

i)對手加注額:對手加注的總籌碼比例;

j)自身加注額:自身加注的總籌碼比例.

其中,前4 種特征由特征提取器直接獲得并組成得到對手特征向量,特征向量(例如:[0.143 2,0.483 3,0.652 8,0.118 9])中每一維度分別對應表示:訪問頻率、棄牌率、攤牌率和期望牌力.而游戲特征則由上述其余6 種特征對應組成,表示當前游戲公共信息和智能體私有信息.

對于對手博弈風格度量模塊,本文需要獲取特征提取器中本階段游戲所對應的歷史路徑.對于其中每個結點本文設計了11 種對手博弈風格特征fl(aij)(l=1,2,···,11) 組成對應的特征向量aij,除了上述所列舉的攤牌率和期望牌力,還包括當前牌局狀態對手選擇棄牌、跟牌/過牌、加注動作的概率(即特征提取器在當前牌局狀態對應結點下每條邊的訪問頻率),由于加注動作被抽象為7 種,因此特征提取器每個結點上都將得到一個11 維的特征向量aij.

3)對手設置

為給智能體策略網絡種群演化訓練提供對手,本文從圖4 對手池策略空間中采樣得到8 種具有已知風格的對手智能體 (O1,O2,···,O8),每種對手智能體的博弈風格及詳細定義如表1 所示.表1 中前4 個對手 (O1,O2,O3,O4)是4 種風格最為明顯的智能體,策略較為簡單因而具有較高的利用率,在種群演化訓練過程中比較容易被剝削.而表1 中后4 個對手 (O5,O6,O7,O8)策略相對復雜且利用率適中,有利于在種群演化訓練過程中提高智能體策略的博弈水平.

表1 對手智能體博弈風格及定義Table 1 The opponents＇play styles and definitions

為驗證智能體在對手策略不斷變化時的適應能力,本文設計了一個可以進行策略動態切換的對手智能體Orandom,該智能體從對手池策略空間中每隔500 局游戲隨機采樣一種對手策略作為自身策略.

4)實驗參數設置

表2 為策略網絡結構和遺傳算法訓練的相關參數,表2 中數據是經過對算法訓練的收斂速度和最終平均適應度水平綜合考慮后確定的,各類策略網絡均是使用表中所設置參數值進行種群演化訓練得到.

表2 策略網絡結構與訓練參數Table 2 Policy network structure and the training hyper-parameters

基礎策略網絡通過種群智能體與定義的8 種對手交互訓練得到,訓練過程中對種群的100 個智能體進行300 代演化訓練.每個智能體與單個對手每次對打 104種牌局,并對牌局進行手牌交換后重新對打,從而排除牌局隨機性對性能的影響.因此,種群中每一個智能體均與每個對手對打 2×104局游戲后進行適應性評估和選擇過程.最終第300 代種群中適應度最高的智能體策略網絡保存為基礎策略網絡.

克制策略網絡是通過智能體只與一種已知風格對手進行種群演化訓練得到的,訓練過程中也對種群的100 個智能體進行了300 代的種群演化訓練,然后保存第300 代中適應度最高的智能體策略網絡作為一種克制策略網絡.因此對于對手池中定義的8 種不同風格對手,最終得到8 個能夠分別克制對應對手的策略網絡.

為構建對手特征庫,首先利用每種克制策略網絡重新構建智能體,然后與其克制對手對打 105局游戲,最后將特征提取器分別保存并構建對手特征庫.

表2 中策略輸出網絡隱含層神經元數量和種群生存率2 種參數對算法的穩定性和收斂水平具有較大影響,為確定上述兩種參數的合適取值,本文在基礎策略網絡訓練過程中分別對2 種參數進行了網格搜索,參數對比結果見圖8 和圖9.

圖8 策略輸出網絡隱含層神經元數量對種群平均適應度的影響Fig.8 The influence of the hidden neurons in policy output network on population fitness

圖9 種群生存率對種群平均適應度的影響Fig.9 The influence of population survival rates on population average fitness

從圖8 中數據對比可知,策略輸出網絡隱含層神經元數量的取值會對種群會的平均適應度收斂水平造成一定影響.神經元數目在50 到300 之間取值過程中,隨著神經數量的增加適應度水平也在不斷提升.當神經元數量達到一定數量后(即300 左右及以上),適應度水平并不會隨之一直提升,而是最終達到一定的水平并趨于穩定.從圖9 可明顯看出,種群生存率對平均適應度的影響出現與圖8 類似的變化趨勢.說明當所選的參數值超過一定 “閾值”之后,系統性能的收斂水平對參數變化并不敏感.因而,在保證算法收斂水平的前提下盡量使用較少的參數量,根據網格搜索的結果最終分別將上述2 種參數設置為300 和0.25.

3.2 消融實驗

1)基礎策略網絡訓練

基礎策略網絡演化訓練時智能體一直與多個對手博弈交互,由于對手具有不同的博弈風格和水平,因此訓練過程中與不同對手的交互先后順序可能會對種群的整體適應度產生較大影響.為最大化種群適應度,本文設計了一種三階段的訓練策略并與其他三種進行對比實驗,得到如圖10 所示的種群平均適應度變化曲線,其中:訓練策略1 中智能體種群在300 代的演化訓練時一直同時與表1 中的8 種對手交互;訓練策略2 中智能體種群在前100 代演化訓練中一直與前4 種對手交互,后200 代則只與后4 種對手交互;訓練策略3 中智能體種群在前100 代演化訓練中一直與前4 種對手交互,后200代則與8 種對手交互;訓練策略4 中智能體種群在前100 代訓練中一直與前4 種對手交互,中間100代只與后4 種對手交互,最后100 代則同時與8 種對手交互.

圖10 不同訓練策略對種群平均適應度的影響Fig.10 The influence of different training strategies on population average fitness

訓練策略1 中智能體需要一直同時面對8 種不同風格對手進行對打訓練,經過190 代左右的種群演化訓練,其平均適應度最終收斂在0.1212 左右.該訓練策略在訓練過程中與另外兩種訓練策略相比表現出更大的 “震蕩”幅度,而且需要更多的演化代數才能使種群的平均適應度提升并趨于平穩.

訓練策略2 采用二階段的分層訓練方法,第1階段中種群在第30 代左右平均適應度得到快速提升并收斂穩定在0.8515 左右;在第2 階段中,由于所面對的對手利用率較低,因此種群在第101 代時的策略無法有效剝削此類對手,使其平均適應度也迅速降低至-1.5645.經過第2 階段的訓練,種群在第130 代左右平均適應度最終穩定到0.3312 左右.該訓練策略 雖然與訓練策略1 相比能夠明顯提高種群平均適應度收斂速度,但最終的平均適應度卻明顯低于訓練策略4.這表明每次只面對其中4 種對手的分層訓練策略可能會使種群在第2 階段的訓練后陷入局部最優,從而失去對前四種對手的克制性.

訓練策略3 也采用兩階段的分層訓練方法,是在策略2 的基礎上更改第2 階段所面對的對手得到,即后200 代同時面對8 種對手.從曲線對比來看,策略3 最終收斂水平與策略2 并無太大差異,但值得注意的是策略3 在第2 階段訓練開始時的震蕩幅度明顯強于策略2,訓練過程中收斂速度和穩定性明顯低于策略2.此外,策略3 與策略4 相比最終并不能達到相近適應度水平.

訓練策略4 采用三階段的演化訓練方案,在前200 代的種群演化訓練過程中其與策略2 的曲線變化趨勢相似,種群的平均適應度最終穩定在0.665 4左右,與另外兩種策略相比最終適應度得到較大提升.這表明訓練策略4 的三階段分層訓練方式使種群具有較快的收斂速度并且避免陷入局部最優問題,最大化地探索了種群的博弈性能.

由圖10 可以看出,訓練策略4 能使種群平均適應度較快地收斂到更高的水平,因此本文將其作為基礎策略網絡的種群演化訓練策略.

2)在線博弈階段消融實驗

為驗證在線博弈階段種群策略集成框架中不同模塊的作用,本節對其進行消融實驗,結果見表3,其中Slumbot1http://www.slumbot.com/是世界計算機撲克大賽中2 人無限注德州撲克組冠軍智能體,代表納什均衡策略智能體,并作為本實驗對照組,表3 中每組實驗數據均表示不同智能體面對某種對手時的評估性能,例如智能體Abase與對手O1的評估結果是1 000 mbb/h,表示經過 2×104局游戲的對打評測后,結果表明Abase博弈性能優于O1.

Atar為克制策略智能體,其構建分別使用了不同的克制策略網絡,主要用于分別評估每種克制策略網絡對其所克制對手的剝削性能.因此,表3 中第1 行評測數據均是某種對手與對應克制策略智能體的評估結果,比如第1 行中第1 組數據代表對手O1的克制策略博弈性能為999.92 mbb/h.由測評數據可以看出,各克制策略均能有效克制對應類型的對手.由于克制策略只能針對一種對手,所以此類評測數據可視為本文提出的種群策略集成框架智能體在面對對手池中已知對手時的性能 “上界”.

表3 消融實驗結果(mbb/h)Table 3 Ablation study results (mbb/h)

Abase為基礎策略智能體,其構建只使用基礎策略網絡,用于單獨評估基礎策略網絡的性能.測試數據表明Abase在單獨面對已知的不同對手時均具有相對良好的博弈性能,這驗證了基礎策略網絡所采用的三階段分層種群演化訓練方式,既能保證種群博弈性能得到快速提升,又能避免因為不同訓練階段面對不同對手所造成的克制策略 “遺忘”問題.此外,Abase與動態策略對手Orandom的評測結果為5 105.38 mbb/h,這說明即使對手策略變化時基礎策略也具有一定的適應性,所以基礎策略網絡的輸出可以作為建模置信度較低時的安全策略.

Aave為克制策略網絡靜態集成的智能體,其策略是直接將各個克制策略網絡的輸出進行 “加和”得到的(即博弈風格度量矩陣為均勻分布),主要用于探究在沒有安全策略和對手博弈風格度量矩陣的情況下直接進行策略集成時智能體的性能表現.從Aave、Atar及Abase的實驗結果對比可以看出,這種直接對局部最優解 “加和”的集成方法,失去了克制策略原有的剝削性能,使智能體即使在面對已知對手時也無法保證其博弈性能.此外,Aave與動態策略對手Orandom的評測結果為-1 068.44 mbb/h,說明在面對對手變化時,Aave由于沒有對手相似度的度量模塊,導致其不具有對動態策略的適應性.

Aint為沒有基礎策略作為安全策略的動態集成策略智能體(即在Aave的基礎上加入對手博弈風格度量模塊),用于評價在只使用對手博弈風格度量并進行策略集成時智能體的性能表現.通過Aint與Aave的實驗數據對比可以發現,在使用博弈風格度量矩陣將克制策略進行加權集成后,Aint的博弈性能相比Aave得到顯著提升,這說明Aint的集成策略保留了各克制策略的剝削性能.在面對策略隨機變化的對手Orandom時,Aint的測評結果明顯低于其在面對8 種已知對手時的平均性能,這說明在對手策略變化時,Aint由于由于沒有基礎策略作為安全性保障,因此容易因建模置信度低而造成決策失誤.

A*為本文提出的種群策略集成框架所對應的智能體.相比于智能體Aint,A*雖然在面對已知對手時性能表現略低于Aint,但是因其擁有基礎策略網絡模塊作為安全策略,使得在面對動態策略對手Orandom時A*的性能均明顯優于Aint和Abase,這體現基礎策略網絡可以有效減緩可能出現的決策失誤問題.此外,從分別面對Orandom時的評測結果來看,A*的性能為6 359.36 mbb/h,明顯高于Slumbot 對應的3 387.13 mbb/h,這說明即使在面對對手策略變化時A*相比傳統的納什均衡策略也能夠更好地剝削對手,保證自身能夠有良好的博弈性能.

3.3 性能對比

1)算法博弈性能

為評估智能體A*的實際博弈性能,本節將其與第1.2 節所述4 種方法、知識AI 和Orandom分別對打測評,結果見表4,其中知識AI 是5 種基于人類專業玩家策略的規則智能體,該類智能體具有動態的策略和完備的人類常見打法,可以模擬人類玩家行為,表格中知識AI 的評測數據均是與五種人類規則AI 對打 2×104局游戲后的平均結果.

從表4 可以看出,智能體A*、ASHE、NFSP 和知識AI 分別在面對目前具有最強性能的Slumbot 和DeepStack 時,評測統計結果說明這種利用CFR 算法求解的近似納什均衡策略極難被剝削.智能體A*在面對知識AI 時評測統計結果達到229.64 mbb/h,與ASHE 和Slumbot 分別對應的-13 mbb/h 和52.43 mbb/h 相比得到大幅度性能提升,另外在面對Orandom時智能體A*同樣具有最好的性能表現.

表4 博弈性能對比結果(mbb/h)Table 4 Performance comparison results (mbb/h)

為評估不同方法智能體在博弈過程中策略的動態變化情況,本文記錄了智能體A*、ASHE、Slumbot 和DeepStack 分別與Orandom測評過程中的收益變化情況,博弈性能變化曲線如圖11 所示.數據從第5 000 局游戲開始,每隔500 局游戲統計一次前5 000 局的平均博弈性能得到的.可以看出,Slumbot 和DeepStack 這種典型的納什均衡策略智能體,在面對動態策略對手Orandom時由于策略的靜態性使其不具備動態適應性.智能體A*和ASHE 能夠不斷收集交互數據從而建模對手,使其均具有一定的適應能力,但由于智能體A*能夠通過策略集成策略框架來根據對手實際風格特征針對性地適應對手,使其相對ASHE 具有更加強大的動態適應性.

圖11 對打測評過程中博弈性能變化Fig.11 The change of game performance in the evaluation process

上述實驗可以有效說明,本文所提出的博弈求解框架,在博弈交互過程中可以不斷建模對手從而獲得一定的適應性,并相比已有方法能夠大幅提升面對不斷變化的對手策略時的博弈性能.實驗結果也驗證納什均衡策略所存在的嚴重限制智能體剝削性問題,使其在對手策略變化時無法最大化自身收益.

2)算法輕量性

為評估本文所提出博弈求解框架的輕量性,本節對比不同算法分別在訓練和測評2 個階段的資源需求,包括存儲資源需求、計算資源需求以及測評的動作響應時間.詳細對比數據如表5 所示,表5數據均來自原始論文以及復現時的實際數據.

表5 算法輕量性對比Table 5 Light-weight comparison

對于訓練階段,從存儲資源需求來看,Slumbot 和DeepStack 由于需要使用CFR 相關算法求解并保存納什均衡策略,因此需要500 GB 以上的存儲資源,NFSP 則需要50 GB 以上的內存資源將不斷采樣到的交互數據保存到經驗回放池,而智能體A*和ASHE 僅需要約30 GB 的存儲資源來離線保存牌力數據.從算法計算資源需求來看,智能體A*略高于ASHE 的計算資源需求(小于2 倍),僅需一臺無GPU 的常規計算機使用約2000 個CPU小時的計算量,遠低于Slumbot、DeepStack 和NFSP 這種需要大規模計算機集群進行分布式計算求解的智能體.在對打測評階段,智能體A*對每一局游戲的實際牌力進行在線解算,在不犧牲響應速度的前提下有效降低對存儲資源的需求,使其對存儲和計算資源的需求量均小于其他智能體.最終,智能體A*能夠以平均小于0.1 秒的動作響應時間進行博弈交互,遠低于DeepStack 和人類玩家.

綜上所述,本文提出的博弈求解框架能夠在較少計算和存儲資源的情況下保證自身博弈性能和響應速度,相比其他已知求解方法更具有輕量性優勢.

4 結論

本文提出了一種針對兩人無限注德州撲克這種典型大規模不完美信息博弈問題的博弈求解框架,具有輕量高效并能快速識別和適應對手策略變化等優點.該框架首先基于演化學習方法對智能體進行種群演化訓練得到剝削不同風格對手的克制策略網絡,然后對未知風格對手進行在線建模和風格度量,最后采用種群策略集成最大化剝削和利用對手.

針對基礎策略網絡的種群演化訓練過程,本文探討了4 種不同的訓練策略對種群平均適應度的影響.通過對比,本文的三階段分層訓練方式能有效提升訓練速度和種群平均適應度.在線博弈階段的消融實驗中,本文驗證了不同模塊的作用.實驗數據表明,本文提出的種群策略集成框架能有效度量未知對手的博弈風格,并調整自身集成策略來提升收益.由評測結果可得,本博弈求解框架智能體A*在分別面對動態策略的對手Orandom和人類規則的知識AI 時,其博弈性能明顯強于基于納什均衡策略的智能體.這說明相比納什均衡策略,即使對手策略發生變化A*也能夠更好地剝削對手,保證自身良好的博弈性能.綜上所述,本文提出的不完美信息博弈求解框架能夠有效建模未知對手并度量其所屬風格,利用克制策略的加權集成與對手交互,有效提高智能體在面對不同對手時的剝削性能.

本文提出的博弈求解框架具有一定的通用性,該框架不僅適用于德州撲克這一特定游戲環境,還可以為實際生活中的諸多不完美信息博弈問題提供一種可行的解決思路.未來值得進一步探索的問題包括強化學習在本框架中的應用方式以及本框架在多人德州撲克游戲中的拓展問題等.