近日，DeepMind的AI智能體DeepNash，在西洋陸軍棋（Stratego）中花式戰(zhàn)勝專業(yè)級人類玩家，成功躋身Top 3。

12月1日，論文正式在Science上發(fā)表。

論文地址：http://www.science.org/doi/10.1126/science.add4679

用這個AI，致敬約翰·納什

在如今這個時代，玩游戲的AI已經(jīng)發(fā)展到一個全新的階段。

以往，許多科學家會用國際象棋和圍棋訓(xùn)練AI，而DeepMind這次用的Stratego，是一款經(jīng)典的棋盤游戲，要比國際象棋和圍棋更復(fù)雜，比撲克更巧妙。

而這個名為DeepNash的AI智能體，通過與自己對戰(zhàn)的方式，從零開始學習Stratego。

現(xiàn)在，DeepNash在世界上最大的在線Stratego平臺Gravon的人類專家中，排名歷史前三。

DeepNash采用的是一種全新的打法，理論依據(jù)是博弈論和無模型深度強化學習。

看得出來，這個名字也意在致敬著名的美國數(shù)學家約翰·納什（John Nash）。

他提出的納什均衡（Nash equilibrium），又稱為非合作博弈均衡，是博弈論中非常重要的一環(huán)。

Stratego的玄機在哪里？

歷來，棋盤游戲就一直是衡量AI進步的標準，因為它能夠使我們研究人類和機器如何在受控環(huán)境中，制定和執(zhí)行策略。

而這個Stratego的玄機，究竟在哪里呢？

與國際象棋和圍棋的不同之處在于，Stratego是一種不完全信息博弈：玩家無法直接觀察對手棋子的身份。

因為這種復(fù)雜性，基于AI的Stratego系統(tǒng)，往往再努力，也就是業(yè)余水平，不可能達到「專家」的水準。

在以往，各種AI之所以在游戲中大獲全勝、完爆人類，是因為一種叫「博弈樹搜索」的AI技術(shù)。

「博弈樹搜索」雖然可以在充分掌握信息的各種游戲中大殺四方，但對于Stratego這樣的游戲，卻有些束手無策，因為它的可擴展性不夠。

而在這一點上，DeepNash就完爆了博弈樹搜索。

實際上，DeepNash掌握了Stratego的價值，已經(jīng)遠遠超越了這個游戲本身。

現(xiàn)實世界往往就是很復(fù)雜，信息是有限的。真正先進的AI系統(tǒng)，所面臨的環(huán)境就如同Stratego這樣。

DeepNash成功地向我們展示了，AI如何在不確定的情況下，成功地平衡了結(jié)果，解決了復(fù)雜的問題。

Stratego怎么玩

Stratego是一款回合制奪旗游戲。游戲中，玩家需要虛張聲勢，迂回戰(zhàn)術(shù)，收集信息，巧妙地操作。

它是一款零和博弈，所以一個玩家的任何收益，都代表著對手同等數(shù)量的損失。

聽起來似乎與我們的軍棋很像。

Stratego與軍棋的不同之處在于，它有更多數(shù)量的棋子、更多的軍銜較多，棋盤設(shè)計較簡單，沒有鐵路、行營和裁判。

雙方布陣時，要將所有棋子豎立，不能讓對方看到。

布陣完成之后，由紅方先走棋，隨后輪流移動一枚棋子。

棋子中，軍旗和地雷不能移動，偵察兵可以橫豎移動任意格，不可越過棋子，其余棋子只能橫豎走一格。

當雙方棋子在同一格內(nèi)，就一同揭開，判斷大小，勝的棋子放回原位、正面朝后，輸?shù)钠遄泳捅灰瞥?/p>

Stratego勝利方式與中國軍棋類似，以奪得對方軍旗或消滅所有能動的棋子為勝利。

為什么Stratego對于AI這么有挑戰(zhàn)性？部分原因在于，它是一種不完全信息博弈。

Stratego中的兩位玩家，在把40個棋子排成起始陣型時，是彼此隱藏的。

因為玩家無法獲得相同的知識，因此在做出任何決定時，他們都需要平衡所有可能的結(jié)果。

Stratego棋子的種類和排名

左：棋子排名。在游戲中，軍銜較高的棋子獲勝，唯一的例外是10（元帥）被間諜攻擊；炸彈總是獲勝，唯一的例外是被礦工捕獲。

中間：可能的起始陣型。旗幟要安全地藏在后面，兩側(cè)的炸彈提供保護。兩個淡藍色區(qū)域是「湖泊」，永遠不能進入。

右：一盤正在進行的游戲，可以看到，藍方的間諜捕獲了紅方的元帥。

這個游戲，把AlphaZero都難倒了

在Stratego中，信息都是隱藏的。

只有遭遇其他玩家時，對方棋子的身份才會顯露出來。

