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