基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的西洋跳棋評(píng)估算法

丁錦鈺

（洛陽(yáng)市第一高級(jí)中學(xué)，河南洛陽(yáng)，471000）

0 引言

計(jì)算機(jī)博弈被認(rèn)為是人工智能最富挑戰(zhàn)性的研究方向之一。2007年，8×8棋盤的西洋跳棋（英國(guó)跳棋）已被破解，而目前10×10棋盤的西洋跳棋由于搜索空間和評(píng)估因素的復(fù)雜性顯著增大，還有待破解。西洋跳棋[2]是一種雙人棋盤游戲，10×10棋盤的西洋跳棋由雙方各20枚棋子組成，放置于各自陣營(yíng)的底部?jī)尚?，由黑方先走，且?guī)定棋子只能向左前或右前方兩個(gè)方向行進(jìn)，如果要“吃子”，需保證敵方棋子的左前方和右前方?jīng)]有棋子。若本方棋子走到對(duì)方陣營(yíng)的“底線”，便可“成王”（王棋）。王棋在“吃子”時(shí)，必須“連吃”，直到無子可“吃”為止，而普通棋只能“吃子”一次。

計(jì)算機(jī)博弈系統(tǒng)中，搜索深度、評(píng)估因素等均影響著博弈系統(tǒng)的智能化。其中，評(píng)估函數(shù)是重要影響因素之一。本文通過對(duì)常用的評(píng)估算法—靜態(tài)估值和遺傳算法的分析，提出了基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的西洋跳棋評(píng)估算法。目前該算法已廣泛應(yīng)用于五子棋、圍棋等，但還較少應(yīng)用在10×10棋盤的西洋跳棋博弈系統(tǒng)中。

1 現(xiàn)有的西洋跳棋博弈系統(tǒng)評(píng)估算法

1.1 靜態(tài)估值

靜態(tài)估值[4][5]通過對(duì)影響棋局狀態(tài)的因素進(jìn)行人為的加權(quán)量化，得出局面評(píng)估值，其評(píng)估公式如下：

其中，y是最終要得到的局面評(píng)估值，iω為各個(gè)評(píng)估因素所占的權(quán)重，xi是影響棋局狀態(tài)的評(píng)估因素，如棋子的類型、棋子在棋局中的位置、棋子的位置關(guān)系等。

1.2 遺傳算法

遺傳算法是一種模擬進(jìn)化過程的隨機(jī)搜索方法。采用遺傳算法進(jìn)行局面評(píng)估的西洋跳棋博弈系統(tǒng)[2]的初始權(quán)值是隨機(jī)產(chǎn)生的，之后會(huì)通過篩選得出最優(yōu)的權(quán)值組合。為了實(shí)現(xiàn)參數(shù)自動(dòng)調(diào)整，提高訓(xùn)練效率，在調(diào)整權(quán)值的過程中可采用監(jiān)督學(xué)習(xí)（如最小均方算法LMS），根據(jù)實(shí)際值和期望

其中，為調(diào)整后的權(quán)值結(jié)果，nω為目前的權(quán)值，η為學(xué)習(xí)效率，表示權(quán)重調(diào)整的幅度，Dn是監(jiān)督學(xué)習(xí)中的目標(biāo)權(quán)值。然而，這種權(quán)值調(diào)整方法會(huì)使得收斂速度和平穩(wěn)誤差不能同時(shí)滿足，有一定局限性。

采用遺傳算法作為西洋跳棋博弈系統(tǒng)的評(píng)估算法，可以使該系統(tǒng)實(shí)現(xiàn)自主學(xué)習(xí)，但其隨機(jī)性太強(qiáng)，以致訓(xùn)練效率較慢。值之間的誤差來進(jìn)行迭代調(diào)整，直至結(jié)果最優(yōu)。其權(quán)重調(diào)整公式可總結(jié)如下：

2 基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的西洋跳棋評(píng)估算法

2.1 神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)

神經(jīng)網(wǎng)絡(luò)是典型的監(jiān)督學(xué)習(xí)方法。目前應(yīng)用最多的是BP神經(jīng)網(wǎng)絡(luò)，可以通過誤差反向傳播來調(diào)整權(quán)值，減小誤差，在一次次的迭代中，達(dá)到權(quán)值組合的最優(yōu)值。

