人工智能導(dǎo)論蒙特卡洛搜索

1、第8章蒙特卡羅博弈方法計算機(jī)博弈理論的研究希望計算機(jī)能夠像人一樣、思維、判斷和推理，并能夠做出理性的決策。棋類博弈由于規(guī)則明確、競技性高，且人類選手往往勝于計算機(jī)等原因，在計算機(jī)博弈理論的研究過程中一直受到重要關(guān)注和深入的探討，并促進(jìn)了計算機(jī)博弈理論的發(fā)展。傳統(tǒng)的基于博弈樹搜索和靜態(tài)評估的博弈方法在國際象棋、中國象棋等棋類項目中獲得了明顯的成功，該類項目的盤面估計與博弈樹搜索過程相而獨立，棋子在盤面中的作用相對明確，且棋局中的專家規(guī)則相對較為容易概括和總結(jié)。然而傳統(tǒng)的博弈理論在計算機(jī)圍棋博弈中遇到了明顯的困難：國棋具右巨大的搜索空間：盤面評估與博弈樹搜索緊密相關(guān)，只能通過對將來落子的可能性進(jìn)行

2、分析才能準(zhǔn)確地確定棋子之間的關(guān)系；與此同時，高層次的圍棋知識也很難歸納，歸納之后常有例外，井且在手工構(gòu)建圍棋知識和規(guī)則的過程中常會出現(xiàn)矛盾而導(dǎo)致不一致性。這些獨特的因素為困棋及擁有類似性質(zhì)的計算機(jī)博弈問題研究帶來了新的挑戰(zhàn)。從2006年開始，計算機(jī)圍棋博弈的相關(guān)研究有了跨越式的發(fā)展，基于蒙特卡羅模擬的博弈樹搜索算法獲得了重要的成功，并開始逐步引領(lǐng)計算機(jī)博弈理論研究的方向。在本章，我們將介紹蒙特卡羅博弈理論及其在圍棋等棋類博弈中的應(yīng)用。8.1基本概念8. 1.1馬爾科夫決策過程馬爾科夫決策過程是序貫決策過程的主要研究領(lǐng)域之一，一個序貫決策過程包括以下幾點：1所有的決策時刻點集；2系統(tǒng)的所有可能的

3、狀態(tài)集合：3可以采用的全體行動集合：4與狀態(tài)和行動相關(guān)聯(lián)的既得回報或費用集合；5與狀態(tài)和行動相關(guān)聯(lián)的轉(zhuǎn)移概率的集合。一般來講，我們總認(rèn)為決策者在開始做決策的時候這些量是已知的,在此基礎(chǔ)上，馬爾科夫決策過程是一類特殊的序貫決策問題，其特點是可采用的行動集、既得回報和轉(zhuǎn)移概率只是依賴于當(dāng)前的狀態(tài)和選取的行動，而與過去的歷史無關(guān)。一個馬爾科夫決策過程的主要組成包括：決策周期、狀態(tài)、行動、轉(zhuǎn)移概率和報酬。作為決策苕，所面對的問題根據(jù)系統(tǒng)的轉(zhuǎn)移概率抓住特定的機(jī)會，適時的做出一系列的行動或選擇，以期達(dá)到?jīng)Q策者心中的某種最優(yōu)化目標(biāo)。由于受控制的系統(tǒng)在持續(xù)發(fā)展，過去的決策可以通過狀態(tài)的轉(zhuǎn)移影響到當(dāng)前的決策，一

4、般來講，當(dāng)前一步的最優(yōu)選擇不一定是全局最優(yōu)的決策，必須要考慮系統(tǒng)在將來狀態(tài)上的預(yù)期機(jī)會和費用。決策時刻與決策周期選取行動的時間點被稱為決策時刻，并用T記錄所有決策時刻的點集。丁是非負(fù)實直線上的子集，它可以是有限點集、可列無限點集或者是連續(xù)集合。在了為離散的情況下，決策都是在決策時刻做出的；而在丁為連續(xù)集的情況下，系統(tǒng)可以連續(xù)的做決策，也可以在某些隨機(jī)點或某些事件發(fā)生時做決策，甚至由決策者選擇時機(jī)做出決策等。對于離散時間問題，兩個相鄰的決策時刻被稱為決策周期或者階段，我們把有限階段的決策時刻集記為7=0,1,2，,N),而把無限階段的決策時刻記為T=0,1,2,狀態(tài)與行動集在每一個決策時刻上對系

