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

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

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

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

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

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

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

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

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

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

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

Stratego的玄機在哪里？

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

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

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

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

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

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

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

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

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

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

Stratego怎么玩

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

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

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

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

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

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

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

當雙方棋子在同一格內，就一同揭開，判斷大小，勝的棋子放回原位、正面朝后，輸的棋子就被移除。

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

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

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

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

Stratego棋子的種類和排名

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

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

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

這個游戲，把AlphaZero都難倒了

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

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

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

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

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

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

美國作家杰克倫敦曾經指出：「生活中，我們并不總是持有好牌，但有時，一手爛牌也能打得很好。」

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

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

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

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

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

Stratego：AI要征服的高地

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

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

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

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

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

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

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

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

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

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

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

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

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

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

DeepNash將R-NaD與深度神經網絡架構相結合，并收斂到納什均衡。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

最終，它的確獲勝了。

虛張聲勢的「藝術」

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

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

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

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

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

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

人類玩家（紅方）確信追逐自己的8的未知棋子一定是 DeepNash 的 10（因為此時DeepNash已經輸掉了自己唯一的9

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

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

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

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

未來不可估量

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

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

此外，R-NaD還有望在其他不同目標的領域，解鎖AI的新應用。

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

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

而現(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