一種用于兩人零和博弈對(duì)手適應(yīng)的元策略演化學(xué)習(xí)算法

吳哲 李凱 徐航 興軍亮,

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

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

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

正是考慮到兩人零和博弈領(lǐng)域內(nèi)現(xiàn)有方法的局限性,本文創(chuàng)新性地提出一種在博弈過(guò)程中可以快速適應(yīng)未知風(fēng)格對(duì)手的元策略演化學(xué)習(xí)算法.本方法不以納什均衡為求解目標(biāo),因此可以獲取遠(yuǎn)超均衡解的收益,同時(shí)又避免了對(duì)手建模類(lèi)方法對(duì)大量交互數(shù)據(jù)的需求.圖1 展示了本方法的訓(xùn)練流程.

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

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

1 相關(guān)工作

1.1 均衡解求解

在兩人零和博弈中,若存在這樣的一個(gè)策略組合: 每個(gè)策略都是其他策略的最佳響應(yīng),那么這一策略組合便被稱(chēng)為納什均衡策略組[19].在這個(gè)策略組中,每一個(gè)玩家都不可能因?yàn)閱畏矫娓淖冏陨聿呗远黾邮找?而且在任何一個(gè)有限兩人零和博弈中都必然存在納什均衡[19?20].因此,求取近似納什均衡解來(lái)保證最壞情況下的收益,成為了目前兩人零和博弈問(wèn)題下主流的解決方案.

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

1.2 對(duì)手建模

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

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

1.3 元學(xué)習(xí)

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

目前針對(duì)元學(xué)習(xí)的研究主要集中于以下三類(lèi):1)距離度量類(lèi)方法[34],通過(guò)學(xué)習(xí)不同任務(wù)之間的距離度量,從而達(dá)到在距離空間內(nèi)快速適應(yīng)新任務(wù)的目標(biāo);2)基于循環(huán)神經(jīng)網(wǎng)絡(luò)的元學(xué)習(xí)類(lèi)方法[35],通過(guò)建立記憶系統(tǒng)來(lái)匹配面對(duì)新任務(wù)的決策模式;3)與模型無(wú)關(guān)的元學(xué)習(xí)類(lèi)方法[32],主要通過(guò)訓(xùn)練得到一個(gè)比較好的網(wǎng)絡(luò)初始化參數(shù)來(lái)加速適應(yīng)過(guò)程.本文主要結(jié)合第三類(lèi)元學(xué)習(xí)方法試圖在決策空間內(nèi)找到一組比較好的網(wǎng)絡(luò)初始化權(quán)重,從而在面對(duì)未知對(duì)手時(shí)可以進(jìn)行快速適應(yīng).

1.4 演化算法

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

2 兩人零和博弈中的快速適應(yīng)算法

本文所提出的適用于兩人零和博弈的快速適應(yīng)算法會(huì)在本節(jié)內(nèi)進(jìn)行詳細(xì)介紹.本算法的目標(biāo)在于,克服傳統(tǒng)兩人零和博弈中均衡求解法不具備策略適應(yīng)性和對(duì)手建模方法對(duì)數(shù)據(jù)量要求大的固有缺陷.本算法創(chuàng)新性地將元學(xué)習(xí)方法引入博弈求解過(guò)程,并使用種群演化算法[40?41]為元模型的訓(xùn)練提供對(duì)手模型,克服了元學(xué)習(xí)方法依賴(lài)手工設(shè)計(jì)訓(xùn)練任務(wù)的弊端.

算法整體架構(gòu)如圖1 所示.本算法主要包含元模型訓(xùn)練器 (見(jiàn)第2.2 節(jié))和對(duì)手種群演化池 (見(jiàn)第2.3 節(jié)) 兩個(gè)模塊.元模型訓(xùn)練器的目標(biāo)是優(yōu)化得到一個(gè)元模型,該元模型在決策空間內(nèi)擁有良好的策略初始化.在面對(duì)未知風(fēng)格對(duì)手時(shí),能夠通過(guò)少量交互來(lái)快速適應(yīng)其策略,使得元模型收益盡可能大.為了提升元模型的泛化性,對(duì)手種群演化池在訓(xùn)練過(guò)程中不斷提供訓(xùn)練樣本給元模型.與傳統(tǒng)元學(xué)習(xí)方法在圖像分類(lèi)、檢測(cè)等任務(wù)中需要手工設(shè)計(jì)任務(wù)集不同,對(duì)手種群通過(guò)進(jìn)化算法為元模型的訓(xùn)練提供了一套自動(dòng)的課程學(xué)習(xí)[42]方案.