5、統(tǒng)的唯一描述符就是“狀態(tài)”，記博弈系統(tǒng)的所有可能狀態(tài)集合為s,S也被稱為“狀態(tài)空間:如果在任一個決策時刻，決策者所觀察到的狀態(tài)為iES,則他可以在狀態(tài)i的可用行動集4(i)中選取行動QC4，其中做i)也稱為當(dāng)前狀態(tài)的“行動空間”。令：4=Uiws(。并且假設(shè)S和i)都不依賴于時刻3狀態(tài)集合S和行動集合4(i)可以是任意的行限集合、可數(shù)的無限集合、行限維歐氏空間的緊致子集或者是完備可分度量空間上的博雷爾(Borel)子集，除非特別聲明，我們總考慮S和4均為離散集的情況。行動的選取可以是確定性的選取一個，也可以在多個允許的行動中隨機(jī)性地選取。我們記尸伊)為4(。的博雷爾子集上的所有概率分布，記尸Q

6、4)為4的博雷爾子集上的所有概率分布，隨機(jī)選取行動就是選取一個概率分布尸()0(4(。)，其中，選取行動QE/1的概率是P(a),如果這個分布是退化的，則為確定性地選擇行動。轉(zhuǎn)移概率和報酬對于任意一個決策時刻，在狀態(tài)i采取行動aE4(i)之后將產(chǎn)生兩個結(jié)果，一是決策者獲得報酬lr(i,a)：二是卜.一個決策時刻系統(tǒng)所處的狀態(tài)將由概率分布P(|i,a)決定。報酬r(i,a)是定義在iES和QW/(i)上的實值函數(shù)，當(dāng)r(i,a)為正值時，表示決策者所獲得的收入，當(dāng)其為負(fù)值時，表示決策者所付出的費用。從模型的角度來看,報酬r(i,a)是即時的，但是在這個決策周期內(nèi)它是何時或如何獲得的并不重要，在選

7、取行動后，模型只需知道它的值或期望值。實際上，報酬可以包括到卜.一個決策時刻的一次性收入、持續(xù)到下一階段的累積收入，或轉(zhuǎn)移到下一個狀態(tài)的隨機(jī)收入等。一般來講報酬還依賴卜.一個決策時刻的狀態(tài)j,即此時，采取行動Q的期望報酬值為：jws上式中非負(fù)函數(shù)P0|i,a)是下一個決策時刻系統(tǒng)轉(zhuǎn)移到狀態(tài)j的概率，函數(shù)P(|i,a)被稱為轉(zhuǎn)移概率函數(shù)。需要注意的是，在一般的實際問題中，狀態(tài)轉(zhuǎn)移是可以發(fā)生在兩個決策時刻的中間的，但是在不影響決策的情況卜.，我們的模型依然適用。通常我們假設(shè)：VP01i，a)=l我們把五重組T,S,4(i),P(|i,a),r(i,a)稱為一個“馬爾科夫決策過程”，其轉(zhuǎn)移概率和報酬

8、僅僅依賴于當(dāng)前的狀態(tài)和決策者選取的行動，而不依賴于過去的歷史。這里我們把包括了最優(yōu)準(zhǔn)則的馬爾科夫決策過程稱為“馬爾科夫決策問題”。8.1.2圍棋落子模型由于圍棋是一種策略性二人棋類游戲，棋手在相互對弈的過程中所卜的每一步棋，都是經(jīng)過深思熟慮、精密決策的結(jié)果。在對弈時，棋手不僅要考慮當(dāng)前所下根子取得的效果，也要照顧到長遠(yuǎn)的利益。同時，棋手在下棋的過程中只針對當(dāng)前盤面進(jìn)行決策，對于同樣的盤面，棋手不用去考慮其中經(jīng)歷的不同步驟。可以說，棋手在下定一手棋后所能獲得的收益，只與當(dāng)前棋盤的狀態(tài)和即將選取的行動有關(guān)，而與以往的歷史沒有關(guān)系。所以圍棋落子的過程應(yīng)被看成馬爾科夫決策過程。我們知道，馬爾科夫決策過

9、程可以用五重族U，S,4(i),P(Ji,a),r(i,a)表示，圍棋落子過程也不例外：決策時刻T：顯然地，圍棋是一個有限階段的決策問題，在有限步對弈后，就能看到小不的加只汝君出的啟/橫工，數(shù)為N,則LN的時同內(nèi)，貨白9萬交皆進(jìn)行決策。由于黑方先行，所以在奇數(shù)時刻黑方進(jìn)行決策，而在偶數(shù)時刻白方進(jìn)行決策。狀態(tài)空間S：記s=(8(m),W(n)為狀態(tài),其中向量8(m)=伽比邛麻，,Pbm)描述了到目前為止盤面上所有黑棋的位置，向量W(n)=(pwl,pw2，,尺n)描述了到目前為止盤面上所有白棋的位置。從前面的解釋我們可以知道，圍棋的狀態(tài)空間S是相當(dāng)大的。可用行動集4(s)：定義為在盤面s卜的所有