強(qiáng)化學(xué)習(xí)[6]是一種無導(dǎo)師的機(jī)器學(xué)習(xí)方法。計(jì)算機(jī)選擇一個(gè)動(dòng)作作用于環(huán)境，環(huán)境狀態(tài)在發(fā)生改變后，隨之產(chǎn)生一個(gè)強(qiáng)化信號(hào)。若計(jì)算機(jī)選擇的動(dòng)作獲得了獎(jiǎng)勵(lì)，那么它以后選擇此動(dòng)作的趨勢(shì)會(huì)加強(qiáng)。

2.2 算法設(shè)計(jì)

為了讓計(jì)算機(jī)在有限時(shí)間內(nèi)選取更優(yōu)的招法，本文將神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)相結(jié)合的評(píng)估算法，應(yīng)用在西洋跳棋（10×10棋盤）博弈系統(tǒng)中。強(qiáng)化學(xué)習(xí)算法的引入能夠更高效地對(duì)棋局進(jìn)行學(xué)習(xí)和評(píng)估，并在不斷的學(xué)習(xí)過程中積累經(jīng)驗(yàn)，使評(píng)估結(jié)果更為準(zhǔn)確，但博弈過程中局面狀態(tài)往往復(fù)雜多樣，數(shù)據(jù)龐大。BP神經(jīng)網(wǎng)絡(luò)的引入正好可以彌補(bǔ)這一缺陷，它作為評(píng)估函數(shù)的載體，可以有效避免數(shù)據(jù)災(zāi)難的問題，在訓(xùn)練學(xué)習(xí)過程中增強(qiáng)評(píng)估函數(shù)的泛化能力，大大提高博弈水平。

2.2.1 神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)

本文將神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)成三層結(jié)構(gòu)，如圖1所示，具體設(shè)計(jì)如下：

圖1 神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)

輸入層：由51個(gè)神經(jīng)元構(gòu)成。其中，25個(gè)可表示為我方特征（我方棋盤領(lǐng)域），其余25個(gè)為對(duì)手特征（對(duì)方棋盤領(lǐng)域）。第51個(gè)神經(jīng)元作為偏置節(jié)點(diǎn)，可代表當(dāng)前下棋方（若當(dāng)前下棋方為我方，則取值為1，反之取為-1）。

隱含層：隱含層選用一層，根據(jù)大量前期經(jīng)驗(yàn)，神經(jīng)元的個(gè)數(shù)選為輸入層神經(jīng)元個(gè)數(shù)的1/3，因此選取17個(gè)神經(jīng)元。

輸出層：由于西洋跳棋博弈系統(tǒng)的神經(jīng)網(wǎng)絡(luò)預(yù)期輸出為評(píng)估值，故輸出層可選擇1個(gè)神經(jīng)元。

2.2.2 神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)的結(jié)合

本文針對(duì)靜態(tài)估值和遺傳算法的不足，提出了基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的西洋跳棋評(píng)估算法，采用神經(jīng)網(wǎng)絡(luò)作為西洋跳棋局面的評(píng)估函數(shù)，選用 TD(λ)算法來調(diào)整網(wǎng)絡(luò)權(quán)值，該算法是由Richard Sutton[7]等人提出的，目前已有廣泛的應(yīng)用。假設(shè) Y1, Y2,… ,Ym為中間局面的序列，神經(jīng)網(wǎng)絡(luò)中初始權(quán)重采用隨機(jī)值，神經(jīng)網(wǎng)絡(luò)得到的初始評(píng)估值為P1, P2,… ,Pn。最終的西洋跳棋棋局勝負(fù)結(jié)果用Z表示（-1表示對(duì)方勝，0表示和棋，1表示我方勝）。此時(shí)，權(quán)值調(diào)整函數(shù)可表示如下：

其中，ωn+1表示調(diào)整后的權(quán)值，ωn表示當(dāng)前權(quán)值，表示每個(gè)局面的調(diào)整值，其計(jì)算公式如下：

