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

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

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

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

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

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