10、可落子點的集合，如果無任何可落子點，貝必(s)=0。轉(zhuǎn)移概率P(|s,a)：在給定狀態(tài)和行動集(可落子點)下，轉(zhuǎn)移概率決定了每一個行動(選擇哪個落子點)被選擇的概率，原則上其定義方式?jīng)]有絕對限制，但是其定義與每個落子點的價值緊密相關(guān)。如前所述，圍棋中每一個落子的潛在價值較為難以估計，為轉(zhuǎn)移概率的定義帶來了一定的難度。簡單地，我們可以定義如下的等概率模型：(1,如果(s)=0.即沒有任何可落子點P(-|S,Q)=1-，如果M(s)|=M,即有M個可落子點在該模型中，我們認(rèn)為每一個可落子點被選中的概率是相等的，這樣的假設(shè)前提是下根苕完全沒有領(lǐng)域內(nèi)的經(jīng)驗知識。實際上，經(jīng)驗可以指導(dǎo)我們以更高的概率選擇

11、更容易獲勝的點作為最終的行棋。但是，由于圍棋經(jīng)臉的好壞難以定量衡量，因此我們很難給出加入經(jīng)驗后各可行狀態(tài)的轉(zhuǎn)移概率。所以，我們在建立馬爾科夫決策模型時，只簡單的考慮從當(dāng)前狀態(tài)等概地轉(zhuǎn)移到下一個可行狀態(tài)的情況。報酬：凡表示到目前為止黑棋所占領(lǐng)地域的大小，段,表示到目前為止白棋所占領(lǐng)地域的大小。闈棋落子模型是一類較特殊的馬爾科夫決策模型，因為在整個決策過程中所有的報酬并不累加為最后的總報酬，而只有最后一次決策后雙方獲得的報酬才是最后的總報酬，但這不影響決策時刻爭取較高報酬的重要性。8.2蒙特卡羅方法及模擬評估理論蒙特卡羅算法以及基于蒙特卡羅隨機(jī)模擬的局面評估方法構(gòu)成了蒙特卡羅博弈理論的基礎(chǔ)。在本部

12、分，我們將首先介紹蒙特卡羅算法，并以計算機(jī)圍棋博弈為例介紹其在計算機(jī)博弈系統(tǒng)中的具體應(yīng)用。8.2.1蒙特卡羅方法蒙特卡羅(Monte-Carlo)方法也稱為隨機(jī)模擬方法，行時也稱作隨機(jī)抽樣技術(shù)或統(tǒng)計試驗方法。它的基本思想是，為了求解數(shù)學(xué)、物理、工程技術(shù)以及生產(chǎn)管理等方面的問題，首先建立一個概率模型或隨機(jī)過程，使它的參數(shù)等于問題的解，然后通過對模型或過程的觀察或抽樣試驗來計算所求參數(shù)的統(tǒng)計特征，最后給出所求解的近似值。蒙特卡羅方法可以解決各種類型的問題，但總的來說，用蒙特卡羅方法處理的問題視其是否涉及隨機(jī)過程的性態(tài)和結(jié)果可以分為兩類：第一類是確定性的數(shù)學(xué)問題，用蒙特卡羅方法求解這類問題的步驟是，

13、首先建立一個與所求解有關(guān)的概率模型，使所求的解就是我們所建立模型的概率分布或數(shù)學(xué)期望，然后對這個模型進(jìn)行隨機(jī)抽樣觀察，即產(chǎn)生隨機(jī)變量，最后用其算術(shù)平均值作為所求解的近似估計值。計算多重積分、求解逆矩陣、解線性代數(shù)方程組、解積分方程、解某些偏微分方程的邊值問題和計算微分算子的特征值等都屬于這類。第二類是隨機(jī)性問題的模擬，例如中子在介質(zhì)中的擴(kuò)散等問題，這是因為中子在介質(zhì)內(nèi)部不僅受到某些確定性的影響，而且更多的是受到隨機(jī)性的影響。對于這類問題，雖然有時可表示為多重積分或某些函數(shù)方程，并進(jìn)而可考慮用隨機(jī)抽樣方法求解，然而一般情況下都不采用這種間接模擬方法，而是采用直接模擬方法，即根據(jù)實際物理情況的概率

14、法則，用電子計算機(jī)進(jìn)行抽樣試臉。原子核物理問，題、運籌學(xué)中的庫存問題、隨機(jī)服務(wù)系統(tǒng)中的排隊問題、動物的生態(tài)競爭和傳染病的芨延等都屬于這一類。在應(yīng)用蒙特卡羅方法解決實際問題的過程中，往往需要重點考慮如下幾個方面的內(nèi)容：1 對求解的問題建立簡單而又便于實現(xiàn)的概率統(tǒng)計模型，使所求的解恰好是所建立模型的概率分布或數(shù)學(xué)期望；2 根據(jù)概率統(tǒng)計模型的特點和計算實踐的需要，盡最改進(jìn)模型，以便減小方差和降低費用，提高計算效率；3 建立對隨機(jī)變量的抽樣方法，其中包括建立產(chǎn)生偽隨機(jī)數(shù)的方法和建立對所遇到的分布產(chǎn)生隨機(jī)變量的隨機(jī)抽樣方法；4 給出獲得所求解的統(tǒng)計估計值及其方差或標(biāo)準(zhǔn)誤差的方法。卜面，我們將通過蒙特卡羅

15、方法的幾個典型應(yīng)用對其有一個更深的理解。蒲豐投針問題1777年法國科學(xué)家蒲豐提出的一種計算圓周率7T的方法，即隨機(jī)投針法，這就是著名的林豐投針問題。這一方法的步驟是，取一張白紙，在上面畫上許多條間距為d的等距平行線，另取一根長度為3vd）的針，隨機(jī)地向畫有平行直線的紙上投擲71次，并觀察針與直線相交的次數(shù)，記為血。圖81蒲豐投針示意圖及其概率模型設(shè)針與平行線的夾角為W,針的中點到平行線的最近距離為x，如圖81左所示.可知針與平行線相交的充要條件為另一方面，我們有OWxW(和Q(p/62)，則認(rèn)為實驗失敗。設(shè)實驗成功的概率為人若在N次試臉中有次成功，則比值提給出/的一個無偏估計值：nIaN設(shè)隨機(jī)

16、變量：限&，62)=則有/=4(612)，而與此同時:=/廣皈4/e)延1延2JqJq%2)假=廣01。fMdx從而:f1nI=）QfMdXN當(dāng)抽樣點數(shù)為N時，使用此種方法所得近似解的統(tǒng)計誤差只與N有關(guān)（與之正相7N關(guān)），不隨枳分維數(shù)的改變而改變。因此當(dāng)枳分維度較高時，蒙特卡羅方法相對于其他數(shù)值解法更優(yōu)。8.2.2蒙特卡羅評估基于蒙特卡洛模擬的局勢評估方法，可以與傳統(tǒng)的靜態(tài)局面評估方法相比對。在計算機(jī)用棋中，我們常常利用類似于一維定積分中的擲點法完成對圍棋盤面的評估。具體來講，當(dāng)我們給定某一個棋盤局面時，算法在當(dāng)前局面的所有可落子點中隨機(jī)選擇一個點攜上棋子，并不斷重復(fù)這個隨機(jī)選擇可落子點（擲點

