編者注：《吃豆人》是一款由南夢宮公司制作的街機(jī)游戲，游戲最初于1980年5月22日在日本發(fā)行。本游戲由南夢宮公司的巖谷徹設(shè)計(jì)，游戲于1980年10月由Midway Games公司在美國發(fā)行。

星際爭霸是由暴雪娛樂有限公司制作發(fā)行的一系列戰(zhàn)爭題材科幻游戲。游戲系列主要由Chris Metzen與James Phinney設(shè)計(jì)開發(fā)。游戲的劇情發(fā)生在26世紀(jì)初期的克普魯星區(qū)——位于遙遠(yuǎn)的銀河系中心，游戲最初于1998年發(fā)行。

修改蒙特卡洛樹搜索讓人工智能像人類一樣玩視頻游戲

聯(lián)合編譯：Blake、陳圳、章敏

摘要

在本文中，我們實(shí)現(xiàn)了人工智能玩家可以像人類一樣玩一些視頻游戲。為此，我們使用了幾種運(yùn)用蒙特卡洛樹搜索的UCT算法，通過選擇偏差行為重復(fù)當(dāng)下行動、暫停、限制行動快速轉(zhuǎn)換。另外，我們使用人類玩家的行動軌跡來對重復(fù)行為傾向進(jìn)行建模，這個(gè)模型被用來偏差調(diào)整UCT算法。實(shí)驗(yàn)證明我們的修正的MCTS（蒙特卡洛樹搜索）機(jī)器人BoT，在重復(fù)動作上表現(xiàn)和人類玩家相似。另外，我們通過調(diào)查得出人工智能玩家在一些游戲中表現(xiàn)得和人類一樣。

1. 引言與背景

當(dāng)開發(fā)一個(gè)算法用來玩游戲時(shí)，目標(biāo)通常是讓它玩得盡量好。對于許多游戲來說，成功有一個(gè)合適且明確的數(shù)字標(biāo)準(zhǔn)?？赡苁欠?jǐn)?shù)、游戲進(jìn)度（拿到多少東西、多少等級、多遠(yuǎn)距離），或者是玩家能打敗的最高等級對象。這個(gè)數(shù)字標(biāo)準(zhǔn)也是衡量計(jì)算機(jī)算法玩游戲是否成功的標(biāo)準(zhǔn)，AI的目的就是使這個(gè)數(shù)字最大化。這些游戲標(biāo)準(zhǔn)被用來進(jìn)行AI智能競賽，包括像象棋、圍棋、模擬賽車和星際爭霸等游戲。

然而在其他領(lǐng)域有更加適合的度量成功的標(biāo)準(zhǔn)，特別要提到的一種是衡量人工智能能夠玩得多類似人類玩家（特定某個(gè)玩家或者大多數(shù)玩家）的標(biāo)準(zhǔn)。對于不同的場景這個(gè)很重要，其中一個(gè)例子程序生成內(nèi)容時(shí)，對于一個(gè)游戲來說使用基于搜索的程序內(nèi)容生成方法很重要。這些方法特別倚靠對于內(nèi)容測試的模擬，人工智能玩家為了測試它的質(zhì)量去玩新的內(nèi)容。在這種情況下，這些內(nèi)容應(yīng)該是由類似人類一樣的人工智能玩家去進(jìn)行測試，不像人類的人工智能玩家測試的話可能會在很多地方出現(xiàn)很大差異，即便它們都有相同的技能等級。無論是對于專業(yè)游戲公司還是業(yè)余開發(fā)者（最近大獲成功的馬里奧賽車等），人工智能自動測試都非常重要。類似人類玩家對于創(chuàng)作教程和其它形式的演示也十分重要。最后，對于普通玩家來說在游戲有像人類玩家一樣的非人類角也很重要。大部分人認(rèn)為多人游戲的流行有可能是因?yàn)樵谟螒蛑腥狈尚诺碾娔X玩家。相似的，如果和太聰明的電腦玩家對抗也沒意思，所以一般游戲都會削減部分電腦玩家的實(shí)力以期更好的和人類玩家匹配。值得一提的是，雖然在娛樂游戲中這部分還存在爭論，但是在比較嚴(yán)肅的游戲、虛擬現(xiàn)實(shí)、任務(wù)型游戲、實(shí)時(shí)交互模擬游戲中電腦玩家實(shí)力是對等的。

