UCT－RAVE算法在多人非完備信息博弈中的應用

芮雄星，王一莉

（南京工業大學 電子與信息工程學院，江蘇 南京210009）

0 引 言

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

1 UCT－RAVE介紹

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

1.1 UCT介紹

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

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

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

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

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

1.2 RAVE介紹

RAVE （rapid action value estimation）［11］是基于值 （valuebased）函數的強化學習思想在UCT方法中的應用。RAVE收集并評價UCT搜索中產生的狀態動作對，并在下一次UCT搜索時加以引導，使UCT能夠更多的搜索更好的分支。

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

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

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

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

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

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

則

動態規劃理論保證至少存在一個策略π＊使得對任意s∈S有

值函數Q（s，a）的估計有很多種算法，比如TD（λ）［13］。如果環境模型是已知的或是可學習的，那么基于值函數的強化學習算法可用于基于樣本的搜索。可從模型中抽樣來獲得模擬場景，通過模擬經驗來更新值函數。

RAVE是基于值函數Q（s，a）的強化學習方法，通過基于樣本的搜索樹來動態更新值函數。為了與UCT相結合，RAVE的收益公式定義為

式中：m（s，a）——s狀態下a動作被選擇的次數，m（s）——s狀態被訪問的次數。

1.3 UCT和RAVE結合

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

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

2 UCT－RAVE在非完備信息博弈中的應用

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

2.1 蒙特卡羅抽樣算法

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

2.2 UCT－RAVE與蒙特卡羅抽樣相結合

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

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

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

3 實例分析

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

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

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

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

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

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

表2 UCT－RAVE算法對戰結果

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

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

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

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

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

4 結束語

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

［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，Furtak 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，Fabien Teytaud，Olivier Teytaud.Biasing Monte－Carlo simulations through RAVE values ［C］.The International Conference on Computers and Games.Berlin：Springer，2010：59－68.