17、）的過程，直到雙方都沒有可下點（即對弈結(jié)束），再把這個最終狀態(tài)的勝負(fù)結(jié)果反饋回去，作為評估當(dāng)前局面的依據(jù)。當(dāng)然簡單的隨機(jī)擲點可以保證良好的隨機(jī)效果，但是由于隨機(jī)性很強會影響做出正確評估的收斂速度：特別地，由于圍棋的狀態(tài)空間非常巨大，我們所能搜索的是狀態(tài)空間的一個小部分，所以如果能在隨機(jī)策略中加入啟發(fā)式知識將加快收斂速度，因此，在隨機(jī)選點的過程中，一些策略也可被加入進(jìn)來，并可以根據(jù)不同策略的緊要程度來排列這些策略在隨機(jī)過程中作用的先后順序，這些策略本身也可以根據(jù)其重要程度被賦予不同的隨機(jī)性。通過對蒙特卡羅評估的介紹我們可以發(fā)現(xiàn)，以蒙特卡羅方法為基礎(chǔ)的評估方式更加適用丁圍棋博弈過程。靜態(tài)評估方法盡

18、管可以達(dá)到一定的效果，但由丁陽根棋局情況相當(dāng)復(fù)雜且規(guī)模龐大，單單采用一套固定的靜態(tài)的規(guī)則去覆蓋所行的情況必然會由于各種例外情況的出現(xiàn)而產(chǎn)生出各種不足。更為重要的是，圍棋規(guī)則的描述不可能非常的準(zhǔn)確。圍棋中每個棋子的作用都差不多，而棋子的影響力更多的取決于它周圍的環(huán)境，以及該棋子連接或距離較近的己方棋子和對方棋子都是決定其影響力的因索，這使得圍棋中的很多情況甚至連職業(yè)棋手也很難精確的描述，而只能具體情況具體處理。另外，過度復(fù)雜的規(guī)則不僅會讓機(jī)器處理起來效率低卜.，而且也會超出人們對系統(tǒng)實際運行效果的理解程度。因此，對于圍棋、五子棋及類似棋類博弈游戲，蒙特卡洛評估相比于靜態(tài)評估方法具有明顯的優(yōu)勢。它