在許多情況下，電腦玩家打游戲的時(shí)候和人類并不一樣。這是經(jīng)過許多次觀察不同游戲得出的非正式的結(jié)論。據(jù)稱象棋程序即使在擁有和人類同等水準(zhǔn)的情況下，它的下法和人類玩家也不一樣。當(dāng)?shù)搅艘曨l游戲時(shí)，在超級瑪麗兄弟和虛幻競技場等游戲中也出現(xiàn)了同樣的情況。許多研究人員嘗試為這些游戲特別定制一些AI玩家，最近的兩個(gè)游戲2K BotPrize和馬里奧AI冠軍賽就特別嘗試讓電腦玩家像人類一樣行動來進(jìn)行競賽。在這些競賽中，上述電腦玩家直接與人類玩家進(jìn)行競爭，然后讓評委來判定到底誰才是電腦玩家。結(jié)果表明，想要?jiǎng)?chuàng)造一個(gè)類人類的電腦玩家比創(chuàng)造一個(gè)能贏比賽或者拿高分的電腦玩家要難。

另外一個(gè)就是這些競賽以及相關(guān)研究提出了一系列初步的計(jì)算機(jī)游戲算法異于人類玩家不的表現(xiàn)。因?yàn)殡娔X玩家不會受到人類反應(yīng)次數(shù)的限制，我們觀察到一個(gè)特點(diǎn)，通常人類玩家不可能變化的這么快速且頻繁。還有一個(gè)就是不暫停，大多數(shù)人類玩家都會偶爾暫停來估算下前面的可能性，但是電腦玩家不會。最后，大多數(shù)算法在高風(fēng)險(xiǎn)策略上容易表現(xiàn)出懦弱的傾向（有人會說大多數(shù)人類玩家容易表現(xiàn)出草率的傾向）。

1.1 通用視頻游戲和MCTS

雖然曾經(jīng)有過許多針對特定游戲的類人類玩家嘗試，考慮到游戲設(shè)計(jì)主要知識不同，很少有人嘗試設(shè)計(jì)通用的類人類電腦玩家。就我們所知，還沒有任何一個(gè)AI玩家能夠在任何游戲中表現(xiàn)的和人類玩家一樣。針對所有的游戲而不是特定的某一款的挑戰(zhàn)是全局游戲策略（GGP），組合游戲、棋盤游戲或者全局視頻游戲AI（GVG-AI）等都是基于AI競賽的。對于這些競賽來說，電腦玩家不僅要玩單一的一個(gè)游戲，它們還必須玩它們從未見過的游戲。在本文中，我們將主要聚焦在針對GVG-AI競賽上。

大多數(shù)在GVG-AI上表現(xiàn)好的都是基于蒙特卡洛樹搜索算法的（MCTS）。這是最近才提出的一個(gè)針對隨機(jī)計(jì)劃和玩游戲的算法。與其他樹形搜索算法主要有兩個(gè)不同：（1）在節(jié)點(diǎn)擴(kuò)展的時(shí)候，MCTS能夠平衡探索之間的關(guān)系，使得搜索更加有重點(diǎn)。（2）MCTS使用隨機(jī)步驟來取代評估運(yùn)算。在革新圍棋算法后，MCTS算法變得十分流行。使用MCTS的電腦玩家比其他所有電腦玩家都要表現(xiàn)好，能達(dá)到人類玩家中最好的水準(zhǔn)。在全局視頻游戲AI方面，相關(guān)MCTS的成功大部分要?dú)w于發(fā)展特定游戲修正的不可能性。MCTS因?yàn)樗耐ㄓ眯宰兊檬钟杏谩?/p>