其中，α為學(xué)習(xí)速率，取值為(0,1，?ωYk表示第k個(gè)局面評(píng)估值對(duì)權(quán)值的偏導(dǎo)數(shù)，通過引入λ可以修正前1～i個(gè)局面評(píng)價(jià)，即若λ取0，僅對(duì)第i個(gè)局面評(píng)價(jià)做修正，λ取1，則對(duì)前i個(gè)局面做同等程度的修正，λ取( )0,1范圍中的值時(shí)，表示對(duì)第t到第1個(gè)局面評(píng)估做λ指數(shù)級(jí)的衰減修正。而當(dāng)最終勝負(fù)結(jié)果出來時(shí)，用Z代替公式(4)中的Yi+1。

3 效果分析

宮瑞敏等[1]將TD-BP算法應(yīng)用在五子棋博弈系統(tǒng)中，實(shí)現(xiàn)了具有自適應(yīng)學(xué)習(xí)能力的五子棋博弈系統(tǒng)，其實(shí)驗(yàn)結(jié)果表明，該算法的博弈系統(tǒng)可以較快地得到良好的訓(xùn)練成果。王玨等[3]將神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)相結(jié)合的算法應(yīng)用在中國(guó)象棋博弈系統(tǒng)中，采用隨機(jī)對(duì)弈、專家棋譜數(shù)據(jù)庫(kù)等作為訓(xùn)練樣本，實(shí)驗(yàn)表明采用該算法的博弈系統(tǒng)可以盡快地學(xué)到基礎(chǔ)的博弈知識(shí)，但是后期學(xué)習(xí)效果不如預(yù)期，影響強(qiáng)化學(xué)習(xí)的因素還需進(jìn)一步探索。

由于西洋跳棋和五子棋、中國(guó)象棋等棋類有很強(qiáng)的相似性，如與中國(guó)象棋均屬于吃子類游戲，且棋局大小類似。因此，可以分析得出，將神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)相結(jié)合的算法（TD-BP算法）應(yīng)用到西洋跳棋博弈系統(tǒng)中，與靜態(tài)估值評(píng)估算法相比會(huì)有較好的自適應(yīng)學(xué)習(xí)能力，與遺傳算法相比有較快的學(xué)習(xí)效率。由于筆者的學(xué)術(shù)基礎(chǔ)和時(shí)間問題，本文所提出算法的實(shí)驗(yàn)部分將會(huì)在未來工作中完成。

4 總結(jié)與展望

評(píng)估算法是西洋跳棋計(jì)算博弈水平的重要衡量因素之一。本文對(duì)目前西洋跳棋博弈系統(tǒng)主要采用的評(píng)估算法（靜態(tài)估值和遺傳算法）進(jìn)行了描述和分析，其中，靜態(tài)估值雖構(gòu)造簡(jiǎn)單，但不具備自適應(yīng)學(xué)習(xí)能力，而遺傳算法雖可以自主學(xué)習(xí)，但隨機(jī)性較強(qiáng)，訓(xùn)練時(shí)間較久?；诖?，本文將神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)相結(jié)合的評(píng)估算法，即TD-BP算法，應(yīng)用在西洋跳棋博弈系統(tǒng)中，該算法不僅可以加強(qiáng)西洋跳棋的自適應(yīng)學(xué)習(xí)能力，還可以提高訓(xùn)練效率。通過對(duì)現(xiàn)有采用TD-BP算法的幾個(gè)博弈系統(tǒng)（如中國(guó)象棋和五子棋）的分析，得出將該算法應(yīng)用在西洋跳棋博弈系統(tǒng)中將會(huì)有較好的博弈水平。

在未來工作中，筆者將實(shí)現(xiàn)本文所提出的基于神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的西洋跳棋博弈系統(tǒng)，并通過大量的實(shí)驗(yàn)，評(píng)估該算法的適用性。同時(shí)，筆者也將繼續(xù)研究影響評(píng)估效果的因素，通過實(shí)驗(yàn)結(jié)果調(diào)整神經(jīng)網(wǎng)絡(luò)和強(qiáng)化學(xué)習(xí)的參數(shù)。此外，筆者將把研究聚焦于更廣泛的角度，即同時(shí)研究更適用于西洋跳棋的搜索和評(píng)估算法。