1
| 本文作者： 李尊 | 2016-07-07 12:44 |
編者注：《吃豆人》是一款由南夢宮公司制作的街機游戲，游戲最初于1980年5月22日在日本發行。本游戲由南夢宮公司的巖谷徹設計，游戲于1980年10月由Midway Games公司在美國發行。
星際爭霸是由暴雪娛樂有限公司制作發行的一系列戰爭題材科幻游戲。游戲系列主要由Chris Metzen與James Phinney設計開發。游戲的劇情發生在26世紀初期的克普魯星區——位于遙遠的銀河系中心，游戲最初于1998年發行。
聯合編譯：Blake、陳圳、章敏
摘要
在本文中，我們實現了人工智能玩家可以像人類一樣玩一些視頻游戲。為此，我們使用了幾種運用蒙特卡洛樹搜索的UCT算法，通過選擇偏差行為重復當下行動、暫停、限制行動快速轉換。另外，我們使用人類玩家的行動軌跡來對重復行為傾向進行建模，這個模型被用來偏差調整UCT算法。實驗證明我們的修正的MCTS（蒙特卡洛樹搜索）機器人BoT，在重復動作上表現和人類玩家相似。另外，我們通過調查得出人工智能玩家在一些游戲中表現得和人類一樣。
1. 引言與背景
當開發一個算法用來玩游戲時，目標通常是讓它玩得盡量好。對于許多游戲來說，成功有一個合適且明確的數字標準。可能是分數、游戲進度（拿到多少東西、多少等級、多遠距離），或者是玩家能打敗的最高等級對象。這個數字標準也是衡量計算機算法玩游戲是否成功的標準，AI的目的就是使這個數字最大化。這些游戲標準被用來進行AI智能競賽，包括像象棋、圍棋、模擬賽車和星際爭霸等游戲。
然而在其他領域有更加適合的度量成功的標準，特別要提到的一種是衡量人工智能能夠玩得多類似人類玩家（特定某個玩家或者大多數玩家）的標準。對于不同的場景這個很重要，其中一個例子程序生成內容時，對于一個游戲來說使用基于搜索的程序內容生成方法很重要。這些方法特別倚靠對于內容測試的模擬，人工智能玩家為了測試它的質量去玩新的內容。在這種情況下，這些內容應該是由類似人類一樣的人工智能玩家去進行測試，不像人類的人工智能玩家測試的話可能會在很多地方出現很大差異，即便它們都有相同的技能等級。無論是對于專業游戲公司還是業余開發者（最近大獲成功的馬里奧賽車等），人工智能自動測試都非常重要。類似人類玩家對于創作教程和其它形式的演示也十分重要。最后，對于普通玩家來說在游戲有像人類玩家一樣的非人類角也很重要。大部分人認為多人游戲的流行有可能是因為在游戲中缺乏可信的電腦玩家。相似的，如果和太聰明的電腦玩家對抗也沒意思，所以一般游戲都會削減部分電腦玩家的實力以期更好的和人類玩家匹配。值得一提的是，雖然在娛樂游戲中這部分還存在爭論，但是在比較嚴肅的游戲、虛擬現實、任務型游戲、實時交互模擬游戲中電腦玩家實力是對等的。
在許多情況下，電腦玩家打游戲的時候和人類并不一樣。這是經過許多次觀察不同游戲得出的非正式的結論。據稱象棋程序即使在擁有和人類同等水準的情況下，它的下法和人類玩家也不一樣。當到了視頻游戲時，在超級瑪麗兄弟和虛幻競技場等游戲中也出現了同樣的情況。許多研究人員嘗試為這些游戲特別定制一些AI玩家，最近的兩個游戲2K BotPrize和馬里奧AI冠軍賽就特別嘗試讓電腦玩家像人類一樣行動來進行競賽。在這些競賽中，上述電腦玩家直接與人類玩家進行競爭，然后讓評委來判定到底誰才是電腦玩家。結果表明，想要創造一個類人類的電腦玩家比創造一個能贏比賽或者拿高分的電腦玩家要難。
另外一個就是這些競賽以及相關研究提出了一系列初步的計算機游戲算法異于人類玩家不的表現。因為電腦玩家不會受到人類反應次數的限制，我們觀察到一個特點，通常人類玩家不可能變化的這么快速且頻繁。還有一個就是不暫停，大多數人類玩家都會偶爾暫停來估算下前面的可能性，但是電腦玩家不會。最后，大多數算法在高風險策略上容易表現出懦弱的傾向（有人會說大多數人類玩家容易表現出草率的傾向）。
1.1 通用視頻游戲和MCTS
雖然曾經有過許多針對特定游戲的類人類玩家嘗試，考慮到游戲設計主要知識不同，很少有人嘗試設計通用的類人類電腦玩家。就我們所知，還沒有任何一個AI玩家能夠在任何游戲中表現的和人類玩家一樣。針對所有的游戲而不是特定的某一款的挑戰是全局游戲策略（GGP），組合游戲、棋盤游戲或者全局視頻游戲AI（GVG-AI）等都是基于AI競賽的。對于這些競賽來說，電腦玩家不僅要玩單一的一個游戲，它們還必須玩它們從未見過的游戲。在本文中，我們將主要聚焦在針對GVG-AI競賽上。
大多數在GVG-AI上表現好的都是基于蒙特卡洛樹搜索算法的（MCTS）。這是最近才提出的一個針對隨機計劃和玩游戲的算法。與其他樹形搜索算法主要有兩個不同：（1）在節點擴展的時候，MCTS能夠平衡探索之間的關系，使得搜索更加有重點。（2）MCTS使用隨機步驟來取代評估運算。在革新圍棋算法后，MCTS算法變得十分流行。使用MCTS的電腦玩家比其他所有電腦玩家都要表現好，能達到人類玩家中最好的水準。在全局視頻游戲AI方面，相關MCTS的成功大部分要歸于發展特定游戲修正的不可能性。MCTS因為它的通用性變得十分有用。
標準的MCTS在玩實時視頻游戲（如馬里奧）上比棋盤游戲（如圍棋）表現要糟一些，主要有這些因：必須實時做出決定（大約每40毫秒），電腦玩家可以隨機做出決定，但是由于缺乏及時反饋，通常不能評估決定之后的所隱含的信息。另外，游戲樹需要針對每個時間步做出修正調整。雖然標準MCTS在實時視頻游戲上存在這些問題，但是它在2014GVG-AI競賽上仍然取得了不錯的成績。
1.2 主旨
本文所提出的難題是創造出針對GVG框架的表現良好的類人類玩家。這類玩家需要在這些游戲上能夠表現得和人類一樣好。
本文的架構如下，首先我們介紹GVG-AI和我們用來獲取數據的游戲，然后介紹用來衡量人類玩家行為和電腦玩家行為的量化標準。接著，為了提高電腦玩家的人類相似度我們對MCTS核心算法進行了一系列的修改，以及我們的模擬結果。
再后我們進行了一系列調查，讓受訪者來在大量的游戲錄像中區分人類玩家和電腦玩家，結合受訪者判斷的結果我們對量化結果進行了討論。通過討論，我們得出這項工作能夠更進一步拓展，創造出類人類的通用游戲AI是可能的。
2. 試驗平臺和數據收集
我們使用GVG-AI平臺來進行試驗，因為它包含大量的擁有相同玩家API的視頻內容，且它很容易被用來進行數據收集。這些游戲是用VGDL來進行編碼的，能夠代表許多2D游戲。目前，這些游戲包括：Seaquest、Frogger和Space Invaders。
為了和標準MCTS玩家進行對比，我們首先收集了人類玩家行為來進行分析。為了實現這個目的，我們設計了一個小程序用來讓玩家對指定游戲進行存檔到服務器以便追蹤。每一個追蹤軌跡都包含了這個玩家的暫停、存檔等一系列行為。我們一共收集了11個不同玩家的209條游戲記錄，這11個玩家全是我們實驗室的。我們也記錄了包括GVG-AI在內50條標準MCTS玩家的游戲記錄。所有的玩家都完了三個不同游戲的第一關：
l 太空侵略者(Aliens)：VGDL編碼的Space Invaders。外星怪物能夠左右移動和發射子彈，這個游戲的目的是殺光所有的外星怪物。
l 吃豆人(PacMan)：VGDL編碼的Pac-Man（吃豆人），怪物在迷宮中朝四個方向運動。目標是吃掉所有的點，同時避免被追趕的幽靈抓住。
l 塞爾達傳說(Zelda) ：VGDL在早期的塞爾達傳說中實現了地牢系統。游戲角色可以向四個方向運動，并且用劍向它的正面方向進攻。其目標是獲得鑰匙并且在未死亡的情況下到達出口。怪獸會隨機移動，如果與玩家相遇，它便會殺死玩家。玩家既不能躲避怪獸，也不能在其它的點用劍殺死它。
3.玩家行動的定量測量
我們分析了收集的數據，并且對比了人類和標準MCTS游戲路徑的不同之處。對比結果顯示，他們在幾個方面有著很大的不同。我們注意到在一排的兩個幀中，標準的MCTS幾乎很少重復兩個同樣的行動（例如，左，右，上，下，攻擊）。而人類玩家在一排的多個幀中趨向于重復幾次相同的行動。同樣，MCTS很少重復無效的行動，而人類玩家在一排多個幀中，會重復很多次無效的行動。所以，標準的MCTS相比于人類玩家，更趨向于調整自己的行動。后續部分詳細解釋了這方面的原因。
3.1行動長度
行動長度指每個行動重復的次數，無效的行動除外。游戲時，由于非瞬間反應時間，人類玩家趨向于重復按相同的鍵。另一方面，標準的MCTS可以更迅速地作出反應，因此它傾向于使很多長度為1的單幀動作。
為了計算行動長度，我們測試了每一個游戲路徑中，玩家的行動所發的時間。計算一個行動所含的總幀數（當一個行動用于x幀時，x就是記錄者）并把它加入直方圖中。直方圖總數分類以后，最終行動長度可能的直方圖為Pa，如圖1所示。
圖1：人類玩家的行動長度直方圖
3.2無效行動長度
無效行動長度指一個完全無效行動重復的次數。游戲時，人類玩家趨于偶然性的停留（例如，不動）去思考，或者改變方向。然而，人工智能代理的反應通常都很快，所以不需要暫停和思考。
圖2：人類玩家的無效行動長度直方圖Pn。
為了計算無效行動長度，我們再一次測試了每一個游戲路徑中，玩家的行動所發的時間，但是，這次我僅僅計算了重復無效行動所需的時間。最終的無效行動直方圖為Pn，如圖2所示。
3.3行動改變的頻率。
行動改變頻率的度量標準是，測量玩家從一個行動到一個新行動所發的時間（例如連續幀中從上變成左），然后通過游戲路徑中幀的總數進行劃分。游戲時，人工智能代理可以自由的在每個幀中選擇最好的行動，經常頻繁的改變行動會增加我們正努力避免的抖動效果。高效意味著高抖動，而且這通常只發生在人工智能代理中。在模型中，我們并沒有使用它來選擇行動，但在第6節中我們使用了該度量標準，對比人類玩家和AI代理。
4.提出的MCTS修改方案
蒙特卡洛樹搜索（MCTS）是一個隨機樹搜索算法，它被廣泛應用于一般游戲以及特定玩法的游戲如Go:在適用的情況下，它逐漸接近和極大極小值算法一樣的結果。并非以深度第一或者寬度第一的方式探索樹，MCTS隨機探索搜索樹中以前沒有訪問過的新區域，同時還探索了已經發現有前途但被沒有充分探討的領域，為了理解這種修改，我們首先敘述標準MCTS算法主要的四大步驟：
1.選擇：算法選擇樹中的一個點進行擴大。在該步驟中MCTS樹通過使用上置信算法（UCB）平衡探索與開發。
其中Xj是整個運行中所有通過這個節點并負責開發的平均點價值（高平均值將被更多的利用），C是激勵探索常量，N是點j所有分支的訪問數量，nj是該點的訪問數量。
2.擴大：MCTS隨機采用點j中一個未被訪問的分支進行擴大
3.模擬：MCTS使用隨機移動的方式進行游戲，直到它達到了終止狀態（贏/損）或決定
使用一個啟發式近似模擬。
4.反向傳播：MCTS使用模擬步驟中得到的結果——包括——平均分數Xj，總訪問數N，數中每個點的分支訪問nj，更新所有原先的分支點。
GVG-AI想出了一個標準MCTS實現方法作為其中一個AI代理，這使它變成了支持視頻游戲，而不是支持MCTS通常被用于的典型的組合游戲。并非一直游戲直到達至最終狀態，它僅僅是模擬固定數量的行動，然后使用一個啟發式函數評估達到的狀態。該函數對于獲得最終狀態做出了積極的貢獻，對于失去最終狀態做出了消極的貢獻，或者最終狀態沒有達到而代理到達了的總分。
接下來，我們敘述了在GVG-AI MCTS算法方面的改變——為了讓以它更像人類的方式行動。我們將這些修改吸納進了一個我們稱之為BoT的代理中。
4.1人類建模
我們首先在標準UCB等式中加入了一個術語Hj，以便更多的模擬類似人類的行為，和一個調諧常數α以便均衡探索，開發，和類人類建模。
Hj自身是一個函數，它取決于游戲狀態和先前被選擇的行動。該函數有助于MCTS模擬類似人類行為的選擇過程。例如，如果原先的移動的運動長度為1并且當前狀態是同樣的行為，這意味著價值應該更高以便激勵采取同樣的行動（如3.1節中解釋得一樣）。行動的時間更長，Hj就會隨之減少。
Hj的參數是從第3節人類玩家游戲路徑的直方圖記錄中計算出來的；我們將MCTS算法轉變成更像人類行動長度和無效行動長度的分布，我們首先基于樹中原先的行動，選擇合適的直方圖：普通的行動用P=Pa表示，無效的行動用P=Pn表示。然后計算l，當前行動進行了多久，以及計算累積概率T（l）等于l逐步增加到無窮時P（l）的和。停留l幀后，改變動作可能性為T（l），繼續保持動作的可能性為1-T（l）。因此，Hj是從可能的數據驅動模型中計算出來的，并且取決于MCTS游戲數中最近的原型。
在該階段，我們僅僅使用了修改作為描述。AI代理表現出的結果符合簡單人類的分布，但沒有表現出符合完整的人類分布。無效的移動類似于走入進墻中，AI代理變得不可信任的部分原因，是缺乏長期的規劃和怯懦。因此，我們增加了如下的技術提高代理的可信度。
4.2小分支的整理
小分枝整理消除了所有MCTS偶然選擇的無效動作，例如走入墻中，立刻扭轉方向，和攻擊堅不可摧的對象。無效的動作是指當執行一個移動動作后，玩家的方向和位置沒有改變。有著無效動作的分支將不會被進一步探索。而且行動整理的規則事先被指定了，因為我們希望在沒有學習或訓練階段的情況下，我們的方法也適用于游戲；它們是令人信服地，這也同樣是從數據中學習到的;
4.3地圖探索獎勵
地圖探索獎勵是指，通過獎勵訪問地圖中未被經常訪問的區域，鼓舞MCTS去探索游戲地圖中新的位置。這被介紹來幫代理提高長期訓練。我們模擬等式2增加了一個獎勵探索期。
其中E是一個獎勵的探索期貢獻的常數，visited（xj，yj）代理當前地圖區域被玩家訪問的次數。
4.4極大極小值
極大極小值是Jacobsen等人提出的，其中的幾個技術被用于提高MCTS運行無限Mario Bros的性能，極大極小值通常被建議為Mario中克服懦弱行為的方法——角色會不自覺的避開間隙和敵人。很多GVG游戲中也出現了同樣的問題，代理經常逃離敵人而不是殺死它。
一個最大的價值被用于平均值Xj和最大分支價值之間，而并非使用UCB等式中的平均價值Xj。等式4顯示了式1新的探索部分，代替Xj和Xj*。
其中Q是兩個時期中最大的參數，max是分支中實現的最大價值，Xj是原先UCB中一樣的平均價值。
為了讓它更像人類，輸出特性視覺檢測選擇出價值Q=0.25時效果最好。高價值的Q導致代理變得非常勇敢并且死于敵人的攻擊，而低價值的Q導致代理變得非常的懦弱。
5.模擬結果
該部分用四種類型的玩家對比了第3節中的定量測量：（a）標準MCTS，（b）AdrienCtx, 2014GVG-AI比賽的冠軍，（c）我們的BoT算法，（d）真實的人類玩家。我們在三個相同的游戲中將他們進行了對比：異形（Aliens），食豆小子（PacMan），塞爾達傳說（Zelda）。
圖3通過行動長度，對不同的代理和人類玩家進行了對比。可以看出，Adrienctx和標準MCTS支持長度為1的短期行動，而人類玩家支持重復同樣的行動。
正如我們所看到的那樣，AdrienCtx和標準MCTS都支持長度在1之內的移動，但是人類更支持重復同樣的動作。BoT算法（藍色）更傾向于選擇相同的動作，這與人類玩家的選擇更接近。
圖3：人類玩家，標準MCTS，Adrien和BoT代理的動作幅度分布。
圖4比較了人類玩家和代理的無效動作長度。標準MCTS（綠色）大部分無效動作較短——且長度都在1左右。另一方面，AdrienCtx（紫色）無效動作最長，其長度在11。為分析且不再讓無效動作發生，這一代理代表的是游戲開始前11視頻幀，并且會解釋這一特殊時間段的分布。BoT（藍色）更傾向于選擇無效動作，這與人類玩家的分布相似。
圖4：人類玩家，標準MCTS，AdrienCtx和我們的BoT代理的無效動作分布。
圖5通過動作到動作之間的變化頻率直方圖比較人類玩家和其他代理之間的差別程度。人類玩家（淡藍色）很少轉變動作。但是，標準MCTS和AdrienCtx會經常進行動作轉換，如直方圖。我們的BoT代理分布更接近人類，這會減少變化的數量。
我們的目標不僅僅是模仿人類分布，更是要將類似人類分布和MCTS的一般性和積極表現連接起來。一個只會簡單模仿人類分布動作的算法能完美適應游戲，但卻會是一個冷酷的壞玩家。為確保改進的MCTS的普遍性，我們必須將分數和勝負率作為表現的評測標準。
表1：人類，標準MCTS，AdrienCtx和BoT代理的勝出率和平均得分。
表1比較了人類和三種算法的表現。前面的數據是勝出率，后面的是在所有游戲和代理配對中的平均得分。由上述標準可見，我們的BoT算法和標準MCTS的得分差不多。從得分可見，BoT算法在PacMan和Zelda的表現都很好，但在Alien中表現較差。這可能是因為，由于“地圖探索獎金”空間探索總是比射擊更重要。
6.用戶研究
為證實我們的算法比標準MCTS表現的更接近人類，我們實施了一個類似圖靈測試的用戶研究。基于三個游戲對我們的算法進行評估：Zelda，Pacman，和Boulderdash。Boulderdash是一個由First Star Software開發的一款經典游戲。玩家必須挖洞，收集珠寶并成功逃脫；但與此同時，必須躲避滾落的巖石和移動的怪物。之所以選擇這款游戲，是因為這款游戲的玩法與Aliens相比差別更大。
在每一款游戲中，我們都會對4名玩家進行比較：（a）標準MCTS；（b）AdrienCtx，在2014年的GVG-AI 比賽中獲得優勝；（c）我們的BoT算法；（d）人類玩家。對于每一種情況，我們回通過GVG-AI系統生成3個視頻，最終的視頻數是：3游戲*4算法*3視頻=36視頻。
用戶研究是在網頁游覽器內進行的。每一位參與者會看到2段視頻，這2段都是從同一游戲中選取的，且分別標準為A和B。緊接著參與者會被問到“哪一個視頻是人類玩家在玩？”，且會給予4個選擇A，B，兩個都是或是都不是。它們會賦予一個自由領域標注為“你是如何決定的？”。所以我們能更好地理解它們是如何做決定的。參與者會被要求至少評估20場游戲，但如果參與者只評估一場游戲，結果不會被采納。在我們的研究中有34為參與者，每一位參加者會評價10場游戲左右，平均值為9.18,，總的評價次數為312。因為每一場評價包含2場游戲，所以在我們的研究n=624樣本。
表3顯示了用戶評價的結果。每一部分都會顯示是由人類操作的視頻游戲的次數。第一行，人類準確的判斷出哪些是由人類操作的視頻游戲，且在Zelda游戲中表現最好，準確率在88.7%左右；在Pacman中表現最差，準確率只有70.2%。第二行，我們可以看到標準MCTS表現較差，最好的準確率是在Pacman中，只有33.3%；最差的是在Boulderdash中，準確率只有8.3%。在剩下的兩種算法中，BoT在Pacman中表現最好，準確率到達人類判斷標準，而AdrienCtx在Zelda和Boulderdash中表現最好。
為檢驗重要性，我們對每一款游戲和代理都進行雙向測試，并假設具有人類特征的百分比與標準MCTS的百分比相匹配。除Pacman和AdrienCtx之外，我們的p值＜.01，不管其他代理和游戲的假設。這就顯示，對于n=624最重要的結果是算法對于參與者把人類行為加入AI有重要影響。
我們也分析了觀察者基于視頻的可選自由文本反應，為探究究竟哪些常見問題讓人們相信，他所看到的游戲視頻不是由人類所操作。在關鍵詞或是表達語義相同時，答案會進行編碼。表2顯示的是能判斷玩家是AI的高頻關鍵詞。
表2：從用戶研究中得出的判斷玩家不是人類的常見有效理由。
通過聯合我們自己的觀察以及調查者的反饋，所有的發現結果解釋如下。標準MCTS顯示的大部分問題并未在文章開始部分提及：抖動，無效移動，比如撞墻，或是長期沒有目標。AdrienCtx避免了大部分的問題，但卻敗在非人的反應速度，包括面對較多敵人時的快速和準確打擊。實際上，一些觀察員認為AdrienCtx是在作弊。BoT的反應更接近于人類，因為它更傾向于重復移動和等待。因為“慣性”它同樣也會顯示下列行為，在Pacamn中尤為明顯。
表3：評價的百分比和具體數字。
7.結論
MCTS是目前最成功的算法——或者說算法結構——就GGP和GVG-AI比賽和相關的軟件框架表現而言。但是在標準形式中，這個算法并不能表現的近似人類行為。在本文中，我們在GVG-AI的框架之內進行人類和MCTS代理在不同的游戲中進行比較。我們同樣對MCTS的關鍵內核進行改進，讓它的行為更接近于人類。改進的關鍵在于UCT公式中添加一個新的條款，會讓行為選擇更加偏向于近似人類行為。此改進的關鍵有效之處就在于通過計算機測試和靈圖使用者研究確定了“BoT”。我們相信BoT代理對于自動檢測，GVG-AI框架內的游戲說明，新游戲的生成和在不同游戲中開發近似人類玩家的游戲策略十分有效。
via IJCAI 2016
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
