浙大提出會打德撲的「自我博弈」AI，還會玩射擊遊戲

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

隨著深度強化學習的快速發展，AI 已經在圍棋等信息完整的遊戲中戰勝了人類專業玩家。然而，「星際爭霸」等信息不完整遊戲的研究還沒有取得同樣的進展。這類研究的一大問題是，它們很少從理論和量化的角度考慮對其訓練和結果進行評估，因此效果難以保證。

博弈論是研究現實世界競賽中人類行為模式的基石。該理論主要研究智能體如何通過競爭與合作實現其利益最大化並度量決策的質量。它已經成為計算機科學中一個頗具吸引力的研究任務。名為「算法博弈論」的交互研究課題已經確立，並隨著人工智能的發展受到越來越多的關注。對於交易、交通管理等現實世界中的複雜問題，計算維度會急劇增加，因此有必要利用算法和人工智能的思想使其在實踐中發揮作用，這也是該研究的主要動機之一。

在博弈論中，納什均衡是博弈的一個最優解決方案，即沒有人可以通過緩和自己的策略獲得額外收益。虛擬對弈（Fictitious Play）是求解正規博弈中納什均衡的一種傳統算法。虛擬對弈玩家反覆根據對手的平均策略做出最佳反應。玩家的平均策略將收斂到納什均衡。Heinrich 等人提出了廣泛的虛擬對弈（Extensive Fictitious Play），將虛擬對弈的概念擴展到了擴展式博弈。然而，狀態在每個樹節點中都以查找表的形式表示，因此（類似狀態的）泛化訓練是不切實際的，而且平均策略的更新需要遍歷整個遊戲樹，這就給大型遊戲帶來了維數災難。

虛擬自我對弈（Fictitious Self-Play，FSP）通過引入基於樣本的機器學習方法解決這些問題。對最佳反應的逼近是通過強化學習學到的，平均策略的更新是通過基於樣本的監督學習進行的。但為了提高採樣效率，智能體之間的交互由元控制器協調，並且與學習是異步的。

Heinrich 和 Silver 介紹了神經虛擬自我對弈（NFSP），將 FSP 與神經網絡函數近似結合起來。一個玩家由 Q-學習網絡和監督式學習網絡組成。該算法通過貪婪深度Q學習（greedy deep Q-learning）計算一個「最佳反應」，通過對智能體歷史行為的監督學習計算平均策略。它通過引入預期動態來解決協調問題——玩家根據它們的平均策略和最佳反應展開行動。這是第一個在不完全博弈中不需要任何先驗知識就能學習近似納什均衡的端到端強化學習方法。

然而，由於對手策略的複雜性和深度 Q 網絡在離線模式下學習的特點，NFSP 在搜索空間和搜索深度規模較大的遊戲中表現較差。本文提出了蒙特卡洛神經虛擬自我對弈（Monte Carlo Neural Fictitious Self Play，MC-NFSP），該算法結合了 NFSP 與蒙特卡洛樹搜索（Monte Carlo Tree Search）。研究人員在雙方零和的棋牌遊戲中評估了該方法。實驗表明，在奧賽羅棋中，MC-NFSP 將收斂到近似納什均衡，但 NFSP 無法做到。

另一個缺點是在 NFSP 中，最佳反應依賴於深度 Q-學習的計算，這需要很長時間的計算直到收斂。在本文中，研究人員提出了異步神經虛擬自我對弈（ANFSP）方法，使用並行的 actor learner 來穩定和加速訓練。多個玩家並行進行決策。玩家分享 Q 學習網絡和監督學習網絡，在 Q 學習中累積多個步驟的梯度，並在監督學習中計算小批量的梯度。與 NFSP 相比，這減少了數據存儲所需的內存。研究人員在雙人零和撲克遊戲中評估了其方法。實驗表明，與 NFSP 相比，ANFSP 可以更加穩定和快速地接近近似納什均衡。

為了展示 MC-NFSP 和 ANFSP 技術在複雜遊戲中的優勢，浙大研究人員還評估了算法在多人 FPS 對戰遊戲的有效性，其中 AI 智能體隊伍和人類組成的隊伍進行了比賽，新提出的系統提供了良好的策略和控制，幫助 AI 戰勝了人類。

神經虛擬自我對弈

虛擬對弈（FP）是根據自我對弈學習納什均衡的經典博弈論模型。在每次迭代的時候，玩家隊伍根據對方的平均策略做出最佳回應，並更新其平均策略。在特定的遊戲場景（如零和遊戲）中，玩家在虛擬對弈中的平均策略可以達到納什均衡。因為 FP 主要是針對正規博弈，Heinrish 等人將 FP 擴展為虛擬自我對弈，FSP 致力於遍歷遊戲擴展形式的遊戲樹，有可能在更大規模的遊戲中找到納什均衡。但是 FSP 方法需要玩家和對手遵循動作順序，因此它不適合信息不完整的遊戲。