而國際象棋和圍棋的不同之處在于，它們是「完美信息博弈」，因為對戰(zhàn)雙方確切地知道每一顆棋子的位置和身份。

DeepMind的AlphaZero，在完美信息博弈中表現(xiàn)一向出色，但在Stratego中，它卻被難倒了。

在國際象棋中，AlphaZero在4小時后就超越了Stockfish；在將棋中，AlphaZero在2小時后超越了Elmo；而圍棋中，AlphaZero在30小時后超越了擊敗李世石的AlphaGo

Stratego更類似于德州撲克，需要類似人類的能力——人類需要在信息不全的情況下做出決定，還需要虛張聲勢。

美國作家杰克倫敦曾經(jīng)指出：「生活中，我們并不總是持有好牌，但有時，一手爛牌也能打得很好?！?/p>

其實很多AI也很擅長打德?lián)洌鼈兠鎸tratego時，卻懵逼了——這個游戲的流程實在是太長了！

玩家要獲勝，需要走出數(shù)百步。所以游戲中的推理，必須針對大量的連續(xù)動作，在這個過程中，很難明顯看出每個動作對于最終結(jié)果會有怎樣的影響。

國際象棋、撲克、圍棋和Strateg之間的規(guī)模差異

而且，與國際象棋、圍棋和撲克牌相比，可能的博弈狀態(tài)數(shù)量（「博弈樹復(fù)雜性」）已經(jīng)超出了圖表，解決起來更是異常困難。

而這，也正是Stratego令人如此興奮的原因——它代表了AI社區(qū)長達數(shù)十年的挑戰(zhàn)。

Stratego：AI要征服的高地

多年來，如何讓人工智能在Stratego游戲中脫穎而出，成為AI研究者的重點。

在這個游戲中戰(zhàn)勝人類玩家，主要有兩大難點。

首先，該游戲的博弈樹有10的535次方種狀態(tài)，即一局游戲中會有10的535次方種可能的布局。相比之下，圍棋的布局也只有10的360次方種可能。

其次，在Stratego中，人工智能需要推理對手超過10的66次方種部署策略，而撲克只有一千種可能出現(xiàn)的牌對。

因此，想要破解Stratego紛繁復(fù)雜的布局并非易事，如何戰(zhàn)勝人類Stratego玩家，是AI研究者面對的前所未有的挑戰(zhàn)。

如何完爆其他AI？靠R-NaD這個核心利器

DeepNash之所以完爆其他AI，是因為它采用了一種基于博弈論和無模型深度強化學習相結(jié)合的新穎方法。

「無模型」就意味著，DeepNash并沒有試圖在游戲中明確地模擬對手的狀態(tài)。

尤其是在博弈的早期階段，當DeepNash對對手的棋子知之甚少時，這種建模即使可能完成，大概率也是無效的。

而且，由于Stratego的博弈樹復(fù)雜性如此之大，DeepNash無法采用其他AI在玩游戲時用的蒙特卡洛樹搜索。后者正是AI在不太復(fù)雜的棋盤游戲和撲克中，取得里程碑式成就的關(guān)鍵。

可見，均衡策略雖然可以在對局雙方輪流行動的完全信息博弈中發(fā)揮作用，但它在不完全信息博弈中就顯得力不從心。

DeepNash采用的，是一種新的博弈論算法思想——正則化納什動態(tài)規(guī)劃（Regularized Nash Dynamic，R-NaD）。

這個無模型的強化學習算法，是DeepNash的核心。

它引導(dǎo)著DeepNash，讓它的學習行為朝著納什均衡的方向發(fā)展。

DeepNash將R-NaD與深度神經(jīng)網(wǎng)絡(luò)架構(gòu)相結(jié)合，并收斂到納什均衡。

包括三步：獎勵轉(zhuǎn)換（reward transformation）、動態(tài)規(guī)劃（dynamics）和更新迭代（udate）。

研究團隊通過重復(fù)應(yīng)用這三個步驟，直到生成一系列固定點用以證明算法收斂到原始博弈的納什均衡。

對戰(zhàn)最強的Stratego機器人（包括計算機戰(zhàn)略世界錦標賽的幾位獲勝者）時，DeepNash的勝率高達97%，經(jīng)常取得100%的勝率。

而在Gravon游戲平臺上，對抗頂級的人類玩家時，DeepNash取得了84%的勝率，贏得了歷史前三的排名。

當然，在對局中不能無限制地通過博弈論達到納什均衡，因為這種方式下玩家的勝率無法保證。

均衡策略只在完全信息博弈下充分適用，在不完全信息的游戲下，還需要別的策略才能出奇制勝。

在初始的排兵布陣上，DeepNash就采用了一些非凡的玩法。為了變得難以利用（hard to exploit），DeepNash制定了一種不可預(yù)測的策略（unpredictable strategy）。

