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

1、時(shí)序差分學(xué)習(xí)在非完備信息機(jī)器博弈中的應(yīng)用,王軒 許朝陽哈爾濱工業(yè)大學(xué)深圳研究生院智能計(jì)算中心2007.10.3,主要內(nèi)容,時(shí)序差分學(xué)習(xí)算法介紹,非完備信息博弈,完備信息博弈（Perfect Information Game ）:中國象棋；圍棋；…非完備信息博弈（Imperfect Information Game ）:四國軍棋；牌類游戲：紅心大戰(zhàn)，拱豬….….,非完備信息博弈樹,菱形表示隨機(jī)節(jié)點(diǎn),,四國軍旗

2、游戲,,蒙特卡羅抽樣,,,,,根據(jù)前面的走步來更新棋子的概率表；根據(jù)更新后的棋子概率表，為棋盤上的 每個(gè)棋子隨機(jī)選擇棋子的種類，得到一個(gè) 完備信息棋局；對(duì)該完備信息棋局進(jìn)行MaxMin博弈樹搜索， 找到一個(gè)最佳走步；多次重復(fù)上述過程，選擇選中次數(shù)最多的走步 作為最終的最佳走步；,概率表的建立,,,,,根據(jù)112個(gè)經(jīng)典布局來設(shè)定各個(gè)棋子的概率表；根據(jù)走步結(jié)果來修改棋子的概率表；為棋盤上的每個(gè)棋子都建立各自的概率

3、表；,主要內(nèi)容,時(shí)序差分學(xué)習(xí)算法介紹,時(shí)序差分學(xué)習(xí),最早由Sutton提出 ；他證明時(shí)序差分學(xué)習(xí)可以和有監(jiān)督學(xué)習(xí) 獲得同樣的結(jié)果而且占用更少的內(nèi)存， 收斂更快；TD最成功的應(yīng)用是Tesauro 根據(jù)時(shí)序差分編制的西洋雙陸棋 程序TDGammon，棋力可以和最好的人類棋手相媲美；,TD Gammon,,時(shí)序差分學(xué)習(xí)場景,,時(shí)序差分學(xué)習(xí)基本概念,智能體（Agent）從外部環(huán)境（Environmen

4、t）中讀取輸入（State），根據(jù)State來選擇采取哪個(gè)行動(dòng)（Action）；外部環(huán)境根據(jù)action的結(jié)果提供給智能體一個(gè)回報(bào)值（reward）；在一個(gè)階段結(jié)束之后，智能體根據(jù)回報(bào)值，采用某個(gè)學(xué)習(xí)算法（例如時(shí)序差分學(xué)習(xí)算法）來調(diào)整自己的行為；,時(shí)序差分調(diào)整算法基本概念,步數(shù) t = 1，2，3，……表示到了第幾步；St 表示第t步時(shí)的棋盤狀態(tài) ；w是描述棋局狀態(tài)的一個(gè)向量，里面是描述棋局的各種參數(shù)（如各種棋子的基本值等

5、）；rst表示在狀態(tài)St時(shí)采取某個(gè)走步所獲得的回報(bào)值；在游戲結(jié)束時(shí)的 回報(bào)值rsn是確定的，比如1表示贏了，－1表示輸了 ，0表示和局；定義估值函數(shù)J（ St ，w）來模擬逼近第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ù)

6、 J（S ，w）在棋局狀態(tài)S下能夠和真實(shí)回報(bào)值J*（ S, w ）之間的error最小 ：定義在第t步的時(shí)序差分dt如下：最后的dN-1是實(shí)際的最終結(jié)果rsn和第n-1步預(yù)測之間的差值。在一輪游戲結(jié)束時(shí)，TD (λ)利用下面的公式來更新和調(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í)的速率；

7、λ也是一個(gè)0到1之間的正常數(shù)，控制著時(shí)序差分更新時(shí)向前傳播的 百分比；,主要內(nèi)容,時(shí)序差分學(xué)習(xí)算法介紹,系統(tǒng)運(yùn)行界面,,系統(tǒng)基本架構(gòu),,,四國軍旗系統(tǒng)特點(diǎn),搜索空間巨大；非完備信息博弈，這里采用了蒙特卡羅抽樣技術(shù)來解決；搜索算法根據(jù)軍棋游戲的特點(diǎn)，使用了歷史啟發(fā)搜索算法，History Heuristics；估值函數(shù)采用時(shí)序差分學(xué)習(xí)技術(shù)進(jìn)行優(yōu)化,估值函數(shù)的優(yōu)化-時(shí)序差分,估值函數(shù)是博弈程序的核心；原來的估值函數(shù)結(jié)構(gòu)簡單

8、，難以有效的描述棋局；時(shí)序差分定義了一系列的描述棋盤的參數(shù)，并通過不斷調(diào)整這些參數(shù)來逼近棋局的真實(shí)狀況；,四國軍旗系統(tǒ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來模擬逼近回報(bào)值r；,四國軍旗

9、中的時(shí)序差分,在一局游戲結(jié)束時(shí)根據(jù)時(shí)序差分學(xué)習(xí)算法進(jìn)行調(diào)整；希望對(duì)從游戲開始到游戲結(jié)束所經(jīng)歷的每個(gè)棋局S，由估值函數(shù) J（S，w）所算出來的回報(bào)值和真實(shí)值J*之間的 差值最??；例如，理想的回報(bào)值可能是這樣的： S1 S2 …… SN-1 SN 0.90 0.92

10、 0.98 1 估值函數(shù)J（S，w）得到的結(jié)果可能是： S1 S2 …… SN-1 0.3 0.5 0.8 這里期望通過調(diào)

11、整w，可是使得在每個(gè)棋局狀態(tài)S，估值函數(shù)得到的結(jié)果都能夠非常接近理想回報(bào)值。,時(shí)序差分調(diào)整過程,對(duì)游戲過程中經(jīng)歷的每個(gè)狀態(tài)Si， 計(jì)算出 J（ Si ，w），利用J來作為估值函數(shù)計(jì)算博弈樹搜索時(shí)博弈樹的各個(gè)葉節(jié)點(diǎn)的估值；對(duì)游戲所經(jīng)歷的各步，t＝1，2，3，…N-1,計(jì)算出時(shí)序差分：根據(jù)時(shí)序差分公式來更新參數(shù)向量w：,參數(shù)向量w,為了更準(zhǔn)確有效的描述棋盤狀態(tài)S，定義了下面幾組參數(shù)來構(gòu)成參數(shù)向量w：棋子基本值數(shù)組：如司令的基本

12、值為500，炸彈為300，軍旗為1000等；棋子靈活性數(shù)組：如司令的靈活性為2.0，工兵的靈活性為0.8等；進(jìn)攻位置加分?jǐn)?shù)組：如在敵方軍旗附近的位置加分，行營位置加分等；特殊組合得分：如炸彈－師長對(duì)得分，三角雷得分等；威脅－保護(hù)比例：棋子受到威脅（或受到保護(hù)）時(shí)的減分（或加分）比例等；,估值函數(shù)J,可以看作是一個(gè)1×n的向量v和n×1的參數(shù)向量w的內(nèi)積； 例如： N是（基本值數(shù)組的各個(gè)參數(shù)

13、所對(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è)參數(shù)×靈活性數(shù)組參數(shù)所對(duì)應(yīng)的系數(shù) ＋ ……. J對(duì)w是處處可導(dǎo)的，滿足時(shí)序差分的條件；,有待改進(jìn)的地方,學(xué)習(xí)過程較為緩慢；能夠精確有效描述棋局的各種