近日，DeepMind的AI智能體DeepNash，在西洋陸軍棋（Stratego）中花式擊敗專業級人類玩家，成功躋身Top 3。
12月1日，論文正式在Science上發表。
論文地址：http://www.science.org/doi/10.1126/science.add4679
在現今這個時代，玩遊戲的AI已經發展到一個全新的階段。
以往，許多科學家會用西洋棋和圍棋訓練AI，而DeepMind這次用的Stratego，是一款經典的棋盤遊戲，要比西洋棋和圍棋更複雜，比撲克更巧妙。
而這個名為DeepNash的AI智能體，透過與自己對戰的方式，從零開始學習Stratego。
現在，DeepNash在世界上最大的線上Stratego平台Gravon的人類專家中，排名歷史前三。
DeepNash採用的是一種全新的打法，理論基礎是賽局理論和無模型深度強化學習。
看得出來，這個名字也意在致敬著名的美國數學家約翰‧納許（John Nash）。
他所提出的納許均衡（Nash equilibrium），又稱為非合作賽局均衡，是賽局理論中非常重要的一環。
歷來，棋盤遊戲就一直是衡量AI進步的標準，因為它能夠使我們研究人類和機器如何在受控環境中，制定和執行策略。
而這個Stratego的玄機，究竟在哪裡呢？
與西洋棋和圍棋的不同之處在於，Stratego是一種不完全資訊賽局：玩家無法直接觀察對手棋子的身份。
因為這種複雜性，基於AI的Stratego系統，往往再努力，也就是業餘水平，不可能達到「專家」的水準。
在以往，各種AI之所以在遊戲中大獲全勝、完爆人類，是因為一種叫做「博弈樹搜尋」的AI技術。
「遊戲樹搜尋」雖然可以在充分掌握資訊的各種遊戲中大殺四方，但對於Stratego這樣的遊戲，卻有些束手無策，因為它的可擴展性不夠。
而在這一點上，DeepNash就完爆了博弈樹搜尋。
實際上，DeepNash掌握了Stratego的價值，已經遠遠超越了這個遊戲本身。
現實世界往往就是很複雜，資訊是有限的。真正先進的AI系統，所面臨的環境就如同Stratego。
DeepNash成功地向我們展示了，AI如何在不確定的情況下，成功地平衡了結果，解決了複雜的問題。
Stratego怎麼玩
Stratego是一款回合製奪旗遊戲。遊戲中，玩家需要虛張聲勢，迂迴戰術，收集訊息，巧妙地操作。
它是一款零和博弈，所以一個玩家的任何收益，都代表著對手同等數量的損失。
聽起來似乎跟我們的軍棋很像。
Stratego與軍棋的不同之處在於，它有更多數量的棋子、更多的軍階較多，棋盤設計較簡單，沒有鐵路、行營和裁判。
雙方布陣時，要將所有棋子豎立，不能讓對方看到。
布陣完成之後，由紅方先走棋，隨後輪流移動一枚棋子。
棋子中，軍旗和地雷不能移動，偵察兵可以橫豎移動任意格，不可越過棋子，其餘棋子只能橫豎走一格。
當雙方棋子在同一格內，就一同揭開，判斷大小，勝的棋子放回原位、正面朝後，輸的棋子就被移除。
Stratego勝利方式與中國軍棋類似，以奪得對方軍旗或消滅所有能動的棋子為勝利。
為什麼Stratego對於AI這麼有挑戰性？部分原因在於，它是一種不完全資訊賽局。
Stratego中的兩位玩家，在把40個棋子排成起始陣型時，是彼此隱藏的。
因為玩家無法獲得相同的知識，因此在做出任何決定時，他們都需要平衡所有可能的結果。
Stratego棋子的種類和排名
#左：棋子排名。在遊戲中，軍階較高的棋子獲勝，唯一的例外是10（元帥）被間諜攻擊；炸彈總是獲勝，唯一的例外是被礦工捕獲。
中間：可能的起始陣型。旗幟要安全地藏在後面，兩側的炸彈提供保護。兩個淡藍色區域是“湖泊”，永遠不能進入。
右：一盤正在進行的遊戲，可以看到，藍方的間諜捕獲了紅方的元帥。
這個遊戲，把AlphaZero都難倒了
在Stratego中，訊息都是隱藏的。
只有遭遇其他玩家時，對手棋子的身份才會顯露出來。
而西洋棋和圍棋的不同之處在於，它們是「完美資訊博弈」，因為對戰雙方確切地知道每一顆棋子的位置和身分。
DeepMind的AlphaZero，在完美資訊遊戲中表現一向出色，但在Stratego中，它卻被難倒了。
在西洋棋中，AlphaZero在4小時後就超越了Stockfish；在將棋中，AlphaZero在2小時後超越了Elmo；而圍棋中，AlphaZero在30小時後超越了擊敗李世石的AlphaGo
Stratego更類似於德州撲克，需要類似人類的能力——人類需要在資訊不全的情況下做出決定，還需要虛張聲勢。
美國作家傑克倫敦曾經指出：「生活中，我們並不總是持有好牌，但有時，一手爛牌也能打得很好。」
其實很多AI也很擅長打德撲，但它們面對Stratego時，卻懵逼了－－這個遊戲的流程實在是太長了！
玩家要獲勝，需要走出數百步。所以遊戲中的推理，必須針對大量的連續動作，在這個過程中，很難明顯看出每個動作對於最終結果會有怎樣的影響。
西洋棋、撲克、圍棋和Strateg之間的規模差異
而且，與西洋棋、圍棋和撲克牌相比，可能的博弈狀態數量（「博弈樹複雜度」）已經超越了圖表，解決起來更是異常困難。
而這，也正是Stratego令人如此興奮的原因──它代表了AI社群長達數十年的挑戰。
Stratego：AI要征服的高地
多年來，如何讓人工智慧在Stratego遊戲中脫穎而出，成為AI研究者的重點。
在這個遊戲中擊敗人類玩家，主要有兩大難點。
首先，該遊戲的賽局樹有10的535次方種狀態，即一局遊戲中會有10的535次方種可能的佈局。相較之下，圍棋的佈局也只有10的360次方種可能。
其次，在Stratego中，人工智慧需要推理對手超過10的66次方種部署策略，而撲克只有一千種可能出現的牌對。
因此，想要破解Stratego紛繁複雜的佈局並非易事，如何戰勝人類Stratego玩家，是AI研究者面對的前所未有的挑戰。
DeepNash之所以完爆其他AI，是因為它採用了一種基於博弈論和無模型深度強化學習相結合的新穎方法。
「無模型」就意味著，DeepNash並沒有試圖在遊戲中明確地模擬對手的狀態。
尤其是在博弈的早期階段，當DeepNash對對手的棋子知之甚少時，這種建模即使可能完成，大機率也是無效的。
而且，由於Stratego的博弈樹複雜性如此之大，DeepNash無法採用其他AI在玩遊戲時用的蒙特卡羅樹搜尋。後者正是AI在不太複雜的棋盤遊戲和撲克中，取得里程碑式成就的關鍵。
可見，均衡策略雖然可以在對局雙方輪流行動的完全資訊賽局中發揮作用，但它在不完全資訊賽局中就顯得力不從心。
DeepNash採用的，是一種新的博弈論演算法思想－正則化納許動態規劃（Regularized Nash Dynamic，R-NaD）。
這個無模型的強化學習演算法，是DeepNash的核心。
它引導著DeepNash，讓它的學習行為朝著納許均衡的方向發展。
DeepNash將R-NaD與深度神經網路架構結合，並收斂到納許均衡。
包含三步驟：獎勵轉換（reward transformation）、動態規劃（dynamics）和更新迭代（udate）。
研究團隊透過重複應用這三個步驟，直到產生一系列固定點用以證明演算法收斂到原始博弈的納許均衡。
對戰最強的Stratego機器人（包括電腦戰略世界錦標賽的幾位獲勝者）時，DeepNash的勝率高達97%，經常取得100%的勝率。
而在Gravon遊戲平台上，對抗頂級的人類玩家時，DeepNash取得了84%的勝率，贏得了歷史前三名的排名。
當然，在對局中不能無限制地透過賽局理論達到納許均衡，因為這種方式下玩家的勝率無法保證。
均衡策略只在完全資訊賽局下充分適用，在不完全資訊的遊戲下，還需要別的策略才能出奇制勝。
在初始的排兵布陣上，DeepNash就採用了一些非凡的玩法。為了變得難以利用（hard to exploit），DeepNash制定了一種不可預測的策略（unpredictable strategy）。
這意味著在初期的部署上，就要足夠多變，防止對手在隨後的一系列對陣中，發現自己的模式。
而在賽局階段，DeepNash也會在看似相同的動作之間，盡量隨機化（randomise），來防止自己變得可利用。
在這個過程中，隱藏訊息非常重要。
隱藏訊息，讓對手摸不著頭腦
現實場景下，人們還會用其他手段來取得勝利，如詐唬（bluffing）。
正如「博弈論之父」馮諾伊曼所描述的：「現實生活中充滿『虛張聲勢』、『欺騙的小伎倆』以及『猜測別人會認為我打算做什麼』。 」
陶哲軒的《紅眼睛與藍眼睛自殺難題》：我知道，我知道他知道，我知道他知道他知道…
在這方面，DeepNash也是不遑多讓。
研究團隊展示了DeepNash的兩種唬人技巧：主動詐唬（positive bluffing）與被動詐唬（negative bluffing）。
所謂主動詐唬，就是假裝自己的棋子等級很高，威懾對手。簡單來說就是「虛張聲勢」。
在這個例子中，DeepNash就給我們好好地上了一課：
在對戰人類玩家（紅方）時，DeepNash（藍方）在遊戲初期以犧牲了7（少校）和8（上校）等棋子的代價，找出了對手的10（元帥）， 9（將軍），一個8和兩個7。
至此，DeepNash（藍方）就找到對手的許多最強大的棋子，同時，將自己的關鍵棋子隱藏起來。
乍一看，DeepNash似乎處於明顯劣勢：它的7和8 out 了，但人類對手保留了排名7及以上的所有棋子。
但是，DeepNash笑到了最後——憑藉著自己探得的對方高層的可靠情況，它估算自己的獲勝幾率為70%。
最終，它的確贏了。
虛張聲勢的「藝術」
在撲克中，優秀的玩家會玩心理戰，即使在我方弱勢的情況下，也要讓對方形成威懾。
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有潛力超越雙人遊戲的設定，解決大規模的現實世界問題。
此外，R-NaD還有望在其他不同目標的領域，解鎖AI的新應用。
例如在交通管理的規模優化中，人們不清楚他人的意圖或環境訊息，此時R-NaD有望優化司機的出行時間。
人類的世界，天然地具有不可預測性。
而現在，人們創造了一個面對不確定性時具有魯棒性的通用AI系統，這讓我們對於人類的未來充滿了想像。
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
以上是DeepMind再登Science！ AI「破壁者」玩心機吊打人類大師的詳細內容。更多資訊請關注PHP中文網其他相關文章！
