跳棋系統(tǒng)中的關(guān)鍵算法

張陽+黎素珍

摘要：計算機博弈是當(dāng)下在人工智能范疇內(nèi)一個十分重要并且十分有挑戰(zhàn)性的課題，是人工智能領(lǐng)域的重要分支。人工智能在棋類游戲中的應(yīng)用十分廣泛。目前，對于五子棋，國際象棋，中國象棋等棋牌類游戲的計算機博弈軟件有很多且智能水平都相對較高，而高水平跳棋軟件在國內(nèi)并不多見。該文在對大量相關(guān)文獻的分析和研究的基礎(chǔ)上，具體研究了跳棋博弈軟件的博弈樹搜索算法、評估函數(shù)。提出了三種不同搜索效率的算法來實現(xiàn)分級博弈，評估算法使用TD-BP算法。論文主要研究了以下幾個方面的問題：第一，根據(jù)走法生成所構(gòu)造的博弈樹，研究了一些廣泛使用的博弈樹搜索算法，并介紹了一些改進的搜索算法，在設(shè)計中結(jié)合部分搜索算法進行使用。第二，研究了主要包括靜態(tài)估值函數(shù)和其他具有機器自學(xué)習(xí)能力的評估函數(shù)，在實際設(shè)計中，將BP神經(jīng)網(wǎng)絡(luò)與增強學(xué)習(xí)算法結(jié)合使用。

關(guān)鍵詞：計算機博弈；搜索算法；分級博弈；評估函數(shù)

中圖分類號：TP311 文獻標(biāo)識碼：A 文章編號：1009-3044（2016）33-0070-04

1機器博弈系統(tǒng)關(guān)鍵要素

機器博弈系統(tǒng)的設(shè)計是將現(xiàn)實中的棋牌類游戲通過計算機語言表達(dá)，并通過計算機強大的存儲能力和計算能力使計算機擁有較高的棋力水平。

在機器博弈中，最核心的思想就是對博弈樹節(jié)點的評估函數(shù)和對博弈樹搜索方法的結(jié)合使用。

機器博弈的基本思想確定一個機器博弈系統(tǒng)的基本構(gòu)成如下：

1） 知識表示，可以用來描述當(dāng)前棋局中各個棋位上的落子情況，各棋子之間的關(guān)系及棋子與某棋位之間關(guān)系等信息。博弈系統(tǒng)可以從中讀取當(dāng)前棋局的狀態(tài)信息，知識表示往往是機器博弈系統(tǒng)值非?；A(chǔ)但是不可或缺的一部分。

2） 走法產(chǎn)生機制，主要在某一棋局狀態(tài)下用來產(chǎn)生整個博弈樹，即在當(dāng)前棋局下，生成走棋方可選擇的所有走棋方案。在博弈樹的任意一個節(jié)點上，走法產(chǎn)生機制可以產(chǎn)生這個節(jié)點的所有子節(jié)點，各子節(jié)點再產(chǎn)生孫節(jié)點，通過逐層生成，最后生成完整的博弈樹。

3） 搜索算法，主要用來在博弈樹中的所有合法走法中選出一個利益最大的走法，即最優(yōu)路徑。

4） 評估函數(shù)，根據(jù)某一棋局的具體特征對當(dāng)前棋局進行評估并量化，為搜索算法的選擇提供依據(jù)，從而通過搜索算法找出最優(yōu)走法。

2 跳棋軟件搜索算法的設(shè)計

2.1跳棋博弈系統(tǒng)的搜索算法與分級博弈

本文主要對跳棋系統(tǒng)的分級博弈進行設(shè)計與實現(xiàn)。分級博弈的控制有兩種設(shè)計方式：

1）使用不同的搜索函數(shù)，通過搜索效率與搜索的準(zhǔn)確度的差別來區(qū)分博弈等級。

2） 使用相同的搜索函數(shù)，并通過不同準(zhǔn)確度的評估函數(shù)來區(qū)分搜索函數(shù)的準(zhǔn)確度，從而實現(xiàn)分級博弈。

本文主要研究設(shè)計使用不同的搜索函數(shù)來實現(xiàn)不同級別的人機博弈。

由于在跳棋游戲中博弈樹的深度不可估計，所以在搜索時深度要達(dá)到博弈樹的最終深度基本是不可能的，而且跳棋系統(tǒng)在實際使用時，要考慮到網(wǎng)絡(luò)延遲，服務(wù)器的負(fù)載能力等因素，為了不影響用戶的游戲體驗，所以在設(shè)計搜索函數(shù)時，設(shè)定一個搜索時間上限t，使用迭代加深的搜索算法，在t時間內(nèi)，各個博弈級別的搜索函數(shù)將當(dāng)前所能搜索到的最優(yōu)解作為最終方案。根據(jù)服務(wù)器不同的性能設(shè)置不同的搜索時間上限t。