19、通過對當(dāng)前局面卜的每個的可選點進(jìn)行大最的模擬來得出相應(yīng)的勝負(fù)的統(tǒng)計特性，在簡單情況卜.，勝率較高的點就可以認(rèn)為是較好的點予以選擇。8. 3蒙特卡羅規(guī)劃蒙特卡羅規(guī)劃是解決馬爾科夫決策問題的有效方法之一，它是以蒙特卡羅方法的思想為基礎(chǔ)的一種規(guī)劃方法。在蒙特卡羅規(guī)劃中，可以將馬爾科夫決策過程中可能出現(xiàn)的狀態(tài)轉(zhuǎn)移過程用狀態(tài)樹建立并表示出來。不同于普通搜索樹的建立，蒙特卡羅規(guī)劃算法通過從初始狀態(tài)開始重復(fù)給出隨機(jī)模擬空件，并逐步擴(kuò)展搜索樹中的每個節(jié)點，而每一次模擬事件都是“狀態(tài)-行為-回報”的三元序列。因此，相對于在評估之初就將(6急含)博弈樹進(jìn)行展開的靜態(tài)方法而言，蒙特卡羅規(guī)劃的過程是一種動態(tài)的搜索過程

20、，蒙特卡羅規(guī)劃的基本思想如圖8.2所示。圖82蒙特卡羅規(guī)劃過程示意在該過程中，算法首先根據(jù)一定的策略在搜索樹上選擇一個節(jié)點用于擴(kuò)展，該策略被稱為搜索樹策略QreePolicy)。該策略往往需要綜合考慮兩個方面的因索：一是對尚未充分了解的節(jié)點的探索(exploration),以盡早發(fā)現(xiàn)潛在價值高的節(jié)點并盡早排除潛在價值低的節(jié)點：二是時當(dāng)前有較大希望的節(jié)點的利用(exploitation),以盡可能地抓住機(jī)會創(chuàng)造對己方更有利的局勢。當(dāng)確定了擴(kuò)展節(jié)點之后，算法以該節(jié)點為根進(jìn)行大量的隨機(jī)模擬，并根據(jù)模擬的結(jié)果確定在該根節(jié)點下如何落子，并更新祖先節(jié)點的估計值，該策略一般稱為模擬策略或默認(rèn)策略efault

21、Policy)。在平凡情況下，算法在每一次模擬中從根節(jié)點的狀態(tài)開始，隨機(jī)地選擇一個落子點x進(jìn)行落子，接下來不斷地交替隨機(jī)落子直至棋局結(jié)束，并根據(jù)結(jié)束時雙方的勝負(fù)狀態(tài)來確定當(dāng)前狀態(tài)下落子點%的估計值。當(dāng)完成大量的模擬之后，對每一種落子點的估計值將變得更為準(zhǔn)確，算法以此來決定最終的落子，并向上依次更新祖先節(jié)點的估計值。更具體來講，蒙特卡羅規(guī)劃算法共包含四個基本步驟，分別為選擇(selection)、擴(kuò)展(Expansion)、模擬(Simulation)和回溯(JBackpropagation),如圖83所示。圖中的每個節(jié)點表示博弈過程中的一個盤面狀態(tài)，每一條邊表示在父節(jié)點上采取一個行動,并得到子

22、節(jié)點所對應(yīng)的狀態(tài)。這四個基本步驟依次執(zhí)行，從而完成一次搜索：1選擇：從根節(jié)點出發(fā)，在搜索樹上自上而卜迭代式執(zhí)行一個子節(jié)點選擇策略，直至找到當(dāng)前最為緊迫的可擴(kuò)展節(jié)點為止，一個節(jié)點是可擴(kuò)展的，當(dāng)且僅當(dāng)其所時應(yīng)的狀態(tài)是非停止?fàn)顟B(tài)，且擁有未被訪問過的子狀態(tài)；2 .擴(kuò)展：根據(jù)當(dāng)前可執(zhí)行的行動，向選定的節(jié)點上添加一個（或多個）子節(jié)點以擴(kuò)展搜索樹；3 .模擬：根據(jù)默認(rèn)策略在擴(kuò)展出來的一個（或多個）子節(jié)點上執(zhí)行蒙特卡羅棋局模擬，并確定節(jié)點的估計值：4回溯：根據(jù)模擬結(jié)果向上依次更新祖先節(jié)點的估計值，并更新其狀態(tài)。算法1：蒙特卡羅規(guī)劃(MCTSapproach)functionMCTSSEARCH(s0)以狀態(tài)S

