計算機博弈算法與編程 課件 6UCT算法、7Q學習算法

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

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

當最有“希望”求解問題的分支數(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ù)。∑Ti是節(jié)點n的訪問次數(shù)。c是一個手工設定的常數(shù)。c的作用是平衡UCT算法的利用需求（exploitation）和探索需求（exploration）。UCT算法-擴展2、擴展擴展是將節(jié)點添加到UCT搜索樹中當搜索到達葉子節(jié)點時，UCT算法執(zhí)行擴展操作（Expansion）：把此葉子節(jié)點允許的所有合法下一步產(chǎn)生的子節(jié)點，作為新的葉子節(jié)點加入到搜索樹中，并正確初始化其v值和T值。UCT算法-模擬3、模擬UCT算法并沒有使用額外的評估函數(shù)來獲取新葉子節(jié)點的評估v值，而是使用缺省仿真策略來繼續(xù)搜索直到游戲進入結(jié)束狀態(tài)。此時，棋盤上每一個位置都有明確的歸屬，黑方贏還是白方贏可以很容易地計算出來．葉子結(jié)點的評估值就是當黑方勝時為1，白方贏為0。最簡單的缺省仿真策略就是在所有的合法下一步中，均勻地隨機選擇下一步。用隨機策略作為缺省仿真策略產(chǎn)生的程序棋力不高，因此大多數(shù)棋力不錯的程序都采用了更加復雜的缺省仿真策略。

UCT算法-反向傳播4、反向傳播結(jié)果回傳從葉子節(jié)點開始，沿搜索路徑逐級向上更新，直到根節(jié)點。UCT算法-優(yōu)勢一、UCT的工作模式是時間可控的我們可以在算法執(zhí)行過程中的任何時間突然終止算法，UCT算法可以返回一個差不多理想的結(jié)果。當然如果給與更為充分的時間的話，算法結(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)存，使得算法運行的時間復雜性和空間復雜性可以被更好的控制。UCT算法-優(yōu)勢其次，正因為上述特性，對于較好的作為被選候補的節(jié)點，算法往往可以進行更為深入的搜索，同時，這種非對稱性擴展完全是在算法的執(zhí)行過程中自動進行的。因此，和傳統(tǒng)的博弈樹算法相比較，UCT算法有著其獨有的優(yōu)勢，特別是當博弈樹規(guī)模非常大的時候。UCT算法首次應用的圍棋博弈系統(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 }}ReturnbestMove//selectUCT算法-改進說明：f(ni)-與知識和模擬次數(shù)相關(guān)，例如可以為k*value/TiUCT算法-與Monte-Carlo實際比較UCT算法-應用1、開局庫開發(fā)2、棋局對弈3、機器學習相結(jié)合7Q學習算法強化學習：強化學習是程序通過經(jīng)驗學習行為知識的機器學習方法。智能體(Agent)以“試錯”的方式進行學習，通過與環(huán)境進行交互獲得的獎賞來指導行為，其目標是使智能體獲得最大的獎賞。Q學習算法在設計強化學習系統(tǒng)時主要考慮以下三方面的內(nèi)容：(1)如何表示狀態(tài)空間和動作空間。(2)如何選擇建立信號以及如何通過學習來修正不同狀態(tài)—動作對的值。(3)如何根據(jù)這些值來選擇合適的動作。Q學習算法Q-學習算法是強化學習算法中基于價值的算法，Q即為Q(s,a)，就是在某一個時刻的state狀態(tài)下，采取動作a能夠獲得收益的期望，環(huán)境會根據(jù)agent的動作反饋相應的獎賞(reward)，所以算法的主要思想就是將state和action構(gòu)建成一張Q表來存儲Q值，然后根據(jù)Q值來選取能夠獲得最大收益的動作。如果有適當?shù)姆椒ㄓ嬎愠鲈u分值Q，那么只需要找出一個合適的行動a使得Q的值為最大，這樣就可以確定最優(yōu)行動策略。Q學習算法Q表實際上就是狀態(tài)、動作、與估計的未來獎勵之間的映射表Q學習算法Q學習案例Q學習算法Q表數(shù)據(jù)Q學習算法獎勵公式更新公式Q學習算法Q學習算法過程Q學習算法的基本過程如下：(1)設置參數(shù)γ，并初始化獎勵矩陣R。(2)將Q表初始化為0。(3)For每一個過程隨機選擇一個初始狀態(tài) DoWhile(目標狀態(tài)未達到)

從當前狀態(tài)的所有可能的動作中，選擇一個動作

使用這一個動作，達到下一個狀態(tài)

在下一個狀態(tài)的所有可能動作中，選一個Q值最大的動作

按獎勵公式和更新公式計算Q值

設置下一個狀態(tài)為當前狀態(tài) EndDoEndForQ學習算法利用矩陣Q的算法如下：(1)設置當前狀態(tài)=初始狀態(tài)。(2)從當前狀態(tài)開始，尋找具有最高Q值的動作。(3)設置當