根據(jù)本章上述小結(jié)對各種博弈樹搜索算法的優(yōu)劣分析與比較，本文設(shè)計了三種博弈樹搜索算法。三種搜索算法如下：

1）負(fù)極大值與迭代加深相結(jié)合算法，使用該算法來實現(xiàn)初級博弈水平的博弈樹搜索，該算法的部分偽代碼如下所示：

在該算法中，雖然使用了迭代加深搜索算法來控制搜索的深度，但是在某一深度搜索時，該搜索算法沒有使用任何剪枝技術(shù)，造成搜索時間比較長，搜索深度不能達(dá)到理想深度。其實此算法與傳統(tǒng)的廣度優(yōu)先算法相比并沒有任何優(yōu)勢，甚至在搜索的時間復(fù)雜度上更復(fù)雜，但是考慮到實現(xiàn)過程中的控制方便，使用了迭代加深的搜索算法。

在初級水平的跳棋系統(tǒng)中，該搜索算法的搜索結(jié)果與實際最優(yōu)解往往相差很大，計算機棋手的走子的水平也相對較低。

2）采用了α-β剪枝搜索算法和迭代加深算法相結(jié)合的算法作為本系統(tǒng)的搜索算法，該算法在初級博弈水平的搜索算法的基礎(chǔ)上結(jié)合了迭代加深算法。在規(guī)定的搜索時間內(nèi)，在深度不斷增加的情況下對博弈樹進行循環(huán)搜索，在搜索深度達(dá)到temp時，將該層節(jié)點進行排序，并從根節(jié)點開始深度為temp+1的搜索，在搜索過程中，從temp深度的搜索結(jié)果中已排序的最優(yōu)節(jié)點開始優(yōu)先搜素，進行α-β剪枝，搜索完畢后再對搜索節(jié)點再次排序，如此循環(huán)搜索，直到達(dá)到搜索時間限制或者得到最優(yōu)解。該算法的流程圖如圖1所示。

該算法與1）中的算法相比，在搜索過程中結(jié)合了α-β剪枝的搜索方法。由于在某一深度的搜索過程中，對該深度的節(jié)點進行評估排序，在深度增加后的搜索過程中會優(yōu)先搜索更優(yōu)的節(jié)點，所以該算法的剪枝的效果非常好，效率也會大大提高。

該算法在2）中算法的基礎(chǔ)上與置換表啟發(fā)算法相結(jié)合，在搜索博弈樹過程中，將搜索過的節(jié)點信息，包括節(jié)點評估值、深度、當(dāng)前棋局狀態(tài)以及最優(yōu)節(jié)點信息保存在置換表中。搜索時，在某一深度搜索中，如果遇到置換表中存在相同的棋局狀態(tài)，則直接在置換表中提取信息，選擇最優(yōu)節(jié)點進行下一深度的搜索。另外使用了渴望搜索算法替換了普通的α-β剪枝搜索算法，由于本算法使用了置換表啟發(fā)，所以渴望搜索中的期望搜索值可以比較精確，所以在搜索效率上會有很大提升。

該算法與2）中算法相比，減少了迭代加深算法在各個深度搜索時對節(jié)點進行評估排序的消耗，考慮到博弈樹的寬度，在數(shù)據(jù)庫中搜索置換表的信息產(chǎn)生的消耗往往比在某一層中隊所有節(jié)點進行評估排序的消耗小的多。另外，隨著搜索的深度不斷增加，對無用節(jié)點的搜索也會相應(yīng)增多，所以使用置換表能夠很好的提高搜索效率。但是，該算法比較依賴于置換表中信息的數(shù)量與準(zhǔn)確性，所以，需要為跳棋軟件提供大量學(xué)習(xí)樣本進行訓(xùn)練，才能體現(xiàn)出該算法的優(yōu)勢。

在本節(jié)中，主要設(shè)計三種博弈樹算法來實現(xiàn)分級博弈，通過控制搜索時間來區(qū)分搜索結(jié)果的優(yōu)劣。