2.1 問(wèn)題建模

為確保整個(gè)算法的通用性和可拓展性,元模型M使用深度神經(jīng)網(wǎng)絡(luò)πθ進(jìn)行建模,用于訓(xùn)練的對(duì)手P被建模為π?.由此元模型與對(duì)手交互的過(guò)程可以建模為兩人馬爾科夫博弈[5]過(guò)程:

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

2.2 元模型訓(xùn)練算法

其中,α代表學(xué)習(xí)率,代表元模型πθ面對(duì)固定對(duì)手Pi的損失函數(shù),γ代表折扣因子,MPi用于表示更新后的元模型.為了提升元模型的泛化能力,中的對(duì)手策略不斷被采樣并完成上述梯度更新過(guò)程.算法最終的目標(biāo)是使得元模型可以快速適應(yīng)每一個(gè)當(dāng)前對(duì)手Pi并最大化平均獎(jiǎng)勵(lì),即目標(biāo)函數(shù)為:

其中,β代表元模型參數(shù)更新的步長(zhǎng).

針對(duì)該優(yōu)化目標(biāo)進(jìn)行求導(dǎo)后得到:

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

總結(jié)來(lái)看,使用上述目標(biāo)函數(shù)進(jìn)行梯度更新的訓(xùn)練算法旨在找到這樣一個(gè)元模型: 僅需與對(duì)手進(jìn)行少量交互(即只進(jìn)行幾次梯度更新)就可以學(xué)會(huì)如何適應(yīng)對(duì)手策略并剝削(獎(jiǎng)勵(lì)最大化).元模型訓(xùn)練算法的具體步驟詳見(jiàn)算法1.種群演化對(duì)手策略生成(Opponent strategy generation,OSG)模塊將在第2.3 節(jié)進(jìn)行詳細(xì)闡述.

算法1.元模型訓(xùn)練算法

該算法主要包含兩個(gè)階段,首先通過(guò)種群演化算法得到訓(xùn)練用的對(duì)手策略集合,然后再通過(guò)元模型訓(xùn)練算法得到快速適應(yīng)性.第2.3 節(jié)對(duì)種群演化算法進(jìn)行描述.

2.3 種群演化對(duì)手生成

在迭代開(kāi)始前,首先隨機(jī)初始化一個(gè)對(duì)手策略的種群B={P1,P2,···,PN},此時(shí)元模型策略M也會(huì)被補(bǔ)充到對(duì)手種群中,用于引導(dǎo)對(duì)手策略在演化初期快速提升博弈水平,提高訓(xùn)練效率.

種群策略的初始化完成以后,使用元模型來(lái)評(píng)估當(dāng)前種群中每一個(gè)對(duì)手策略的適應(yīng)度.適應(yīng)度F被形式化為對(duì)手策略Pi與元模型在一個(gè)對(duì)局步長(zhǎng)內(nèi)獲得的累計(jì)獎(jiǎng)勵(lì)總和:

評(píng)估結(jié)束后,選擇 (Selection) 算子基于當(dāng)前種群策略的適應(yīng)度,以?的比例挑選出適應(yīng)度靠前的部分個(gè)體組成精英團(tuán)體E.對(duì)手種群池中剩余部分的策略 (B ?E) 通過(guò)與精英團(tuán)體E內(nèi)的策略進(jìn)行交叉 (Crossover) 以及自身策略的變異 (Mutation),來(lái)獲得提升策略適應(yīng)度的機(jī)會(huì).精英團(tuán)體E內(nèi)策略的基因會(huì)完整保留到下一代種群中,不會(huì)受到交叉和變異算子的影響,這使得種群內(nèi)部表現(xiàn)優(yōu)異的基因(網(wǎng)絡(luò)權(quán)重)可以不斷延續(xù)下去.

