梁思立，姜桂飛＊，陳泰劼，鄧益超，戰(zhàn)瑀璠，張玉志

1.南開大學(xué)，軟件學(xué)院，天津 300350

2.香港大學(xué)，工程學(xué)院，香港特別行政區(qū) 999077

3.新加坡國立大學(xué)，計(jì)算機(jī)學(xué)院，新加坡 117417

4.南開大學(xué)，金融學(xué)院，天津 300381

引 言

人工智能在近二十年取得了一系列的顯著成果。譬如，1997年IBM 的超級(jí)計(jì)算機(jī)“深藍(lán)”（Deep Blue）戰(zhàn)勝國際象棋冠軍Kasparov；2011年IBM的超級(jí)電腦“沃森”（Watson）擊敗了綜藝節(jié)目“Jeopardy!”的常勝冠軍；2017年Google DeepMind開發(fā)的“阿爾法圍棋”（AlphaGo）程序戰(zhàn)勝國際圍棋冠軍柯潔。這些成果標(biāo)志著人工智能在許多特定的領(lǐng)域，如象棋、圍棋等，取得了巨大的成功。但是，正如計(jì)算機(jī)科學(xué)家Feng-hsiung Hsu 所指出的，這些成果對(duì)通用人工智能（Artificial General Intelligence）的意義是有限的，因?yàn)檫@些智能系統(tǒng)都是高度專一化、面向單一任務(wù)的，并且它們所展現(xiàn)出來的智能很大程度上依賴于程序員對(duì)算法的設(shè)計(jì)[1]。正如“深藍(lán)”和“沃森”不能下圍棋，“阿爾法圍棋”不能下象棋或參加綜藝節(jié)目“Jeopardy!”，甚至達(dá)不到最基本的水平，它們的智能并不具有通用性。

為了構(gòu)建具有通用性的智能系統(tǒng)，斯坦福大學(xué)的計(jì)算機(jī)科學(xué)家Michael Genesereth 等研究者在2005年提出了名為通用博弈策略（General Game Playing,GGP）的研究項(xiàng)目，旨在設(shè)計(jì)能夠成功地以人類水準(zhǔn)進(jìn)行任意已知或未知博弈的人工智能系統(tǒng)[2]。也就是說，它要求智能系統(tǒng)不僅能夠進(jìn)行簡(jiǎn)單的井字棋游戲（Tic-Tac-Toe），還能夠進(jìn)行圍棋、國際象棋等復(fù)雜游戲。這類智能系統(tǒng)被稱為通用博弈系統(tǒng)（General Game Player）。自2005年起，美國人工智能協(xié)會(huì)通過在國際人工智能頂級(jí)會(huì)議AAAI 或IJCAI上舉辦GGP 競(jìng)賽來推動(dòng)這一項(xiàng)目的研究。到目前為止，這一競(jìng)賽已成功舉辦了12 屆。經(jīng)過十多年的發(fā)展與研究，GGP 競(jìng)賽已成為檢測(cè)人工智能水平，特別是通用智能發(fā)展的重要陣地[3]。

目前通用博弈系統(tǒng)所使用的主流算法是蒙特卡洛樹搜索算法（Monte Carlo Tree Search,MCTS）及其變種[4]。MCTS 算法以其通用性廣泛地被用于GGP 競(jìng)賽，然而與針對(duì)特定博弈所設(shè)計(jì)的算法相比，其性能仍有很大的提升空間。一般來說，由博弈規(guī)則所推導(dǎo)出的關(guān)于這一博弈的專門信息，往往對(duì)設(shè)計(jì)該博弈的有效決策算法具有重要作用，而原始的MCTS 算法在工作過程并沒有結(jié)合博弈的專門信息進(jìn)行決策[5-6]。同時(shí)，在GGP 平臺(tái)運(yùn)行中，通用博弈系統(tǒng)的準(zhǔn)備時(shí)間、行動(dòng)時(shí)間都是十分有限的。由此，如何在實(shí)時(shí)的在線搜索過程中獲取并運(yùn)用博弈的專門信息來提升MCTS 算法的搜索效率成為這一領(lǐng)域的研究熱點(diǎn)[7]。

