計算機博弈算法與編程 課件 6UCT算法

6UCT算法UCT算法（UpperConfidenceBoundApplytoTree），即上限置信區(qū)間算法，是一種博弈樹搜索算法，該算法將蒙特卡洛樹搜索(Monte—CarloTreeSearch，MCTS)方法與UCB公式結(jié)合，在超大規(guī)模博弈樹的搜索過程中相對于傳統(tǒng)的搜索算法有著時間和空間方面的優(yōu)勢。6UCT算法UCT(UpperConfidenceboundsappliedtoTrees)的算法，是匈牙利國家科學(xué)院計算機與自動化研究所（位于布達佩斯）的列文特·科奇什(LeventeKocsis)與加拿大阿爾伯塔大學(xué)（UniversityofAlberta，位于埃德蒙頓）的喬鮑·塞派什瓦里(CsabaSzepesvári)合作提出的，是著名的蒙特卡羅方法(MonteCarlomethod)的擴展應(yīng)用。6UCT算法示意圖6UCT算法

UCT算法與傳統(tǒng)搜索技術(shù)的最大區(qū)別在于不同的分支可以有不同的搜索深度。 UCT算法在不同的深度獲取評估值．對于最有“希望”求解問題的分支，UCT算法的搜索深度可以很深（遠大于d），而對于“希望”不大的分支，其搜索深度可以很淺（遠小于d）。

當(dāng)最有“希望”求解問題的分支數(shù)量遠少于“希望”不大的分支數(shù)量時，UCT算法就可以把搜索資源有效地用于最有“希望”求解問題的分支，從而獲得比傳統(tǒng)搜索算法更深的有效深度d′。這個具有神奇力量的“希望”是由樹內(nèi)選擇策略計算的．UCT算法四個步驟UCT算法共分四步完成：1、選擇2、擴展3、模擬4、方向傳播UCT算法-選擇1、選擇其中：

vi是以節(jié)點ni為根節(jié)點的子樹的所有仿真結(jié)果的平均值，反映了根據(jù)目前仿真結(jié)果觀測到的節(jié)點ni能提供的回報值的期。Ti是節(jié)點ni的訪問次數(shù)，也是節(jié)點ni被樹內(nèi)選擇策略選中的次數(shù)?！芓i是節(jié)點n的訪問次數(shù)。c是一個手工設(shè)定的常數(shù)。c的作用是平衡UCT算法的利用需求（exploitation）和探索需求（exploration）。UCT算法-擴展2、擴展擴展是將節(jié)點添加到UCT搜索樹中當(dāng)搜索到達葉子節(jié)點時，UCT算法執(zhí)行擴展操作（Expansion）：把此葉子節(jié)點允許的所有合法下一步產(chǎn)生的子節(jié)點，作為新的葉子節(jié)點加入到搜索樹中，并正確初始化其v值和T值。UCT算法-模擬3、模擬UCT算法并沒有使用額外的評估函數(shù)來獲取新葉子節(jié)點的評估v值，而是使用缺省仿真策略來繼續(xù)搜索直到游戲進入結(jié)束狀態(tài)。此時，棋盤上每一個位置都有明確的歸屬，黑方贏還是白方贏可以很容易地計算出來．葉子結(jié)點的評估值就是當(dāng)黑方勝時為1，白方贏為0。最簡單的缺省仿真策略就是在所有的合法下一步中，均勻地隨機選擇下一步。用隨機策略作為缺省仿真策略產(chǎn)生的程序棋力不高，因此大多數(shù)棋力不錯的程序都采用了更加復(fù)雜的缺省仿真策略。

UCT算法-反向傳播4、反向傳播結(jié)果回傳從葉子節(jié)點開始，沿搜索路徑逐級向上更新，直到根節(jié)點。UCT算法-優(yōu)勢一、UCT的工作模式是時間可控的我們可以在算法執(zhí)行過程中的任何時間突然終止算法，UCT算法可以返回一個差不多理想的結(jié)果。當(dāng)然如果給與更為充分的時間的話，算法結(jié)果會非常逼近實際的最優(yōu)值。但是這一點在alpha-beta搜索中是絕對行不通的。UCT算法-優(yōu)勢二、UCT具有更好的魯棒性這是因為它使用一種平滑的方式處理搜索過程中的不確定性。在每個節(jié)點，其計算值取決于它的搜索節(jié)點序列上的所有子節(jié)點的計算值，其值是一個經(jīng)過平滑的最大值的估計值。這樣，由于每個子節(jié)點的計算過程都經(jīng)過重新的抽樣計算，不會因為個別嚴重偏離事實的抽樣結(jié)果而對最終的結(jié)果產(chǎn)生致命性的影響。同時，由于算法在確定計算的節(jié)點序列時，依賴于第一層子節(jié)點的估值以及該估值的可信度。UCT算法-優(yōu)勢三、在UCT搜索算法的過程中，博弈樹以一種非對稱的形式動態(tài)擴展出來這樣做有兩個好處。首先，傳統(tǒng)的博弈樹擴展方式，仍然以alpha-beta搜索樹為例，每向下擴展一層都意味著博弈書規(guī)模的指數(shù)型增長以及搜索時間的指數(shù)型增加。對于內(nèi)存和CPU性能都有限的個人電腦來說，這一問題有的情況下是致命的。而在UCT算法搜索過程中，每次對于更深一層的擴展僅局限于搜索序列的最后一個節(jié)點。這樣的UCT算法可以在擴展節(jié)點的同時不斷的動態(tài)釋放計算過的節(jié)點內(nèi)存，使得算法運行的時間復(fù)雜性和空間復(fù)雜性可以被更好的控制。UCT算法-優(yōu)勢其次，正因為上述特性，對于較好的作為被選候補的節(jié)點，算法往往可以進行更為深入的搜索，同時，這種非對稱性擴展完全是在算法的執(zhí)行過程中自動進行的。因此，和傳統(tǒng)的博弈樹算法相比較，UCT算法有著其獨有的優(yōu)勢，特別是當(dāng)博弈樹規(guī)模非常大的時候。UCT算法首次應(yīng)用的圍棋博弈系統(tǒng)，以及本文即將討論的四國軍棋博弈系統(tǒng)都屬此例。因此，UCT搜索算法在本系統(tǒng)中的使用是切合實際的。MCT(UCT)算法-偽碼VoidMCTS(NoderootNode){ currentNode<-rootNode while(currentNode∈T) { lastNode<-currentNode currentNode<-select(current)//選擇 } lastNode<-Expand(lastNode)//擴展 R<-playSimulatedGame(lastNode)//模擬 while(currentNode∈T) { currentNode<-backPropagate(R)//反向傳播 currentNode.visitCount<-currentNode.visiteCount+1 currentNode<-currentNode.parent }}Return