23、o創(chuàng)建根節(jié)點為,while尚未用完計算時長doVi-TREEPOLICY(v0),AdefaultpolicysOD),BACKUPg),endwhilereturna(BESTCHILD(Vo),算法1描述了蒙特卡羅規(guī)劃的偽代碼，在該算法中，節(jié)點火是與初始狀態(tài)So相對應(yīng)的根節(jié)點，s(u)表示節(jié)點口所對應(yīng)的狀態(tài)。算法首先從根節(jié)點開始調(diào)用搜索樹策略并返回該過程中所確定的待擴(kuò)展節(jié)點及其對應(yīng)的狀態(tài)斗：接卜.來，算法從狀態(tài)演開始調(diào)用默認(rèn)策略進(jìn)行隨機(jī)模擬，返回報酬A,并更新力及祖先節(jié)點的估計值：算法最終采取行動Q，并返回為根節(jié)點火計算得到的最優(yōu)子節(jié)點BESTCHILD(V0),當(dāng)然，這里的“最優(yōu)”與博弈

24、的具體情況和算法的具體實現(xiàn)有關(guān)。采用蒙特卡洛規(guī)劃的一個重要原因是，它可以保證我們在從始至終的每一次隨機(jī)模擬中隨時得到行為的評價。因此，如果在模擬過程中某個狀態(tài)被再次訪問到，我們便可以利用之前的“行為-回報”信息來為接下來的選擇做參考，借此便可以加速評價的收斂速度。一方面，如果被重發(fā)訪問到的狀態(tài)很少，那么蒙特卡洛規(guī)劃就退化成非選擇性的蒙特卡洛方法；另一方面，如果被重復(fù)訪問到的后續(xù)狀態(tài)在很大程度上都集中在少數(shù)幾個狀態(tài)上，那么相對于其他算法而言，蒙特卡洛規(guī)劃則具有明顯的優(yōu)勢。具體到闈棋問題中，就是屬于上面談到的第二類情況，在每個當(dāng)前狀態(tài)下，可選擇的點最多不超過361個，而這些可選點中基本可以找到一些

25、明顯偏好的點。因此，當(dāng)模擬次數(shù)達(dá)到幾萬次甚至幾十萬上百萬次的時候，在這些較好的點上必然會聚集大量的模擬。下面將以闈棋為例，給出一個蒙特卡羅規(guī)劃過程的示例性實現(xiàn)。當(dāng)棋手面對一個待決策盤面時，他需要從多個可下點中選擇一個行棋，因此，如果我們行足夠的時間做模擬，則我們可以做以卜.的統(tǒng)計：設(shè)輪到一方進(jìn)行決策時共有k個點可供選擇，第i個節(jié)點具有參數(shù)珥和叫，分別表示到該次模擬為止第i個節(jié)點被選中的次數(shù)，以及在其所對應(yīng)的這/次模擬中第i個節(jié)點獲得勝利的次數(shù)。當(dāng)輪到算法給出落子時，我們將待決策的盤面作為某子樹的根節(jié)點，然后在可下點中隨機(jī)選擇一點Pi，iCi,k并進(jìn)行以下模擬過程：1 如果該節(jié)點第一次被選中，即

26、吃=0，則將填入該節(jié)點后的盤面作為葉節(jié)點加入搜索樹中并采用隨機(jī)投點的方式完成之后的行棋過程。在這一過程結(jié)束之后他自動加1.如果模擬至終盤得到勝利的結(jié)果則叫加(為收益)，如果終盤得到失敗的結(jié)果則叫減接著我們將葉節(jié)點的信息返回給上層節(jié)點，即讓其父節(jié)點的訪問次數(shù)加1,收益加上其子節(jié)點收益變化值的負(fù)值-(這是因為父節(jié)點對應(yīng)于對方落子的情況)。如果父節(jié)點仍有父節(jié)點的話，則其父節(jié)訪問次數(shù)加1，獲得的收益加上其子節(jié)點收益變化值的負(fù)值即依此類推，直至根節(jié)點為止，該次模擬結(jié)束并進(jìn)行新一次的模擬；2 .如果該點不是第一次被選中，即小0,亦即填入該節(jié)點后的盤面已作為葉節(jié)點加入搜索樹中，則我們以該盤面為子樹的根節(jié)點再

27、一次執(zhí)行構(gòu)建搜索樹的過程。在模擬時間結(jié)束后，我們可以簡單地計算根節(jié)點的每個兒子可卜點的模擬收益率：P(win)=ni而在k個可卜點中收益率最高的可卜點即為該次決策的結(jié)果。通過以上方法，就可以簡單的實現(xiàn)計算機(jī)圍棋博弈的選點落子過程。當(dāng)然，這種解決過程因為蒙特卡羅規(guī)劃的收斂缺乏效率而并沒在計算機(jī)圍棋博弈中直接使用，我們在卜.一節(jié)將介紹以此為基礎(chǔ)的更加優(yōu)秀的算法。8.3UCB和UCT算法8.3.1多臂老虎機(jī)模型我們都知道好場里行-種賭博機(jī)器名叫老虎機(jī)，當(dāng)我們將賭注放入某個老虎機(jī)并拉動手臂后，就會出現(xiàn)或好或壞的收益結(jié)果。多臂老虎機(jī)擁有k個手臂，拉動每個手臂所能產(chǎn)生的回報互不相關(guān)，而賭博者的目的就是為了

28、獲得盡可能多的收益，在多臂老虎機(jī)模型中也是如此，我們希望找到一個合理的策略，可以使得拉動手臂的人獲得最大的收益。賭博者要從這k個手臂中選擇一個手臂進(jìn)行操作來獲得回報，這個回報可能為正值、?；蛘哓?fù)值；每個手臂的回報所遵循的分布方式是不盡相同的，而拉動同一個手臂所獲得的回報滿足某一特定的分布：并且在某一個特定的時間段內(nèi)，賭博者只能拉動有限次數(shù)，而我們要做的就是在有限的拉動次數(shù)中找到一個策略，使得賭博者可以根據(jù)這個策略在規(guī)定的最后一次拉動中獲得盡可能大的回報?？梢韵胂?，在游戲開始之前所有的手臂對玩家來說都是等價的，若想知道哪個手臂最好，就需要不斷的去試探，并通過不斷的試探發(fā)現(xiàn)規(guī)律，以此來推斷出哪個手

