近年來機(jī)器博弈受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注,機(jī)器博弈領(lǐng)域的研究也取得了令人矚目的成績(jī),例如Deep Mind的Alphago擊敗頂尖圍棋選手、CMU的多人德?lián)渲悄荏wPluribus擊敗頂級(jí)牌手以及Open AI的Open AI Five擊敗Dota職業(yè)隊(duì)伍。機(jī)器博弈相關(guān)技術(shù)也正被應(yīng)用于很多實(shí)際場(chǎng)景中,例如智能交通、智能推薦、多輪對(duì)話、量化交易等。根據(jù)參與者是否完全掌握博弈局面的所有信息可以把機(jī)器博弈分為完備信息博弈和非完備信息博弈�，F(xiàn)實(shí)場(chǎng)景中的諸多決策問題都可以建模成非完備信息博弈中的策略求解問題,但目前的機(jī)器博弈算法需要對(duì)問題的狀態(tài)空間進(jìn)行抽象,在高維動(dòng)作空間中表現(xiàn)不佳,且通常僅適用于二人博弈。因此研究能夠應(yīng)用于復(fù)雜狀態(tài)空間、支持連續(xù)動(dòng)作、適用于多人博弈的非完備信息博弈策略求解算法具有重大意義。本文在虛擬自我對(duì)局的算法框架下,結(jié)合深度強(qiáng)化學(xué)習(xí)、多智能體強(qiáng)化學(xué)習(xí)、蒙特卡洛樹搜索等技術(shù)來解決策略優(yōu)化問題,以德州撲克和炸彈人為實(shí)驗(yàn)平臺(tái),研究二人和多人博弈問題中的策略求解。針對(duì)復(fù)雜博弈問題通常需要利用先驗(yàn)知識(shí)進(jìn)行狀態(tài)空間抽象的問題,本文提出了利用深度強(qiáng)化學(xué)習(xí)和自適應(yīng)的蒙特卡洛搜索樹算法來求解... 

【文章來源】：哈爾濱工業(yè)大學(xué)黑龍江省 211工程院校 985工程院校

【文章頁(yè)數(shù)】：61 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

擴(kuò)展形式的博弈樹

哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文弈游戲結(jié)束。（4）回溯（Backpropagation）：遞歸地向上訪問父節(jié)點(diǎn)，并更新當(dāng)前節(jié)點(diǎn)的統(tǒng)計(jì)信息。MCTS的搜索過程可以歸納為兩種不同的策略，如圖2-2所示，一種是樹策略(TreePolicy),即是從搜索樹中已經(jīng)包含的節(jié)點(diǎn)中選擇或創(chuàng)建葉節(jié)點(diǎn)(選擇和擴(kuò)展)。第二種是默認(rèn)策略（DefaultPolicy），根據(jù)默認(rèn)策略進(jìn)行博弈直至博弈終端節(jié)點(diǎn)返回模擬結(jié)果。Alphogo中的快速走子策略就是第二種的默認(rèn)策略。一旦樹搜索中斷或達(dá)到預(yù)設(shè)的計(jì)算時(shí)間，搜索就會(huì)終止，并且通過某種機(jī)制在根節(jié)點(diǎn)t0處選擇動(dòng)作a。Schadd[48]根據(jù)Chaslot等人[49]的工作，描述了選擇最優(yōu)子節(jié)點(diǎn)的四種方法：（1）Maxchild：選擇收益最多的子節(jié)點(diǎn)。（2）Robustchild：選擇訪問次數(shù)最多的子節(jié)點(diǎn)。（3）Max-Robustchild:選擇訪問次數(shù)和收益均為最多的子節(jié)點(diǎn)，如果不存在則繼續(xù)蒙特卡洛樹搜索，直到達(dá)到可接受的訪問次數(shù)為止。（4）Securechild：選擇最大化置信區(qū)間下界的子節(jié)點(diǎn)。圖2-2蒙特卡洛樹搜索2.3.2置信上界樹搜索MCTS的目標(biāo)是近似當(dāng)前狀態(tài)可采取動(dòng)作的真實(shí)博弈收益，這是通過迭代構(gòu)建部分搜索樹來實(shí)現(xiàn)的，而如何構(gòu)建樹取決于樹策略。置信上界樹搜索算法(UpperConfidenceBoundforTrees,UCT)是備受關(guān)注的蒙特卡洛樹搜索算法，因?yàn)閁CT算法可用來解決MCTS中的“探索和利用”問題，探索就是指對(duì)未訪問節(jié)點(diǎn)的選擇，利用則是指對(duì)迭代過程中的已知?dú)v史信息的利用，UCT算法就是在蒙特卡洛樹搜索的子節(jié)點(diǎn)選擇階段采用了UCB算法。Kocsis[50]提出了利用上限置信區(qū)間(UpperConfidenceBounds,用UCB)來實(shí)現(xiàn)樹搜索，通過蒙特卡洛模擬來近似子節(jié)點(diǎn)的預(yù)期獎(jiǎng)勵(lì)。UCB具有簡(jiǎn)單高效的優(yōu)點(diǎn)，且可以保證在遺憾增長(zhǎng)的情況下保持最優(yōu)界限在一個(gè)恒定范圍內(nèi)，可以將迭代中選擇子節(jié)點(diǎn)?