這意味著在初期的部署上，就要足夠多變，防止對手在隨后的一系列對陣中，發(fā)現(xiàn)自己的模式。

而在博弈階段，DeepNash也會在看似相同的動作之間，盡量地隨機化（randomise），來防止自己變得可利用。

在這個過程中，隱藏信息非常重要。

隱藏信息，讓對手摸不著頭腦

現(xiàn)實場景下，人們還會用其他手段來取得勝利，如詐唬（bluffing）。

正如「博弈論之父」馮·諾伊曼所描述的那樣：「現(xiàn)實生活中充滿『虛張聲勢』、『欺騙的小伎倆』以及『猜測別人會認為我打算做什么』?！?/p>

陶哲軒的「紅眼睛與藍眼睛自殺難題」：我知道，我知道他知道，我知道他知道他知道……

在這方面，DeepNash也是不遑多讓。

研究團隊展示了DeepNash的兩種唬人技巧：主動詐唬（positive bluffing）與被動詐唬（negative bluffing）。

所謂主動詐唬，就是假裝自己的棋子等級很高，威懾對手。簡單來說就是「虛張聲勢」。

在這個例子中，DeepNash就給我們好好地上了一課：

在對戰(zhàn)人類玩家（紅方）時，DeepNash（藍方）在游戲初期以犧牲了 7（少校）和 8（上校）等棋子的代價，找出了對手的 10（元帥）， 9（將軍），一個8和兩個7。

至此，DeepNash（藍方）就找到對手的許多最強大的棋子，同時，將自己的關(guān)鍵棋子隱藏起來。

乍一看，DeepNash似乎處于明顯劣勢：它的7和8 out 了，但人類對手保留了排名7及以上的所有棋子。

但是，DeepNash笑到了最后——憑借著自己探得的對方高層的可靠情況，它估算自己的獲勝幾率為70%。

最終，它的確獲勝了。

虛張聲勢的「藝術(shù)」

在撲克中，優(yōu)秀的玩家會玩心理戰(zhàn)，即使在我方弱勢的情況下，也要讓對方形成威懾。

DeepNash也學會了這種虛張聲勢的策略——被動詐唬（negative bluffing）。

也就是我們常說的「扮豬吃老虎」：將自己等級高的棋子偽裝成等級低的棋子，等到對方上當后再一舉拿下。

在下面這個例子中，DeepNash使用2（很弱是偵察兵）去追擊對手暴露身份的8。

人類對手據(jù)此判斷，追擊者很可能是10，因此嘗試引誘它進入間諜的伏擊圈。

最終，DeepNash成功地以小博大，用小棋子2成功地滅掉了對手的關(guān)鍵棋子間諜。

人類玩家（紅方）確信追逐自己的8的未知棋子一定是 DeepNash 的 10（因為此時DeepNash已經(jīng)輸?shù)袅俗约何ㄒ坏?

以下是DeepNash與（匿名）人類專家進行的這四個完整游戲視頻，第 1場、第 2場、第 3場、第 4 場，點擊進去，你會收獲更多的驚喜。（視頻地址在引用素材中列出）

DeepNash的游戲水平讓我感到驚訝。我從未聽說過，有哪個人造Stratego玩家的水平，能接近贏得人類玩家所需的水平。

但親自與DeepNash交手后，我對它在Gravon上取得前3的排名并不驚訝。我預(yù)測：如果讓它參加人類的世界錦標賽，它會做得很好。

——Vincent de Boer，論文合著者，前Stratego世界冠軍

未來不可估量

可以看到，DeepMind的這種新穎的R-NaD方法，可以直接應(yīng)用于完美或不完美信息的其他雙人零和博弈。

R-NaD有潛力超越雙人游戲的設(shè)定，解決大規(guī)模的現(xiàn)實世界問題。

此外，R-NaD還有望在其他不同目標的領(lǐng)域，解鎖AI的新應(yīng)用。

比如在交通管理的規(guī)模優(yōu)化中，人們不清楚他人的意圖或環(huán)境信息，此時R-NaD有望優(yōu)化司機的出行時間。

人類的世界，天然地具有不可預(yù)測性。

而現(xiàn)在，人們創(chuàng)建了一個面對不確定性時具有魯棒性的通用AI系統(tǒng)，這讓我們對于人類的未來充滿了想象。

參考資料：

http://www.science.org/doi/10.1126/science.add4679

https://www.nature.com/articles/d41586-022-04246-7

https://www.deepmind.com/blog/mastering-stratego-the-classic-game-of-imperfect-information

https://youtu.be/HaUdWoSMjSY

https://youtu.be/L-9ZXmyNKgs

https://youtu.be/EOalLpAfDSs

https://youtu.be/MhNoYl_g8mo