玩家和對手需要遵循動作順序的要求使得 FSP 不適用於信息不完整的遊戲。神經虛擬自我對弈（NFSP）是一個在信息不完整的遊戲上學習近似納什均衡的模型。該模型結合了虛擬博弈和深度學習。在每一步，玩家會選擇混合使用最佳反應和平均策略。玩家通過深度 Q 學習接近最佳反應，並通過監督學習更新平均策略。只有當玩家根據最佳反應決定動作時，狀態-動作對（St, at）會被存儲在監督學習記憶中。

蒙特卡洛神經虛擬自我對弈（MC-NFSP）

該算法利用兩種神經網絡：蒙特卡洛樹搜索的策略-估值網絡（policy-value network）（如最佳反應網絡，bestresponse network）和監督學習的策略網絡（如平均策略網絡）。最佳反應網絡如圖 2 所示。神經網絡的輸入是邊界狀態。策略-估值網絡有兩種輸出：策略 p（當前狀態到動作概率的映射）和估值 v（指定狀態的預測值）。估值範圍為「0，1」，其中輸掉比賽的對應估值 0，贏得比賽的對應估值 1。在浙大研究人員提出的網絡中，relu 激活函數用於卷積層；dropout 用於全連接層以減少過擬合；softmax 用於策略概率。策略網絡幾乎與最佳反應網絡相同，但前者僅輸出策略 p 0（不會輸出估值），而這也是玩家的平均策略。

圖 2：MCTS 的最佳反應網絡

實驗

浙大研究人員在改進版無限制州撲克（Leduc Hold』em）中對 ANFSP 和 NFSP 進行比較。為了簡化計算，浙大研究人員在無限制德州撲克中將每輪的最大賭注大小限制為 2。實驗研究了改進版無限制德州撲克中 ANFSP 對納什均衡的收斂性，並以學得策略的可利用性作為比較標準。

圖 5 顯示在改進版無限制德州撲克中 ANFSP 接近納什均衡。可利用性持續降低，並在 140w 個遊戲片段後穩定在 0.64 左右。訓練時間約 2 小時。

圖 5：ANFSP 在改進版無限制德撲中的可利用性

在第一人稱射擊遊戲（FPS）中的評估

為了在信息不完整的複雜遊戲中評估本文算法的有效性，研究人員在一個 FPS 遊戲上訓練了該算法，並且讓它與人類對戰。本次實驗中使用的 FPS 平臺是由浙大研究人員設計的。遊戲場景是兩個隊伍（10 VS 10）的攻防對抗。在訓練過程中，一方是 MC-NFSP，另一方是由上千場人類遊戲（SL-Human）訓練的記憶。該實驗在固定的封閉式 255 x 255 正方形地圖上進行。整個地圖被分為 12 x 12 個區域，每個區域有一個 20 x 20 的正方形。

圖 7：FPS 遊戲環境

與本文之前的研究不同，這兩個網絡是同時為外部隊伍和內部隊伍構建和訓練的。圖 8 顯示了外部隊伍的訓練結果（內部隊伍的訓練結果與此類似）。從圖中不難看出，訓練收斂得非常快（少於 150 個片段，每個片段有 5 場遊戲）。外部隊伍對戰 SL-Human 的勝率提高了 80%，而訓練損失接近 0。

圖 8：在 FPS 遊戲上的評估結果

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

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

摘要：人工智能領域的研究人員已經用 AI 在信息完整的大規模遊戲上達到了人類水準，但要在信息不完整的大規模遊戲（即戰爭遊戲、足球教練或商業策略遊戲）上實現最優結果（即近似納什均衡）仍是一大挑戰。神經虛擬自我對弈（NFSP）算法可以通過自我對弈，在沒有先驗領域知識的情況下有效學習信息不完整遊戲的近似納什均衡。但是，它依賴於深度 Q 網絡，但這種網絡是離線的而且很難融入對手策略不斷變化的在線遊戲，因此深度 Q 網絡無法在遊戲中用大規模搜索和深度搜索來達到近似納什均衡。本文中，我們提出了蒙特卡洛神經虛擬自我對弈（MC-NFSP）算法，該方法結合了蒙特卡洛樹搜索和 NFSP，大大提高了模型在信息不完整的大規模零和遊戲中的表現。實驗證明，該算法可以利用大規模深度搜索達到 NFSP 無法實現的近似納什均衡。此外，我們開發了異步神經虛擬自我對弈（ANFSP）算法，該算法使用異步架構和並行架構來收集遊戲經驗。在實驗中，我們發現並行 actor-learner 能夠進一步加速和穩定訓練。

閱讀更多 機器之心 的文章

關鍵字: 星際爭霸 射擊遊戲 圍棋