另一方面，隨著“阿爾法圍棋”的巨大成功，強(qiáng)化學(xué)習(xí)在博弈領(lǐng)域中的作用日益重要[8-9]。近期，一些研究工作提出了結(jié)合強(qiáng)化學(xué)習(xí)技術(shù)來提升MCTS 算法的性能。譬如，深度神經(jīng)網(wǎng)絡(luò)可以用于學(xué)習(xí)博弈的專門信息，并基于此對(duì)博弈狀態(tài)價(jià)值進(jìn)行近似估值，然后再結(jié)合MCTS 算法來提升搜索空間的效率[9]。特別地，Xiao 等研究者利用強(qiáng)化學(xué)習(xí)中的泛化思想，即相似狀態(tài)共享信息，提出了記憶增強(qiáng)的蒙特卡洛算法（Memory-Augmented Monte Carlo Tree Search）[10]。該算法在MCTS 算法的基礎(chǔ)上，維護(hù)一個(gè)記憶結(jié)構(gòu)，用記憶結(jié)構(gòu)中該狀態(tài)的相似狀態(tài)來估計(jì)該狀態(tài)的價(jià)值，用以提高狀態(tài)價(jià)值估計(jì)的準(zhǔn)確性。論文的研究結(jié)果表明記憶增強(qiáng)的蒙特卡洛算法在理論和實(shí)踐上都改善了MCTS 算法的性能[10]。本文嘗試將這一方法擴(kuò)展應(yīng)用于GGP 領(lǐng)域，以構(gòu)建高效的通用博弈系統(tǒng)。實(shí)驗(yàn)結(jié)果表明，與基于原始的蒙特卡洛方法所構(gòu)建的通用博弈系統(tǒng)相比，本文所構(gòu)建的通用博弈系統(tǒng)無論在決策水平還是效率上都有了顯著的提升。

本文的主要結(jié)構(gòu)組織如下：第1 部分主要討論了與本文密切相關(guān)的研究工作；第2 部分概述了通用博弈策略GGP 項(xiàng)目，包括GGP 平臺(tái)，通用游戲描述語言；第3 部分重點(diǎn)闡述了蒙特卡洛樹搜索算法的優(yōu)化方案，通用博弈系統(tǒng)的構(gòu)建和實(shí)現(xiàn)；第4部分基于GGP 平臺(tái)，通過對(duì)比實(shí)驗(yàn)全面評(píng)估了所構(gòu)建的通用博弈系統(tǒng)的性能水平；第5 部分對(duì)本文的主要工作進(jìn)行了總結(jié)并指出了進(jìn)一步的研究方向。

1 相關(guān)工作

關(guān)于通用博弈系統(tǒng)的研究可以追溯到Pitrat 和Pell 的工作，他們?cè)O(shè)計(jì)了原則上能夠進(jìn)行任意給定的象棋類棋盤游戲的智能系統(tǒng)[11-12]。然而，這些早期系統(tǒng)局限于特殊的二人棋盤游戲，只能夠解決相對(duì)狹窄的一類游戲。對(duì)通用博弈系統(tǒng)更廣泛的研究興趣是由國際人工智能頂級(jí)會(huì)議AAAI 或IJCAI 上舉行的年度GGP 競(jìng)賽所激發(fā)的。經(jīng)過十多年的發(fā)展，關(guān)于通用博弈系統(tǒng)的研究已成為人工智能領(lǐng)域一個(gè)重要的研究主題[13]。

博弈策略的生成算法是構(gòu)建通用博弈系統(tǒng)的關(guān)鍵技術(shù)。在GGP 發(fā)展的初期，以MiniMax 算法及其變種為主的基于評(píng)估的搜索算法一度占據(jù)主導(dǎo)地位，如GGP 競(jìng)賽冠軍Cluneplayer 和Fluxplayer 采用的就是基于評(píng)估的搜索算法[14-15]。自從2007年冠軍Cadiaplayer 首次采用基于模擬的搜索算法開始，基于模擬的搜索算法逐漸成為構(gòu)建通用博弈系統(tǒng)的主流算法[16]。其中，MCTS 算法正是基于模擬的搜索算法的典型代表。這一算法使用非平衡擴(kuò)展的方法，在擴(kuò)展階段快速地將大部分未來發(fā)展可能較差的分支排除，使得計(jì)算機(jī)能將更多的算力分配在對(duì)未來發(fā)展可能更加優(yōu)秀的分支的探索上。因此，MCTS 算法及其變種是目前通用博弈系統(tǒng)使用的主流算法[7]。

