信息安全技術(shù)研究中心-年-度-匯-報(bào)

時(shí)序差分學(xué)習(xí)在非完備信息

機(jī)器博弈中的應(yīng)用王軒許朝陽(yáng)哈爾濱工業(yè)大學(xué)深圳研究生院智能計(jì)算中心2007.10.3主要內(nèi)容非完備信息博弈簡(jiǎn)介12時(shí)序差分在四國(guó)軍旗中的應(yīng)用3時(shí)序差分學(xué)習(xí)算法介紹非完備信息博弈完備信息博弈（PerfectInformationGame）:中國(guó)象棋；圍棋；…非完備信息博弈（ImperfectInformation

Game）:四國(guó)軍棋；牌類游戲：紅心大戰(zhàn)，拱豬….….非完備信息博弈樹菱形表示隨機(jī)節(jié)點(diǎn)四國(guó)軍旗游戲蒙特卡羅抽樣根據(jù)前面的走步來(lái)更新棋子的概率表；根據(jù)更新后的棋子概率表，為棋盤上的每個(gè)棋子隨機(jī)選擇棋子的種類，得到一個(gè)完備信息棋局；對(duì)該完備信息棋局進(jìn)行MaxMin博弈樹搜索，找到一個(gè)最佳走步；多次重復(fù)上述過(guò)程，選擇選中次數(shù)最多的走步作為最終的最佳走步；概率表的建立根據(jù)112個(gè)經(jīng)典布局來(lái)設(shè)定各個(gè)棋子的概率表；根據(jù)走步結(jié)果來(lái)修改棋子的概率表；為棋盤上的每個(gè)棋子都建立各自的概率表；主要內(nèi)容

非完備信息博弈簡(jiǎn)介12時(shí)序差分在四國(guó)軍旗中的應(yīng)用3

時(shí)序差分學(xué)習(xí)算法介紹時(shí)序差分學(xué)習(xí)最早由Sutton提出；他證明時(shí)序差分學(xué)習(xí)可以和有監(jiān)督學(xué)習(xí)獲得同樣的結(jié)果而且占用更少的內(nèi)存，

收斂更快；TD最成功的應(yīng)用是Tesauro

根據(jù)時(shí)序差分編制的西洋雙陸棋

程序TDGammon，棋力可以和最好的人類棋手相媲美；TDGammon時(shí)序差分學(xué)習(xí)場(chǎng)景時(shí)序差分學(xué)習(xí)基本概念智能體（Agent）從外部環(huán)境（Environment）中讀取輸入（State），根據(jù)State來(lái)選擇采取哪個(gè)行動(dòng)（Action）；外部環(huán)境根據(jù)action的結(jié)果提供給智能體一個(gè)回報(bào)值（reward）；在一個(gè)階段結(jié)束之后，智能體根據(jù)回報(bào)值，采用某個(gè)學(xué)習(xí)算法（例如時(shí)序差分學(xué)習(xí)算法）來(lái)調(diào)整自己的行為；時(shí)序差分調(diào)整算法基本概念步數(shù)t

=

1，2，3，……表示到了第幾步；St

表示第t步時(shí)的棋盤狀態(tài)

；w是描述棋局狀態(tài)的一個(gè)向量，里面是描述棋局的各種參數(shù)（如各種棋子的基本值等）；rst表示在狀態(tài)St時(shí)采取某個(gè)走步所獲得的回報(bào)值；在游戲結(jié)束時(shí)的回報(bào)值rsn是確定的，比如1表示贏了，－1表示輸了，0表示和局；定義估值函數(shù)J（St

，w）來(lái)模擬逼近第t步時(shí)采取某個(gè)走步時(shí)的回報(bào)值rst；假設(shè)從游戲開始到結(jié)束經(jīng)歷了n步，則估值函數(shù)序列為：J（S1

，w）,J（S2，w）….J（Sn-1，w）,rsn;時(shí)序差分調(diào)整算法期望找到一個(gè)最佳向量w，使得估值函數(shù)J（S

，w）在棋局狀態(tài)S下能夠和真實(shí)回報(bào)值J*（S,w）之間的error最?。憾x在第t步的時(shí)序差分dt如下：最后的dN-1是實(shí)際的最終結(jié)果rsn和第n-1步預(yù)測(cè)之間的差值。在一輪游戲結(jié)束時(shí)，TD(λ)利用下面的公式來(lái)更新和調(diào)整參數(shù)向量w:時(shí)序差分公式其中是估值函數(shù)J在狀態(tài)St時(shí)關(guān)于參數(shù)向量w的偏導(dǎo)數(shù)，