標(biāo)準(zhǔn)的MCTS在玩實(shí)時(shí)視頻游戲（如馬里奧）上比棋盤游戲（如圍棋）表現(xiàn)要糟一些，主要有這些因：必須實(shí)時(shí)做出決定（大約每40毫秒），電腦玩家可以隨機(jī)做出決定，但是由于缺乏及時(shí)反饋，通常不能評估決定之后的所隱含的信息。另外，游戲樹需要針對每個(gè)時(shí)間步做出修正調(diào)整。雖然標(biāo)準(zhǔn)MCTS在實(shí)時(shí)視頻游戲上存在這些問題，但是它在2014GVG-AI競賽上仍然取得了不錯(cuò)的成績。

1.2 主旨

本文所提出的難題是創(chuàng)造出針對GVG框架的表現(xiàn)良好的類人類玩家。這類玩家需要在這些游戲上能夠表現(xiàn)得和人類一樣好。

本文的架構(gòu)如下，首先我們介紹GVG-AI和我們用來獲取數(shù)據(jù)的游戲，然后介紹用來衡量人類玩家行為和電腦玩家行為的量化標(biāo)準(zhǔn)。接著，為了提高電腦玩家的人類相似度我們對MCTS核心算法進(jìn)行了一系列的修改，以及我們的模擬結(jié)果。

再后我們進(jìn)行了一系列調(diào)查，讓受訪者來在大量的游戲錄像中區(qū)分人類玩家和電腦玩家，結(jié)合受訪者判斷的結(jié)果我們對量化結(jié)果進(jìn)行了討論。通過討論，我們得出這項(xiàng)工作能夠更進(jìn)一步拓展，創(chuàng)造出類人類的通用游戲AI是可能的。

2. 試驗(yàn)平臺和數(shù)據(jù)收集

我們使用GVG-AI平臺來進(jìn)行試驗(yàn)，因?yàn)樗罅康膿碛邢嗤婕褹PI的視頻內(nèi)容，且它很容易被用來進(jìn)行數(shù)據(jù)收集。這些游戲是用VGDL來進(jìn)行編碼的，能夠代表許多2D游戲。目前，這些游戲包括：Seaquest、Frogger和Space Invaders。

為了和標(biāo)準(zhǔn)MCTS玩家進(jìn)行對比，我們首先收集了人類玩家行為來進(jìn)行分析。為了實(shí)現(xiàn)這個(gè)目的，我們設(shè)計(jì)了一個(gè)小程序用來讓玩家對指定游戲進(jìn)行存檔到服務(wù)器以便追蹤。每一個(gè)追蹤軌跡都包含了這個(gè)玩家的暫停、存檔等一系列行為。我們一共收集了11個(gè)不同玩家的209條游戲記錄，這11個(gè)玩家全是我們實(shí)驗(yàn)室的。我們也記錄了包括GVG-AI在內(nèi)50條標(biāo)準(zhǔn)MCTS玩家的游戲記錄。所有的玩家都完了三個(gè)不同游戲的第一關(guān)：

l  太空侵略者(Aliens)：VGDL編碼的Space Invaders。外星怪物能夠左右移動和發(fā)射子彈，這個(gè)游戲的目的是殺光所有的外星怪物。

l  吃豆人(PacMan)：VGDL編碼的Pac-Man（吃豆人），怪物在迷宮中朝四個(gè)方向運(yùn)動。目標(biāo)是吃掉所有的點(diǎn)，同時(shí)避免被追趕的幽靈抓住。

l  塞爾達(dá)傳說(Zelda) ：VGDL在早期的塞爾達(dá)傳說中實(shí)現(xiàn)了地牢系統(tǒng)。游戲角色可以向四個(gè)方向運(yùn)動，并且用劍向它的正面方向進(jìn)攻。其目標(biāo)是獲得鑰匙并且在未死亡的情況下到達(dá)出口。怪獸會隨機(jī)移動，如果與玩家相遇，它便會殺死玩家。玩家既不能躲避怪獸，也不能在其它的點(diǎn)用劍殺死它。