本節(jié)所提出的種群演化算法通過(guò)不斷自動(dòng)生成對(duì)手策略來(lái)為元模型提供訓(xùn)練數(shù)據(jù).選擇算子的應(yīng)用使得對(duì)手種群的博弈水平逐步提升,從而為元模型的訓(xùn)練構(gòu)建了一個(gè)課程學(xué)習(xí)的范式.同時(shí),交叉和變異算子的應(yīng)用豐富了種群策略的多樣性.用于訓(xùn)練的對(duì)手策略風(fēng)格越多樣,元模型的泛化能力就越強(qiáng).算法2 詳細(xì)描述了種群演化對(duì)手生成的具體步驟.

算法2.種群演化對(duì)手生成算法

本文中種群策略池的規(guī)模設(shè)定主要考慮了環(huán)境復(fù)雜度和算法收斂速度兩個(gè)方面,統(tǒng)一設(shè)置為10.精英團(tuán)體E占種群策略的比例?根據(jù)不同問(wèn)題在0.2～0.5 內(nèi)取值.變異率m utprob根據(jù)不同問(wèn)題在0.1～0.3 內(nèi)取值.變異強(qiáng)度 m utstrength設(shè)置為0.1,即對(duì)應(yīng)10%的高斯噪聲.

3 實(shí)驗(yàn)評(píng)估

本節(jié)通過(guò)構(gòu)建一系列對(duì)比實(shí)驗(yàn),來(lái)驗(yàn)證本文所提出的元模型訓(xùn)練算法在兩人零和博弈中的有效性.第3.1 節(jié)給出了用于實(shí)驗(yàn)評(píng)估的仿真環(huán)境和基線(xiàn)算法介紹.第3.2 節(jié)給出了算法訓(xùn)練及測(cè)試過(guò)程中的詳細(xì)參數(shù)設(shè)置.第3.3 節(jié)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析.

3.1 評(píng)估環(huán)境與基線(xiàn)算法

3.1.1 評(píng)估環(huán)境

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

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

兩人有限注德州撲克是現(xiàn)實(shí)世界德?lián)渫婕页Ｓ玫囊环N撲克玩法.LHE 共包含52 張牌,游戲總共有4 個(gè)階段,每個(gè)玩家在翻牌前階段 (Pre-flop) 會(huì)得到2 張私有牌,在后續(xù)的翻牌階段 (Flop)、轉(zhuǎn)牌階段 (Turn)、河牌階段 (River) 會(huì)分別發(fā)出3 張、1 張、1 張,總共5 張公共牌.玩家在每個(gè)階段的可選動(dòng)作包括 “過(guò)牌 (Check)”、“加注 (Raise)”、“跟牌(Call)”、“棄牌 (Fold)”.若無(wú)人棄牌則牌力高的一方獲得游戲勝利.

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

3.1.2 基線(xiàn)算法

為驗(yàn)證元模型訓(xùn)練算法的優(yōu)越性,本文與前面所介紹的求解兩人零和博弈中的經(jīng)典方法進(jìn)行了實(shí)驗(yàn)對(duì)比.具體使用的基線(xiàn)算法如下.

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

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

3.1.3 實(shí)驗(yàn)參數(shù)設(shè)置

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

圖2 本文算法與基線(xiàn)算法在RoboSumo 中的對(duì)比Fig.2 Comparison of our method with the baseline algorithm in RoboSumo

圖3 消融實(shí)驗(yàn)Fig.3 Ablation study

表2 本文算法與基線(xiàn)算法在Leduc 環(huán)境中的對(duì)比Table 2 The average return of our method and baseline methods in Leduc

表3 本文算法與基線(xiàn)算法在LHE 環(huán)境中的對(duì)比Table 3 The average return of our method and baseline methods in LHE

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 元模型有效性驗(yàn)證

本節(jié)用于驗(yàn)證元模型訓(xùn)練算法的有效性.首先,對(duì)訓(xùn)練得到的元模型的快速適應(yīng)性進(jìn)行驗(yàn)證.模型的適應(yīng)過(guò)程被限制為與當(dāng)前對(duì)手只進(jìn)行三步梯度更新,通過(guò)統(tǒng)計(jì)每步梯度更新后的平均收益來(lái)觀測(cè)當(dāng)前元模型的適應(yīng)能力.其次,快速適應(yīng)后的元模型被進(jìn)一步用于與各類(lèi)基線(xiàn)算法進(jìn)行對(duì)比,通過(guò)統(tǒng)計(jì)與各類(lèi)對(duì)手10 000 局對(duì)戰(zhàn)的平均收益來(lái)觀測(cè)各類(lèi)算法的表現(xiàn)情況.在不同任務(wù)上的具體實(shí)驗(yàn)參數(shù)設(shè)置見(jiàn)表1.