α是一個(gè)0到1之間的一個(gè)正常數(shù)，控制了學(xué)習(xí)的速率；λ也是一個(gè)0到1之間的正常數(shù)，控制著時(shí)序差分更新時(shí)向前傳播的百分比；主要內(nèi)容

非完備信息博弈簡(jiǎn)介12

時(shí)序差分在四國(guó)軍旗中的應(yīng)用3時(shí)序差分學(xué)習(xí)算法介紹系統(tǒng)運(yùn)行界面系統(tǒng)基本架構(gòu)四國(guó)軍旗系統(tǒng)特點(diǎn)搜索空間巨大；非完備信息博弈，這里采用了蒙特卡羅抽樣技術(shù)來(lái)解決；搜索算法根據(jù)軍棋游戲的特點(diǎn)，使用了歷史啟發(fā)搜索算法，History

Heuristics；估值函數(shù)采用時(shí)序差分學(xué)習(xí)技術(shù)進(jìn)行優(yōu)化估值函數(shù)的優(yōu)化-時(shí)序差分估值函數(shù)是博弈程序的核心；原來(lái)的估值函數(shù)結(jié)構(gòu)簡(jiǎn)單，難以有效的描述棋局；時(shí)序差分定義了一系列的描述棋盤的參數(shù)，并通過(guò)不斷調(diào)整這些參數(shù)來(lái)逼近棋局的真實(shí)狀況；四國(guó)軍旗系統(tǒng)場(chǎng)景設(shè)計(jì)Agent是人工智能玩家；Environment外部環(huán)境是所有可能的棋局構(gòu)成的集合；State是當(dāng)前棋局；Action集合是在當(dāng)前棋局下所有合法的走步；回報(bào)值r在游戲結(jié)束時(shí)，有3個(gè)可能的值：1，－1，0。1表示贏了，－1表示輸了，0表示和局；游戲中間使用估值函數(shù)J來(lái)模擬逼近回報(bào)值r；四國(guó)軍旗中的時(shí)序差分在一局游戲結(jié)束時(shí)根據(jù)時(shí)序差分學(xué)習(xí)算法進(jìn)行調(diào)整；希望對(duì)從游戲開始到游戲結(jié)束所經(jīng)歷的每個(gè)棋局S，由估值函數(shù)J（S，w）所算出來(lái)的回報(bào)值和真實(shí)值J*之間的差值最??；例如，理想的回報(bào)值可能是這樣的：S1S2……SN-1SN0.900.920.981估值函數(shù)J（S，w）得到的結(jié)果可能是：S1S2……SN-10.30.50.8

這里期望通過(guò)調(diào)整w，可是使得在每個(gè)棋局狀態(tài)S，估值函數(shù)得到的結(jié)果都能夠非常接近理想回報(bào)值。時(shí)序差分調(diào)整過(guò)程對(duì)游戲過(guò)程中經(jīng)歷的每個(gè)狀態(tài)Si，

計(jì)算出J（Si，w），利用J來(lái)作為估值函數(shù)計(jì)算博弈樹搜索時(shí)博弈樹的各個(gè)葉節(jié)點(diǎn)的估值；對(duì)游戲所經(jīng)歷的各步，t＝1，2，3，…N-1,計(jì)算出時(shí)序差分：根據(jù)時(shí)序差分公式來(lái)更新參數(shù)向量w：參數(shù)向量w為了更準(zhǔn)確有效的描述棋盤狀態(tài)S，定義了下面幾組參數(shù)來(lái)構(gòu)成參數(shù)向量w：棋子基本值數(shù)組：如司令的基本值為500，炸彈為300，軍旗為1000等；棋子靈活性數(shù)組：如司令的靈活性為2.0，工兵的靈活性為0.8等；進(jìn)攻位置加分?jǐn)?shù)組：如在敵方軍旗附近的位置加分，行營(yíng)位置加分等；特殊組合得分：如炸彈－師長(zhǎng)對(duì)得分，三角雷得分等；威脅－保護(hù)比例：棋子受到威脅（或受到保護(hù)）時(shí)的減分（或加分）比例等；估值函數(shù)J可以看作是一個(gè)1×n的向量v和n×1的參數(shù)向量w的內(nèi)積；例如：N是（基本值數(shù)組的各個(gè)參數(shù)所對(duì)應(yīng)的系數(shù)，靈活性數(shù)組的各個(gè)參數(shù)所對(duì)應(yīng)的系數(shù)，…）,w是（基本值數(shù)組的各個(gè)參數(shù)，靈活性數(shù)組的各個(gè)參數(shù)，…），則J＝基本值數(shù)組的各個(gè)參數(shù)×基本值數(shù)組系數(shù)所對(duì)應(yīng)的系數(shù)

＋靈活性數(shù)組的各個(gè)參