為了改善MCTS 算法的性能，構(gòu)建更高效的通用博弈系統(tǒng)，近期一些研究工作嘗試將強(qiáng)化學(xué)習(xí)技術(shù)運(yùn)用到GGP 領(lǐng)域并取得了初步的結(jié)果。譬如，研究者Benacloch-Ayuso 提出了框架RL-GGP 用以測(cè)試不同的強(qiáng)化算法在GGP 領(lǐng)域的運(yùn)用，但其并沒有給出關(guān)于這些算法的性能評(píng)估結(jié)果[17]。也有研究工作將時(shí)間差分學(xué)習(xí)（Temporal-Difference Learning）用于改善MCTS 算法[18]。特別地，有研究者將強(qiáng)化學(xué)習(xí)的Q-learning 與MCTS 算法相結(jié)合應(yīng)用到GGP 領(lǐng)域，但實(shí)驗(yàn)結(jié)果表明，結(jié)合后的算法不僅存在收斂速度慢的問題，且決策效果并沒有比MCTS算法更好[19]。而Goldwaser 和Thielscher 研究者將AlphaZero 所使用的通用深度強(qiáng)化學(xué)習(xí)算法擴(kuò)展應(yīng)用到GGP 領(lǐng)域，與MCTS 算法的變種—上限置信區(qū)間算法（Upper Confidence Bound Apply to Tree,UCT）進(jìn)行對(duì)比，實(shí)驗(yàn)表明，同深度強(qiáng)化學(xué)習(xí)算法相結(jié)合的MCTS 算法的決策效果得到了顯著的改善[20]。本論文受論文[10]提出方法的啟發(fā)，進(jìn)一步推進(jìn)了這一方向的研究工作。

2 GGP 概述

本部分將對(duì)GGP 的基本框架進(jìn)行整體介紹。

2.1 GGP 平臺(tái)

GGP 平臺(tái)為研究者提供在線競(jìng)技評(píng)測(cè)服務(wù)，同時(shí)收集大量的博弈實(shí)戰(zhàn)信息供研究者使用，為研究者設(shè)計(jì)和改進(jìn)通用博弈系統(tǒng)提供數(shù)據(jù)支持。經(jīng)過十多年的發(fā)展，GGP 平臺(tái)已成為衡量博弈系統(tǒng)智能程度的重要陣地。

具體地，GGP 平臺(tái)通過博弈主機(jī)（Game Manager）向研究者提供數(shù)百種博弈的規(guī)則描述、比賽記錄、圖形化展示以及博弈狀態(tài)數(shù)據(jù)，并通過網(wǎng)絡(luò)與玩家通信，接收他們的博弈決策；通用博弈系統(tǒng)在本地運(yùn)行，通過GGP 平臺(tái)所提供的應(yīng)用程序編程接口與博弈主機(jī)相互通信。

在線對(duì)弈時(shí)，博弈主機(jī)是玩家對(duì)弈的裁判，其工作流程如圖1所示。博弈主機(jī)首先向GGP 玩家同時(shí)發(fā)送博弈開始的信息，包括博弈規(guī)則、玩家在博弈中扮演的角色、博弈的準(zhǔn)備時(shí)間以及行動(dòng)時(shí)間。收到博弈開始的信息，各個(gè)玩家有一段時(shí)間來理解博弈規(guī)則，即準(zhǔn)備時(shí)間，通常是30 秒到120 秒。準(zhǔn)備時(shí)間結(jié)束后，博弈正式進(jìn)入第一回合。每個(gè)回合，博弈主機(jī)會(huì)告知玩家是否要采取行動(dòng)。玩家有思考決策時(shí)間，即行動(dòng)時(shí)間，一般在60 秒內(nèi)。超過行動(dòng)時(shí)間，博弈主機(jī)會(huì)隨機(jī)給玩家指派一個(gè)行動(dòng)。在下一個(gè)回合時(shí)，博弈主機(jī)會(huì)將上一回合各個(gè)玩家采取的行動(dòng)發(fā)送給各個(gè)玩家，玩家可以據(jù)此更新博弈狀態(tài)并結(jié)合博弈規(guī)則推斷出當(dāng)前狀態(tài)的合法行動(dòng)。同時(shí)博弈主機(jī)在接收到所有玩家的行動(dòng)后會(huì)計(jì)算出下一回合的博弈狀態(tài)，并判定這一狀態(tài)是否為博弈結(jié)束狀態(tài)。如果是結(jié)束狀態(tài)，則告知各玩家博弈結(jié)束并給出博弈結(jié)果；如果不是，則進(jìn)入下一個(gè)博弈回合。其中，博弈主機(jī)與各玩家的信息交互遵循的是TCP/IP 協(xié)議[7]。

