機器自學習博弈策略研究與實現(xiàn).pdf

1、人工智能是近年來很活躍的研究領域之一。機器學習和博弈是人工智能研究的重要分支。國內(nèi)外對博弈的研究已經(jīng)較為廣泛,特別是IBM的國際象棋程序“深藍”,已經(jīng)達到了人類的世界冠軍水平。但是這些程序或者需要經(jīng)過大量訓練,或者采用死記硬背的學習方法,或者是采用大規(guī)模搜索算法實現(xiàn),難以避免“組合爆炸”的危機,因此,一個真正“智能”的,有學習能力的高效率的博弈策略還有待進一步研究。
　　本文將TD(Temporal Difference)預測與B

2、P神經(jīng)網(wǎng)絡相結合,得到一種用于博弈的強化學習法,以博弈中常用的極小極大搜索法和NegeScout搜索法為基礎,并應用它實現(xiàn)了一個能自學習的五子棋博弈程序。該方法克服了使用靜態(tài)估值函數(shù)的不足,實踐證明,該方法是成功的,使用該方法的程序經(jīng)過較短時間的訓練后達到了較好的下棋水平。
　　本文首先研究了五子棋在計算機中的表示問題,討論了計算機中存貯棋局和識別下棋次序,局勢狀態(tài)變化及局勢特征的等方法。其次研究了博弈樹的極小極大搜索技術及在此基

3、礎上的α-β剪枝過程和剪枝優(yōu)化問題。實現(xiàn)將候選的后繼節(jié)點按位置鄰近順序排序,使剪枝過程得到優(yōu)化。此外還研究了α-β剪枝的改進算法NegeScout算法,此算法首先采用一小的有限α-β窗口,以確定實際估計值的范圍,再在這個較小的范圍中搜索實際的估計值。由于在較小的范圍中搜索,效率能得以提高。再次,根據(jù)五子棋的特點,提取棋局局勢的若干特征,對這些特征賦加權分,并對整個棋局進行特征統(tǒng)計,采用一個線性函數(shù)求得棋局的總估計分值。實踐中,采用極小極

4、大搜索加此靜態(tài)估值技術的初版程序,達到了比初學者強的水平,一些比較熟練的業(yè)余人員時常也會負于此程序。采用固定的估值法,估值的不準確使其“智力”較低,而且固定的賦值方式使其不能通過學習提高。因此我們繼續(xù)研究,利用強化學習法(Reiforcement Learning)設計了第二版本,具有自學習功能的五子棋程序。TD即瞬時差異預測法是指在一個對局中相鄰兩個時刻的局面的形勢判斷差值,如果這個形勢判斷函數(shù)比較準確,則這個差(即瞬時差異)應該接近

5、于0,即用后一局面的估計分值作為前一局面的實際可能估計分值。
　　本文中采用將TD預測法與BP神經(jīng)網(wǎng)絡相結合,采用三層BP神經(jīng)網(wǎng)絡結構來設計一非線性估值函數(shù),將不同棋局特征的數(shù)目加入神經(jīng)網(wǎng)絡的輸入端,輸出端輸出對局勢的估計分值。學習過程中,按照TD預測法原理,計算網(wǎng)絡誤差,利用BP神經(jīng)網(wǎng)絡誤差傳播法,在對弈過程中,不斷調(diào)整神經(jīng)網(wǎng)絡的權值,使其網(wǎng)絡估值準確度在學習中逐步改善,提高程序的下棋水平。針對BP神經(jīng)網(wǎng)絡收斂速度慢,本文還采用