3.玩家行動的定量測量

我們分析了收集的數(shù)據(jù)，并且對比了人類和標(biāo)準(zhǔn)MCTS游戲路徑的不同之處。對比結(jié)果顯示，他們在幾個(gè)方面有著很大的不同。我們注意到在一排的兩個(gè)幀中，標(biāo)準(zhǔn)的MCTS幾乎很少重復(fù)兩個(gè)同樣的行動（例如，左，右，上，下，攻擊）。而人類玩家在一排的多個(gè)幀中趨向于重復(fù)幾次相同的行動。同樣，MCTS很少重復(fù)無效的行動，而人類玩家在一排多個(gè)幀中，會重復(fù)很多次無效的行動。所以，標(biāo)準(zhǔn)的MCTS相比于人類玩家，更趨向于調(diào)整自己的行動。后續(xù)部分詳細(xì)解釋了這方面的原因。

3.1行動長度

行動長度指每個(gè)行動重復(fù)的次數(shù)，無效的行動除外。游戲時(shí)，由于非瞬間反應(yīng)時(shí)間，人類玩家趨向于重復(fù)按相同的鍵。另一方面，標(biāo)準(zhǔn)的MCTS可以更迅速地作出反應(yīng)，因此它傾向于使很多長度為1的單幀動作。

為了計(jì)算行動長度，我們測試了每一個(gè)游戲路徑中，玩家的行動所發(fā)的時(shí)間。計(jì)算一個(gè)行動所含的總幀數(shù)（當(dāng)一個(gè)行動用于x幀時(shí)，x就是記錄者）并把它加入直方圖中。直方圖總數(shù)分類以后，最終行動長度可能的直方圖為Pa，如圖1所示。

圖1：人類玩家的行動長度直方圖

3.2無效行動長度

無效行動長度指一個(gè)完全無效行動重復(fù)的次數(shù)。游戲時(shí)，人類玩家趨于偶然性的停留（例如，不動）去思考，或者改變方向。然而，人工智能代理的反應(yīng)通常都很快，所以不需要暫停和思考。

圖2：人類玩家的無效行動長度直方圖Pn。

為了計(jì)算無效行動長度，我們再一次測試了每一個(gè)游戲路徑中，玩家的行動所發(fā)的時(shí)間，但是，這次我僅僅計(jì)算了重復(fù)無效行動所需的時(shí)間。最終的無效行動直方圖為Pn，如圖2所示。

3.3行動改變的頻率。

行動改變頻率的度量標(biāo)準(zhǔn)是，測量玩家從一個(gè)行動到一個(gè)新行動所發(fā)的時(shí)間（例如連續(xù)幀中從上變成左），然后通過游戲路徑中幀的總數(shù)進(jìn)行劃分。游戲時(shí)，人工智能代理可以自由的在每個(gè)幀中選擇最好的行動，經(jīng)常頻繁的改變行動會增加我們正努力避免的抖動效果。高效意味著高抖動，而且這通常只發(fā)生在人工智能代理中。在模型中，我們并沒有使用它來選擇行動，但在第6節(jié)中我們使用了該度量標(biāo)準(zhǔn)，對比人類玩家和AI代理。

4.提出的MCTS修改方案

蒙特卡洛樹搜索（MCTS）是一個(gè)隨機(jī)樹搜索算法，它被廣泛應(yīng)用于一般游戲以及特定玩法的游戲如Go:在適用的情況下，它逐漸接近和極大極小值算法一樣的結(jié)果。并非以深度第一或者寬度第一的方式探索樹，MCTS隨機(jī)探索搜索樹中以前沒有訪問過的新區(qū)域，同時(shí)還探索了已經(jīng)發(fā)現(xiàn)有前途但被沒有充分探討的領(lǐng)域，為了理解這種修改，我們首先敘述標(biāo)準(zhǔn)MCTS算法主要的四大步驟：