圖1 博弈主機(jī)工作流程[7]Fig.1 The workflow diagram of the Game Manager[7]

2.2 通用博弈描述語言

GGP 領(lǐng)域的官方語言即通用博弈描述語言（General Game Description Language,GDL）是由斯坦福大學(xué)GGP 項(xiàng)目團(tuán)隊(duì)在2005年提出的[21]。

GDL 是一種聲明式的邏輯程序語言，使用命題集合來表示狀態(tài)。對(duì)于一個(gè)博弈，GDL 定義一個(gè)狀態(tài)命題集合，用來描述博弈狀態(tài)的基本信息；在博弈狀態(tài)集合與的冪集之間建立一個(gè)單射，用來表示博弈狀態(tài)上的事實(shí)信息。對(duì)任意一個(gè)狀態(tài) 和任意一個(gè)命題，若有則在上為真，反之則為假。同時(shí)，GDL 定義了動(dòng)作集合，且任意玩家 的合法動(dòng)作集都是的子集。在此基礎(chǔ)上，GDL 定義了描述博弈要素的集合，如表1所示。

表1 描述博弈要素的命題集合[7]Table 1 The proposition set for representing elements of games[7]

GDL 語言雖然簡(jiǎn)單但足夠描述任意有窮的完全信息的博弈規(guī)則[21]。值得一提的是，GDL 最初是為了描述完全信息博弈而設(shè)計(jì)的，最近被擴(kuò)展成GDLII、GDL-III分別用于描述不同程度的非完全信息博弈，如撲克牌、Bughouse 國際象棋等[22-23]。

3 通用博弈系統(tǒng)

本部分將首先介紹GGP 領(lǐng)域的主流算法MCTS算法及其變種UCT 算法，然后闡述本文所使用的方法，最后探討如何基于這一方法來構(gòu)建和實(shí)現(xiàn)通用博弈系統(tǒng)。

3.1 蒙特卡洛樹搜索算法

MCTS 算法是一種在給定的決策空間中尋找最優(yōu)決策的方法，通過在決策空間中抽取隨機(jī)樣本，并根據(jù)這些樣本構(gòu)建搜索樹。對(duì)于一些可以被表示為序貫決策樹的人工智能領(lǐng)域，比如博弈和規(guī)劃問題，MCTS 算法已經(jīng)產(chǎn)生了深遠(yuǎn)的影響。

MCTS 算法的核心思想是通過迭代來構(gòu)建搜索樹，直到達(dá)到某個(gè)預(yù)定義的預(yù)算上限（這個(gè)上限通常可以是時(shí)間限制、內(nèi)存限制或迭代次數(shù)限制），此時(shí)搜索停止，并返回根節(jié)點(diǎn)的最佳行動(dòng)。對(duì)于GGP，搜索樹中的每一個(gè)節(jié)點(diǎn)都代表著博弈狀態(tài)空間中的一個(gè)狀態(tài)。

在MCTS 算法的每次迭代中，主要包含選擇、擴(kuò)展、模擬、反向傳播四個(gè)步驟。在具體闡述每一步驟之前，先對(duì)以下符號(hào)進(jìn)行說明：

·集合 是博弈狀態(tài)的集合。

下面對(duì)MCTS 算法所包含的四個(gè)步驟進(jìn)行逐一說明。

（1）選擇

從根節(jié)點(diǎn)開始，遞歸地應(yīng)用選擇策略來對(duì)搜索樹進(jìn)行遍歷，直到達(dá)到一個(gè)可擴(kuò)展節(jié)點(diǎn)。如果一個(gè)節(jié)點(diǎn)代表著一個(gè)非結(jié)束狀態(tài)，并且它有未被訪問過（擴(kuò)展過）的子節(jié)點(diǎn)，則稱它是可擴(kuò)展的。原始的MCTS 算法的選擇策略為：

即選擇當(dāng)前狀態(tài)下行動(dòng)價(jià)值最大的行動(dòng)。

（2）擴(kuò)展

當(dāng)搜索到達(dá)一個(gè)可擴(kuò)展節(jié)點(diǎn)后，算法將對(duì)其一未被加入搜索樹的子節(jié)點(diǎn)加入搜索樹中，并對(duì)該子節(jié)點(diǎn)執(zhí)行模擬和反向傳播，完成后進(jìn)入下次迭代。

（3）模擬

