張陽+黎素珍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

棋子價(jià)值的評估：在一些棋類中，因?yàn)楦髌遄哟嬖谧叻ㄏ拗疲云遄拥姆N類的不同決定了該棋子的價(jià)值，比如在象棋中，車和馬的價(jià)值就不同，在跳棋游戲中，因?yàn)楦鱾€(gè)棋子在走法上不存在什么差異，所以初始的價(jià)值都是相同的。

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

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

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

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

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

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

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

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

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

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

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