丁錦鈺

（洛陽市第一高級中學，河南洛陽，471000）

0 引言

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

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

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

1.1 靜態(tài)估值

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

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

1.2 遺傳算法

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

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

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

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

2.1 神經(jīng)網(wǎng)絡(luò)和強化學習

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

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

2.2 算法設(shè)計

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

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

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

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

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

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

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

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

本文針對靜態(tài)估值和遺傳算法的不足，提出了基于神經(jīng)網(wǎng)絡(luò)和強化學習的西洋跳棋評估算法，采用神經(jīng)網(wǎng)絡(luò)作為西洋跳棋局面的評估函數(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īng)網(wǎng)絡(luò)得到的初始評估值為P1, P2,… ,Pn。最終的西洋跳棋棋局勝負結(jié)果用Z表示（-1表示對方勝，0表示和棋，1表示我方勝）。此時，權(quán)值調(diào)整函數(shù)可表示如下：

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

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

3 效果分析

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

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

4 總結(jié)與展望

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

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