人工智能導(dǎo)論：蒙特卡羅博弈方法

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