人工智能已在圍棋這樣的完美信息游戲上實(shí)現(xiàn)了遠(yuǎn)超人類的水平，但在信息未完全披露的多人對(duì)戰(zhàn)游戲上還無法戰(zhàn)勝人類。近年來，OpenAI 和 DeepMind 在 DOTA2 和星際爭霸 2 上的嘗試都難言成功。近日，來自浙江大學(xué)的研究人員提出了一種新方法，結(jié)合蒙特卡洛樹搜索和 NFSP，大大提高了在信息不完整的大規(guī)模零和游戲上的表現(xiàn)。

面對(duì)信息不完整的環(huán)境，浙大的研究人員提出了異步神經(jīng)虛擬自我對(duì)弈（ANFSP）方法，讓 AI 學(xué)會(huì)在多個(gè)虛擬環(huán)境中進(jìn)行「自我博弈」，從而生成最優(yōu)決策。他們的方法在德州撲克和多人 FPS 射擊游戲中均取得了不錯(cuò)表現(xiàn)。

隨著深度強(qiáng)化學(xué)習(xí)的快速發(fā)展，AI 已經(jīng)在圍棋等信息完整的游戲中戰(zhàn)勝了人類專業(yè)玩家。然而，「星際爭霸」等信息不完整游戲的研究還沒有取得同樣的進(jìn)展。這類研究的一大問題是，它們很少從理論和量化的角度考慮對(duì)其訓(xùn)練和結(jié)果進(jìn)行評(píng)估，因此效果難以保證。

博弈論是研究現(xiàn)實(shí)世界競賽中人類行為模式的基石。該理論主要研究智能體如何通過競爭與合作實(shí)現(xiàn)其利益最大化并度量決策的質(zhì)量。它已經(jīng)成為計(jì)算機(jī)科學(xué)中一個(gè)頗具吸引力的研究任務(wù)。名為「算法博弈論」的交互研究課題已經(jīng)確立，并隨著人工智能的發(fā)展受到越來越多的關(guān)注。對(duì)于交易、交通管理等現(xiàn)實(shí)世界中的復(fù)雜問題，計(jì)算維度會(huì)急劇增加，因此有必要利用算法和人工智能的思想使其在實(shí)踐中發(fā)揮作用，這也是該研究的主要?jiǎng)訖C(jī)之一。

在博弈論中，納什均衡是博弈的一個(gè)最優(yōu)解決方案，即沒有人可以通過緩和自己的策略獲得額外收益。虛擬對(duì)弈（Fictitious Play）是求解正規(guī)博弈中納什均衡的一種傳統(tǒng)算法。虛擬對(duì)弈玩家反復(fù)根據(jù)對(duì)手的平均策略做出最佳反應(yīng)。玩家的平均策略將收斂到納什均衡。Heinrich 等人提出了廣泛的虛擬對(duì)弈（Extensive Fictitious Play），將虛擬對(duì)弈的概念擴(kuò)展到了擴(kuò)展式博弈。然而，狀態(tài)在每個(gè)樹節(jié)點(diǎn)中都以查找表的形式表示，因此（類似狀態(tài)的）泛化訓(xùn)練是不切實(shí)際的，而且平均策略的更新需要遍歷整個(gè)游戲樹，這就給大型游戲帶來了維數(shù)災(zāi)難。

虛擬自我對(duì)弈（Fictitious Self-Play，F(xiàn)SP）通過引入基于樣本的機(jī)器學(xué)習(xí)方法解決這些問題。對(duì)最佳反應(yīng)的逼近是通過強(qiáng)化學(xué)習(xí)學(xué)到的，平均策略的更新是通過基于樣本的監(jiān)督學(xué)習(xí)進(jìn)行的。但為了提高采樣效率，智能體之間的交互由元控制器協(xié)調(diào)，并且與學(xué)習(xí)是異步的。

Heinrich 和 Silver 介紹了神經(jīng)虛擬自我對(duì)弈（NFSP），將 FSP 與神經(jīng)網(wǎng)絡(luò)函數(shù)近似結(jié)合起來。一個(gè)玩家由 Q-學(xué)習(xí)網(wǎng)絡(luò)和監(jiān)督式學(xué)習(xí)網(wǎng)絡(luò)組成。該算法通過貪婪深度Q學(xué)習(xí)（greedy deep Q-learning）計(jì)算一個(gè)「最佳反應(yīng)」，通過對(duì)智能體歷史行為的監(jiān)督學(xué)習(xí)計(jì)算平均策略。它通過引入預(yù)期動(dòng)態(tài)來解決協(xié)調(diào)問題——玩家根據(jù)它們的平均策略和最佳反應(yīng)展開行動(dòng)。這是第一個(gè)在不完全博弈中不需要任何先驗(yàn)知識(shí)就能學(xué)習(xí)近似納什均衡的端到端強(qiáng)化學(xué)習(xí)方法。

