UCT－RAVE算法在多人非完備信息博弈中的應(yīng)用

芮雄星，王一莉

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京210009）

0 引 言

完備信息博弈和非完備信息博弈是機器博弈的兩個分支，對于完備信息博弈，國內(nèi)外已經(jīng)取得了的很多較好的研究成果。而非完備信息博弈領(lǐng)域的相關(guān)研究還不十分成熟，目前為止非完備信息下很成功的人工智能博弈程序還很少。傳統(tǒng)的基于最小最大 （minimax）搜索的算法很難適用于多人非完備信息博弈，由于每個博弈者可能使用不同的博弈策略，很難找到一個靜態(tài)評價函數(shù)能夠很好的應(yīng)對每種博弈策略；而非完備信息的存在導(dǎo)致不確定博弈行為大量增加，博弈搜索空間將變得龐大［1］。而且，alpha－beta剪枝在多人博弈中效率很低，雖然在二人完備信息博弈中alpha－beta剪枝能使空間復(fù)雜度從O（bd）降為O（bd/2），但在多人博弈中，最好的情況只能使空間復(fù)雜度降為，其中n為玩家人數(shù)［2］。本文將介紹一種新的博弈 搜 索 算 法 UCT－RAVE［3－4］。 并 通 過 與 蒙 特 卡 羅 抽 樣（Monte－Carlo sampling）技術(shù)［5］相結(jié)合，將其應(yīng)用于多人非完備信息博弈中。通過簡單的三人爭上游牌類博弈實例，驗證此方法的可行性和有效性；并與UCT算法比較，測試其性能。

1 UCT－RAVE介紹

UCT－RAVE是應(yīng)用于樹搜索的上限置信區(qū)間 （upper confidence bound applied to tree search）方法和快速動作值估計 （rapid action value estimation）方法的結(jié)合，是結(jié)合蒙特卡羅 （Monte－Carlo）搜索方法和強化學(xué)習(xí) （reinforcement learning）方法為一體的一種博弈搜索算法，由Sylvain應(yīng)用在計算機圍棋上獲得了巨大的成功［6］。

1.1 UCT介紹

UCT （UCB applied to TRee）是利用UCB （upper confidence bound）公式和蒙特卡羅模擬的結(jié)果來增量擴展搜索狀態(tài)的一種算法。UCB是為了解決K臂賭博機問題［7］而產(chǎn)生的，K臂賭博機是一種假想的具有K只手柄的老虎機，可做的動作是選擇并拉下其中的一只手柄，而由此所贏取的一定數(shù)量的錢就是和這個手柄 （動作）相關(guān)聯(lián)的收益（reward）。問題是如何根據(jù)當(dāng)前已經(jīng)掌握的每只手柄的收益情況決定下次拉下哪知手柄，一般來說，玩家會根據(jù)當(dāng)前所積累的知識來做決定，這稱之為開發(fā) （exploitation）。如果一味的選擇已開發(fā)過的手柄，而不嘗試其它的手柄，則可能會錯過收益率更高的手柄，因此應(yīng)當(dāng)適度地嘗試未開發(fā)過的手柄，這稱之為探索 （exploration）。UCB試圖解決開發(fā)與探索之間的矛盾，尋找開發(fā)與探索之間的平衡點［8］。

UCB利用當(dāng)前掌握的知識加上一個調(diào)整項來平衡開發(fā)與探索之間的矛盾。在每次做出選擇時，UCB根據(jù)每只手柄到目前為止的平均收益值，加上調(diào)整項的值，得出本次選擇此手柄的UCB值，挑選擁有最大UCB值的手柄作為本次所要選擇的手柄。UCB公式表示如下

式中：UCBi——第i只手柄經(jīng)由UCB公式運算后所得到的值，Xi——第i只手柄到目前為止的平均收益值，Ti——第i只手柄被選擇的次數(shù)，N——到目前為止所有手柄選擇次數(shù)的總和。公式中前項即為此手柄的過去表現(xiàn)，即開發(fā)項，后項則是調(diào)整值，即探索項。其中調(diào)整項值會隨這只手柄被選擇次數(shù)的增加而減少，以便選擇手柄時，不過分拘泥于舊有的表現(xiàn)，適當(dāng)探索其它手柄。從而在開發(fā)和探索之間進行平衡。