在新節(jié)點(diǎn)運(yùn)行模擬策略直至博弈結(jié)束狀態(tài)，并返回獎(jiǎng)勵(lì)值。模擬策略通常包含兩種：一種是均勻隨機(jī)策略，通過均勻隨機(jī)選擇動(dòng)作進(jìn)行對(duì)弈直到到達(dá)博弈結(jié)束狀態(tài)；另一種則是啟發(fā)式策略，引入特定博弈的專門信息，極大地降低模擬深度、減少分支，加快收斂的速度，但也會(huì)相應(yīng)的降低搜索空間，有可能會(huì)陷入局部最優(yōu)的困境。

（4）反向傳播

在選擇階段，原始的MCTS 算法只選擇當(dāng)前行動(dòng)價(jià)值最高的行動(dòng)，但事實(shí)上，當(dāng)前行動(dòng)價(jià)值低的節(jié)點(diǎn)可能在多次迭代后，發(fā)現(xiàn)它具有更好的表現(xiàn)，因此為了避免陷入局部最優(yōu)，需要更好地平衡探索和利用的關(guān)系。

多臂老虎機(jī)問題（Multi-Armed Bandits）正是一個(gè)探究如何平衡探索和利用的研究方向。其中，Auer 等研究者提出的UCB1 方法（Upper Confidence Bound-1）在該問題上取得了很不錯(cuò)的效果[25]。同時(shí)，Kocsis 等研究者還將UCB1 方法與MCTS 算法相結(jié)合，提出UCT 算法，將多臂老虎機(jī)的平衡探索和利用的思想應(yīng)用到序貫決策問題[26]。

具體地，不同于MCTS 算法，UCT 算法在選擇階段不再選取當(dāng)前行動(dòng)價(jià)值最大的行動(dòng)，而是選擇最大置信上界的行動(dòng)，即：

3.2 蒙特卡洛樹搜索算法的優(yōu)化

在巨大的博弈狀態(tài)空間和相對(duì)有限的搜索時(shí)間的情況下，MCTS 算法估計(jì)狀態(tài)價(jià)值的方差比較大，無法保證估計(jì)值的準(zhǔn)確性，而估計(jì)值的不準(zhǔn)確將誤導(dǎo)搜索樹的構(gòu)建，嚴(yán)重降低程序的性能。為了解決上述問題，有研究者提出了記憶增強(qiáng)的蒙特卡洛樹搜索算法（M-MCTS），利用相似狀態(tài)間的共同信息，在在線搜索中提高狀態(tài)價(jià)值估計(jì)的準(zhǔn)確性[10]。M-MCTS 算法的結(jié)構(gòu)如圖2所示。

圖2 M-MCTS 算法原理示意圖[10]Fig.2 An illustration of M-MCTS[10]

其中，

（1）更新（Update）：當(dāng)搜索樹的節(jié)點(diǎn)中的信息發(fā)生更新時(shí)，需要同時(shí)更新中的對(duì)應(yīng)項(xiàng)。

（2）加入（Add）：當(dāng)搜索樹進(jìn)行擴(kuò)展時(shí)，需要將新節(jié)點(diǎn)也對(duì)應(yīng)加入到中；若滿了，則使用最近最少訪問的策略進(jìn)行替換。

（3）查找（Query）：通過查找操作，找到該狀態(tài)最相近的個(gè)狀態(tài)記為將這些狀態(tài)的狀態(tài)價(jià)值的加權(quán)平均作為該狀態(tài)的記憶狀態(tài)價(jià)值，即：

特別地，在M-MCTS 算法中，使用的是熵正則策略優(yōu)化（Entropy Regularized Policy Optimization）的方法來確定權(quán)重。

3.3 通用博弈系統(tǒng)的建立

本節(jié)介紹如何將M-MCTS 算法的思想用于通用博弈系統(tǒng)的構(gòu)建。

為此，本文對(duì)M-MCTS 算法進(jìn)行了如下修改，用以構(gòu)建通用博弈系統(tǒng)：

（1）將UCB1 方法加入到M-MCTS 算法中，同時(shí)完全使用記憶狀態(tài)值而不是狀態(tài)價(jià)值來引導(dǎo)搜索樹的構(gòu)建，故選擇策略為：

（2）在進(jìn)行反向傳播更新時(shí)，不再使用原先的增量均值的更新，而是使用以下更新策略：

需要說明的是，在具體實(shí)現(xiàn)時(shí)，本文在查詢操作時(shí)僅使用其自身的狀態(tài)價(jià)值。