1.選擇：算法選擇樹中的一個(gè)點(diǎn)進(jìn)行擴(kuò)大。在該步驟中MCTS樹通過使用上置信算法（UCB）平衡探索與開發(fā)。

其中Xj是整個(gè)運(yùn)行中所有通過這個(gè)節(jié)點(diǎn)并負(fù)責(zé)開發(fā)的平均點(diǎn)價(jià)值（高平均值將被更多的利用），C是激勵(lì)探索常量，N是點(diǎn)j所有分支的訪問數(shù)量，nj是該點(diǎn)的訪問數(shù)量。

2.擴(kuò)大：MCTS隨機(jī)采用點(diǎn)j中一個(gè)未被訪問的分支進(jìn)行擴(kuò)大

3.模擬：MCTS使用隨機(jī)移動的方式進(jìn)行游戲，直到它達(dá)到了終止?fàn)顟B(tài)（贏/損）或決定

使用一個(gè)啟發(fā)式近似模擬。

4.反向傳播：MCTS使用模擬步驟中得到的結(jié)果——包括——平均分?jǐn)?shù)Xj，總訪問數(shù)N，數(shù)中每個(gè)點(diǎn)的分支訪問nj，更新所有原先的分支點(diǎn)。

GVG-AI想出了一個(gè)標(biāo)準(zhǔn)MCTS實(shí)現(xiàn)方法作為其中一個(gè)AI代理，這使它變成了支持視頻游戲，而不是支持MCTS通常被用于的典型的組合游戲。并非一直游戲直到達(dá)至最終狀態(tài)，它僅僅是模擬固定數(shù)量的行動，然后使用一個(gè)啟發(fā)式函數(shù)評估達(dá)到的狀態(tài)。該函數(shù)對于獲得最終狀態(tài)做出了積極的貢獻(xiàn)，對于失去最終狀態(tài)做出了消極的貢獻(xiàn)，或者最終狀態(tài)沒有達(dá)到而代理到達(dá)了的總分。

接下來，我們敘述了在GVG-AI MCTS算法方面的改變——為了讓以它更像人類的方式行動。我們將這些修改吸納進(jìn)了一個(gè)我們稱之為BoT的代理中。

4.1人類建模

我們首先在標(biāo)準(zhǔn)UCB等式中加入了一個(gè)術(shù)語Hj，以便更多的模擬類似人類的行為，和一個(gè)調(diào)諧常數(shù)α以便均衡探索，開發(fā)，和類人類建模。

Hj自身是一個(gè)函數(shù)，它取決于游戲狀態(tài)和先前被選擇的行動。該函數(shù)有助于MCTS模擬類似人類行為的選擇過程。例如，如果原先的移動的運(yùn)動長度為1并且當(dāng)前狀態(tài)是同樣的行為，這意味著價(jià)值應(yīng)該更高以便激勵(lì)采取同樣的行動（如3.1節(jié)中解釋得一樣）。行動的時(shí)間更長，Hj就會隨之減少。

Hj的參數(shù)是從第3節(jié)人類玩家游戲路徑的直方圖記錄中計(jì)算出來的；我們將MCTS算法轉(zhuǎn)變成更像人類行動長度和無效行動長度的分布，我們首先基于樹中原先的行動，選擇合適的直方圖：普通的行動用P=Pa表示，無效的行動用P=Pn表示。然后計(jì)算l，當(dāng)前行動進(jìn)行了多久，以及計(jì)算累積概率T（l）等于l逐步增加到無窮時(shí)P（l）的和。停留l幀后，改變動作可能性為T（l），繼續(xù)保持動作的可能性為1-T（l）。因此，Hj是從可能的數(shù)據(jù)驅(qū)動模型中計(jì)算出來的，并且取決于MCTS游戲數(shù)中最近的原型。