UCT把每一個節(jié)點都當(dāng)作是一個K臂賭博機問題［9－10］，而此節(jié)點的每一個分支，都是K臂賭博機的一只手柄。選擇分支，就會獲得相對應(yīng)的收益，對于博弈而言，UCB公式的收益值就等于該狀態(tài)下的勝率，而該勝率是按照蒙特卡羅抽樣的概念，用模擬博弈的結(jié)果來決定。所謂的模擬博弈，就是給定一個局面 （在此給的是葉節(jié)點所代表的局面），由計算機接手博弈，直到終局，然后判定并回傳勝負結(jié)果。UCT會據(jù)此結(jié)果，更新葉節(jié)點到根節(jié)點路徑上所有節(jié)點的收益值。可以用狀態(tài)動作對 （s，a）的方式來表示UCT收益公式

式中：n（s，a）——s狀態(tài)下a動作被選擇的次數(shù)，n（s）——s狀態(tài)被訪問的次數(shù)，而選擇動作的策略πUCT（s）就是使平均收益最大化：。

1.2 RAVE介紹

RAVE （rapid action value estimation）［11］是基于值 （valuebased）函數(shù)的強化學(xué)習(xí)思想在UCT方法中的應(yīng)用。RAVE收集并評價UCT搜索中產(chǎn)生的狀態(tài)動作對，并在下一次UCT搜索時加以引導(dǎo)，使UCT能夠更多的搜索更好的分支。

強化學(xué)習(xí)是一種無監(jiān)督的機器學(xué)習(xí)方法，它被稱之為“和批評者一起學(xué)習(xí)”。批評者 （critic）并不反饋應(yīng)該做什么，而僅僅反饋之前所做的怎么樣12。最典型的強化學(xué)習(xí)算法是Q學(xué)習(xí)算法，可以看作是馬爾可夫決策過程（Markov decision processes）的一種變化形式。

馬爾可夫決策過程是強化學(xué)習(xí)的數(shù)學(xué)模型，它是由四元組組成：＜S，A，R，T＞，其中S是離散的狀態(tài)集，A是離散的動作集，R：S×A→R是獎勵函數(shù)，T：S×A→PD（S）是狀態(tài)轉(zhuǎn)移函數(shù)，PD（S）是狀態(tài)集S上的概率分布函數(shù)。

典型的基于折扣報酬的強化學(xué)習(xí)問題通?？梢悦枋鰹榻o定＜S，A，R，T＞，尋找策略π使得期望折扣報酬總和最大

式中：Vπ（s）——折算累積回報，上式可以改寫為

式中：r（s，a）——s狀態(tài)下執(zhí)行a所得的報酬值，γ是折扣因子。

定義Q（s，a）為從狀態(tài)s開始并使用a作為第一個動作時的最大折算累積回報，換言之，Q的值為從狀態(tài)s執(zhí)行動作a的立即回報加上以后遵循最優(yōu)策略的值

則

動態(tài)規(guī)劃理論保證至少存在一個策略π＊使得對任意s∈S有

值函數(shù)Q（s，a）的估計有很多種算法，比如TD（λ）［13］。如果環(huán)境模型是已知的或是可學(xué)習(xí)的，那么基于值函數(shù)的強化學(xué)習(xí)算法可用于基于樣本的搜索?？蓮哪Ｐ椭谐闃觼慝@得模擬場景，通過模擬經(jīng)驗來更新值函數(shù)。

RAVE是基于值函數(shù)Q（s，a）的強化學(xué)習(xí)方法，通過基于樣本的搜索樹來動態(tài)更新值函數(shù)。為了與UCT相結(jié)合，RAVE的收益公式定義為

式中：m（s，a）——s狀態(tài)下a動作被選擇的次數(shù)，m（s）——s狀態(tài)被訪問的次數(shù)。

1.3 UCT和RAVE結(jié)合

UCT需要對每個s∈S狀態(tài)下可供選擇的動作進行抽樣，以便比較各分支的收益情況并做出路徑選擇。如果動作空間巨大，可供選擇的分支數(shù)就很多，要用足夠多的模擬次數(shù)來區(qū)分分支的好壞［14－15］，而巨大的模擬次數(shù)將影響算法的性能。為減少模擬次數(shù)，UCT中加入在線學(xué)習(xí)知識RAVE，將RAVE值作為分支選擇的另一參考，以提高分支選擇的準(zhǔn)確性。引入線性因子β（s，a）把QUCT和QRAVE線性組合到一起

式中：k——平等因子，控制了QUCT和QRAVE所占的比重。同樣選擇動作的策略πUR（s）就是使平均收益最大化

2 UCT－RAVE在非完備信息博弈中的應(yīng)用

