時序差分學習在非完備信息

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

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

非完備信息博弈簡介12時序差分在四國軍旗中的應用3

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

收斂更快；TD最成功的應用是Tesauro

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

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

=

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

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

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

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

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

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

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

非完備信息博弈簡介12

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

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

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

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

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