計(jì)算機(jī)博弈算法與編程 課件 6UCT算法、7Q學(xué)習(xí)算法

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

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

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

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

UCT算法-反向傳播4、反向傳播結(jié)果回傳從葉子節(jié)點(diǎn)開始，沿搜索路徑逐級(jí)向上更新，直到根節(jié)點(diǎn)。UCT算法-優(yōu)勢(shì)一、UCT的工作模式是時(shí)間可控的我們可以在算法執(zhí)行過(guò)程中的任何時(shí)間突然終止算法，UCT算法可以返回一個(gè)差不多理想的結(jié)果。當(dāng)然如果給與更為充分的時(shí)間的話，算法結(jié)果會(huì)非常逼近實(shí)際的最優(yōu)值。但是這一點(diǎn)在alpha-beta搜索中是絕對(duì)行不通的。UCT算法-優(yōu)勢(shì)二、UCT具有更好的魯棒性這是因?yàn)樗褂靡环N平滑的方式處理搜索過(guò)程中的不確定性。在每個(gè)節(jié)點(diǎn)，其計(jì)算值取決于它的搜索節(jié)點(diǎn)序列上的所有子節(jié)點(diǎn)的計(jì)算值，其值是一個(gè)經(jīng)過(guò)平滑的最大值的估計(jì)值。這樣，由于每個(gè)子節(jié)點(diǎn)的計(jì)算過(guò)程都經(jīng)過(guò)重新的抽樣計(jì)算，不會(huì)因?yàn)閭€(gè)別嚴(yán)重偏離事實(shí)的抽樣結(jié)果而對(duì)最終的結(jié)果產(chǎn)生致命性的影響。同時(shí)，由于算法在確定計(jì)算的節(jié)點(diǎn)序列時(shí)，依賴于第一層子節(jié)點(diǎn)的估值以及該估值的可信度。UCT算法-優(yōu)勢(shì)三、在UCT搜索算法的過(guò)程中，博弈樹以一種非對(duì)稱的形式動(dòng)態(tài)擴(kuò)展出來(lái)這樣做有兩個(gè)好處。首先，傳統(tǒng)的博弈樹擴(kuò)展方式，仍然以alpha-beta搜索樹為例，每向下擴(kuò)展一層都意味著博弈書規(guī)模的指數(shù)型增長(zhǎng)以及搜索時(shí)間的指數(shù)型增加。對(duì)于內(nèi)存和CPU性能都有限的個(gè)人電腦來(lái)說(shuō)，這一問(wèn)題有的情況下是致命的。而在UCT算法搜索過(guò)程中，每次對(duì)于更深一層的擴(kuò)展僅局限于搜索序列的最后一個(gè)節(jié)點(diǎn)。這樣的UCT算法可以在擴(kuò)展節(jié)點(diǎn)的同時(shí)不斷的動(dòng)態(tài)釋放計(jì)算過(guò)的節(jié)點(diǎn)內(nèi)存，使得算法運(yùn)行的時(shí)間復(fù)雜性和空間復(fù)雜性可以被更好的控制。UCT算法-優(yōu)勢(shì)其次，正因?yàn)樯鲜鎏匦?，?duì)于較好的作為被選候補(bǔ)的節(jié)點(diǎn)，算法往往可以進(jìn)行更為深入的搜索，同時(shí)，這種非對(duì)稱性擴(kuò)展完全是在算法的執(zhí)行過(guò)程中自動(dòng)進(jìn)行的。因此，和傳統(tǒng)的博弈樹算法相比較，UCT算法有著其獨(dú)有的優(yōu)勢(shì)，特別是當(dāng)博弈樹規(guī)模非常大的時(shí)候。UCT算法首次應(yīng)用的圍棋博弈系統(tǒng)，以及本文即將討論的四國(guó)軍棋博弈系統(tǒng)都屬此例。因此，UCT搜索算法在本系統(tǒng)中的使用是切合實(shí)際的。MCT(UCT)算法-偽碼VoidMCTS(NoderootNode){ currentNode<-rootNode while(currentNode∈T) { lastNode<-currentNode currentNode<-select(current)//選擇 } lastNode<-Expand(lastNode)//擴(kuò)展 R<-playSimulatedGame(lastNode)//模擬 while(currentNode∈T) { currentNode<-backPropagate(R)//反向傳播 currentNode.visitCount<-currentNode.visiteCount+1 currentNode<-currentNode.parent }}ReturnbestMove//selectUCT算法-改進(jìn)說(shuō)明：f(ni)-與知識(shí)和模擬次數(shù)相關(guān)，例如可以為k*value/TiUCT算法-與Monte-Carlo實(shí)際比較UCT算法-應(yīng)用1、開局庫(kù)開發(fā)2、棋局對(duì)弈3、機(jī)器學(xué)習(xí)相結(jié)合7Q學(xué)習(xí)算法強(qiáng)化學(xué)習(xí)：強(qiáng)化學(xué)習(xí)是程序通過(guò)經(jīng)驗(yàn)學(xué)習(xí)行為知識(shí)的機(jī)器學(xué)習(xí)方法。智能體(Agent)以“試錯(cuò)”的方式進(jìn)行學(xué)習(xí)，通過(guò)與環(huán)境進(jìn)行交互獲得的獎(jiǎng)賞來(lái)指導(dǎo)行為，其目標(biāo)是使智能體獲得最大的獎(jiǎng)賞。Q學(xué)習(xí)算法在設(shè)計(jì)強(qiáng)化學(xué)習(xí)系統(tǒng)時(shí)主要考慮以下三方面的內(nèi)容：(1)如何表示狀態(tài)空間和動(dòng)作空間。(2)如何選擇建立信號(hào)以及如何通過(guò)學(xué)習(xí)來(lái)修正不同狀態(tài)—?jiǎng)幼鲗?duì)的值。(3)如何根據(jù)這些值來(lái)選擇合適的動(dòng)作。Q學(xué)習(xí)算法Q-學(xué)習(xí)算法是強(qiáng)化學(xué)習(xí)算法中基于價(jià)值的算法，Q即為Q(s,a)，就是在某一個(gè)時(shí)刻的state狀態(tài)下，采取動(dòng)作a能夠獲得收益的期望，環(huán)境會(huì)根據(jù)agent的動(dòng)作反饋相應(yīng)的獎(jiǎng)賞(reward)，所以算法的主要思想就是將state和action構(gòu)建成一張Q表來(lái)存儲(chǔ)Q值，然后根據(jù)Q值來(lái)選取能夠獲得最大收益的動(dòng)作。如果有適當(dāng)?shù)姆椒ㄓ?jì)算出評(píng)分值Q，那么只需要找出一個(gè)合適的行動(dòng)a使得Q的值為最大，這樣就可以確定最優(yōu)行動(dòng)策略。Q學(xué)習(xí)算法Q表實(shí)際上就是狀態(tài)、動(dòng)作、與估計(jì)的未來(lái)獎(jiǎng)勵(lì)之間的映射表Q學(xué)習(xí)算法Q學(xué)習(xí)案例Q學(xué)習(xí)算法Q表數(shù)據(jù)Q學(xué)習(xí)算法獎(jiǎng)勵(lì)公式更新公式Q學(xué)習(xí)算法Q學(xué)習(xí)算法過(guò)程Q學(xué)習(xí)算法的基本過(guò)程如下：(1)設(shè)置參數(shù)γ，并初始化獎(jiǎng)勵(lì)矩陣R。(2)將Q表初始化為0。(3)For每一個(gè)過(guò)程隨機(jī)選擇一個(gè)初始狀態(tài) DoWhile(目標(biāo)狀態(tài)未達(dá)到)

從當(dāng)前狀態(tài)的所有可能的動(dòng)作中，選擇一個(gè)動(dòng)作

使用這一個(gè)動(dòng)作，達(dá)到下一個(gè)狀態(tài)

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

按獎(jiǎng)勵(lì)公式和更新公式計(jì)算Q值

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