基于上述方法，本文利用GGP 平臺(tái)提供的基礎(chǔ)代碼來具體實(shí)現(xiàn)通用博弈系統(tǒng)?；A(chǔ)代碼涵蓋了博弈狀態(tài)機(jī)的構(gòu)建、維護(hù)和狀態(tài)轉(zhuǎn)換等功能，同時(shí)提供了設(shè)置博弈和展示對(duì)戰(zhàn)雙方博弈狀況的可視化界面。所構(gòu)建的系統(tǒng)將在準(zhǔn)備時(shí)間內(nèi)進(jìn)行對(duì)博弈的理解和一些預(yù)處理，接受該博弈的GDL 語言描述，理解博弈規(guī)則并生成該博弈的狀態(tài)機(jī)，并在剩余的時(shí)間內(nèi)運(yùn)行通用博弈系統(tǒng)進(jìn)行決策。

在基礎(chǔ)代碼中，主要有兩個(gè)核心類：一個(gè)是狀態(tài)機(jī)類（StateMachine），負(fù)責(zé)各種博弈狀態(tài)機(jī)的構(gòu)建和維護(hù)，提供博弈結(jié)束狀態(tài)的獎(jiǎng)勵(lì)值、給定角色在當(dāng)前狀態(tài)可以選擇的合法動(dòng)作以及執(zhí)行給定動(dòng)作后轉(zhuǎn)換到的后繼狀態(tài)；另一個(gè)是博弈玩家類（Gamer），提供了獲取博弈當(dāng)前狀態(tài)、獲取博弈當(dāng)前擁有控制權(quán)的角色、獲取當(dāng)前博弈狀態(tài)機(jī)等功能。

具體地，我們需要實(shí)現(xiàn)本系統(tǒng)的核心函數(shù)——?jiǎng)幼鬟x擇函數(shù)，在該函數(shù)內(nèi)我們將從狀態(tài)機(jī)獲取博弈當(dāng)前狀態(tài)作為根節(jié)點(diǎn)，構(gòu)建決策樹，并在每步時(shí)限內(nèi)運(yùn)行我們修改的M-MCTS 算法，遞歸地進(jìn)行搜索、擴(kuò)展、模擬、更新并提取記憶、反向傳播，最終選擇平均獎(jiǎng)勵(lì)值最高的動(dòng)作返回。

4 實(shí)驗(yàn)結(jié)果和分析

本部分以GGP 平臺(tái)上提供的原始的蒙特卡洛MC 方法的通用博弈系統(tǒng)作為基準(zhǔn)，通過對(duì)比試驗(yàn)全面評(píng)估所構(gòu)建通用博弈系統(tǒng)的性能水平。

4.1 實(shí)驗(yàn)平臺(tái)及環(huán)境設(shè)置

本文的實(shí)驗(yàn)是在Ubuntu 系統(tǒng)上現(xiàn)實(shí)的，實(shí)驗(yàn)運(yùn)行的服務(wù)器設(shè)備是Linux 內(nèi)核，Intel(R)的CPU E5-2650，128GB 內(nèi)存，采用GGP 平臺(tái)進(jìn)行對(duì)比實(shí)驗(yàn)。

為了全面評(píng)估所構(gòu)建的通用博弈系統(tǒng)的智能水平，本文從以往GGP 競(jìng)賽中選取六組不同類型的博弈游戲進(jìn)行測(cè)試[27]。具體博弈特征如表2所示。

表2 實(shí)驗(yàn)測(cè)試游戲Table 2 Games in the experiments

在實(shí)驗(yàn)過程中，博弈準(zhǔn)備時(shí)間統(tǒng)一設(shè)置為30s，通過對(duì)行動(dòng)時(shí)間、先后手以及更新比例 三個(gè)參數(shù)的設(shè)置來全面的評(píng)估本文所構(gòu)建通用博弈系統(tǒng)在六組博弈上的性能表現(xiàn)。具體地，為了保證模擬次數(shù)，玩家采取行動(dòng)的時(shí)間分別設(shè)置為15s、30s、45s、60s；由于先后手對(duì)博弈，特別是雙人零和完全信息博弈的勝率具有影響，實(shí)驗(yàn)中每組博弈對(duì)弈雙方在進(jìn)行50 局后互換角色；為了考察最優(yōu)的記憶更新比例，分別設(shè)置為0.5、0.8。

4.2 實(shí)驗(yàn)結(jié)果及分析