29、臂可能獲得最大的回報。由于玩家所擁有的試探次數(shù)是有限的，因此不得不在探索和利用間尋求一個平衡點，探索就是通過進(jìn)行更*的試探以獲得更多的知識，這包括盡可能排除收益低的手臂和盡可能發(fā)現(xiàn)收益高的手臂，而利用則是充分利用當(dāng)前已經(jīng)獲得的知識(對每個手臂所對應(yīng)的收益高低的判斷)獲得盡可能大的回報。該模型所蘊含的在搜索過程權(quán)衡探索和利用的基本思想是對蒙特卡羅規(guī)劃方法進(jìn)行改進(jìn)的核心內(nèi)容之一。在卜面的內(nèi)容中，我們將介紹該思想卜.的兩個典型算法信心上限算法(UpperConfidenceBound,UCB)和信心上限樹算法(UpperConfidenceBoundsforTrees,UCT),它們構(gòu)成現(xiàn)代蒙特卡羅

30、博弈理論的基礎(chǔ)算法。8.3.2UCB算法以上的多臂老虎機(jī)問題可以抽象為如卜的數(shù)學(xué)模型：一個有k個臂的老虎機(jī)被一系列的隨機(jī)收益值所表示Xit，X2t，.，Mr，.,Xn,其中1i1.這里的i表示第i個臂的編號，拉動第i個臂，所得到的回報序列為Mi，X23,，旦不同的手臂的收益分布之間沒有相互關(guān)系。解決多臂老虎機(jī)問題實際上就是選擇一個策略4去決定卜一次將被拉動的手臂的編號，這個決策既取決于過去每個臂已經(jīng)被拉動的次數(shù)，也受限于這些被拉動的次數(shù)中每個手臂上取得的收益值。假設(shè)756）表示當(dāng)總的拉動次數(shù)為n時，第，號手臂被拉動的次數(shù)，那么當(dāng)進(jìn)行n次拉動后根據(jù)當(dāng)前策略4所產(chǎn)生的損失可以表示為：P=-ETj(

31、n)nj其中表示收益最好的手臂的收益均值，勺為第j號手臂被拉動后所產(chǎn)生的收益均值。在Lai和Robbins的1985年的關(guān)于該問題的經(jīng)典文章中講到，對于某一特定的回報分布，拉動策略滿足：瓦弓-。（甲門）+0（1）其中，當(dāng)？IT8時，右O（l）-0,并且：dI|p）=J吶*為在任一次嘗試中，手-臂j的回報分布概率密度號和當(dāng)前歸I報最高的手臂的概率密度P*之間的KL測度。因而在嘗試的次數(shù)（亦即隨機(jī)模擬的次數(shù)）足夠多時，最優(yōu)的手臂被拉動的次數(shù)和其它手臂被拉動的次數(shù)之間有較大的差距，具體而言，次優(yōu)的手臂j被拉動的次數(shù)滿足：我們還可以把損失表示為-Et=it=i從這個公式我們可以看出，造成損失的原因是我