本文設(shè)計的三種搜索算法都使用到了迭代加深算法。從表面上看，該搜索算法在循環(huán)搜索的過程中會對淺深度的博弈樹節(jié)點重復(fù)搜索。但在博弈樹中，隨著深度的增加，節(jié)點數(shù)呈指數(shù)倍增長，所以對淺深度節(jié)點的多次遍歷造成的冗余可以忽略不計。并且在實際使用過程中，在限制的搜索時間內(nèi)，對搜索深度的估算不切實際，在不同的棋局局面下搜索的深度都不相同。所以，使用迭代加深的搜索算法思想效果比較好，搜索效率并不比廣度優(yōu)先搜索算法慢很多，而它的空間復(fù)雜度卻和深度優(yōu)先搜索算法差不多，比廣度優(yōu)先算法小很多。

3 跳棋系統(tǒng)評估函數(shù)的設(shè)計

在博弈樹的搜索中，因為計算機的資源有限和對機器反應(yīng)的實時性有一定的要求，所以機器搜索往往不能達(dá)到很深的層次。因此可以機器搜索博弈樹的過程中，搜索達(dá)到一定深度時，對當(dāng)前棋局進行評估，從而機器可以根據(jù)評估值的優(yōu)劣來選擇具體的走法[1]。

棋局評估就是對當(dāng)前局面狀態(tài)信息進行量化成計算機能夠識別的機器語言，計算機利用量化信息對當(dāng)前局面進行推理、判斷及評估，評估出當(dāng)前局面的優(yōu)劣，進而做出行動決策。對于一個具體的博弈對象來說，局面評估是影響機器求解是否準(zhǔn)確的關(guān)鍵[2]。

3.1靜態(tài)估值方法

靜態(tài)估值算法是指對于任何一個棋局狀態(tài)，根據(jù)人類對該棋類的了解，選取出對當(dāng)前棋局狀態(tài)優(yōu)劣有影響的幾個因素，并根據(jù)這幾個因素對棋局的影響力大小，給它們分配對應(yīng)的權(quán)值，以下是靜態(tài)估值方法的形式化公式：

設(shè)y是最終要得到的評估值，xi為影響棋局優(yōu)劣的各個因素，wi為對應(yīng)的特征xi對棋局影響力的權(quán)值。

在靜態(tài)估值函數(shù)中，決定靜態(tài)估值函數(shù)的主要有四個因素：

棋子價值的評估：在一些棋類中，因為各棋子存在走法限制，所以棋子的種類的不同決定了該棋子的價值，比如在象棋中，車和馬的價值就不同，在跳棋游戲中，因為各個棋子在走法上不存在什么差異，所以初始的價值都是相同的。

棋子在棋盤中位置的評估：幾乎在所有棋類中，棋子在棋盤中的位置不同，棋子相應(yīng)的價值也會不一樣。比如在跳棋中，處于敵方陣營的棋子的價值最大，距離地方陣營越近的棋子其價值也越大。

棋子靈活性的評估：棋子的靈活性主要體現(xiàn)在該棋子可以有多少種走法，每一種走法也都有相應(yīng)的價值。

棋子位置關(guān)系評估：棋子之間的關(guān)系是評估算法中非常重要的一個因素，在博弈時，己方的一個棋子可能對對方造成威脅，也有可能對對方形成幫助。在跳棋博弈中，如果一個棋子可以被對方某棋子當(dāng)做跳的橋，則該棋子的價值應(yīng)該降低，而若該棋子可以被己方其他棋子當(dāng)做跳棋的橋，則該棋子的價值應(yīng)該增加。若該棋子占據(jù)了對方棋子要跳棋的落點位置，則該棋子的價值也應(yīng)該得到增加，相反，若占據(jù)了己方其他棋子跳橋的落點位置，則該棋子的價值應(yīng)該得到削減。

但是任何一種棋類棋局的評估的要素往往錯綜復(fù)雜，人為基本上不可能考慮完全并對應(yīng)每個特征并給出合理的權(quán)值，肯定會有所誤差。然而由于在大部分搜索算法中，博弈樹搜索的過程是先搜索到某一深度，根據(jù)其評估值，再由下向上回推到根節(jié)點，從而得出搜索的結(jié)果路徑，所以如果在某一層的某個節(jié)點處發(fā)生評估值誤差，可能會引起上級節(jié)點處的決策誤差而選擇錯誤的分枝，通過層層向上傳播到根節(jié)點，搜索算法最后將會得到一條錯誤的路徑，而且該錯誤也是不能挽回的。

雖然靜態(tài)估計值有上述很多缺點，但其在機器博弈的實際應(yīng)用中，可以利用靜態(tài)估值算法構(gòu)造一個簡化的機器博弈系統(tǒng)，該系統(tǒng)可以用來與具有機器學(xué)習(xí)能力的機器博弈系統(tǒng)對弈，為該機器博弈系統(tǒng)提供學(xué)習(xí)模式，從而提高其評估函數(shù)的準(zhǔn)確性。