哈爾濱工業(yè)大學(xué)工程碩士學(xué)位論文Rainbow表現(xiàn)優(yōu)異[57]。圖2-3DQN算法框架2.4.3策略梯度策略梯度算法直接優(yōu)化智能體的行為策略，相較于值迭代方法，通常具有更好的收斂性，在高維或連續(xù)動(dòng)作空間中有效，并且可以學(xué)習(xí)隨機(jī)策略。隨機(jī)策略在博弈中比較重要，因?yàn)榭梢员苊獗粚?duì)手過利用。對(duì)于可微策略，只要它不為零，就可以解析地計(jì)算策略梯度。Sutton[58]指出對(duì)于可微策略，其策略梯度可以表示為：Eπθ[θlogπ(a|s;θ)Qπθ(s,a)](2-15)策略梯度的前一項(xiàng)可以理解為一個(gè)描述智能體策略的方向向量，描述的是參數(shù)的更新方向，第二項(xiàng)則是一個(gè)標(biāo)量，用來估計(jì)行動(dòng)軌跡的預(yù)期收益Q值，相當(dāng)于是對(duì)策略的評(píng)價(jià)項(xiàng)，因此結(jié)合前后兩項(xiàng)策略梯度可以理解為通過降低低收益軌跡的出現(xiàn)概率，以及增加高收益軌跡的概率來實(shí)現(xiàn)策略的參數(shù)更新。策略梯度的第二項(xiàng)可以采用六種評(píng)價(jià)函數(shù)。傳統(tǒng)的策略梯度算法則是采取軌跡總收益、動(dòng)作收益以及引入基線的動(dòng)作收益來作為評(píng)估指標(biāo)，這三種方法因?yàn)槭侵苯討?yīng)用軌跡的真實(shí)獎(jiǎng)勵(lì)，類似蒙特卡洛的思想，因此不存在偏差，但是多步軌跡會(huì)導(dǎo)致樣本數(shù)據(jù)方差大。而后文講到的結(jié)合值迭代的策略梯度算法則是通過值函數(shù)來評(píng)估策略，可以直接利用Q函數(shù)來評(píng)價(jià)�；蛘咭胍粋�(gè)狀態(tài)值函數(shù)來作為基線獎(jiǎng)勵(lì)從而引出優(yōu)勢(shì)函數(shù)來評(píng)估智能體策略：A(at,st)=Q(at,st)V(st)(2-16)其中Q(at表示動(dòng)作值函數(shù)，V(st表示狀態(tài)值函數(shù)。此外，還可以利用狀態(tài)值函數(shù)-16-

【參考文獻(xiàn)】：
碩士論文
[1]基于狀態(tài)抽象和殘局解算的二人非限制性德州撲克策略的研究[D]. 胡開亮.哈爾濱工業(yè)大學(xué) 2017



本文編號(hào)：3437806