DeepMind在游戲AI領域又有了新成績，這次是西洋陸軍棋。

在AI游戲領域，人工智能的進展往往通過棋盤游戲進行展現。棋盤游戲可以度量和評估人類和機器如何在受控環境中發展和執行策略。數十年來，提前規劃的能力一直是AI在國際象棋、跳棋、將棋和圍棋等完美信息游戲以及撲克、蘇格蘭場等不完美信息游戲中取得成功的關鍵。

西洋陸軍棋（Stratego）已經成為AI研究的下一批前沿領域之一。該游戲的階段和機制的可視化圖如下1a所示。該游戲面臨以下兩個挑戰。

其一，Stratego 的博弈樹具有 10535個可能狀態，這要多于已經得到充分研究的不完美信息游戲無限制德州撲克（10164個可能狀態）和圍棋游戲（10360個可能狀態）。

其二，在Stratego的給定環境中行動需要在游戲開始時為每個玩家推理超過1066個可能的部署，而撲克只有103對可能的牌。圍棋和國際象棋等完美信息游戲沒有私有部署階段，因此避免了Stratego中這一挑戰帶來的復雜性。

目前，我們不可能使用基于模型的SOTA完美信息規劃技術，也無法使用將游戲分解為獨立情況的不完美信息搜索技術。

由于這些原因，Stratego為研究大規模策略交互提供了一個挑戰性基準。與大多數棋盤游戲相似，Stratego測試我們循序地做出相對較慢、深思熟慮和合乎邏輯決策的能力。又由于該游戲的結構非常復雜，AI研究社區幾乎沒能取得什么進展，人工智能體只能達到人類業余玩家的水平。因此，在從零開始且沒有人類演示數據的情況下，開發智能體學習端到端策略以在Stratego的不完美信息下做出最佳決策，仍然是AI研究面臨的重大挑戰之一。

近日，在 DeepMind 的一篇最新論文中，研究者提出了 DeepNash，它是一種無需人類演示、以無模型（model-free）方式學習Stratego自我博弈的智能體。DeepNask擊敗了以往的SOTA AI智能體，并在該游戲最復雜的變體Stratego Classic中實現了專家級人類玩家的水平。

論文地址：https://arxiv.org/pdf/2206.15378.pdf。

DeepNash的核心是一種條理化、無模型的強化學習算法，研究者稱為Regularized Nash Dynamics（R-NaD）。DeepNash將R-NaD與一個深度神經網絡架構相結合，并收斂到納什均衡，這意味著它學會了在激勵競爭下比賽，并對試圖利用它的競爭對手具有穩健性。

下圖 1 b 為DeepNash方法的高級概覽。研究者在Gravon游戲平臺上將它的表現與各種SOTA Stratego機器人和人類玩家進行了系統比較。結果顯示，DeepNash以超過 97% 的勝率擊敗了當前所有 SOTA機器人，并與人類玩家進行了激烈競爭，在2022年度和各個時期的排行榜上都位列前3名，勝率達到了84%。

研究者表示，在學習算法中不部署任何搜索方法的情況下，AI算法第一次能夠在復雜棋盤游戲中達到人類專家水平，也是AI首次在Stratego游戲中實現人類專家水平。

方法概述

DeepNash 采用端到端的學習策略運行Stratego，并在游戲開始時將棋子戰術性地放在棋盤上（見圖 1a），在game-play階段，研究者使用集成深度 RL 和博弈論方法。智能體旨在通過自我博弈來學習一個近似的納什均衡。

該研究采用無需搜索的正交路徑，并提出了一種新方法，將自我博弈中的無模型（model-free）強化學習與博弈論算法思想——正則化納什動力學 (RNaD) 相結合。

無模型部分意味著該研究沒有建立一個明確的對手模型來跟蹤對手可能出現的狀態，博弈論部分基于這樣的思路，即在強化學習方法的基礎上，他們引導智能體學習行為朝著納什均衡的方向發展。這種組合方法的主要優點是不需要從公共狀態中顯式地模擬私有狀態。另外一個復雜的挑戰是，將這種無模型的強化學習方法與R-NaD相結合，使西洋陸軍棋中的自我博弈與人類專家玩家相競爭，這是迄今為止尚未實現的。這種組合的DeepNash方法如上圖1b所示。

正則化納什動力學算法

DeepNash 中使用的 R-NaD 學習算法是基于正則化思想以達到收斂的目的，R-NaD 依賴于三個關鍵步驟，如下圖 2b所示：

DeepNash 由三個組件組成：(1) 核心訓練組件 R-NaD；(2) 微調學習策略以減少模型采取極不可能動作的殘差概率，以及 (3) 測試時進行后處理以過濾掉低概率動作并糾錯。

DeepNash 的網絡由以下組件構成：一個帶有殘差塊和跳躍連接的 U-Net 主干，以及四個頭。第一個 DeepNash 頭將價值函數輸出為標量，而其余三個頭通過在部署和游戲期間輸出其動作的概率分布來編碼智能體策略。這個觀測張量的結構如圖3所示：

實驗結果

DeepNash 還與幾個現有的Stratego計算機程序進行了評估：Probe 在 Computer Stratego 世界錦標賽中，其中有三年奪冠（2007 年、2008 年、2010 年）；Master of the Flag在 2009 年贏得了該冠軍；Demon of Ignorance 是 Stratego 的開源實現；Asmodeus、Celsius、Celsius1.1、PeternLewis 和 Vixen 是 2012 年在澳大利亞大學編程競賽中提交的程序，此次比賽PeternLewis 獲勝。

如表1所示，DeepNash在對抗所有這些智能體時贏得了絕大多數的游戲，盡管DeepNash沒有接受過對抗訓練，只是使用自我博弈。

 
下圖 4a舉例說明DeepNash中的一些經常重復的部署方式；圖 4b 顯示了 DeepNash（藍方）在棋子中落后（輸掉了 7 和 8）但在信息方面領先的情況，因為紅方的對手有 10、9、8 和兩個7。圖 4c 中的第二個示例顯示了 DeepNash 有機會用其 9 捕獲對手的 6，但這一舉措并未被考慮，可能是因為DeepNash認為保護 9 的身份被認為比物質收益更重要。

 
在下圖5a中，研究者展示了積極的唬騙（positive bluffing），玩家假裝棋子的價值高于實際價值。DeepNash用未知棋子Scout (2) 追逐對手的8，并假裝它是10。對手認為這個棋子可能是10，將其引導至Spy旁邊（可以捕獲10）。但是，為了奪取這枚棋子，對手的Spy輸給了DeepNash的Scout。

第二類唬騙為消極唬騙（negative bluffing），如下圖5b所示。它與積極唬騙相反，玩家假裝棋子的價值低于實際價值。

下圖5c展示了一種更復雜的bluff，其中DeepNash將其未公開的Scout (2)接近對手的10，這可以被解釋為Spy。這種策略實際上允許藍方在幾步之后用7捕獲紅方的5，因此獲得material，阻止5捕獲Scout (2)，并揭示它實際上并不是Spy。