表1 不同環(huán)境下的實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Hyperparameters settings

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

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

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

本文所提出的種群演化對(duì)手生成算法,正是通過(guò)選擇、交叉、變異算子實(shí)現(xiàn)了兼顧難度與風(fēng)格的對(duì)手自動(dòng)生成.元模型通過(guò)不斷與這些自動(dòng)生成的對(duì)手進(jìn)行訓(xùn)練,逐步提升了自身策略的適應(yīng)性.第3.2.2 節(jié)對(duì)該對(duì)手生成模塊的作用機(jī)制展開(kāi)了詳細(xì)實(shí)驗(yàn)驗(yàn)證.最后,與基線(xiàn)算法 “本文算法 +PPO”的實(shí)驗(yàn)結(jié)果對(duì)比也說(shuō)明了本算法具有與模型無(wú)關(guān)(Model-agnostic) 的性質(zhì)[32],可以與任何梯度優(yōu)化算法兼容.

3.2.2 種群演化模塊驗(yàn)證

本節(jié)主要針對(duì)第2.3 節(jié)中提出的種群演化對(duì)手生成算法的作用機(jī)制展開(kāi)實(shí)驗(yàn)驗(yàn)證.主要包括: 1) 算法消融性實(shí)驗(yàn);2) 演化自動(dòng)生成的對(duì)手策略是否具有多樣性;3) 超參數(shù)設(shè)置對(duì)實(shí)驗(yàn)性能的影響.

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

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

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

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

超參數(shù)的選擇對(duì)實(shí)驗(yàn)性能也會(huì)造成一定影響,表1 中詳細(xì)展示了通過(guò)網(wǎng)格搜索確定的一組超參數(shù).其中,“評(píng)估局?jǐn)?shù)”的設(shè)置會(huì)對(duì)實(shí)驗(yàn)性能產(chǎn)生較大影響.圖5 顯示了評(píng)估局?jǐn)?shù)的不同取值對(duì)元模型性能的影響.當(dāng)評(píng)估局?jǐn)?shù)較少時(shí),模型性能出現(xiàn)了劇烈震蕩;隨著評(píng)估局?jǐn)?shù)的增加,模型的方差逐漸變小,性能也隨之提升.這是因?yàn)樵搮?shù)代表了對(duì)手生成模塊中選擇算子評(píng)估對(duì)手模型性能的對(duì)局?jǐn)?shù)量,這直接影響了子代種群的模型性能.通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),評(píng)估局?jǐn)?shù)較多時(shí)挑選出的子代種群有利于模型性能的提升,在本文的三類(lèi)實(shí)驗(yàn)場(chǎng)景中,50～100是一個(gè)比較合理的范圍,能夠兼顧評(píng)估速度與質(zhì)量.

圖5 超參數(shù)設(shè)置對(duì)模型性能影響Fig.5 Effect of hyperparameter settings

4 結(jié)論

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

在Leduc 撲克、LHE 以及RoboSumo 中的實(shí)驗(yàn)結(jié)果表明,本文算法在與對(duì)手進(jìn)行少量交互的情況下,使用同一個(gè)元模型針對(duì)不同風(fēng)格的對(duì)手都實(shí)現(xiàn)了快速適應(yīng).相比于均衡類(lèi)算法,本文算法能夠?qū)崿F(xiàn)對(duì)次優(yōu)對(duì)手的剝削;相比于對(duì)手建模類(lèi)算法,本文算法避免了顯式建模過(guò)程,提高了模型的泛化能力.消融實(shí)驗(yàn)與可視化實(shí)驗(yàn)的結(jié)果顯示了本文算法所使用的對(duì)手演化生成模塊與元模型更新算法的有效性.如何將本文算法應(yīng)用到更大規(guī)模的游戲(例如,無(wú)限注德州撲克)以及如何結(jié)合均衡類(lèi)算法的優(yōu)點(diǎn)來(lái)保證元模型在適應(yīng)過(guò)程中的安全性,是本文未來(lái)可以繼續(xù)研究的方向.