然而，由于對(duì)手策略的復(fù)雜性和深度 Q 網(wǎng)絡(luò)在離線模式下學(xué)習(xí)的特點(diǎn)，NFSP 在搜索空間和搜索深度規(guī)模較大的游戲中表現(xiàn)較差。本文提出了蒙特卡洛神經(jīng)虛擬自我對(duì)弈（Monte Carlo Neural Fictitious Self Play，MC-NFSP），該算法結(jié)合了 NFSP 與蒙特卡洛樹搜索（Monte Carlo Tree Search）。研究人員在雙方零和的棋牌游戲中評(píng)估了該方法。實(shí)驗(yàn)表明，在奧賽羅棋中，MC-NFSP 將收斂到近似納什均衡，但 NFSP 無法做到。

另一個(gè)缺點(diǎn)是在 NFSP 中，最佳反應(yīng)依賴于深度 Q-學(xué)習(xí)的計(jì)算，這需要很長時(shí)間的計(jì)算直到收斂。在本文中，研究人員提出了異步神經(jīng)虛擬自我對(duì)弈（ANFSP）方法，使用并行的 actor learner 來穩(wěn)定和加速訓(xùn)練。多個(gè)玩家并行進(jìn)行決策。玩家分享 Q 學(xué)習(xí)網(wǎng)絡(luò)和監(jiān)督學(xué)習(xí)網(wǎng)絡(luò)，在 Q 學(xué)習(xí)中累積多個(gè)步驟的梯度，并在監(jiān)督學(xué)習(xí)中計(jì)算小批量的梯度。與 NFSP 相比，這減少了數(shù)據(jù)存儲(chǔ)所需的內(nèi)存。研究人員在雙人零和撲克游戲中評(píng)估了其方法。實(shí)驗(yàn)表明，與 NFSP 相比，ANFSP 可以更加穩(wěn)定和快速地接近近似納什均衡。

為了展示 MC-NFSP 和 ANFSP 技術(shù)在復(fù)雜游戲中的優(yōu)勢，浙大研究人員還評(píng)估了算法在多人 FPS 對(duì)戰(zhàn)游戲的有效性，其中 AI 智能體隊(duì)伍和人類組成的隊(duì)伍進(jìn)行了比賽，新提出的系統(tǒng)提供了良好的策略和控制，幫助 AI 戰(zhàn)勝了人類。

虛擬對(duì)弈（FP）是根據(jù)自我對(duì)弈學(xué)習(xí)納什均衡的經(jīng)典博弈論模型。在每次迭代的時(shí)候，玩家隊(duì)伍根據(jù)對(duì)方的平均策略做出最佳回應(yīng)，并更新其平均策略。在特定的游戲場景（如零和游戲）中，玩家在虛擬對(duì)弈中的平均策略可以達(dá)到納什均衡。因?yàn)?FP 主要是針對(duì)正規(guī)博弈，Heinrish 等人將 FP 擴(kuò)展為虛擬自我對(duì)弈，F(xiàn)SP 致力于遍歷游戲擴(kuò)展形式的游戲樹，有可能在更大規(guī)模的游戲中找到納什均衡。但是 FSP 方法需要玩家和對(duì)手遵循動(dòng)作順序，因此它不適合信息不完整的游戲。

玩家和對(duì)手需要遵循動(dòng)作順序的要求使得 FSP 不適用于信息不完整的游戲。神經(jīng)虛擬自我對(duì)弈（NFSP）是一個(gè)在信息不完整的游戲上學(xué)習(xí)近似納什均衡的模型。該模型結(jié)合了虛擬博弈和深度學(xué)習(xí)。在每一步，玩家會(huì)選擇混合使用最佳反應(yīng)和平均策略。玩家通過深度 Q 學(xué)習(xí)接近最佳反應(yīng)，并通過監(jiān)督學(xué)習(xí)更新平均策略。只有當(dāng)玩家根據(jù)最佳反應(yīng)決定動(dòng)作時(shí)，狀態(tài)-動(dòng)作對(duì)（St, at）會(huì)被存儲(chǔ)在監(jiān)督學(xué)習(xí)記憶中。

圖 1：FSP 和 NFSP 的訓(xùn)練效率

該算法利用兩種神經(jīng)網(wǎng)絡(luò)：蒙特卡洛樹搜索的策略-估值網(wǎng)絡(luò)（policy-value network）（如最佳反應(yīng)網(wǎng)絡(luò)，bestresponse network）和監(jiān)督學(xué)習(xí)的策略網(wǎng)絡(luò)（如平均策略網(wǎng)絡(luò)）。最佳反應(yīng)網(wǎng)絡(luò)如圖 2 所示。神經(jīng)網(wǎng)絡(luò)的輸入是邊界狀態(tài)。策略-估值網(wǎng)絡(luò)有兩種輸出：策略 p（當(dāng)前狀態(tài)到動(dòng)作概率的映射）和估值 v（指定狀態(tài)的預(yù)測值）。估值范圍為「0，1」，其中輸?shù)舯荣惖膶?duì)應(yīng)估值 0，贏得比賽的對(duì)應(yīng)估值 1。在浙大研究人員提出的網(wǎng)絡(luò)中，relu 激活函數(shù)用于卷積層；dropout 用于全連接層以減少過擬合；softmax 用于策略概率。策略網(wǎng)絡(luò)幾乎與最佳反應(yīng)網(wǎng)絡(luò)相同，但前者僅輸出策略 p 0（不會(huì)輸出估值），而這也是玩家的平均策略。