在非完備信息博弈中，博弈的真實狀態(tài)是不可知的，比如牌類游戲中對手的牌是未知的，進行博弈的玩家所掌握的信息是不對稱的和不完備的，這使得非完備信息博弈的研究更具有挑戰(zhàn)性。為了應(yīng)用UCT－RAVE算法，必須把這部分未知信息確定下來，可以通過猜測或計算等多種方法，而應(yīng)用最廣泛的是蒙特卡羅抽樣方法。

2.1 蒙特卡羅抽樣算法

蒙特卡羅方法又稱為計算機隨機模擬方法，是一種基于隨機數(shù)的計算方法。它通過隨機抽樣將非完備信息博弈問題轉(zhuǎn)換為完備信息博弈問題，同時通過大規(guī)模的抽樣次數(shù)來逼近真實的情況。該方法在一些非完備信息博弈游戲中，例如Alberta的橋牌程序，已經(jīng)取得了較好的效果。

2.2 UCT－RAVE與蒙特卡羅抽樣相結(jié)合

UCT－RAVE算法運行過程中的兩個重要因素在于節(jié)點的動態(tài)擴展和節(jié)點值的回溯運算。在非完備信息條件下，這兩點是無法實現(xiàn)的。因此UCT－RAVE算法必須與可以將非完備信息條件轉(zhuǎn)換為完備信息條件的蒙特卡羅抽樣算法相結(jié)合。

UCT－RAVE與蒙特卡羅抽樣算法的結(jié)合體現(xiàn)在搜索算法初始化過程中完備信息局面的生成。在UCT－RAVE算法進行一次搜索時，首先使用蒙特卡羅抽樣算法對非完備信息局面進行抽樣生成完備信息局面。然后UCT－RAVE算法依據(jù)這個完備信息局面進行一次搜索和節(jié)點的擴展。下次搜索將基于另一個蒙特卡羅抽樣生成的完備信息局面，每次搜索所生成的節(jié)點都保存于同一棵搜索樹中，樹中的每一個節(jié)點的勝率將代表綜合各種可能的局面下的平均表現(xiàn)。

圖1為應(yīng)用于非完備信息博弈的UCT－RAVE算法偽代碼，與蒙特卡羅抽樣技術(shù)的結(jié)合使得UCT－RAVE算法在非完備信息博弈樹的搜索問題中可以有效的運行并發(fā)揮自己的優(yōu)勢。

3 實例分析

為了驗證本文方法在多人非完備信息博弈中的效果，選擇了一個簡單的三人爭上游牌類博弈模型，爭上游又稱拱豬、跑得快等，游戲主要流行于江浙一帶，游戲規(guī)則決定了玩家需要盡快把自己手中的牌盡量多的打出去，先把手中的牌出完的玩家獲得勝利。失敗的玩家，根據(jù)手中所剩的牌的數(shù)量計算，剩余的牌越多扣的分數(shù)越多，如圖2所示。

圖1 應(yīng)用于非完備信息博弈的UCT－RAVE算法偽代碼

圖2 三人爭上游牌類博弈畫面

用不同的算法作為玩家出牌的策略進行游戲，比較不同算法的性能表現(xiàn)。為更好的做出比較，限制每次用兩種算法控制3個玩家進行博弈，即只有兩種類型的玩家，用Type A和Type B表示，同時為了消除位置對算法勝率的影響，選擇表1所示的6種不同的位置排列，并平均各種位置排列下算法的表現(xiàn)。

表1 兩種類型玩家的不同位置排列

選取UCT－RAVE算法參數(shù)C值為0.44，k值為100，模擬次數(shù)取5000，分別與UCT算法、隨機 （Random）策略方法進行比較，每種位置排列進行1000次博弈，取平均計算勝率和失敗時剩余的牌的數(shù)量，結(jié)果如表2所示。

表2 UCT－RAVE算法對戰(zhàn)結(jié)果

由表2可以看出，在上述參數(shù)設(shè)置情況下，本文算法對隨機策略時勝率在95%以上，說明了本文算法適用于多人非完備信息博弈模型，表現(xiàn)出一定的智能，和隨機的胡亂出牌有質(zhì)的區(qū)別。對UCT算法的勝率在75%左右，說明了本文算法的智能水平。

為研究模擬次數(shù)對本文UCT－RAVE算法的智能影響，選取10至10000區(qū)間內(nèi)的若干模擬次數(shù)，并與此模擬次數(shù)下的UCT算法進行博弈比較，結(jié)果如圖3所示。

圖3 不同模擬次數(shù)下UCT－RAVE算法的性能

圖3 橫坐標(biāo)為兩種算法所用的蒙特卡羅模擬次數(shù)，縱坐標(biāo)為本文UCT－RAVE算法對UCT算法的勝率，圖中曲線表示隨著模擬次數(shù)變化UCT－RAVE對UCT算法的勝率的變化情況。

