人工智能導論：蒙特卡羅博弈方法

第8章蒙特卡羅博弈方法計算機博弈理論的研究希望計算機能夠像人一樣、思維、判斷和推理，并能夠做出理性的決策。棋類博弈由于規(guī)則明確、競技性高，且人類選手往往勝于計算機等原因，在計算機博弈理論的研究過程中一直受到重要關(guān)注和深入的探討，并促進了計算機博弈理論的發(fā)展。傳統(tǒng)的基于博弈樹搜索和靜態(tài)評估的博弈方法在國際象棋、中國象棋等棋類項目中獲得了明顯的成功，該類項目的盤面估計與博弈樹搜索過程相對獨立，棋子在盤面中的作用相對明確，且棋局中的專家規(guī)則相對較為容易概括和總結(jié)。然而傳統(tǒng)的博弈理論在計算機圍棋博弈中遇到了明顯的困難：圍棋具有巨大的搜索空間；盤面評估與博弈樹搜索緊密相關(guān)，只能通過對將來落子的可能性進行分析才能準確地確定棋子之間的關(guān)系；與此同時，高層次的圍棋知識也很難歸納，歸納之后常有例外，并且在手工構(gòu)建圍棋知識和規(guī)則的過程中常會出現(xiàn)矛盾而導致不一致性。這些獨特的因素為圍棋及擁有類似性質(zhì)的計算機博弈問題研究帶來了新的挑戰(zhàn)。從2006年開始，計算機圍棋博弈的相關(guān)研究有了跨越式的發(fā)展，基于蒙特卡羅模擬的博弈樹搜索算法獲得了重要的成功，并開始逐步引領(lǐng)計算機博弈理論研究的方向。在本章，我們將介紹蒙特卡羅博弈理論及其在圍棋等棋類博弈中的應(yīng)用。8.1基本概念8.1.1馬爾科夫決策過程馬爾科夫決策過程是序貫決策過程的主要研究領(lǐng)域之一，一個序貫決策過程包括以下幾點：所有的決策時刻點集；系統(tǒng)的所有可能的狀態(tài)集合；可以采用的全體行動集合；與狀態(tài)和行動相關(guān)聯(lián)的既得回報或費用集合；與狀態(tài)和行動相關(guān)聯(lián)的轉(zhuǎn)移概率的集合。一般來講，我們總認為決策者在開始做決策的時候這些量是已知的，在此基礎(chǔ)上，馬爾科夫決策過程是一類特殊的序貫決策問題，其特點是可采用的行動集、既得回報和轉(zhuǎn)移概率只是依賴于當前的狀態(tài)和選取的行動，而與過去的歷史無關(guān)。一個馬爾科夫決策過程的主要組成包括：決策周期、狀態(tài)、行動、轉(zhuǎn)移概率和報酬。作為決策者，所面對的問題根據(jù)系統(tǒng)的轉(zhuǎn)移概率抓住特定的機會，適時的做出一系列的行動或選擇，以期達到?jīng)Q策者心中的某種最優(yōu)化目標。由于受控制的系統(tǒng)在持續(xù)發(fā)展，過去的決策可以通過狀態(tài)的轉(zhuǎn)移影響到當前的決策，一般來講，當前一步的最優(yōu)選擇不一定是全局最優(yōu)的決策，必須要考慮系統(tǒng)在將來狀態(tài)上的預期機會和費用。決策時刻與決策周期選取行動的時間點被稱為決策時刻，并用T記錄所有決策時刻的點集。T是非負實直線上的子集，它可以是有限點集、可列無限點集或者是連續(xù)集合。在T為離散的情況下，決策都是在決策時刻做出的；而在T為連續(xù)集的情況下，系統(tǒng)可以連續(xù)的做決策，也可以在某些隨機點或某些事件發(fā)生時做決策，甚至由決策者選擇時機做出決策等。對于離散時間問題，兩個相鄰的決策時刻被稱為決策周期或者階段，我們把有限階段的決策時刻集記為T={0,1,2,…,N}，而把無限階段的決策時刻記為T={0,1,2,…}。狀態(tài)與行動集在每一個決策時刻上對系統(tǒng)的唯一描述符就是“狀態(tài)”，記博弈系統(tǒng)的所有可能狀態(tài)集合為S，S也被稱為“狀態(tài)空間”。如果在任一個決策時刻，決策者所觀察到的狀態(tài)為i∈S，則他可以在狀態(tài)i的可用行動集A(i)中選取行動a∈A(i)，其中A(i)也稱為當前狀態(tài)的“行動空間”。令：A=并且假設(shè)S和A(i)都不依賴于時刻t，狀態(tài)集合S和行動集合A(i)可以是任意的有限集合、可數(shù)的無限集合、有限維歐氏空間的緊致子集或者是完備可分度量空間上的博雷爾（Borel）子集，除非特別聲明，我們總考慮S和A(i)均為離散集的情況。行動的選取可以是確定性的選取一個，也可以在多個允許的行動中隨機性地選取。我們記P(A(i))為A(i)的博雷爾子集上的所有概率分布，記P(A)為A的博雷爾子集上的所有概率分布，隨機選取行動就是選取一個概率分布P(·)∈P(A(i))，其中，選取行動a∈A(i)的概率是P(a)，如果這個分布是退化的，則為確定性地選擇行動。轉(zhuǎn)移概率和報酬對于任意一個決策時刻，在狀態(tài)i采取行動a∈A(i)之后將產(chǎn)生兩個結(jié)果，一是決策者獲得報酬r(i,a)；二是下一個決策時刻系統(tǒng)所處的狀態(tài)將由概率分布P(·|i,a)決定。報酬r(i,a)是定義在i∈S和a∈A(i)上的實值函數(shù)，當r(i,a)為正值時，表示決策者所獲得的收入，當其為負值時，表示決策者所付出的費用。從模型的角度來看，報酬r(i,a)是即時的，但是在這個決策周期內(nèi)它是何時或如何獲得的并不重要，在選取行動后，模型只需知道它的值或期望值。實際上，報酬可以包括到下一個決策時刻的一次性收入、持續(xù)到下一階段的累積收入，或轉(zhuǎn)移到下一個狀態(tài)的隨機收入等。一般來講報酬還依賴下一個決策時刻的狀態(tài)j，即r(i,a,j)。此時，采取行動a的期望報酬值為：r上式中非負函數(shù)P(j|i,a)是下一個決策時刻系統(tǒng)轉(zhuǎn)移到狀態(tài)j的概率，函數(shù)P(·|i,a)被稱為轉(zhuǎn)移概率函數(shù)。需要注意的是，在一般的實際問題中，狀態(tài)轉(zhuǎn)移是可以發(fā)生在兩個決策時刻的中間的，但是在不影響決策的情況下，我們的模型依然適用。通常我們假設(shè)：j∈S我們把五重組{T,S,Ai,P·i,a,r(i,a)}稱為一個“馬爾科夫決策過程”，其轉(zhuǎn)移概率和報酬僅僅依賴于當前的狀態(tài)和決策者選取的行動，而不依賴于過去的歷史。8.1.2圍棋落子模型由于圍棋是一種策略性二人棋類游戲，棋手在相互對弈的過程中所下的每一步棋，都是經(jīng)過深思熟慮、精密決策的結(jié)果。在對弈時，棋手不僅要考慮當前所下棋子取得的效果，也要照顧到長遠的利益。同時，棋手在下棋的過程中只針對當前盤面進行決策，對于同樣的盤面，棋手不用去考慮其中經(jīng)歷的不同步驟?？梢哉f，棋手在下定一手棋后所能獲得的收益，只與當前棋盤的狀態(tài)和即將選取的行動有關(guān)，而與以往的歷史沒有關(guān)系。所以圍棋落子的過程應(yīng)被看成馬爾科夫決策過程。我們知道，馬爾科夫決策過程可以用五重族{T,S,Ai,P·i,a決策時刻T：顯然地，圍棋是一個有限階段的決策問題，在有限步對弈后，就能看到?jīng)Q策的結(jié)果。設(shè)一盤棋的總行棋步數(shù)為N，則在[1,N]的時間內(nèi)，黑白雙方交替進行決策。由于黑方先行，所以在奇數(shù)時刻黑方進行決策，而在偶數(shù)時刻白方進行決策。狀態(tài)空間S：記s=(Bm,Wn)為狀態(tài)，其中向量Bm=(pb1,pb2,…,pbm)描述了可用行動集A(s)：定義為在盤面s下的所有可落子點的集合，如果無任何可落子點，則As轉(zhuǎn)移概率P·s,a：在給定狀態(tài)和行動集（可落子點）下，轉(zhuǎn)移概率決定了每一個行動（選擇哪個落子點）被選擇的概率，原則上其定義方式?jīng)]有絕對限制，但是其定義與每個落子點的價值緊密相關(guān)。如前所述，圍棋中每一個落子的潛在價值較為難以估計，為轉(zhuǎn)移概率的定義帶來了一定的難度。P在該模型中，我們認為每一個可落子點被選中的概率是相等的，這樣的假設(shè)前提是下棋者完全沒有領(lǐng)域內(nèi)的經(jīng)驗知識。實際上，經(jīng)驗可以指導我們以更高的概率選擇更容易獲勝的點作為最終的行棋。但是，由于圍棋經(jīng)驗的好壞難以定量衡量，因此我們很難給出加入經(jīng)驗后各可行狀態(tài)的轉(zhuǎn)移概率。所以，我們在建立馬爾科夫決策模型時，只簡單的考慮從當前狀態(tài)等概地轉(zhuǎn)移到下一個可行狀態(tài)的情況。報酬：Rb表示到目前為止黑棋所占領(lǐng)地域的大小，Rw表示到目前為止白棋所占領(lǐng)地域的大小。圍棋落子模型是一類較特殊的馬爾科夫決策模型，因為在整個決策過程中所有的報酬并不累加為最后的總報酬，而只有最后一次決策后雙方獲得的報酬才是最后的總報酬，但這不影響決策時刻爭取較8.2蒙特卡羅方法及模擬評估理論蒙特卡羅算法以及基于蒙特卡羅隨機模擬的局面評估方法構(gòu)成了蒙特卡羅博弈理論的基礎(chǔ)。在本部分，我們將首先介紹蒙特卡羅算法，并以計算機圍棋博弈為例介紹其在計算機博弈系統(tǒng)中的具體應(yīng)用。8.2.1蒙特卡羅方法蒙特卡羅(Monte-Carlo)方法也稱為隨機模擬方法，有時也稱作隨機抽樣技術(shù)或統(tǒng)計試驗方法。它的基本思想是，為了求解數(shù)學、物理、工程技術(shù)以及生產(chǎn)管理等方面的問題，首先建立一個概率模型或隨機過程，使它的參數(shù)等于問題的解，然后通過對模型或過程的觀察或抽樣試驗來計算所求參數(shù)的統(tǒng)計特征，最后給出所求解的近似值。蒙特卡羅方法可以解決各種類型的問題，但總的來說，用蒙特卡羅方法處理的問題視其是否涉及隨機過程的性態(tài)和結(jié)果可以分為兩類：第一類是確定性的數(shù)學問題，用蒙特卡羅方法求解這類問題的步驟是，首先建立一個與所求解有關(guān)的概率模型，使所求的解就是我們所建立模型的概率分布或數(shù)學期望，然后對這個模型進行隨機抽樣觀察，即產(chǎn)生隨機變量，最后用其算術(shù)平均值作為所求解的近似估計值。計算多重積分、求解逆矩陣、解線性代數(shù)方程組、解積分方程、解某些偏微分方程的邊值問題和計算微分算子的特征值等都屬于這一類。第二類是隨機性問題的模擬，例如中子在介質(zhì)中的擴散等問題，這是因為中子在介質(zhì)內(nèi)部不僅受到某些確定性的影響，而且更多的是受到隨機性的影響。對于這類問題，雖然有時可表示為多重積分或某些函數(shù)方程，并進而可考慮用隨機抽樣方法求解，然而一般情況下都不采用這種間接模擬方法，而是采用直接模擬方法，即根據(jù)實際物理情況的概率法則，用電子計算機進行抽樣試驗。原子核物理問題、運籌學中的庫存問題、隨機服務(wù)系統(tǒng)中的排隊問題、動物的生態(tài)競爭和傳染病的蔓延等都屬于這一類。在應(yīng)用蒙特卡羅方法解決實際問題的過程中，往往需要重點考慮如下幾個方面的內(nèi)容：對求解的問題建立簡單而又便于實現(xiàn)的概率統(tǒng)計模型，使所求的解恰好是所建立模型的概率分布或數(shù)學期望；根據(jù)概率統(tǒng)計模型的特點和計算實踐的需要，盡量改進模型，以便減小方差和降低費用，提高計算效率；建立對隨機變量的抽樣方法，其中包括建立產(chǎn)生偽隨機數(shù)的方法和建立對所遇到的分布產(chǎn)生隨機變量的隨機抽樣方法；給出獲得所求解的統(tǒng)計估計值及其方差或標準誤差的方法。下面，我們將通過蒙特卡羅方法的幾個典型應(yīng)用對其有一個更深的理解。蒲豐投針問題1777年法國科學家蒲豐提出的一種計算圓周率π的方法，即隨機投針法，這就是著名的葡豐投針問題。這一方法的步驟是，取一張白紙，在上面畫上許多條間距為d的等距平行線，另取一根長度為l(l<d)的針，隨機地向畫有平行直線的紙上投擲n次，并觀察針與直線相交的次數(shù)，記為m。圖8.1蒲豐投針示意圖及其概率模型設(shè)針與平行線的夾角為φ，針的中點到平行線的最近距離為x，如圖8.1左所示，可知針與平行線相交的充要條件為x≤l2sinφ。另一方面，我們有0≤x≤d2和0≤φ≤π，從而全概率空間為x-φ平面上的一個矩形，如圖8.1P=在投針實驗中，針與平行線相交的頻率為P=mn，由P≈Pπ≈一維定積分的計算在單位正方形內(nèi)等概率隨機投點N次，其中第i次投點的坐標為(xi,yi)，如果投點滿足不等式y(tǒng)i≤f(xi)，即該點落在曲線y=f(x)用蒙特卡羅的語言來講，就是產(chǎn)生均勻隨機數(shù)ξ1,ξ2，如果ξ1≤f(ξ2)，則認為實驗成功，如果ξ1>f(ξ2)，則認為實驗失敗。設(shè)實驗成功的概率為II≈設(shè)隨機變量：η則有I=E[E從而：I=當抽樣點數(shù)為N時，使用此種方法所得近似解的統(tǒng)計誤差只與N有關(guān)（與1N8.2.2蒙特卡羅評估基于蒙特卡洛模擬的局勢評估方法，可以與傳統(tǒng)的靜態(tài)局面評估方法相比對。在計算機圍棋中，我們常常利用類似于一維定積分中的擲點法完成對圍棋盤面的評估。具體來講，當我們給定某一個棋盤局面時，算法在當前局面的所有可落子點中隨機選擇一個點擺上棋子，并不斷重復這個隨機選擇可落子點（擲點）的過程，直到雙方都沒有可下點（即對弈結(jié)束），再把這個最終狀態(tài)的勝負結(jié)果反饋回去，作為評估當前局面的依據(jù)。當然簡單的隨機擲點可以保證良好的隨機效果，但是由于隨機性很強會影響做出正確評估的收斂速度；特別地，由于圍棋的狀態(tài)空間非常巨大，我們所能搜索的是狀態(tài)空間的一個小部分，所以如果能在隨機策略中加入啟發(fā)式知識將加快收斂速度，因此，在隨機選點的過程中，一些策略也可被加入進來，并可以根據(jù)不同策略的緊要程度來排列這些策略在隨機過程中作用的先后順序，這些策略本身也可以根據(jù)其重要程度被賦予不同的隨機性。通過對蒙特卡羅評估的介紹我們可以發(fā)現(xiàn)，以蒙特卡羅方法為基礎(chǔ)的評估方式更加適用于圍棋博弈過程。靜態(tài)評估方法盡管可以達到一定的效果，但由于圍棋棋局情況相當復雜且規(guī)模龐大，單單采用一套固定的靜態(tài)的規(guī)則去覆蓋所有的情況必然會由于各種例外情況的出現(xiàn)而產(chǎn)生出各種不足。更為重要的是，圍棋規(guī)則的描述不可能非常的準確。圍棋中每個棋子的作用都差不多，而棋子的影響力更多的取決于它周圍的環(huán)境，以及該棋子連接或距離較近的己方棋子和對方棋子都是決定其影響力的因素，這使得圍棋中的很多情況甚至連職業(yè)棋手也很難精確的描述，而只能具體情況具體處理。另外，過度復雜的規(guī)則不僅會讓機器處理起來效率低下，而且也會超出人們對系統(tǒng)實際運行效果的理解程度。因此，對于圍棋、五子棋及類似棋類博弈游戲，蒙特卡洛評估相比于靜態(tài)評估方法具有明顯的優(yōu)勢。它通過對當前局面下的每個的可選點進行大量的模擬來得出相應(yīng)的勝負的統(tǒng)計特性，在簡單情況下，勝率較高的點就可以認為是較好的點予以選擇。8.3蒙特卡羅規(guī)劃蒙特卡羅規(guī)劃是解決馬爾科夫決策問題的有效方法之一，它是以蒙特卡羅方法的思想為基礎(chǔ)的一種規(guī)劃方法。在蒙特卡羅規(guī)劃中，可以將馬爾科夫決策過程中可能出現(xiàn)的狀態(tài)轉(zhuǎn)移過程用狀態(tài)樹建立并表示出來。不同于普通搜索樹的建立，蒙特卡羅規(guī)劃算法通過從初始狀態(tài)開始重復給出隨機模擬事件，并逐步擴展搜索樹中的每個節(jié)點，而每一次模擬事件都是“狀態(tài)-行為-回報”的三元序列。因此，相對于在評估之初就將（隱含）博弈樹進行展開的靜態(tài)方法而言，蒙特卡羅規(guī)劃的過程是一種動態(tài)的搜索過程，蒙特卡羅規(guī)劃的基本思想如圖8.2所示。圖8.2蒙特卡羅規(guī)劃過程示意在該過程中，算法首先根據(jù)一定的策略在搜索樹上選擇一個節(jié)點用于擴展，該策略被稱為搜索樹策略(TreePolicy)。該策略往往需要綜合考慮兩個方面的因素：一是對尚未充分了解的節(jié)點的探索(exploration)，以盡早發(fā)現(xiàn)潛在價值高的節(jié)點并盡早排除潛在價值低的節(jié)點；二是對當前有較大希望的節(jié)點的利用(exploitation)，以盡可能地抓住機會創(chuàng)造對己方更有利的局勢。當確定了擴展節(jié)點之后，算法以該節(jié)點為根進行大量的隨機模擬，并根據(jù)模擬的結(jié)果確定在該根節(jié)點下如何落子，并更新祖先節(jié)點的估計值，該策略一般稱為模擬策略或默認策略(DefaultPolicy)。在平凡情況下，算法在每一次模擬中從根節(jié)點的狀態(tài)開始，隨機地選擇一個落子點x進行落子，接下來不斷地交替隨機落子直至棋局結(jié)束，并根據(jù)結(jié)束時雙方的勝負狀態(tài)來確定當前狀態(tài)下落子點x的估計值。當完成大量的模擬之后，對每一種落子點的估計值將變得更為準確，算法以此來決定最終的落子，并向上依次更新祖先節(jié)點的估計值。更具體來講，蒙特卡羅規(guī)劃算法共包含四個基本步驟，分別為選擇(selection)、擴展(Expansion)、模擬(Simulation)和回溯(Backpropagation)，如圖8.3所示。圖中的每個節(jié)點表示博弈過程中的一個盤面狀態(tài)，每一條邊表示在父節(jié)點上采取一個行動，并得到子節(jié)點所對應(yīng)的狀態(tài)。這四個基本步驟依次執(zhí)行，從而完成一次搜索：圖8.3蒙特卡羅規(guī)劃算法的流程選擇：從根節(jié)點出發(fā)，在搜索樹上自上而下迭代式執(zhí)行一個子節(jié)點選擇策略，直至找到當前最為緊迫的可擴展節(jié)點為止，一個節(jié)點是可擴展的，當且僅當其所對應(yīng)的狀態(tài)是非停止狀態(tài)，且擁有未被訪問過的子狀態(tài)；擴展：根據(jù)當前可執(zhí)行的行動，向選定的節(jié)點上添加一個（或多個）子節(jié)點以擴展搜索樹；模擬：根據(jù)默認策略在擴展出來的一個（或多個）子節(jié)點上執(zhí)行蒙特卡羅棋局模擬，并確定節(jié)點的估計值；回溯：根據(jù)模擬結(jié)果向上依次更新祖先節(jié)點的估計值，并更新其狀態(tài)。算法算法1：蒙特卡羅規(guī)劃（MCTSapproach）functionMctsSearch(s0以狀態(tài)s0創(chuàng)建根節(jié)點vwhile尚未用完計算時長do:vl←TreePolicy(?←DefaultPolicy(s(vBackup(vlendwhilereturna(BestChild(v0算法1描述了蒙特卡羅規(guī)劃的偽代碼，在該算法中，節(jié)點v0是與初始狀態(tài)s0相對應(yīng)的根節(jié)點，s(v)表示節(jié)點v所對應(yīng)的狀態(tài)。算法首先從根節(jié)點開始調(diào)用搜索樹策略并返回該過程中所確定的待擴展節(jié)點vl及其對應(yīng)的狀態(tài)sl；接下來，算法從狀態(tài)sl開始調(diào)用默認策略進行隨機模擬，返回報酬?，并更新vl及祖先節(jié)點的估計值；算法最終采取行動a，并返回為根節(jié)點v0計算得到的最優(yōu)子節(jié)點BestChild(v采用蒙特卡洛規(guī)劃的一個重要原因是，它可以保證我們在從始至終的每一次隨機模擬中隨時得到行為的評價。因此，如果在模擬過程中某個狀態(tài)被再次訪問到，我們便可以利用之前的“行為-回報”信息來為接下來的選擇做參考，借此便可以加速評價的收斂速度。一方面，如果被重復訪問到的狀態(tài)很少，那么蒙特卡洛規(guī)劃就退化成非選擇性的蒙特卡洛方法；另一方面，如果被重復訪問到的后續(xù)狀態(tài)在很大程度上都集中在少數(shù)幾個狀態(tài)上，那么相對于其他算法而言，蒙特卡洛規(guī)劃則具有明顯的優(yōu)勢。具體到圍棋問題中，就是屬于上面談到的第二類情況，在每個當前狀態(tài)下，可選擇的點最多不超過361個，而這些可選點中基本可以找到一些明顯偏好的點。因此，當模擬次數(shù)達到幾萬次甚至幾十萬上百萬次的時候，在這些較好的點上必然會聚集大量的模擬。下面將以圍棋為例，給出一個蒙特卡羅規(guī)劃過程的示例性實現(xiàn)。當棋手面對一個待決策盤面時，他需要從多個可下點中選擇一個行棋，因此，如果我們有足夠的時間做模擬，則我們可以做以下的統(tǒng)計：設(shè)輪到一方進行決策時共有k個點可供選擇,第i個節(jié)點具有參數(shù)ni和wi，分別表示到該次模擬為止第i個節(jié)點被選中的次數(shù)，以及在其所對應(yīng)的這ni次模擬中第i當輪到算法給出落子時，我們將待決策的盤面作為某子樹的根節(jié)點，然后在可下點中隨機選擇一點pi,i∈[i,k]并如果該節(jié)點第一次被選中，即ni=0，則將填入該節(jié)點后的盤面作為葉節(jié)點加入搜索樹中并采用隨機投點的方式完成之后的行棋過程。在這一過程結(jié)束之后ni自動加1，如果模擬至終盤得到勝利的結(jié)果則wi加△（△為收益），如果終盤得到失敗的結(jié)果則wi減△。接著我們將葉節(jié)點的信息返回給上層節(jié)點，即讓其父節(jié)點的訪問次數(shù)加1，收益加上其子節(jié)點收益變化值的負值-△（這是因為父節(jié)點對應(yīng)于對方落子的情況）。如果父節(jié)點仍有父節(jié)點的話，則其父節(jié)訪問次數(shù)加1，獲得的收益加上其子節(jié)點收益變化值的負值--△，即△。依此類推，直至根節(jié)點為止如果該點不是第一次被選中，即ni≠0，亦即填入該節(jié)點后的盤面已作為葉節(jié)點加入搜索樹中，則我們以該盤面為子樹的根節(jié)點再一次執(zhí)行構(gòu)在模擬時間結(jié)束后，我們可以簡單地計算根節(jié)點的每個兒子可下點的模擬收益率：P而在k個可下點中收益率最高的可下點即為該次決策的結(jié)果。通過以上方法，就可以簡單的實現(xiàn)計算機圍棋博弈的選點落子過程。當然，這種解決過程因為蒙特卡羅規(guī)劃的收斂缺乏效率而并沒在計算機圍棋博弈中直接使用，我們在下一節(jié)將介紹以此為基礎(chǔ)的更加優(yōu)秀的算法。8.3UCB和UCT算法8.3.1多臂老虎機模型我們都知道賭場里有一種賭博機器名叫老虎機，當我們將賭注放入某個老虎機并拉動手臂后，就會出現(xiàn)或好或壞的收益結(jié)果。多臂老虎機擁有k個手臂，拉動每個手臂所能產(chǎn)生的回報互不相關(guān)，而賭博者的目的就是為了獲得盡可能多的收益，在多臂老虎機模型中也是如此，我們希望找到一個合理的策略，可以使得拉動手臂的人獲得最大的收益。賭博者要從這k個手臂中選擇一個手臂進行操作來獲得回報，這個回報可能為正值、0或者負值；每個手臂的回報所遵循的分布方式是不盡相同的，而拉動同一個手臂所獲得的回報滿足某一特定的分布；并且在某一個特定的時間段內(nèi)，賭博者只能拉動有限次數(shù)，而我們要做的就是在有限的拉動次數(shù)中找到一個策略，使得賭博者可以根據(jù)這個策略在規(guī)定的最后一次拉動中獲得盡可能大的回報?？梢韵胂?，在游戲開始之前所有的手臂對玩家來說都是等價的，若想知道哪個手臂最好，就需要不斷的去試探，并通過不斷的試探發(fā)現(xiàn)規(guī)律，以此來推斷出哪個手臂可能獲得最大的回報。由于玩家所擁有的試探次數(shù)是有限的，因此不得不在探索和利用間尋求一個平衡點，探索就是通過進行更多的試探以獲得更多的知識，這包括盡可能排除收益低的手臂和盡可能發(fā)現(xiàn)收益高的手臂，而利用則是充分利用當前己經(jīng)獲得的知識（對每個手臂所對應(yīng)的收益高低的判斷）獲得盡可能大的回報。該模型所蘊含的在搜索過程權(quán)衡探索和利用的基本思想是對蒙特卡羅規(guī)劃方法進行改進的核心內(nèi)容之一。在下面的內(nèi)容中，我們將介紹該思想下的兩個典型算法信心上限算法(UpperConfidenceBound,UCB)和信心上限樹算法(UpperConfidenceBoundsforTrees,UCT)，它們構(gòu)成了現(xiàn)代蒙特卡羅博弈理論的基礎(chǔ)算法。8.3.2UCB算法以上的多臂老虎機問題可以抽象為如下的數(shù)學模型：一個有k個臂的老虎機被一系列的隨機收益值所表示{X1t,X2t,…,Xit,…,Xkt}，其中1≤i≤k,t≥1。這里的i表示第解決多臂老虎機問題實際上就是選擇一個策略A去決定下一次將被拉動的手臂的編號，這個決策既取決于過去每個臂己經(jīng)被拉動的次數(shù)，也受限于這些被拉動的次數(shù)中每個手臂上取得的收益值。假設(shè)Tj(n)表示當總的拉動次數(shù)為n時，第j號手臂被拉動的次數(shù)，那么當進行n次拉動后根據(jù)當前策略A所ρ=n其中μ*表示收益最好的手臂的收益均值，μj為第j號手臂被拉動后所產(chǎn)生的收益均值。在Lai和Robbins的1985年的關(guān)于該問題的經(jīng)典文章中講到，對于某一特定的回報分布，E其中，當n→∞時，有oD(為在任一次嘗試中，手臂j的回報分布概率密度Pj和當前回報最高的手臂的概率密度P*之間的KL測度。因而在嘗試的次數(shù)（亦即隨機模擬的次數(shù)）足夠多時，最優(yōu)的手臂被拉動的次數(shù)和其它手臂被拉動的次數(shù)之間有較大的差距，具體而言，次優(yōu)的手臂j被拉動的次數(shù)E我們還可以把損失表示為:ρ=從這個公式我們可以看出，造成損失的原因是我們選取的策略不一定會每次都選擇收益最佳的臂。對于這樣的一大類收益分布問題，已經(jīng)證明沒有任何策略能讓損失的增長速度低于O(lnn)。對于這種收益分布，如果一個策略的損失增長速度不超過Cln(n)，其中C為一個常數(shù)，我們就UCB算法即信心上界算法，是一類解決多臂老虎機問題的算法的總稱，其中，我們將在本節(jié)介紹是UCB1算法是該類算法的代表，可以用如下偽碼表示：算法算法2：信心上限算法（UCB1）functionUCB1foreach手臂j:訪問該手臂并記錄收益endforwhile尚未達到訪問次數(shù)限制do:計算每個手臂的UCB1信心上界Ij訪問信心上界最大的手臂endwhileUCB1算法的核心在于解決繼續(xù)探索和利用當前狀態(tài)之間的平衡問題。它為所有臂記錄了平均收益Xi,Ti(t-1)，并選擇具有I這里的偏移序列ct,sc在Xi,t獨立同分布的條件下，偏移序列PP在搜索的過程中，UCB1被用來確定內(nèi)部節(jié)點將要選擇的下一個嘗試的行為，我們可以用更簡單具體的形式表示UCB1的信心上界索引：I其中，Xj是手臂j所獲得的回報的均值，n是到當前這一時刻為止所訪問的總次數(shù)，Tj(n)是手臂在UCB1算法中，當手臂數(shù)目k>1時，如果k個手臂的回報在[0,1]區(qū)間上分別服從分布P1,P2,…,Pk，8·其中Δj=μ*-μj，μi(1≤i≤k)分別為分布E觀察UCB1算法中上限信心索引的計算公式Ij=Xj+2ln?(n)Tj(n)，我們可以更加直觀的理解其兩部分8.3.3UCT算法雖然利用構(gòu)造蒙特卡羅規(guī)劃算法可以解決圍棋博弈問題，但是由于蒙特卡羅規(guī)劃方法在沒有知識的指導時樹的擴展層數(shù)較少，不利于最優(yōu)解的獲取，因此我們將UCB1算法加入蒙特卡羅規(guī)劃樹的構(gòu)建過程中，形成了我們即將要介紹的信心上限樹算法(UCT)。UCT算法是將UCB1算法思想用于蒙特卡羅規(guī)劃的特定算法，其與只利用蒙特卡羅方法構(gòu)建搜索樹的方法的主要區(qū)別如下：可落子點的選擇不是隨機的，而是根據(jù)UCB1的信心上界值進行選擇，如果可落子沒有被訪問，則其信心上限值為正無窮大，如果可落子點已經(jīng)被訪問過，則其信心上限索引值可以根據(jù)UCB1算法給出的值來確定。在實際應(yīng)用中，我們采用UCB1給出的信心上限值，當我們需要在眾多可下點中選取一個時，我們選擇信心上限值最大的那一個。當模擬結(jié)束后確定最終選擇結(jié)果時，我們不再僅僅根據(jù)勝率做出判斷，而是兼顧信心上限所給出的估計值。在實際應(yīng)用中，選擇方法也是多種多樣的，一些策略中選擇估計值最大的子節(jié)點為落子點，另外由于選擇可落子點進行訪問的過程已經(jīng)兼顧了極小極大算法的思想，所以在另外一些策略中也經(jīng)常直接選擇那個被訪問了最多次的可落子點，等等。UCT算法的基本過程可以用算法3中的偽代碼來描述，在該算法中，每一個節(jié)點v包含四項基本信息，分別為其所對應(yīng)的狀態(tài)s(v)，所對應(yīng)的來自父節(jié)點的行為a(v)，隨機模擬收益Q(v)（例如獲勝次數(shù)），以及在算法3所示的偽代碼中，最終將返回具有最高收益的子節(jié)點所對應(yīng)的行動，這是因為我們在返回值a(BestChild(v0,0))中將UCB1中的常數(shù)c設(shè)為0。在實際系統(tǒng)中，算法也經(jīng)?？梢灾苯臃祷卦L問次數(shù)最多的子節(jié)點所對應(yīng)的行動。需要指出的是，在實際系統(tǒng)中具有最高收益的子節(jié)點和訪問次數(shù)最多的子節(jié)點往往是同一個節(jié)點，但是這一點并不能保證。在基于蒙特卡羅博弈的圍棋博弈程序Erica中，算法在最高收益子節(jié)點和最多訪問子節(jié)點不一致時繼續(xù)進行博弈樹搜索，直至得到相同的結(jié)果。這一策略使Erica的勝率從47%提高到算法算法3：信心上限樹算法（UCT）functionUctSearch(s0以狀態(tài)s0創(chuàng)建根節(jié)點vwhile尚未用完計算時長do:vl←TreePolicy(?←DefaultPolicy(s(vlBackup(vl