在該階段，我們僅僅使用了修改作為描述。AI代理表現(xiàn)出的結(jié)果符合簡單人類的分布，但沒有表現(xiàn)出符合完整的人類分布。無效的移動類似于走入進(jìn)墻中，AI代理變得不可信任的部分原因，是缺乏長期的規(guī)劃和怯懦。因此，我們增加了如下的技術(shù)提高代理的可信度。

4.2小分支的整理

小分枝整理消除了所有MCTS偶然選擇的無效動作，例如走入墻中，立刻扭轉(zhuǎn)方向，和攻擊堅(jiān)不可摧的對象。無效的動作是指當(dāng)執(zhí)行一個(gè)移動動作后，玩家的方向和位置沒有改變。有著無效動作的分支將不會被進(jìn)一步探索。而且行動整理的規(guī)則事先被指定了，因?yàn)槲覀兿Ｍ跊]有學(xué)習(xí)或訓(xùn)練階段的情況下，我們的方法也適用于游戲；它們是令人信服地，這也同樣是從數(shù)據(jù)中學(xué)習(xí)到的;

4.3地圖探索獎(jiǎng)勵(lì)

地圖探索獎(jiǎng)勵(lì)是指，通過獎(jiǎng)勵(lì)訪問地圖中未被經(jīng)常訪問的區(qū)域，鼓舞MCTS去探索游戲地圖中新的位置。這被介紹來幫代理提高長期訓(xùn)練。我們模擬等式2增加了一個(gè)獎(jiǎng)勵(lì)探索期。

其中E是一個(gè)獎(jiǎng)勵(lì)的探索期貢獻(xiàn)的常數(shù)，visited（xj，yj）代理當(dāng)前地圖區(qū)域被玩家訪問的次數(shù)。

4.4極大極小值

極大極小值是Jacobsen等人提出的，其中的幾個(gè)技術(shù)被用于提高M(jìn)CTS運(yùn)行無限Mario Bros的性能，極大極小值通常被建議為Mario中克服懦弱行為的方法——角色會不自覺的避開間隙和敵人。很多GVG游戲中也出現(xiàn)了同樣的問題，代理經(jīng)常逃離敵人而不是殺死它。

一個(gè)最大的價(jià)值被用于平均值Xj和最大分支價(jià)值之間，而并非使用UCB等式中的平均價(jià)值Xj。等式4顯示了式1新的探索部分，代替Xj和Xj*。

其中Q是兩個(gè)時(shí)期中最大的參數(shù)，max是分支中實(shí)現(xiàn)的最大價(jià)值，Xj是原先UCB中一樣的平均價(jià)值。

為了讓它更像人類，輸出特性視覺檢測選擇出價(jià)值Q=0.25時(shí)效果最好。高價(jià)值的Q導(dǎo)致代理變得非常勇敢并且死于敵人的攻擊，而低價(jià)值的Q導(dǎo)致代理變得非常的懦弱。

5.模擬結(jié)果

該部分用四種類型的玩家對比了第3節(jié)中的定量測量：（a）標(biāo)準(zhǔn)MCTS，（b）AdrienCtx, 2014GVG-AI比賽的冠軍，（c）我們的BoT算法，（d）真實(shí)的人類玩家。我們在三個(gè)相同的游戲中將他們進(jìn)行了對比：異形（Aliens），食豆小子（PacMan），塞爾達(dá)傳說（Zelda）。

圖3通過行動長度，對不同的代理和人類玩家進(jìn)行了對比。可以看出，Adrienctx和標(biāo)準(zhǔn)MCTS支持長度為1的短期行動，而人類玩家支持重復(fù)同樣的行動。

正如我們所看到的那樣，AdrienCtx和標(biāo)準(zhǔn)MCTS都支持長度在1之內(nèi)的移動，但是人類更支持重復(fù)同樣的動作。BoT算法（藍(lán)色）更傾向于選擇相同的動作，這與人類玩家的選擇更接近。

圖3：人類玩家，標(biāo)準(zhǔn)MCTS，Adrien和BoT代理的動作幅度分布。