從圖3中可以看出，本文UCT－RAVE算法對戰(zhàn)UCT算法能夠取得70%以上的勝率，而從模擬次數(shù)的角度分析，本文UCT－RAVE算法可以在比較少的模擬次數(shù)下取得較好表現(xiàn)。在模擬次數(shù)極少 （50次以下）的情況下本文UCT－RAVE算法的勝率在50%以下，原因在于過少的模擬次數(shù)不能較準(zhǔn)確的積累強化學(xué)習(xí)的數(shù)據(jù)，使得到的RAVE值很不準(zhǔn)確，從而干擾了UCT的選擇。隨著模擬次數(shù)的不斷增加，勝率呈下降趨勢，是因為大量的模擬次數(shù)足以獲得準(zhǔn)確的勝率值，對RAVE的依賴逐漸減少。

4 結(jié)束語

本文詳細介紹了UCT－RAVE算法的原理和特性，提出了將其與蒙特卡羅抽樣技術(shù)相結(jié)合應(yīng)用于多人非完備信息博弈中，首先通過蒙特卡羅抽樣技術(shù)將非完備信息轉(zhuǎn)化為有一定可信度的完備信息，然后基于此完備信息運用UCTRAVE算法進行搜索，最后綜合多次蒙特卡羅抽樣下的最佳平均收益，選擇最適行動。通過簡單的三人爭上游牌類博弈實驗證明此方法可行有效，并且同樣模擬次數(shù)下能夠獲得比UCT算法更好的性能表現(xiàn)。但是如何選擇本文UCT－RAVE算法的參數(shù)以獲得更好的性能表現(xiàn)有待進一步研究。

［1］Sturtevant N R，Bowling M H.Robust game play against unknown opponents ［C］.Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems.USA：ACM，2006：713－719.

［2］Sturtevant N R.An analysis of UCT in multi－player games［C］.Proceedings of the 6th International Conference on Computers and Games.Berlin：Springer，2008：37－49.

［3］Chaslot G，Saito J T，Bouzy B，et al.Monte－Carlo strategies for computer go［C］.Proceedings of the 18th BeNeLux Conference on Artificial Intelligence.Park：AAAI Press，2006：83－91.

［4］Coulom R.Efficient selectivity and backup operators in Monte－Carlo tree search ［C］.Proceedings of the 5th International Conference on Computers and Games.Berlin：Springer，2006：72－83.

［5］Krauth W.Algorithms and computations［M］.England：Oxford University Press，2006：264－275.

［6］Sylvian Gelly，WANG Yizao，Remi Munos，et al.Modification of UCT with patterns in Monte－Carlo go ［R］.France：INRIA，2006：221－224.

［7］Kocsis L，Szepesvari C.Bandit based Monte－Carlo planning［C］.Proceedings of the 17th European Conference on Machine Learning.Berlin：Springer，2006.

［8］Gelly S，WANG Yizao.Exploration exploitation in Go：UCT for Monte－Carlo go ［C］.Twentieth Annual Conference on Neural Information Processing Systems.Canada：Citeseer，2006：225－236.

［9］WANG Y，Gelly S.Modifications of UCT and sequence－like simulations for Monte－Carlo go ［C］.IEEE Symposium on Computational Intelligence and Games.USA：IEEE，2007：175－182.

［10］Winand M H M，Bjornsson S Y，Saito J T.monte－carlo tree search solver［C］.Proceedings of the 6th International Conference on Computers and Games.Berlin：Springer，2008：25－36.

［11］Gelly S，Silver D.Combining online and offline knowledge in UCT ［C］.Proceedings of the 24th International Conference on Machine Learning.USA：ACM，2007：273－280.

［12］Silver D，Sutton R，Muller M.Reinforcement learning of local shape in the game of go ［C］.Proceedings of the 20th International Joint Conference on Artifical Intelligence.India：Hyderabad，2007：1053－1058.

［13］Nathan Sturtevant，Adam White.Feature construction for reinforcement learning in hearts［C］.Proceedings of the 5th International Conference on Computers and Games.Berlin：Springer，2006：1305－1310.

［14］Buro M，LONG J R，F(xiàn)urtak T，et al.improving state evaluation，inference，and search in trick－based card games ［C］.Proceedings of the 21st International Jont Conference on Artifical Intelligence.USA：ACM，2009：1407－1413.

［15］Arpad Rimmel，F(xiàn)abien Teytaud，Olivier Teytaud.Biasing Monte－Carlo simulations through RAVE values ［C］.The International Conference on Computers and Games.Berlin：Springer，2010：59－68.