32、們選取的策略不一定會每次都選擇收益最佳的臂。對于這樣的一大類收益分布問題，已經(jīng)證明沒有任何策略能讓損失的增長速度低于o（inS）。對于這種收益分布，如果一個策略的損失增長速度不超過cm（），其中c為一個常數(shù)，我們就認(rèn)為它在探索和利用之間找到了一個平衡方法。UCB算法即信心上界算法，是一類解決多臂老虎機(jī)問題的算法的總稱，其中,我們將在本節(jié)介紹是UCB1算法是該類算法的代表，可以用如下偽碼表示：算法2：信心上限算法（UCB1）functionUCB1foreachF臂j:訪問該手臂并記錄收益endforwhile尚未達(dá)到訪問次數(shù)限制do計算每個手臂的UCB1信心上界4（如下所述）訪問信心上界最大的

33、手臂endwhileUCB1算法的核心在于解決繼續(xù)探索和利用當(dāng)前狀態(tài)之間的平衡問題。它為所有臂記錄了平均收益并選擇具有最大置信上界的臂：A=argmaxiq殳兄r（1）+c.uki）這里的偏移序列定義為：在獨立同分布的條件卜，偏移序列Cy滿足如卜的概率收斂不等式：P（兄出+”）廣4P區(qū)5._一%）廠在搜索的過程中，UCB1被用來確定內(nèi)部節(jié)點將要選擇的卜.一個嘗試的行為,我們可以用更簡單具體的形式表示UCB1的信心上界索引:其中，為是手臂j所獲得的回報的均值,21n劭）今是到當(dāng)前這一時刻為止所訪問的總次數(shù)，弓何）是手臂j到目前為止總共所訪問的次數(shù)。在UCB1算法中，當(dāng)手臂數(shù)目kl時，如果k個手臂

34、的回報在0,1區(qū)間上分別服從分布PP2，,Pk，那么當(dāng)總共拉動次手臂之后，該算法的損失不超過以下上限:其中4=一%，出(1WiWk)分別為分布R的數(shù)學(xué)期望，”為出(IWiWk)中的最大值。此外，次優(yōu)手臂j的訪問次數(shù)的數(shù)學(xué)期型滿足以下上限：r18噌卜硒麗觀察UCB1算法中上限信心索引的計算公科=與+腭需，我們可以更加直觀的理解其兩部分的含義，其中前一部分用就是對到目前為止已經(jīng)搜集到的知識的價值，而后一部分則可以看作是尚未充分探索過的節(jié)點需要繼續(xù)探索的必要性。8. 3.3UCT算法雖然利用構(gòu)造蒙特卡羅規(guī)劃算法可以解決圍棋博弈問題，但是由于蒙特卡羅規(guī)劃方法在沒有知識的指導(dǎo)時樹的擴(kuò)展層數(shù)較少，不利于最

35、優(yōu)解的獲取，因此我們將UCB1算法加入蒙特卡羅規(guī)劃樹的構(gòu)建過程中，形成了我們即將要介紹的信心上限樹算法(UCT)。UCT算法是將UCB1算法思想用于蒙特卡羅規(guī)劃的特定算法，其與只利用蒙特卡羅方法構(gòu)建搜索樹的方法的主要區(qū)別如下：1 可落子點的選擇不是隨機(jī)的，而是根據(jù)UCB1的信心上界值進(jìn)行選擇，如果可落子沒有被訪問，則其信心上限值為正無窮大，如果可落子點已經(jīng)被訪問過，則其信心上限索引值可以根據(jù)UCB1算法給出的值來確定。在實際應(yīng)用中，我們采用UCB1給出的信心上限值，當(dāng)我們需要在眾多可下點中選取一個時，我們選擇信心上限值最大的那一個。2 當(dāng)模擬結(jié)束后確定最終選擇結(jié)果時，我們不再僅僅根據(jù)勝率做出判斷，而是兼顧信心上限所給出的估計值。在實際應(yīng)用中，選擇方法也是多種多樣的，一些策略中選擇估計值最大的子節(jié)點為落子點，另外由于選擇可落子點進(jìn)行訪問的過程已經(jīng)兼顧了極小極大算法的思想，所以在另外一些策略中也經(jīng)常直接選擇那個被訪問了最多次的可落子點，等等。UCT算法的基本過程可以用算法3中的偽代碼來描述，在該算法中，每一個節(jié)點D包含四項基本信息，分別為其所對應(yīng)的狀態(tài)s)，所對應(yīng)的來自父節(jié)點的行為a(v),隨機(jī)模擬收益Q(u)(例如獲勝次數(shù))，以及節(jié)點的被訪問次數(shù)N)。在算法3所示的偽代碼中，最終將返回具有最高收益的子節(jié)