圖4比較了人類玩家和代理的無效動作長度。標(biāo)準(zhǔn)MCTS（綠色）大部分無效動作較短——且長度都在1左右。另一方面，AdrienCtx（紫色）無效動作最長，其長度在11。為分析且不再讓無效動作發(fā)生，這一代理代表的是游戲開始前11視頻幀，并且會解釋這一特殊時(shí)間段的分布。BoT（藍(lán)色）更傾向于選擇無效動作，這與人類玩家的分布相似。

圖4：人類玩家，標(biāo)準(zhǔn)MCTS，AdrienCtx和我們的BoT代理的無效動作分布。

圖5通過動作到動作之間的變化頻率直方圖比較人類玩家和其他代理之間的差別程度。人類玩家（淡藍(lán)色）很少轉(zhuǎn)變動作。但是，標(biāo)準(zhǔn)MCTS和AdrienCtx會經(jīng)常進(jìn)行動作轉(zhuǎn)換，如直方圖。我們的BoT代理分布更接近人類，這會減少變化的數(shù)量。

我們的目標(biāo)不僅僅是模仿人類分布，更是要將類似人類分布和MCTS的一般性和積極表現(xiàn)連接起來。一個(gè)只會簡單模仿人類分布動作的算法能完美適應(yīng)游戲，但卻會是一個(gè)冷酷的壞玩家。為確保改進(jìn)的MCTS的普遍性，我們必須將分?jǐn)?shù)和勝負(fù)率作為表現(xiàn)的評測標(biāo)準(zhǔn)。

表1：人類，標(biāo)準(zhǔn)MCTS，AdrienCtx和BoT代理的勝出率和平均得分。

表1比較了人類和三種算法的表現(xiàn)。前面的數(shù)據(jù)是勝出率，后面的是在所有游戲和代理配對中的平均得分。由上述標(biāo)準(zhǔn)可見，我們的BoT算法和標(biāo)準(zhǔn)MCTS的得分差不多。從得分可見，BoT算法在PacMan和Zelda的表現(xiàn)都很好，但在Alien中表現(xiàn)較差。這可能是因?yàn)?，由于“地圖探索獎(jiǎng)金”空間探索總是比射擊更重要。

6.用戶研究

為證實(shí)我們的算法比標(biāo)準(zhǔn)MCTS表現(xiàn)的更接近人類，我們實(shí)施了一個(gè)類似圖靈測試的用戶研究?；谌齻€(gè)游戲?qū)ξ覀兊乃惴ㄟM(jìn)行評估：Zelda，Pacman，和Boulderdash。Boulderdash是一個(gè)由First Star Software開發(fā)的一款經(jīng)典游戲。玩家必須挖洞，收集珠寶并成功逃脫；但與此同時(shí)，必須躲避滾落的巖石和移動的怪物。之所以選擇這款游戲，是因?yàn)檫@款游戲的玩法與Aliens相比差別更大。

在每一款游戲中，我們都會對4名玩家進(jìn)行比較：（a）標(biāo)準(zhǔn)MCTS；（b）AdrienCtx，在2014年的GVG-AI 比賽中獲得優(yōu)勝；（c）我們的BoT算法；（d）人類玩家。對于每一種情況，我們回通過GVG-AI系統(tǒng)生成3個(gè)視頻，最終的視頻數(shù)是：3游戲*4算法*3視頻=36視頻。

用戶研究是在網(wǎng)頁游覽器內(nèi)進(jìn)行的。每一位參與者會看到2段視頻，這2段都是從同一游戲中選取的，且分別標(biāo)準(zhǔn)為A和B。緊接著參與者會被問到“哪一個(gè)視頻是人類玩家在玩？”，且會給予4個(gè)選擇A，B，兩個(gè)都是或是都不是。它們會賦予一個(gè)自由領(lǐng)域標(biāo)注為“你是如何決定的？”。所以我們能更好地理解它們是如何做決定的。參與者會被要求至少評估20場游戲，但如果參與者只評估一場游戲，結(jié)果不會被采納。在我們的研究中有34為參與者，每一位參加者會評價(jià)10場游戲左右，平均值為9.18,，總的評價(jià)次數(shù)為312。因?yàn)槊恳粓鲈u價(jià)包含2場游戲，所以在我們的研究n=624樣本。

