論文題目：
Navigating the landscape of multiplayer games
論文地址：
https://www.nature.com/articles/s41467-020-19244-4#Sec2
多人游戲與策略空間
多人游戲是評(píng)價(jià)和訓(xùn)練AI的重要實(shí)驗(yàn)平臺(tái)，以DeepMind為代表的研究者在國(guó)際象棋、圍棋等兩人零和游戲中創(chuàng)造出了超出人類(lèi)能力的智能主體agent。
但是要繼續(xù)取得進(jìn)步，就需要對(duì)游戲進(jìn)行適當(dāng)?shù)姆诸?lèi)，評(píng)估不同游戲的特性，從而針對(duì)性地訓(xùn)練agent。StarCraft II（星際爭(zhēng)霸）、德州撲克等多人互動(dòng)類(lèi)型的游戲?qū)I技術(shù)提出了挑戰(zhàn)。
為了研究游戲中多個(gè)agent之間如何互動(dòng)，DeepMind研究者利用圖論工具，深入分析了一些大型游戲的拓?fù)浣Y(jié)構(gòu)。相關(guān)成果近日發(fā)表在Nature communications上。
該研究的創(chuàng)新點(diǎn)在于建立了能自動(dòng)化地發(fā)現(xiàn)游戲中的拓?fù)浣Y(jié)構(gòu)的工具，使得各類(lèi)游戲都被放在同一策略空間中進(jìn)行分析。
所謂策略空間（landscape of games），可以看成是將游戲的背景抽離，而只關(guān)注游戲中玩家的策略和互動(dòng)怎樣影響玩家收益。
玩家從青銅到黃金的升級(jí)過(guò)程，不僅是策略的提升過(guò)程，更是玩家（或玩家的策略風(fēng)格）在策略空間的移動(dòng)過(guò)程。有些游戲所需的策略，位于策略空間的高原，一開(kāi)始就不容易。而有些游戲所需的策略位于山地，最初入門(mén)不難，但爬到山頂卻困難重重。這兩種游戲因?yàn)槠鋵W(xué)習(xí)曲線的差異，在策略空間的不同位置。
圖1：將不同游戲置于同一策略空間
研究者將不同游戲置于同一策略空間，如圖所示，其中位置相近的游戲，盡管其規(guī)則不同，但其在策略空間上的相近意味著游戲玩家所需的策略相似。
策略空間下的三種游戲
無(wú)論一個(gè)游戲是否有趣，游戲中必然涉及到幾個(gè)玩家、多種策略，還可以考慮游戲的結(jié)果是否零和，不同玩家間是否對(duì)稱。這些考慮角度都可以看成是從拓?fù)浣Y(jié)構(gòu)上分析游戲。對(duì)于簡(jiǎn)單的游戲，用上述的指標(biāo)可以將其分類(lèi)。
而對(duì)于真實(shí)世界中更復(fù)雜的游戲，可以根據(jù)策略的計(jì)算復(fù)雜度進(jìn)行分類(lèi)。然而一個(gè)計(jì)算上有挑戰(zhàn)性的游戲，并不一定有趣。這說(shuō)明游戲很難通過(guò)單一維度分類(lèi)。
研究者采用的分析方法，是將不同的策略（或者代表某個(gè)策略的agent）看成一群節(jié)點(diǎn)，分析不同策略（或agent）之間的關(guān)系。并建立收益矩陣和網(wǎng)絡(luò)。
根據(jù)不同策略之間的對(duì)比，可以構(gòu)建收益矩陣，如圖2所示。每個(gè)游戲由兩個(gè)玩家組成，每個(gè)玩家有10個(gè)策略（從S0到S9）。格點(diǎn)顏色代表兩兩策略在游戲中出現(xiàn)時(shí)對(duì)應(yīng)的收益（payoff）。紅色表示收益為正，即該策略贏了對(duì)位的另一種策略。收益為負(fù)則是青色。
圖2：不同策略相遇時(shí)，對(duì)應(yīng)的收益矩陣
盡管游戲收益變化各種各樣，但當(dāng)我們剔除游戲本身隨機(jī)性導(dǎo)致的差異，就可以將游戲分為三類(lèi)，分別是可傳導(dǎo)型（圖2-b）、循環(huán)型（圖2-e）和隨機(jī)型（圖2-h）。
可傳導(dǎo)型游戲有明確的傳遞順序，例如Elo機(jī)制游戲，排位高的玩家往往對(duì)應(yīng)著更優(yōu)的策略。循環(huán)型游戲，其策略具有周期性的結(jié)構(gòu)。經(jīng)典的循環(huán)游戲是石頭剪刀布，策略之間彼此制約，形成循環(huán)。而隨機(jī)型游戲，則缺乏清晰的特征。
在這三類(lèi)游戲中，收益變化還會(huì)顯著影響解決游戲的難度，如圖2-c、圖2-f、圖2-i所示。
如何分析游戲的策略空間
該研究中，對(duì)于石頭剪刀布這樣的簡(jiǎn)單游戲，可以窮舉出所有可能的策略。而對(duì)于星際爭(zhēng)霸這樣的大型游戲，則是通過(guò)抽樣，選出部分策略。進(jìn)而構(gòu)建上述的策略矩陣。
圖3：構(gòu)建游戲之間策略空間的流程
構(gòu)建不同游戲策略空間的步驟如圖所示。首先是根據(jù)α-Rank算法，將收益矩陣拆分為不同策略間的轉(zhuǎn)移概率。之后將該圖的特征值映射到拉普拉斯空間，通過(guò)頻域分析，將相似的策略聚類(lèi)。再構(gòu)建出高層次的策略轉(zhuǎn)移圖（從c到e），而將圖中的統(tǒng)計(jì)量進(jìn)行主成分分析（從f到g）。
最終根據(jù)主成分和游戲策略分類(lèi)，就可以生成游戲的策略空間。不同策略類(lèi)型的游戲占據(jù)不同的空間位置。
這種將游戲表示為圖或網(wǎng)絡(luò)的方法，能使我們對(duì)游戲底層結(jié)構(gòu)和復(fù)雜性有更多的洞察。在論文中，作者還發(fā)現(xiàn)游戲策略網(wǎng)絡(luò)的復(fù)雜度和解決游戲的復(fù)雜度之間具有顯著的相關(guān)性。
這套方法能夠用來(lái)分析復(fù)雜的游戲，并將其歸類(lèi)。
AlphaGo和AlphaStar是DeepMind分別為圍棋和星際爭(zhēng)霸設(shè)計(jì)的游戲AI。研究者根據(jù)上述流程，分別研究了它們?cè)谟螒虿呗钥臻g的位置，以及對(duì)應(yīng)的游戲類(lèi)型。
圖4：AlphaGo的游戲策略進(jìn)行分析的過(guò)程
如上圖所示，對(duì)AlphaGo策略聚類(lèi)后，最終能夠?qū)鍤w為循環(huán)型的游戲，即不存在一個(gè)始終占優(yōu)的策略。這也符合我們的常識(shí)。
除了歸類(lèi)，該方法還可以區(qū)分不同策略等級(jí)的玩家（agent）所帶來(lái)的影響。
圖5：使用所有AlphaStar版本來(lái)分析星際爭(zhēng)霸
在對(duì)星際爭(zhēng)霸這樣涉及三個(gè)種族的對(duì)戰(zhàn)類(lèi)游戲的分析中，使用AlphaStar的不同版本（對(duì)應(yīng)不同能力級(jí)別的策略），可以構(gòu)建出游戲的策略空間，如圖5所示?？梢钥吹綀D5-d中，不存在一個(gè)最優(yōu)的策略。是循環(huán)型游戲。
圖6：只用最強(qiáng)的幾個(gè)AlphaStar來(lái)分析星際爭(zhēng)霸
而只使用最強(qiáng)的數(shù)個(gè)AlphaStar智能體，構(gòu)建策略的收益矩陣，經(jīng)過(guò)相同的分析步驟，卻可以得出截然不同的結(jié)論。如圖6-h所示，存在一個(gè)比其他策略都好的最優(yōu)策略。這意味著對(duì)很強(qiáng)的AI來(lái)說(shuō)，星際爭(zhēng)霸是可傳導(dǎo)型游戲。強(qiáng)者之間博弈，反而更容易找到最強(qiáng)的。
研究游戲策略空間的意義
該研究首次結(jié)合博弈論和圖論，根據(jù)游戲策略間的關(guān)系構(gòu)建網(wǎng)絡(luò)，對(duì)多種游戲進(jìn)行了統(tǒng)一分析，論證了復(fù)雜網(wǎng)絡(luò)方法可以用來(lái)解決游戲規(guī)則生成等問(wèn)題。
AI的發(fā)展，與待解決的問(wèn)題息息相關(guān)。挖掘出游戲的策略空間，未來(lái)就可能人工生成位于特定策略空間位置的新游戲，并且設(shè)計(jì)特定的AI解決該游戲。這會(huì)讓AI研究更有針對(duì)性，進(jìn)而擴(kuò)展AI可能的應(yīng)用領(lǐng)域。
如何生產(chǎn)大量有趣的自適應(yīng)環(huán)境以支持研究，是多主體建模、人工社會(huì)、人工生命等領(lǐng)域長(zhǎng)期關(guān)注的問(wèn)題。構(gòu)建游戲策略空間，對(duì)多主體建模的環(huán)境、規(guī)則設(shè)計(jì)也有所啟發(fā)。
除了對(duì)游戲AI和建模設(shè)計(jì)的啟發(fā)，在其他學(xué)科中涉及多個(gè)參與者或多種策略的復(fù)雜博弈問(wèn)題，例如入侵物種和本地物種間的相互作用，也可以借鑒本研究提供的框架。
作者：郭瑞東、劉培源 編輯：鄧一雪
復(fù)雜科學(xué)最新論文
集智斑圖頂刊論文速遞欄目上線以來(lái)，持續(xù)收錄來(lái)自Nature、Science等頂刊的最新論文，追蹤復(fù)雜系統(tǒng)、網(wǎng)絡(luò)科學(xué)、計(jì)算社會(huì)科學(xué)等領(lǐng)域的前沿進(jìn)展?，F(xiàn)在正式推出訂閱功能，每周通過(guò)微信服務(wù)號(hào)「集智斑圖」推送論文信息。掃描下方二維碼即可一鍵訂閱：
聯(lián)系客服