由上面所述可以知道，僅僅根據(jù)人對棋類知識的了解與下棋的經(jīng)驗來確定評估函數(shù)，不僅開銷較大而且得到的評估值往往不夠精確，從而會使得博弈樹的搜索結(jié)果準(zhǔn)確度降低。

3.2 TD-BP學(xué)習(xí)算法

在機器博弈的實際運用中，棋局千變?nèi)f化，所以提供給機器學(xué)習(xí)的學(xué)習(xí)模式是有限而且不一定滿足要求的，而且樣本的輸入也對系統(tǒng)造成了很大的負(fù)擔(dān)。

增強學(xué)習(xí)（Reinforcement Learning and Control）是非監(jiān)督式的學(xué)習(xí)方法，在機器博弈中運用十分廣泛。增強學(xué)習(xí)不依賴于學(xué)習(xí)樣本，而是在與環(huán)境的交互中進行學(xué)習(xí)[3]。增強學(xué)習(xí)的基本原理：agent在某一狀態(tài)下對環(huán)境進行動作action，環(huán)境隨之改變，根據(jù)環(huán)境改變是否有益，環(huán)境根據(jù)一個回報函數(shù)給以agent一個獎賞值，經(jīng)過多次的與環(huán)境交互，agent從而獲得一個獎賞值最高的策略。增強學(xué)習(xí)是一種與人類學(xué)習(xí)方式最為相近的學(xué)習(xí)方式，具有很高的應(yīng)用研究價值。

瞬時間差分（Temporal Dierence Learning）學(xué)習(xí)是一種經(jīng)典的增強學(xué)習(xí)算法，是蒙特卡洛方法和動態(tài)規(guī)劃方法的融合[4]。與BP神經(jīng)網(wǎng)絡(luò)算法不同的是，瞬時間差分算法不依賴于教師信號，可以直接從經(jīng)驗中學(xué)習(xí)，并且可以通過與環(huán)境的交互來及時修正權(quán)值與誤差。

由于BP神經(jīng)網(wǎng)絡(luò)有比較好的學(xué)習(xí)和泛化能力，可以彌補TD算法泛化能力差的缺陷。BP神經(jīng)網(wǎng)絡(luò)是有監(jiān)督的學(xué)習(xí)，即對每個輸入樣本都要求有期望輸出，輸入樣本和期望輸出構(gòu)成學(xué)習(xí)樣本，但是在博弈過程，能夠知道期望輸出的僅僅是最后獲勝棋局的前一棋局狀態(tài)，而在博弈過程中的中間棋局狀態(tài)無法獲得期望輸出，如果單純以棋局狀態(tài)與最終結(jié)果作為訓(xùn)練樣本，這種方式是不可取的，因為博弈的中間棋局狀態(tài)的變化太大，此時如果結(jié)合TD算法，可以正好彌補了應(yīng)用在跳棋博弈中BP神經(jīng)網(wǎng)絡(luò)的有教師信號學(xué)習(xí)的缺陷，TD學(xué)習(xí)算法不需要通過期望輸出來進行權(quán)值調(diào)整和誤差修改，而是利用后面的局面狀態(tài)來估計和分析當(dāng)前的局面，可以對博弈過程中的任何一個棋局進行學(xué)習(xí)，把BP學(xué)習(xí)模式轉(zhuǎn)換為無監(jiān)督式學(xué)習(xí)。TD-BP算法主要思想是利用預(yù)測誤差的方法來調(diào)整神經(jīng)網(wǎng)絡(luò)各連接的權(quán)值，通過對多個局面進行學(xué)習(xí)分析，得到更為準(zhǔn)確的評估值，提高BP神經(jīng)網(wǎng)絡(luò)與現(xiàn)實的擬合度。假設(shè)觀察的結(jié)果序列是X1，X2...Xm并且Z是觀測到的最終結(jié)果，Xi對應(yīng)某一i時刻的觀測結(jié)果，對應(yīng)這m個觀測的結(jié)果，使用評估函數(shù)進行評估，可以得到p1，p2...pm，m個Z的估計。現(xiàn)假設(shè)每一個Z的估計都是關(guān)于觀測結(jié)果的函數(shù)，由于BP神經(jīng)網(wǎng)絡(luò)屬于有教師學(xué)習(xí)，根據(jù)上一小結(jié)所述，BP神經(jīng)網(wǎng)絡(luò)把觀測結(jié)果與最終觀測結(jié)果Z做比較，用標(biāo)準(zhǔn)輸出來產(chǎn)生誤差e。根據(jù)誤差e，從輸出方向輸入方逐層修改權(quán)值，即：