表3顯示了用戶評價(jià)的結(jié)果。每一部分都會顯示是由人類操作的視頻游戲的次數(shù)。第一行，人類準(zhǔn)確的判斷出哪些是由人類操作的視頻游戲，且在Zelda游戲中表現(xiàn)最好，準(zhǔn)確率在88.7%左右；在Pacman中表現(xiàn)最差，準(zhǔn)確率只有70.2%。第二行，我們可以看到標(biāo)準(zhǔn)MCTS表現(xiàn)較差，最好的準(zhǔn)確率是在Pacman中，只有33.3%；最差的是在Boulderdash中，準(zhǔn)確率只有8.3%。在剩下的兩種算法中，BoT在Pacman中表現(xiàn)最好，準(zhǔn)確率到達(dá)人類判斷標(biāo)準(zhǔn)，而AdrienCtx在Zelda和Boulderdash中表現(xiàn)最好。

為檢驗(yàn)重要性，我們對每一款游戲和代理都進(jìn)行雙向測試，并假設(shè)具有人類特征的百分比與標(biāo)準(zhǔn)MCTS的百分比相匹配。除Pacman和AdrienCtx之外，我們的p值＜.01，不管其他代理和游戲的假設(shè)。這就顯示，對于n=624最重要的結(jié)果是算法對于參與者把人類行為加入AI有重要影響。

我們也分析了觀察者基于視頻的可選自由文本反應(yīng)，為探究究竟哪些常見問題讓人們相信，他所看到的游戲視頻不是由人類所操作。在關(guān)鍵詞或是表達(dá)語義相同時(shí)，答案會進(jìn)行編碼。表2顯示的是能判斷玩家是AI的高頻關(guān)鍵詞。

表2：從用戶研究中得出的判斷玩家不是人類的常見有效理由。

通過聯(lián)合我們自己的觀察以及調(diào)查者的反饋，所有的發(fā)現(xiàn)結(jié)果解釋如下。標(biāo)準(zhǔn)MCTS顯示的大部分問題并未在文章開始部分提及：抖動，無效移動，比如撞墻，或是長期沒有目標(biāo)。AdrienCtx避免了大部分的問題，但卻敗在非人的反應(yīng)速度，包括面對較多敵人時(shí)的快速和準(zhǔn)確打擊。實(shí)際上，一些觀察員認(rèn)為AdrienCtx是在作弊。BoT的反應(yīng)更接近于人類，因?yàn)樗鼉A向于重復(fù)移動和等待。因?yàn)椤皯T性”它同樣也會顯示下列行為，在Pacamn中尤為明顯。

表3：評價(jià)的百分比和具體數(shù)字。

7.結(jié)論

MCTS是目前最成功的算法——或者說算法結(jié)構(gòu)——就GGP和GVG-AI比賽和相關(guān)的軟件框架表現(xiàn)而言。但是在標(biāo)準(zhǔn)形式中，這個(gè)算法并不能表現(xiàn)的近似人類行為。在本文中，我們在GVG-AI的框架之內(nèi)進(jìn)行人類和MCTS代理在不同的游戲中進(jìn)行比較。我們同樣對MCTS的關(guān)鍵內(nèi)核進(jìn)行改進(jìn)，讓它的行為更接近于人類。改進(jìn)的關(guān)鍵在于UCT公式中添加一個(gè)新的條款，會讓行為選擇更加偏向于近似人類行為。此改進(jìn)的關(guān)鍵有效之處就在于通過計(jì)算機(jī)測試和靈圖使用者研究確定了“BoT”。我們相信BoT代理對于自動檢測，GVG-AI框架內(nèi)的游戲說明，新游戲的生成和在不同游戲中開發(fā)近似人類玩家的游戲策略十分有效。

via IJCAI 2016

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。