Tic-Tac-Toe (Large)游戲是井字棋的變種，兩個(gè)玩家X,O 依次在5×5 的空格內(nèi)填寫自己的標(biāo)記，任意一方在橫、豎或斜方向五個(gè)標(biāo)記形成一條直線，則獲勝。如圖3所示，相比于基準(zhǔn)的通用博弈系統(tǒng)，我們所構(gòu)建的通用博弈系統(tǒng)性能相對(duì)較高，獲勝率保持在55%以上。同時(shí)，隨著行動(dòng)時(shí)間的增長，所構(gòu)建的通用博弈系統(tǒng)的獲勝率逐步下降，而更新比例 的變化對(duì)其勝率影響并不明顯。

圖3 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Tic-Tac-Toe(Large)游戲上對(duì)弈的獲勝率相對(duì)于行動(dòng)時(shí)間的變化。Fig.3 The winning rate of our player vs.baseline in Tic-Tac-Toe (Large).

如圖4所示，所構(gòu)建的通用博弈系統(tǒng)在規(guī)模增大的游戲Connect 4 上的優(yōu)勢(shì)更加顯著，其獲勝率最高達(dá)99%，最低在88%以上。類似于Tic-Tac-Toe (Large)游戲，隨著行動(dòng)時(shí)間的增長，所構(gòu)建的通用博弈系統(tǒng)的獲勝率逐步下降，但更新比例 的變化對(duì)其影響并不明顯。在游戲規(guī)模進(jìn)一步增大的Connect 5、Breakthrough 上，所構(gòu)建的通用博弈系統(tǒng)的獲勝率高達(dá)100%，且不受行動(dòng)時(shí)間的增長和記憶更新率的影響。

圖4 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Connect 4 游戲上對(duì)弈的獲勝率相對(duì)于行動(dòng)時(shí)間的變化。Fig.4 The winning rate of our player vs.baseline in Connect 4.

可見，在雙人完全信息零和博弈中，所構(gòu)建的通用博弈系統(tǒng)的性能會(huì)隨著游戲規(guī)模的增大而顯著提升，甚至在Connect 5、Breakthrough 等規(guī)模龐大的游戲上對(duì)基于MC 方法的通用博弈系統(tǒng)有著絕對(duì)的優(yōu)勢(shì)，即100%的勝率，如圖5、圖6所示。而在Tic-Tac-Toe (Large)、Connect 4 這些規(guī)模相對(duì)較小的游戲上，由于搜索空間相對(duì)小，基于MC 方法的通用博弈系統(tǒng)通過隨機(jī)模擬能在一些場(chǎng)合下達(dá)到最優(yōu)結(jié)果，且隨著行動(dòng)時(shí)間的增長，其有更大的概率能夠搜索到最優(yōu)的狀態(tài)；另一方面，對(duì)于所構(gòu)建的通用博弈系統(tǒng)，由于其效率已經(jīng)較高，能在相對(duì)短時(shí)間內(nèi)到達(dá)最佳狀態(tài)，無論是行動(dòng)時(shí)間是否增長其都已達(dá)到最優(yōu)決策，故其性能不會(huì)因?yàn)闀r(shí)間增長而發(fā)生變化。因此，在Tic-Tac-Toe (Large)、Connect 4 游戲中，所構(gòu)建的通用博弈系統(tǒng)盡管優(yōu)勢(shì)明顯但沒有達(dá)到100%勝率，且隨著行動(dòng)時(shí)間的增長，其勝率會(huì)隨之下降。

圖5 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Connect 5 游戲上對(duì)弈的獲勝率相對(duì)于行動(dòng)時(shí)間的變化。Fig.5 The winning rate of our player vs.baseline in Connect 5.

圖6 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Breakthrough 游戲上對(duì)弈的獲勝率相對(duì)于行動(dòng)時(shí)間的變化。Fig.6 The winning rate of our player vs.baseline in Breakthrough.