圖 2：MCTS 的最佳反應(yīng)網(wǎng)絡(luò)

浙大研究人員在改進(jìn)版無限制州撲克（Leduc Hold』em）中對(duì) ANFSP 和 NFSP 進(jìn)行比較。為了簡化計(jì)算，浙大研究人員在無限制德州撲克中將每輪的最大賭注大小限制為 2。實(shí)驗(yàn)研究了改進(jìn)版無限制德州撲克中 ANFSP 對(duì)納什均衡的收斂性，并以學(xué)得策略的可利用性作為比較標(biāo)準(zhǔn)。

圖 5 顯示在改進(jìn)版無限制德州撲克中 ANFSP 接近納什均衡。可利用性持續(xù)降低，并在 140w 個(gè)游戲片段后穩(wěn)定在 0.64 左右。訓(xùn)練時(shí)間約 2 小時(shí)。

圖 5：ANFSP 在改進(jìn)版無限制德?lián)渲械目衫眯?/span>

為了在信息不完整的復(fù)雜游戲中評(píng)估本文算法的有效性，研究人員在一個(gè) FPS 游戲上訓(xùn)練了該算法，并且讓它與人類對(duì)戰(zhàn)。本次實(shí)驗(yàn)中使用的 FPS 平臺(tái)是由浙大研究人員設(shè)計(jì)的。游戲場景是兩個(gè)隊(duì)伍（10 VS 10）的攻防對(duì)抗。在訓(xùn)練過程中，一方是 MC-NFSP，另一方是由上千場人類游戲（SL-Human）訓(xùn)練的記憶。該實(shí)驗(yàn)在固定的封閉式 255 x 255 正方形地圖上進(jìn)行。整個(gè)地圖被分為 12 x 12 個(gè)區(qū)域，每個(gè)區(qū)域有一個(gè) 20 x 20 的正方形。

圖 7：FPS 游戲環(huán)境

與本文之前的研究不同，這兩個(gè)網(wǎng)絡(luò)是同時(shí)為外部隊(duì)伍和內(nèi)部隊(duì)伍構(gòu)建和訓(xùn)練的。圖 8 顯示了外部隊(duì)伍的訓(xùn)練結(jié)果（內(nèi)部隊(duì)伍的訓(xùn)練結(jié)果與此類似）。從圖中不難看出，訓(xùn)練收斂得非常快（少于 150 個(gè)片段，每個(gè)片段有 5 場游戲）。外部隊(duì)伍對(duì)戰(zhàn) SL-Human 的勝率提高了 80%，而訓(xùn)練損失接近 0。

圖 8：在 FPS 游戲上的評(píng)估結(jié)果

論文：

Monte Carlo Neural Fictitious Self-Play: Achieve Approximate Nash equilibrium of Imperfect-Information Games

論文地址：https://arxiv.org/abs/1903.09569

摘要：人工智能領(lǐng)域的研究人員已經(jīng)用 AI 在信息完整的大規(guī)模游戲上達(dá)到了人類水準(zhǔn)，但要在信息不完整的大規(guī)模游戲（即戰(zhàn)爭游戲、足球教練或商業(yè)策略游戲）上實(shí)現(xiàn)最優(yōu)結(jié)果（即近似納什均衡）仍是一大挑戰(zhàn)。神經(jīng)虛擬自我對(duì)弈（NFSP）算法可以通過自我對(duì)弈，在沒有先驗(yàn)領(lǐng)域知識(shí)的情況下有效學(xué)習(xí)信息不完整游戲的近似納什均衡。但是，它依賴于深度 Q 網(wǎng)絡(luò)，但這種網(wǎng)絡(luò)是離線的而且很難融入對(duì)手策略不斷變化的在線游戲，因此深度 Q 網(wǎng)絡(luò)無法在游戲中用大規(guī)模搜索和深度搜索來達(dá)到近似納什均衡。本文中，我們提出了蒙特卡洛神經(jīng)虛擬自我對(duì)弈（MC-NFSP）算法，該方法結(jié)合了蒙特卡洛樹搜索和 NFSP，大大提高了模型在信息不完整的大規(guī)模零和游戲中的表現(xiàn)。實(shí)驗(yàn)證明，該算法可以利用大規(guī)模深度搜索達(dá)到 NFSP 無法實(shí)現(xiàn)的近似納什均衡。此外，我們開發(fā)了異步神經(jīng)虛擬自我對(duì)弈（ANFSP）算法，該算法使用異步架構(gòu)和并行架構(gòu)來收集游戲經(jīng)驗(yàn)。在實(shí)驗(yàn)中，我們發(fā)現(xiàn)并行 actor-learner 能夠進(jìn)一步加速和穩(wěn)定訓(xùn)練。

文章來源：機(jī)器之心

IEEE Spectrum

《科技縱覽》

官方微信公眾平臺(tái)