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

在AI游戲領(lǐng)域，人工智能的進(jìn)展往往通過棋盤游戲進(jìn)行展現(xiàn)。棋盤游戲可以度量和評(píng)估人類和機(jī)器如何在受控環(huán)境中發(fā)展和執(zhí)行策略。數(shù)十年來，提前規(guī)劃的能力一直是AI在國際象棋、跳棋、將棋和圍棋等完美信息游戲以及撲克、蘇格蘭場(chǎng)等不完美信息游戲中取得成功的關(guān)鍵。

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

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

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

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

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

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

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

DeepNash的核心是一種條理化、無模型的強(qiáng)化學(xué)習(xí)算法，研究者稱為Regularized Nash Dynamics（R-NaD）。DeepNash將R-NaD與一個(gè)深度神經(jīng)網(wǎng)絡(luò)架構(gòu)相結(jié)合，并收斂到納什均衡，這意味著它學(xué)會(huì)了在激勵(lì)競(jìng)爭(zhēng)下比賽，并對(duì)試圖利用它的競(jìng)爭(zhēng)對(duì)手具有穩(wěn)健性。

下圖 1 b 為DeepNash方法的高級(jí)概覽。研究者在Gravon游戲平臺(tái)上將它的表現(xiàn)與各種SOTA Stratego機(jī)器人和人類玩家進(jìn)行了系統(tǒng)比較。結(jié)果顯示，DeepNash以超過 97% 的勝率擊敗了當(dāng)前所有 SOTA機(jī)器人，并與人類玩家進(jìn)行了激烈競(jìng)爭(zhēng)，在2022年度和各個(gè)時(shí)期的排行榜上都位列前3名，勝率達(dá)到了84%。

研究者表示，在學(xué)習(xí)算法中不部署任何搜索方法的情況下，AI算法第一次能夠在復(fù)雜棋盤游戲中達(dá)到人類專家水平，也是AI首次在Stratego游戲中實(shí)現(xiàn)人類專家水平。

方法概述

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

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

無模型部分意味著該研究沒有建立一個(gè)明確的對(duì)手模型來跟蹤對(duì)手可能出現(xiàn)的狀態(tài)，博弈論部分基于這樣的思路，即在強(qiáng)化學(xué)習(xí)方法的基礎(chǔ)上，他們引導(dǎo)智能體學(xué)習(xí)行為朝著納什均衡的方向發(fā)展。這種組合方法的主要優(yōu)點(diǎn)是不需要從公共狀態(tài)中顯式地模擬私有狀態(tài)。另外一個(gè)復(fù)雜的挑戰(zhàn)是，將這種無模型的強(qiáng)化學(xué)習(xí)方法與R-NaD相結(jié)合，使西洋陸軍棋中的自我博弈與人類專家玩家相競(jìng)爭(zhēng)，這是迄今為止尚未實(shí)現(xiàn)的。這種組合的DeepNash方法如上圖1b所示。

正則化納什動(dòng)力學(xué)算法

DeepNash 中使用的 R-NaD 學(xué)習(xí)算法是基于正則化思想以達(dá)到收斂的目的，R-NaD 依賴于三個(gè)關(guān)鍵步驟，如下圖 2b所示：

DeepNash 由三個(gè)組件組成：(1) 核心訓(xùn)練組件 R-NaD；(2) 微調(diào)學(xué)習(xí)策略以減少模型采取極不可能動(dòng)作的殘差概率，以及 (3) 測(cè)試時(shí)進(jìn)行后處理以過濾掉低概率動(dòng)作并糾錯(cuò)。

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

實(shí)驗(yàn)結(jié)果

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

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

 
下圖 4a舉例說明DeepNash中的一些經(jīng)常重復(fù)的部署方式；圖 4b 顯示了 DeepNash（藍(lán)方）在棋子中落后（輸?shù)袅?7 和 8）但在信息方面領(lǐng)先的情況，因?yàn)榧t方的對(duì)手有 10、9、8 和兩個(gè)7。圖 4c 中的第二個(gè)示例顯示了 DeepNash 有機(jī)會(huì)用其 9 捕獲對(duì)手的 6，但這一舉措并未被考慮，可能是因?yàn)镈eepNash認(rèn)為保護(hù) 9 的身份被認(rèn)為比物質(zhì)收益更重要。

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

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

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