本文以Pacman 3P 吃豆人游戲?yàn)槔u(píng)估了所構(gòu)建的通用博弈系統(tǒng)在多人非對(duì)稱信息游戲中的性能表現(xiàn)。Pacman 3P 游戲一共三個(gè)玩家，其中一個(gè)玩家控制Pacman，另外兩個(gè)玩家每人分別控制一個(gè)Ghost聯(lián)合抓捕Pacman，控制Pacman 的玩家要躲避Ghost，吃掉所有的Pellet 才能獲勝。為了對(duì)實(shí)驗(yàn)結(jié)果有更直觀的觀察，本文進(jìn)行了兩組實(shí)驗(yàn)：首先由基于MC 方法的通用博弈系統(tǒng)控制Pacman，所構(gòu)建的通用博弈系統(tǒng)控制兩個(gè)Ghost；然后互換角色。如圖7所示，所構(gòu)建的通用博弈系統(tǒng)相比基于MC 方法的通用博弈系統(tǒng)在Pacman 和Ghost 的得分比上具有明顯優(yōu)勢(shì)，如在更新比例 為0.8 的情況下，所構(gòu)建的通用博弈系統(tǒng)控制的Pacman 每局游戲平均得分在0.5 左右，而基于MC 方法的通用博弈系統(tǒng)控制的Pacman 得分比則不超過0.3。由于玩家之間的信息并不對(duì)稱，游戲的復(fù)雜度高，行動(dòng)時(shí)間的增長以及更新比例 的變化，對(duì)所構(gòu)建的通用博弈系統(tǒng)的性能影響并不明顯。

圖7 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Pacman 3P 游戲上對(duì)弈的平均得分相對(duì)于行動(dòng)時(shí)間的變化（左：更新比例=0.5；右：更新比例=0.8）。Fig.7 The average score of our player vs.baseline in Pacman 3P (Left:= 0.5 ;Right: = 0.8.).

最后，以Babel 游戲?yàn)槔u(píng)估了所構(gòu)建的通用博弈系統(tǒng)在合作游戲上的性能表現(xiàn)。Babel 是三人合作建高塔的游戲。為了直觀地顯示對(duì)比效果，本文考察了三個(gè)玩家都是所構(gòu)建的通用博弈系統(tǒng)與三個(gè)玩家都是基于MC 方法的通用博弈系統(tǒng)的兩種極端情況，具體結(jié)果如圖8所示。從得分上可以看出，整體上都是所構(gòu)建的通用博弈系統(tǒng)的性能要顯著地優(yōu)于都是基于MC 方法的通用博弈系統(tǒng)的性能。而隨著行動(dòng)時(shí)間的增長，基于所構(gòu)建的通用博弈系統(tǒng)的性能會(huì)逐步下降。其主要原因可能在于作為三人合作游戲Babel 玩家行動(dòng)組合規(guī)模大，游戲搜索寬度過大，隨著時(shí)間的增長，所構(gòu)建的通用博弈系統(tǒng)模擬次數(shù)的增加帶來記憶數(shù)目的增長，甚至達(dá)到記憶上限，這使得最新的記憶項(xiàng)目將替代最近最少查詢的項(xiàng)目，而這些被替換的項(xiàng)目很可能會(huì)導(dǎo)致新近擴(kuò)展?fàn)顟B(tài)的丟失，從而大大減弱了記憶增強(qiáng)的效果。當(dāng)更新比例 為0.5 時(shí)，記憶增強(qiáng)算法的性能下降比0.8 時(shí)相對(duì)明顯，一定程度上支持了這一觀點(diǎn)。不過整體而言，同前面游戲的實(shí)驗(yàn)結(jié)果類似，記憶更新率的變化對(duì)記憶增強(qiáng)算法性能的影響并不明顯。

圖8 所構(gòu)建的通用博弈系統(tǒng)與基準(zhǔn)系統(tǒng)在Babel 游戲上對(duì)弈的平均得分相對(duì)于行動(dòng)時(shí)間的變化。Fig.8 The average score of our player vs.baseline in Babel.

5 總結(jié)與展望

本文在蒙特卡洛樹搜索算法上增加記憶結(jié)構(gòu)以有效地利用博弈的專門信息，提升蒙特卡洛樹搜索的性能；基于此構(gòu)建了通用博弈系統(tǒng)，并依托于GGP 平臺(tái)全面地評(píng)估了所構(gòu)建系統(tǒng)的性能。實(shí)驗(yàn)結(jié)果表明，與GGP 平臺(tái)上的MC 通用博弈系統(tǒng)相比，本文所實(shí)現(xiàn)的通用博弈系統(tǒng)無論在智能水平還是決策效率上都有了顯著提升。如何進(jìn)一步提升通用博弈系統(tǒng)在復(fù)雜博弈特別是非完美信息博弈上的性能；如何將經(jīng)典的對(duì)抗算法與先進(jìn)的機(jī)器學(xué)習(xí)，特別是深度學(xué)習(xí)技術(shù)相結(jié)合以推動(dòng)GGP 領(lǐng)域的發(fā)展，通用人工智能研究的深入，無疑具有重要的理論價(jià)值和廣闊的應(yīng)用前景。

利益沖突聲明

所有作者聲明不存在利益沖突關(guān)系。