張宏達(dá) ,李德才 ,何玉慶
(1.中國科學(xué)院沈陽自動化研究所機(jī)器人學(xué)國家重點(diǎn)實(shí)驗(yàn)室,沈陽 110016;2.中國科學(xué)院機(jī)器人與智能制造創(chuàng)新研究院,沈陽 110016;3.中國科學(xué)院大學(xué),北京 100049)
2016年3月,Deepmind科研團(tuán)隊(duì)的圍棋程序AlphaGo[1]以4∶1的成績戰(zhàn)勝韓國圍棋世界冠軍李世石,這一研究成果在全球范圍內(nèi)引起巨大轟動,人工智能研究再一次吸引了世界的目光。在攻克圍棋這一艱巨任務(wù)之后,Deepmind將研究重點(diǎn)轉(zhuǎn)向更加復(fù)雜的領(lǐng)域——多智能體博弈游戲,并與美國電子游戲公司暴雪娛樂(Blizzard Entertainment)合作,在星際爭霸II的游戲環(huán)境基礎(chǔ)上開發(fā)了可進(jìn)行更高水平人工智能研究的學(xué)習(xí)環(huán)境。鑒于該領(lǐng)域聚集了當(dāng)前人工智能研究領(lǐng)域最具挑戰(zhàn)的難題,國內(nèi)外眾多科研單位也競相投入到這一領(lǐng)域當(dāng)中。多智能體博弈游戲不僅在人工智能研究領(lǐng)域極具研究價(jià)值,其在社會管理、智能交通、經(jīng)濟(jì)、軍事等領(lǐng)域同樣具有巨大的潛在應(yīng)用價(jià)值。
對于當(dāng)前狀態(tài)或動態(tài)變化既無完美信息又無完整信息可用的復(fù)雜動態(tài)環(huán)境,給人工智能研究帶來顯著挑戰(zhàn)[2]?,F(xiàn)實(shí)社會中很多大型、復(fù)雜的動態(tài)環(huán)境問題如路面交通系統(tǒng)、氣象預(yù)報(bào)、經(jīng)濟(jì)預(yù)測、智慧城市管理、軍事決策等均是實(shí)例。然而,對這些實(shí)際問題進(jìn)行建模仿真存在很大困難。與此同時(shí),一系列實(shí)時(shí)策略游戲提供了與真實(shí)環(huán)境相似的、非完美和非完整信息、長遠(yuǎn)規(guī)劃、復(fù)雜問題決策的仿真環(huán)境。這些實(shí)時(shí)策略游戲環(huán)境既能模擬現(xiàn)實(shí)問題的關(guān)鍵難點(diǎn),又具有可準(zhǔn)確評估、迭代迅速、便于交互和布署、可重復(fù)等特點(diǎn),為解決實(shí)際問題提供了絕佳的研究平臺。因此,基于實(shí)時(shí)策略游戲環(huán)境的研究工作對人工智能技術(shù)的發(fā)展和解決復(fù)雜的實(shí)際問題都有重要意義。在眾多的研究平臺中,星際爭霸以其豐富的環(huán)境信息、逼真的環(huán)境場景等特點(diǎn)成為常用的理論研究和方法驗(yàn)證平臺。
實(shí)時(shí)策略游戲——星際爭霸具有實(shí)時(shí)對抗、巨大的搜索空間、非完全信息博弈、多異構(gòu)智能體協(xié)作、時(shí)空推理、多復(fù)雜任務(wù)、長遠(yuǎn)全局規(guī)劃等特點(diǎn),同時(shí)這些也是人工智能領(lǐng)域極具挑戰(zhàn)的難題。自星際爭霸第一版游戲于1998年正式發(fā)布以來,不少研究者將其作為人工智能研究環(huán)境進(jìn)行了大量的研究。2010年開始,一些星際爭霸人工智能游戲程序國際競賽開始舉辦,大量人工智能研究和應(yīng)用成果開始發(fā)布。2016年開始,深度學(xué)習(xí)在星際爭霸中的應(yīng)用展現(xiàn)出強(qiáng)大的信息處理和決策能力,自此之后更多的深度學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)算法被應(yīng)用到該研究領(lǐng)域。基于星際爭霸進(jìn)行的一系列人工智能研究極大促進(jìn)了機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、博弈論、多智能體協(xié)作策略等研究領(lǐng)域的發(fā)展,對與星際爭霸相關(guān)的研究成果進(jìn)行總結(jié),特別是近兩年產(chǎn)生的新的研究理論和成果進(jìn)行梳理,有助于把握該研究領(lǐng)域的研究進(jìn)展和動向,為與該領(lǐng)域相關(guān)的研究提供參考。
綜上,本文主要開展了以下幾方面的工作。首先介紹星際爭霸游戲環(huán)境并分析其給人工智能研究所帶來的挑戰(zhàn)。接著,對現(xiàn)階段星際爭霸相關(guān)研究單位研究成果進(jìn)行介紹,并對該領(lǐng)域的相關(guān)研究方法進(jìn)行了分類。在此基礎(chǔ)上,列舉了與星際爭霸人工智能研究相關(guān)的資源,包括研究平臺、數(shù)據(jù)集以及自主游戲程序競賽。最后,對星際爭霸相關(guān)領(lǐng)域未來可行的研究方向進(jìn)行了預(yù)測。
星際爭霸是暴雪娛樂公司發(fā)布的一款極為經(jīng)典的多角色實(shí)時(shí)策略游戲,目前主要有兩版。自主游戲程序競賽基于1998年發(fā)行的第一版游戲環(huán)境,如圖1。2010年發(fā)行的第二版游戲以其更為細(xì)致逼真的游戲環(huán)境和新的競技模式更受玩家的歡迎,如圖2。
星際爭霸提供三種類型的角色供玩家選擇:人族(Terran)、蟲族(Zerg)、神族(Protoss)。每個(gè)種族均包括多種生命角色、戰(zhàn)斗裝備、功能建筑等多類型單元。三種角色各具特色:
圖1 星際爭霸I競賽環(huán)境Fig.1 StarCraft I competition environment
圖2 星際爭霸II游戲環(huán)境Fig.2 StarCraft II game environment
人族:人族單元靈活、多樣,其平衡了蟲族和神族的特點(diǎn),是兩者性能的均衡。其作戰(zhàn)單元和建筑有陸戰(zhàn)隊(duì)員、攻城坦克、巡洋艦、導(dǎo)彈發(fā)射塔等。
蟲族:蟲族繁衍迅速,需要的資源少,單位能力弱但速度快,常以成群的形式以數(shù)量占據(jù)對抗優(yōu)勢。其作戰(zhàn)單元和建筑有小狗、蟑螂、飛龍、孢子塔等。
神族:神族繁殖率不高,但單元科技水平很高、能力強(qiáng),因此需要的資源也多,常以策略的質(zhì)量取代數(shù)量占據(jù)對抗優(yōu)勢。其作戰(zhàn)單元和建筑有狂熱者、圣堂武士、鳳凰戰(zhàn)機(jī)、光子炮等。
在多人對抗模式中,玩家需要收集盡可能多的礦物、天然氣或零散的獎(jiǎng)勵(lì)等資源來建造更多的生產(chǎn)、防御等建筑物和生產(chǎn)更多的作戰(zhàn)單元并提升建筑單元和作戰(zhàn)單元的技能等級,以最短的時(shí)間消滅敵方來贏得勝利。
與棋類游戲相比,多智能體實(shí)時(shí)策略游戲相關(guān)研究更難,主要體現(xiàn)在以下幾點(diǎn)。
(1)多玩家共存、多異構(gòu)智能體合作。與棋類游戲博弈雙方交替進(jìn)行動作不同,實(shí)時(shí)策略游戲中多玩家同時(shí)推動游戲情節(jié)發(fā)展,不同的玩家可以同時(shí)進(jìn)行動作。游戲中有不同的角色單元和功能建筑,如何更好地發(fā)揮每個(gè)單元的功能也是需要考慮的問題。
(2)實(shí)時(shí)對抗及動作持續(xù)性。實(shí)時(shí)策略游戲是“實(shí)時(shí)”的,意味著玩家需要在很短的時(shí)間內(nèi)進(jìn)行決策并行動。與棋類游戲中玩家有幾分鐘的決策時(shí)間不同,星際爭霸游戲環(huán)境以24幀/秒頻率改變,意味著玩家可以以最高不到42毫秒的頻率進(jìn)行動作。若以環(huán)境改變每8幀玩家進(jìn)行一個(gè)動作的平均水平來看,玩家仍需要以每秒3個(gè)動作的頻率進(jìn)行博弈。不僅如此,玩家輸出的動作有一定的持續(xù)性,需要在一定的時(shí)間持續(xù)執(zhí)行,而非棋類游戲玩家的動作是間斷的、突發(fā)的、瞬時(shí)的。
(3)非完整信息博弈和強(qiáng)不確定性。多數(shù)實(shí)時(shí)策略游戲是部分可觀測的,玩家僅能觀察到自己已經(jīng)探索的部分地圖情況。在星際爭霸中,因?yàn)橛袘?zhàn)爭迷霧的存在,玩家只能看到自己所控制的游戲角色當(dāng)前所處環(huán)境的情況,其它環(huán)境信息無法獲知。而棋類游戲玩家可以獲取全棋盤的情況。多數(shù)實(shí)時(shí)策略游戲具有不確定性,即決策過程中采取的動作都有一定概率促成最后的勝利。
(4)巨大的搜索空間及多復(fù)雜任務(wù)。實(shí)時(shí)策略游戲更復(fù)雜,其在狀態(tài)空間的規(guī)模上和每個(gè)決策環(huán)節(jié)可選擇的動作序列均非常巨大。例如,就狀態(tài)空間而言,一般的棋類游戲狀態(tài)空間在1050左右,德州撲克約為1080,圍棋的狀態(tài)空間為10170。而星際爭霸一個(gè)典型地圖上的狀態(tài)空間比所有這些棋類的狀態(tài)空間都要大幾個(gè)量級。以一個(gè)典型的128×128像素地圖為例,在任何時(shí)候,地圖上可能會有5~400個(gè)單元,每個(gè)單元都可能存在一個(gè)復(fù)雜的內(nèi)在狀態(tài)(剩余的能量和擊打值、待輸出動作等),這些因素將導(dǎo)致可能的狀態(tài)極其龐大。即便是僅僅考慮每個(gè)單元在該地圖上可能的位置,400個(gè)單元即有(128×128)400=16384400≈101685種可能。另一種計(jì)算復(fù)雜度的方式以bd來計(jì)算游戲的復(fù)雜度,其中國際象棋b≈35,d≈80,圍棋b≈30~300,d≈150~200,而星際爭霸b的范圍是1050~10200,d≈36000。
多智能體實(shí)時(shí)策略游戲的這些突出難點(diǎn)給該領(lǐng)域人工智能研究方法帶來巨大挑戰(zhàn)。文獻(xiàn)[2]將本領(lǐng)域研究中的挑戰(zhàn)總結(jié)為規(guī)劃、學(xué)習(xí)、不確定性、時(shí)空推理、領(lǐng)域知識開發(fā)和任務(wù)分解六個(gè)方面。在此基礎(chǔ)上,我們將當(dāng)前研究中的挑戰(zhàn)分為多尺度規(guī)劃與多層次決策一致性、多途徑策略學(xué)習(xí)、降低不確定性、空間和時(shí)間上的多模聯(lián)合推理、領(lǐng)域知識開發(fā)和多層次任務(wù)分解六大挑戰(zhàn)。本領(lǐng)域研究難點(diǎn)與研究挑戰(zhàn)的對應(yīng)關(guān)系如圖3所示。
圖3 多智能體實(shí)時(shí)策略游戲存在的難點(diǎn)與人工智能研究挑戰(zhàn)的對應(yīng)關(guān)系Fig.3 Correspondence between the difficulties of multiagent real-time strategy games and the challenges of artificial intelligence research
(1)多尺度規(guī)劃與多層次決策一致性。一方面,由于多智能體游戲中巨大的狀態(tài)空間和可輸出動作,使得一般的對抗規(guī)劃方法如博弈樹搜索已不能滿足需求,多智能體實(shí)時(shí)策略游戲需要多尺度的規(guī)劃。另一方面,實(shí)時(shí)約束為多異構(gòu)智能體大量的低層次動作規(guī)劃與高層次全局決策目標(biāo)的一致性耦合帶來很大困難,難點(diǎn)在于設(shè)計(jì)一種既考慮復(fù)雜多目標(biāo)優(yōu)化又兼顧計(jì)算效率的方法,最終形成多智能體整體行動的實(shí)時(shí)一致性。
(2)多途徑策略學(xué)習(xí)。除對抗規(guī)劃技術(shù)之外,一些研究團(tuán)隊(duì)將注意力放在多途徑策略學(xué)習(xí)技術(shù)上,其中包含三種策略學(xué)習(xí)問題。一是提前學(xué)習(xí),即開發(fā)已有數(shù)據(jù),如已有游戲回放、已有的針對特定地圖的適當(dāng)策略等。難點(diǎn)在于策略的抽象表達(dá)方法以及在實(shí)際博弈過程中如何合理選擇并應(yīng)用這些策略。另外,這些針對特定環(huán)境的策略是否具有普適性也有待驗(yàn)證。二是游戲中學(xué)習(xí),即在博弈過程中在線學(xué)習(xí)提升游戲水平,這些技術(shù)涉及到強(qiáng)化學(xué)習(xí)方法及對手建模等,其難點(diǎn)在于狀態(tài)空間巨大且部分可觀測。三是游戲間相互學(xué)習(xí),即如何將從一個(gè)游戲中學(xué)到的知識用在另一個(gè)游戲中以提升勝率。一些工作是利用簡單博弈論方法從預(yù)先定義的策略池中挑選合適的策略,但這些固定的策略無法根據(jù)具體對抗環(huán)境進(jìn)行自適應(yīng)調(diào)整和策略提升,因此也限制了對抗的競技水平。
(3)降低不確定性。這里的不確定性主要包括兩個(gè)部分。一是由于游戲是部分可觀測的,玩家無法看到全局的情況,因此需要去偵察來了解更多的情況。難點(diǎn)在于如何設(shè)計(jì)具有自適應(yīng)能力的好的偵察策略和知識表示來降低不確定性。除此之外,由于敵人的策略也是未知的,這種不確定性造成決策的無目的性,不能很好地根據(jù)敵人的策略適時(shí)調(diào)整對抗策略,所以需要通過好的預(yù)測模型預(yù)測對手的意圖。
(4)空間和時(shí)間上的多模聯(lián)合推理??臻g上的推理包括不同功能建筑建造的位置、防御攻擊建筑建造的位置以及對戰(zhàn)中各作戰(zhàn)單元所處的位置等應(yīng)該如何合理安排。除此之外,各功能單元在不同的地形上可以發(fā)揮出不同程度的攻擊、防御等功能,如坦克在高地勢時(shí)攻擊范圍更大等,這些也是空間推理應(yīng)考慮的因素。時(shí)間推理是指玩家既要在當(dāng)前戰(zhàn)斗中采取戰(zhàn)術(shù)戰(zhàn)勝敵人,又需要在更高水平上長遠(yuǎn)地規(guī)劃如何安排自己的資源、建造功能建筑或升級、策略轉(zhuǎn)換等。有些策略是短時(shí)間就可以看到效果的,而有些策略需要較長的時(shí)間才發(fā)揮作用,因此需要長遠(yuǎn)全局規(guī)劃和短期局部規(guī)劃的統(tǒng)一。其中長遠(yuǎn)策略規(guī)劃中由于一些策略在很長一段時(shí)間后才發(fā)揮作用,導(dǎo)致智能體在學(xué)習(xí)過程中不能很好地從長時(shí)間的延遲獎(jiǎng)勵(lì)中學(xué)到有用的策略。另外,由于空間推理和時(shí)間推理是兩種不同模式的推理形式,需要構(gòu)建兩種模式相融合的推理策略。
(5)領(lǐng)域知識開發(fā)。實(shí)時(shí)策略游戲已經(jīng)發(fā)展了多年,產(chǎn)生很多可利用的戰(zhàn)術(shù)動作、規(guī)律和策略等數(shù)據(jù)。充分利用該領(lǐng)域的已有知識可極大提升自主游戲程序的競技水平。該領(lǐng)域早期研究者將從數(shù)據(jù)中總結(jié)的策略編寫成代碼,游戲程序可以從這些編好的代碼中選擇。近兩年大量的游戲數(shù)據(jù)集可供機(jī)器學(xué)習(xí)提取有用信息。如何從大量的數(shù)據(jù)中提取有價(jià)值的策略,形成自主游戲程序的決策網(wǎng)絡(luò),仍存在極大挑戰(zhàn)。
(6)多層次任務(wù)分解。多層次任務(wù)分解是指將多智能體博弈游戲分解成不同的子任務(wù),通過分別解決這些子任務(wù)來降低整體解決的難度。主要可分解成以下幾部分:策略,即高水平?jīng)Q策,如全局戰(zhàn)役主要用什么策略;戰(zhàn)術(shù),即當(dāng)前策略、短時(shí)策略,如一場戰(zhàn)斗中采取何種策略;反應(yīng)控制,即戰(zhàn)斗、戰(zhàn)術(shù)實(shí)施,如戰(zhàn)斗中應(yīng)采取何種走位、用哪種武器攻擊等;地形分析,主要包括敵我雙方所處位置、戰(zhàn)斗地形、可通過道路、地勢等信息;智能收集信息,主要包括敵方建造了何種建筑、生產(chǎn)了哪種類型的戰(zhàn)斗單元、正在采取什么樣的策略等信息。對比而言,人類玩家在玩星際爭霸時(shí),決策常分為微觀操作和宏觀大規(guī)模操作。人們不需要進(jìn)行復(fù)雜的多層次任務(wù)分解,只需根據(jù)具體游戲環(huán)境進(jìn)行微觀或宏觀操作即可。
人工智能和游戲的研究歷史可以追溯到1950年[3]。自1997年5月“深藍(lán)”擊敗國際象棋大師卡斯帕羅夫起至今,已有大量的游戲程序戰(zhàn)勝了經(jīng)典游戲中的世界冠軍,如跳棋、奧賽羅和拼字游戲。一些布署深度神經(jīng)網(wǎng)絡(luò)的“大腦”,甚至在極其復(fù)雜的游戲中擊敗了世界冠軍,如圍棋。
從2000年左右開始,人工智能研究人員開始關(guān)注復(fù)雜的戰(zhàn)略模擬游戲。在早期的研究中,一些人認(rèn)為,智能體需要復(fù)雜的表示和推理能力才能在這些環(huán)境中勝出,而構(gòu)建上述能力是具有挑戰(zhàn)性的。研究人員通過抽象狀態(tài)縮小決策搜索空間、遺傳算法學(xué)習(xí)游戲規(guī)劃、使用領(lǐng)域知識消除靜態(tài)對手假設(shè)、從專家示范中提取行為知識等方法降低搜索的難度,為自主游戲程序賦予更強(qiáng)的能力。
在眾多實(shí)時(shí)策略游戲人工智能研究環(huán)境中,星際爭霸相比之前大多數(shù)工作更具挑戰(zhàn)性。該游戲自1997年出現(xiàn)至今吸引了大量人類玩家,并舉辦了各種級別和類型的國際性賽事。2010年起,以AIIDE、SSCAIT、CIG為代表基于星際爭霸I環(huán)境的各類人工智能比賽開始舉辦,阿爾伯塔大學(xué)、斯坦福大學(xué)、Facebook等眾多高校和研究單位投入其中。這期間的人工智能算法一般被稱為經(jīng)典人工智能程序,大多數(shù)基于規(guī)則。這類自主游戲程序可以打敗游戲內(nèi)置程序,但是遠(yuǎn)遠(yuǎn)比不上人類專業(yè)選手,甚至連普通選手也打不過。
2016年開始,以深度學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)為主的智能體自主學(xué)習(xí)方法開始應(yīng)用于該領(lǐng)域,此類算法被稱為現(xiàn)代人工智能程序。Deepmind和暴雪聯(lián)合開發(fā)了基于星際爭霸II的深度學(xué)習(xí)研究環(huán)境SC2LE。國內(nèi)外眾多極具實(shí)力的科研團(tuán)隊(duì)參與其中,國外有如Deepmind、Facebook、阿爾伯塔大學(xué)、牛津大學(xué)、倫敦大學(xué)等,國內(nèi)如阿里巴巴、騰訊以及中國科學(xué)院自動化研究所等也進(jìn)行了相關(guān)研究。
2009年開始,星際爭霸相關(guān)研究成果開始發(fā)表。我們選出有代表性的成果進(jìn)行統(tǒng)計(jì)(詳見表1),并在下一章節(jié)中進(jìn)行分類分析。
表1 星際爭霸主要研究單位和方法Table 1 The main research groups and methods of StarCraft
本文將相關(guān)領(lǐng)域的研究方法分為基于規(guī)則、經(jīng)典機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)及其它有潛力的發(fā)展方向五類,并將指出這些方法適用于解決哪一類挑戰(zhàn)。
基于規(guī)則的方法用于解決策略學(xué)習(xí)和領(lǐng)域知識利用的挑戰(zhàn)。這些方法將人類玩家在實(shí)踐中總結(jié)出的規(guī)則編寫成程序,作為自主游戲程序的一個(gè)策略模塊,游戲程序在游戲進(jìn)行時(shí)根據(jù)游戲的情況選擇對應(yīng)的策略執(zhí)行即可。Certicky M[4]等根據(jù)熟練玩家用建筑物阻擋敵人進(jìn)入的策略編寫了自主游戲程序。提供一個(gè)準(zhǔn)備使用的聲明式解決方案,采用答案集編程(ASP)的范例,使自主游戲程序也具備合理布局建筑物來阻止敵人進(jìn)入的技能。Weber B[5]等以反應(yīng)性計(jì)劃語言ABL構(gòu)建了在游戲中指揮個(gè)體單位的游戲程序,這種反應(yīng)式規(guī)劃是控制低級單位命令的合適技術(shù),部分減少了玩家需要控制的個(gè)體單位。
我們將除深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)之外的機(jī)器學(xué)習(xí)方法歸為經(jīng)典機(jī)器學(xué)習(xí)方法。根據(jù)各方法對應(yīng)解決多尺度規(guī)劃與多層次決策一致性、多途徑策略學(xué)習(xí)、降低不確定性以及領(lǐng)域知識開發(fā)利用四類挑戰(zhàn),將經(jīng)典機(jī)器學(xué)習(xí)方法分為快速搜索與規(guī)劃、對手策略建模和作戰(zhàn)模型、降低不確定性、行為知識提取和利用四類方法。
4.2.1 快速搜索與規(guī)劃
規(guī)劃與決策問題主要關(guān)注自主游戲程序不同層次的對抗策略如何優(yōu)化生成。David C[6]在星際爭霸人工智能競賽中使用在線的啟發(fā)式搜索算法,該搜索算法能夠?qū)崟r(shí)生成專業(yè)人類玩家水平的構(gòu)建命令。其為考慮時(shí)長、持續(xù)時(shí)間、投資組合的貪婪搜索分別設(shè)計(jì)了三種單位微觀管理算法,并將分層投資組合搜索用于搜索巨大的游戲空間。Aha D W[7]等在搜索內(nèi)部空間的遺傳算法以及偏向子計(jì)劃檢索的加權(quán)算法基礎(chǔ)上改進(jìn),引入一個(gè)計(jì)劃檢索算法,消除了前兩種方法假設(shè)靜態(tài)對手的不足,由此可將學(xué)習(xí)的知識擴(kuò)展到具有完全不同策略的對手。Zhen J S[8]等使用擴(kuò)展拓?fù)涞纳窠?jīng)進(jìn)化(NEAT)算法,以增強(qiáng)人工智能游戲程序的適應(yīng)性,實(shí)現(xiàn)快速、實(shí)時(shí)評估和反應(yīng)。
4.2.2 對手策略建模和作戰(zhàn)模型
策略學(xué)習(xí)問題主要關(guān)注如何從回放數(shù)據(jù)中學(xué)到有用的知識。Weber B G[9]用數(shù)據(jù)挖掘方法從大量的游戲日志中學(xué)習(xí)高水平玩家的策略,并為游戲中的對手建模,以此在游戲中檢測對手策略,預(yù)測對手什么時(shí)候執(zhí)行策略并做出行動。Uriarte A[10]等從回放數(shù)據(jù)中學(xué)習(xí)作戰(zhàn)模型并用它們來模擬實(shí)時(shí)策略游戲中的戰(zhàn)斗。
4.2.3 降低不確定性
不確定性問題一般可由為對手建模、為游戲建模的方法來進(jìn)行預(yù)測,或者使用偵察算法等獲取更多的信息來降低不確定性。Gabriel S[11]等通過使用貝葉斯建模來替代布爾值邏輯,處理信息的不完整性和由此產(chǎn)生的不確定性。通過機(jī)器學(xué)習(xí)從高水平玩家的回放數(shù)據(jù)來對動態(tài)對手建模,進(jìn)行戰(zhàn)略和戰(zhàn)術(shù)適應(yīng)。這些基于概率的玩家模型可以通過不同的輸入應(yīng)用于決策,由此解決不確定情況下的多尺度決策。Park H[12]使用偵察算法和機(jī)器學(xué)習(xí)算法來預(yù)測對手的攻擊時(shí)機(jī)。Hostetler J[13]等提出動態(tài)貝葉斯網(wǎng)絡(luò)策略模型,該模型能夠從現(xiàn)實(shí)的觀察中推斷游戲的未觀察部分。Cho H C[14]通過預(yù)測對手的策略改變命令順序。Erickson G[15]提出預(yù)測游戲中哪個(gè)玩家獲勝的模型。Helmke I[16]等用簡單的戰(zhàn)斗近似模型預(yù)測不涉及微觀管理的戰(zhàn)斗。Uriarte A[10]等提出了雙人博弈游戲的戰(zhàn)斗模型,用來模擬游戲中的戰(zhàn)斗,并分析如何從回放數(shù)據(jù)中學(xué)習(xí)作戰(zhàn)模型。
4.2.4 行為知識提取和利用
領(lǐng)域知識開發(fā)和利用目的是更好地利用已有的策略知識和游戲數(shù)據(jù)。Mishra K[17]等提出基于案例的實(shí)時(shí)計(jì)劃和執(zhí)行方法。通過以個(gè)案的形式從專家示范中提取行為知識,將這些知識通過基于案例的行為生成器調(diào)用形成合適的行為,來實(shí)現(xiàn)當(dāng)前計(jì)劃中的目標(biāo)。Synnaeve G[18]等主張通過人類或游戲程序玩家對錄制的游戲完整狀態(tài)進(jìn)行探索,以發(fā)現(xiàn)如何推理策略。他們把軍隊(duì)組合起來,以此減少高斯混合程度,達(dá)到在組的水平上進(jìn)行戰(zhàn)略推理的目的。
基于深度學(xué)習(xí)的方法用于從當(dāng)前大量的高水平玩家數(shù)據(jù)中學(xué)習(xí)策略,以解決領(lǐng)域知識開發(fā)利用的挑戰(zhàn)。Sukhbaatar S[19]等提出一種深度神經(jīng)模型CommNet,它通過使多智能體間保持連續(xù)通信來完成合作任務(wù)。該網(wǎng)絡(luò)模型可使智能體學(xué)習(xí)彼此溝通的能力,相對于非交互智能體產(chǎn)生了更好的表現(xiàn)。Justesen N[20]等通過深度學(xué)習(xí)直接從游戲回放中學(xué)習(xí)星際爭霸中的宏觀管理決策。從高水平玩家的2005個(gè)回放中提取的789571個(gè)狀態(tài)動作來訓(xùn)練神經(jīng)網(wǎng)絡(luò),預(yù)測下一個(gè)構(gòu)建動作。通過將訓(xùn)練好的網(wǎng)絡(luò)整合到一個(gè)開源的星際爭霸自主游戲程序UAlbertaBot中,該系統(tǒng)可以顯著地超越游戲內(nèi)置的自主程序,并以固定的急速策略進(jìn)行對抗。
強(qiáng)化學(xué)習(xí)和深度強(qiáng)化學(xué)習(xí)一般用于解決策略學(xué)習(xí)中的挑戰(zhàn)。我們將使用強(qiáng)化學(xué)習(xí)或深度強(qiáng)化學(xué)習(xí)的方法按照算法內(nèi)容分為Q學(xué)習(xí)及其變體、Actor-Critic結(jié)構(gòu)及其變體以及分布式多智能體強(qiáng)化學(xué)習(xí)三類。
4.4.1 Q學(xué)習(xí)及其變體
Stefan W[21]等應(yīng)用Q學(xué)習(xí)和Sarsa算法的變體,使用資格痕跡來抵消延遲獎(jiǎng)勵(lì)的問題。其設(shè)計(jì)了一個(gè)能夠在復(fù)雜的環(huán)境中以無監(jiān)督的方式學(xué)習(xí)的智能體,替換非自適應(yīng)的、確定性的游戲人工智能程序來執(zhí)行任務(wù)。針對最大化獎(jiǎng)勵(lì)或?qū)W習(xí)速度兩個(gè)不同的側(cè)重點(diǎn),他們證明一步式Q學(xué)習(xí)和Sarsa在學(xué)習(xí)管理戰(zhàn)斗單元方面是最好的。Mnih V[22]等提出深度Q網(wǎng)絡(luò)方法,可以使用端到端的強(qiáng)化學(xué)習(xí)直接從高維視覺輸入中學(xué)習(xí)成功的策略。該方法在Atari游戲上被證明是有效的,這為用深度強(qiáng)化學(xué)習(xí)解決多智能體的游戲提供了思路。Kempka M[23]等在一個(gè)三維第一人稱視角環(huán)境——VizDoom中驗(yàn)證了視覺強(qiáng)化學(xué)習(xí)的可行性。在一個(gè)基本的移動及射擊任務(wù)和一個(gè)更復(fù)雜的迷宮導(dǎo)航兩種場景中,使用具有Q學(xué)習(xí)和經(jīng)驗(yàn)回放的深度卷積神經(jīng)網(wǎng)絡(luò),都能夠訓(xùn)練出展現(xiàn)人類行為的自主游戲程序。Usunier N[24]等提出深度神經(jīng)網(wǎng)絡(luò)控制器從游戲引擎給出的原始狀態(tài)特征來處理微觀管理場景的方法,解決了軍隊(duì)成員在戰(zhàn)斗中短期低水平的控制問題。同時(shí)提出了一個(gè)結(jié)合策略空間直接探索和反向傳播的啟發(fā)式強(qiáng)化學(xué)習(xí)算法,該算法使用確定性策略來收集學(xué)習(xí)的痕跡,這比 “野獸般的探索”更為有效。
4.4.2 Actor-Critic結(jié)構(gòu)及其變體
Peng P[25]等在處理星際爭霸中協(xié)調(diào)多個(gè)戰(zhàn)隊(duì)作戰(zhàn)打敗敵人任務(wù)時(shí),為了保持一個(gè)可擴(kuò)展而有效的通信協(xié)議,引入了一個(gè)多主體雙向協(xié)調(diào)網(wǎng)絡(luò)——BiCNet。該網(wǎng)絡(luò)含有一個(gè)向量化擴(kuò)展的Actor-Critic公式,可以處理對戰(zhàn)雙方不同類型的任意數(shù)量的智能體的戰(zhàn)斗。在沒有任何監(jiān)督如人類示范或標(biāo)記數(shù)據(jù)的情況下,BiCNet可以學(xué)習(xí)各種經(jīng)驗(yàn)豐富的游戲玩家常用的高級協(xié)調(diào)策略。Foerster J[26]等提出了一種反事實(shí)多智能體(COMA)策略梯度的多智能體Actor-Critic方法。COMA使用集中的Critic來估計(jì)Q函數(shù),用分布式的Actor來優(yōu)化智能體的策略。為了解決多智能體信用分配的挑戰(zhàn),其使用了一個(gè)反事實(shí)的基線,邊際化一個(gè)智能體的行為,同時(shí)保持其他智能體的行為固定。在具有顯著局部可觀的分布式多智能體情況下,COMA方法與其它多智能體Actor-Critic方法中最先進(jìn)的集中控制器最好的表現(xiàn)對比,發(fā)現(xiàn)其平均性能顯著提高。Vinyals O[27]等介紹了適用于星際爭霸II領(lǐng)域的典型深度強(qiáng)化學(xué)習(xí)智能體的初始基線結(jié)果。在迷你游戲中,這些智能體可以通過學(xué)習(xí)達(dá)到與新手玩家相當(dāng)?shù)挠螒蛩?。但是,在完整游戲的?xùn)練中,這些智能體無法取得重大進(jìn)展。
4.4.3 分布式多智能體強(qiáng)化學(xué)習(xí)
Lanctot M[28]等為解決多智能體強(qiáng)化學(xué)習(xí)(MARL)中使用獨(dú)立強(qiáng)化學(xué)習(xí)(InRL)策略在訓(xùn)練期間可能會過擬合其他智能體策略的問題,引入了一個(gè)新的度量即聯(lián)合政策關(guān)聯(lián),來量化這種影響。同時(shí)提出一種通用MARL算法,該算法基于對深度強(qiáng)化學(xué)習(xí)生成的策略混合的近似最佳響應(yīng)以及經(jīng)驗(yàn)博弈分析來計(jì)算策略選擇的元策略。Max J[29]等在第一視角多人游戲中采用雙層優(yōu)化的方法。一群獨(dú)立的強(qiáng)化學(xué)習(xí)智能體通過上千種并行游戲以團(tuán)隊(duì)的形式在隨機(jī)產(chǎn)生的環(huán)境中與對手進(jìn)行博弈。其中這群智能體中每個(gè)個(gè)體學(xué)習(xí)其自己的內(nèi)部獎(jiǎng)勵(lì)以補(bǔ)充來自獲勝的稀疏延遲獎(jiǎng)勵(lì),并使用新穎的時(shí)間分層表示來選擇動作,使得智能體可以在多時(shí)間尺度進(jìn)行推理。
(1)子博弈。Brown N[30]等提出用不完美信息博弈中子博弈方法解決分布式博弈和全局目標(biāo)統(tǒng)一的問題。該方法可用于解決多智能體實(shí)時(shí)策略游戲中分布式局部決策與團(tuán)隊(duì)目標(biāo)統(tǒng)一的問題。
(2)增量學(xué)習(xí)。Xiao C J[31]等提出的增量記憶蒙特卡洛搜索樹方法,為多智能體決策系統(tǒng)通過不斷積累來提升決策能力提供潛在的可行方向。
(3)博弈論。Fang F[32]等用博弈論系統(tǒng)預(yù)測可能的襲擊地點(diǎn),打擊偷獵行為。Tuyls K[33]等讓智能體在非對稱博弈中找納什均衡?;诓┺恼搶Χ嘀悄荏w博弈游戲分析,或許可以從更高水平的視野找到解決辦法。
本章介紹與星際爭霸相關(guān)的資源,包括開源研究平臺、開源數(shù)據(jù)集和人工智能程序競賽。
5.1.1 完整星際爭霸學(xué)習(xí)環(huán)境
(1)SC2LE。Deepmind和暴雪在2017年聯(lián)合推出基于星際爭霸II的人工智能學(xué)習(xí)環(huán)境SC2LE。Lanctot M[28]等描述了星際爭霸II領(lǐng)域的觀察、行動和獎(jiǎng)勵(lì)規(guī)范,并提供了一個(gè)開源的基于Python的接口來與游戲引擎進(jìn)行通信。除了完整的游戲地圖之外,還提供了一套迷你游戲,專注于星際爭霸 II游戲中的不同任務(wù)。
(2)TorchCraft。Synnaeve G[34]等開發(fā)了TorchCraft,一個(gè)通過在機(jī)器學(xué)習(xí)框架Torch中控制游戲來實(shí)現(xiàn)諸如“星際爭霸:母巢之戰(zhàn)”等實(shí)時(shí)策略游戲深度學(xué)習(xí)研究的庫。
5.1.2 類似的AI學(xué)習(xí)環(huán)境
(1)輕量級星際爭霸研究環(huán)境
ELF。Tian Y[35]等提出一個(gè)覆蓋范圍廣、輕量級和靈活的基礎(chǔ)強(qiáng)化學(xué)習(xí)研究平臺——ELF。ELF包含三種游戲環(huán)境(微型實(shí)時(shí)策略、奪旗和塔防)的高度可定制的實(shí)時(shí)策略引擎。其中“微型實(shí)時(shí)策略”作為星際爭霸的微型版本,捕捉了關(guān)鍵的游戲動態(tài),可在筆記本電腦上以每秒40K幀速運(yùn)行。該系統(tǒng)與現(xiàn)代強(qiáng)化學(xué)習(xí)方法結(jié)合使用時(shí),可用6個(gè)CPU和1個(gè)GPU的計(jì)算硬件在一天時(shí)間內(nèi)完成端到端的完整游戲的自主游戲程序訓(xùn)練。此外,該平臺在環(huán)境-智能體通信拓?fù)?、?qiáng)化學(xué)習(xí)方法的選擇、游戲參數(shù)的變化等方面是靈活的,并且可以遷移到現(xiàn)有的基于C/C++的游戲環(huán)境,如ALE。
美國紐約大學(xué)和Facebook AI Research設(shè)計(jì)了一個(gè)簡單的2D游戲環(huán)境,用強(qiáng)化學(xué)習(xí)在該環(huán)境上布署各種神經(jīng)模型,在該環(huán)境中訓(xùn)練的模型可直接應(yīng)用于星際爭霸游戲[36]。
(2)其它相似研究環(huán)境
VizDoom。VizDoom是一個(gè)以第一人稱視角多人射擊類3D游戲Doom為基礎(chǔ)、可進(jìn)行以像素信息為輸入的強(qiáng)化學(xué)習(xí)方法研究平臺。Kempka M[23]等在該環(huán)境中驗(yàn)證了視覺強(qiáng)化學(xué)習(xí)的可行性。在一個(gè)基本的移動及射擊任務(wù)和一個(gè)更復(fù)雜的迷宮導(dǎo)航兩種場景中,使用具有Q學(xué)習(xí)和經(jīng)驗(yàn)回放的卷積深度神經(jīng)網(wǎng)絡(luò),都能夠訓(xùn)練出展現(xiàn)人類行為的有能力的自主游戲程序。
ALE。Naddaf Y[37]介紹了街機(jī)游戲?qū)W習(xí)環(huán)境——ALE。ALE為數(shù)百個(gè)Atari 2600游戲環(huán)境提供界面,并為評估和比較強(qiáng)化學(xué)習(xí)、模型學(xué)習(xí)、基于模型的規(guī)劃、模仿學(xué)習(xí)、遷移學(xué)習(xí)等方法提供了一個(gè)嚴(yán)格的測試平臺。ALE提供的評估方法可以在超過55個(gè)不同的游戲中報(bào)告驗(yàn)證結(jié)果。
Gym。由OpenAI開發(fā)的強(qiáng)化學(xué)習(xí)研究環(huán)境和工具包[38]。
Minecraft。微軟開發(fā)了基于Minecraft(我的世界)游戲的人工智能研究平臺[39]。
另外,還有如Deepmind的Psychalab心理學(xué)實(shí)驗(yàn)室開發(fā)的第一人稱視角3D強(qiáng)化學(xué)習(xí)研究環(huán)境等。
5.2.1 基于星際爭霸II的數(shù)據(jù)集
SC2LE。Deepmind和暴雪在推出基于星際爭霸II的人工智能深度學(xué)習(xí)研究環(huán)境SC2LE的同時(shí),對于完整的游戲地圖,還提供了來自人類專業(yè)玩家的游戲回放數(shù)據(jù)集,并給出從該數(shù)據(jù)訓(xùn)練的神經(jīng)網(wǎng)絡(luò)來預(yù)測游戲結(jié)果和玩家行為的初始基線結(jié)果。
MSC。中科院自動化所的張俊格等發(fā)布了基于SC2LE平臺的新型數(shù)據(jù)集MSC[40]。MSC由良好設(shè)計(jì)的特征向量、預(yù)定義的高水平行動和每個(gè)匹配的最終結(jié)果組成。為便于評估和比較,他們還將MSC劃分為訓(xùn)練、驗(yàn)證和測試集。除了數(shù)據(jù)集之外,他們還提出了基線模型,并提出了全局狀態(tài)評估的初始基線結(jié)果,構(gòu)建了命令預(yù)測。為了對星際爭霸II的宏觀管理進(jìn)行研究,還介紹了數(shù)據(jù)集的各種下游任務(wù)和分析。
5.2.2 基于星際爭霸I的數(shù)據(jù)集
Facebook的Lin Z[41]等開發(fā)了基于星際爭霸I的數(shù)據(jù)集。Synnaeve G[18]等提供了包含大部分游戲狀態(tài)(不僅是玩家的命令)的星際爭霸游戲數(shù)據(jù)集。Alberto Uriarte開發(fā)了持續(xù)更新的基于星際爭霸I的高水平玩家離線數(shù)據(jù)集。
5.3.1 AIIDE
AAAI人工智能和互動數(shù)字娛樂會議(AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment,AIIDE)[42]由人工智能促進(jìn)協(xié)會(AAAI)贊助,每年舉行一次。會議展示關(guān)于娛樂中智能系統(tǒng)建模、開發(fā)和評估的跨學(xué)科研究,重點(diǎn)關(guān)注商業(yè)計(jì)算機(jī)和視頻游戲。該會議長期以來一直以電腦游戲中的人工智能研究為特色,并發(fā)展到游戲以外的娛樂領(lǐng)域,會議上舉行星際爭霸人工智能自主游戲程序競賽。會議從2005年開始,已經(jīng)舉辦了14屆。
5.3.2 CIG
IEEE計(jì)算智能與游戲大會(IEEE Conference on Computational Intelligence and Games,CIG)[43]是將計(jì)算和人工智能技術(shù)應(yīng)用于游戲的年度盛會。會議的領(lǐng)域包括適用于各種游戲的各種計(jì)算智能和人工智能,包括棋盤游戲、視頻游戲和數(shù)學(xué)游戲。于2005年開始作為研討會,自2009年開始作為會議,每年召開一次。該會議上進(jìn)行星際爭霸人工智能自主游戲程序比賽。
5.3.3 SSCAIT
學(xué)生星際爭霸AI錦標(biāo)賽(Student Starcraft AI Tournament & Ladder)[44]是一項(xiàng)教育活動,于2011年首次舉辦,是主要面向?qū)W生(非學(xué)生也允許提交)人工智能和計(jì)算機(jī)科學(xué)的競賽。通過使用BWAPI提交用C++或Java編程的自主游戲程序來進(jìn)行一對一星際爭霸游戲。
非完美信息下的多智能體博弈研究是當(dāng)前眾多人工智能研究團(tuán)隊(duì)努力攻克的難題,雖然有新的成果不斷產(chǎn)生,但直到目前,完整游戲情況下,人工智能游戲程序仍無法達(dá)到人類高水平玩家的水平。為了達(dá)成這一目標(biāo),除了文章前述的研究方法之外,一些研究者將注意力放在多智能體分布式?jīng)Q策上。分層和分任務(wù)決策對星際爭霸來說可能是一種發(fā)展方向,通過將對抗任務(wù)分不同的層次和拆分成不同的任務(wù)模塊,在小的任務(wù)范圍內(nèi)進(jìn)行學(xué)習(xí),最終將這些模塊整合成一個(gè)完整的人工智能游戲程序。另外,將博弈論作為對抗分析的指導(dǎo)方法,會給該領(lǐng)域帶來新的解決思路。除此之外,模仿學(xué)習(xí)、遷移學(xué)習(xí)以及增量式學(xué)習(xí)也可能在該領(lǐng)域展現(xiàn)出好的效果。
多智能體對抗博弈策略在一些實(shí)際領(lǐng)域具有應(yīng)用價(jià)值。其中簡單任務(wù)應(yīng)用如追捕任務(wù),即多機(jī)器人協(xié)同追捕“逃跑者”機(jī)器人。與之類似,有多機(jī)器人協(xié)同阻止入侵者的“疆土防御”任務(wù)。機(jī)器人足球是更高水平的復(fù)雜任務(wù),各足球機(jī)器人需要團(tuán)隊(duì)協(xié)作采取策略與對手機(jī)器人團(tuán)隊(duì)進(jìn)行對抗,防守好自己的球門并盡可能多地進(jìn)球得分。值得注意的是,當(dāng)前多智能體對抗博弈策略研究在軍事領(lǐng)域受到重點(diǎn)關(guān)注。以美國軍方為例,其連續(xù)幾年發(fā)布的無人系統(tǒng)路線圖均將多無人系統(tǒng)在戰(zhàn)場中的協(xié)作作戰(zhàn)列為重點(diǎn)發(fā)展方向,并進(jìn)行了多項(xiàng)以多機(jī)器人系統(tǒng)或集群作戰(zhàn)為內(nèi)容的軍事研究項(xiàng)目。另外,俄羅斯軍方已將多無人系統(tǒng)應(yīng)用于實(shí)際戰(zhàn)場。
目前,多智能體博弈游戲仍是一個(gè)開放的難題,人工智能游戲程序還無法超越人類頂級玩家的水平。隨著人工智能技術(shù)的快速發(fā)展以及越來越多科研團(tuán)隊(duì)投入其中,該領(lǐng)域?qū)懈喔鸷车某晒懤m(xù)產(chǎn)生。