肖秀春 劉澤偉 陳柏桃

摘要

棋局表示、著法生成、搜索算法、局面評(píng)估等是中國(guó)象棋人機(jī)博弈系統(tǒng)的關(guān)鍵，它決定了一個(gè)象棋博弈系統(tǒng)的優(yōu)劣本文重點(diǎn)從優(yōu)化中國(guó)象棋人機(jī)博弈系統(tǒng)性能的目的出發(fā)，圍繞該系統(tǒng)的實(shí)現(xiàn)，探索其若干基本理論問(wèn)題。同時(shí)，探討了中國(guó)象棋人機(jī)博弈樹(shù)的搜索技術(shù);在此基礎(chǔ)上，探索局面估值函數(shù)的建立方法，以及在各類(lèi)搜索算法基礎(chǔ)之上的優(yōu)化思路。

【關(guān)鍵詞】中國(guó)象棋 博弈 棋盤(pán)表示 著法生成 博弈樹(shù)搜索

1 引言

中國(guó)象棋是我國(guó)一門(mén)古老的博弈游戲，其中蘊(yùn)含了大量關(guān)于運(yùn)籌，謀略的思想。人機(jī)對(duì)弈是人與計(jì)算機(jī)之間的決策計(jì)算過(guò)程，它是人工智能的一個(gè)研究分支，它的研究為人工智能帶來(lái)了很多重要的方法和理論，產(chǎn)生了廣泛的社會(huì)影響和學(xué)術(shù)影響。

要實(shí)現(xiàn)人機(jī)對(duì)弈的功能，首先要有能夠反映棋盤(pán)信息的數(shù)據(jù)結(jié)構(gòu)，根據(jù)規(guī)則產(chǎn)生合法著法，并且在輪到計(jì)算機(jī)走子時(shí)，計(jì)算機(jī)能夠搜索到對(duì)己方最為有利的著法。我們可以用一棵“博弈樹(shù)”來(lái)表示下棋的過(guò)程，樹(shù)中的每一個(gè)節(jié)點(diǎn)代表棋盤(pán)上的一個(gè)局面，對(duì)于每一個(gè)局面根據(jù)不同的著法又產(chǎn)生不同的局面，如此直到葉節(jié)點(diǎn)。根據(jù)規(guī)則，可以可靠地判斷輸贏，假設(shè)每次計(jì)算機(jī)都能搜索到最優(yōu)局面，那么計(jì)算機(jī)將處于不敗的地位。但就目前而言，計(jì)算機(jī)能搜索到的層數(shù)有限，因此需要一個(gè)評(píng)估函數(shù)來(lái)判斷局面的好壞，這樣，計(jì)算機(jī)便能通過(guò)評(píng)估函數(shù)選擇對(duì)自己最為有利的著法。

從結(jié)構(gòu)上，可以將一個(gè)人機(jī)對(duì)弈系統(tǒng)分為棋盤(pán)表示，著法生成，搜索算法以及局面評(píng)估幾個(gè)方面。擁有了以上這些，計(jì)算機(jī)便能實(shí)現(xiàn)基本的對(duì)弈功能。與人類(lèi)相比，計(jì)算機(jī)還未能根據(jù)局面的情況制定作戰(zhàn)計(jì)劃，它擅長(zhǎng)的是計(jì)算，因而對(duì)于棋力的增強(qiáng)，則有賴(lài)于搜索算法及局面評(píng)估的結(jié)合，隨著搜索算法的不斷改進(jìn)，搜索過(guò)程中剪枝效率越高，搜索的層次越深;同時(shí)，對(duì)于搜索結(jié)果進(jìn)行的局面評(píng)估越精確，搜索得到的著法便越好，計(jì)算機(jī)的棋力也大幅度提升。

2 棋盤(pán)表示及著法生成

無(wú)疑地，棋盤(pán)表示是中國(guó)象棋人機(jī)博弈系統(tǒng)著法生成的基礎(chǔ)。合適的棋盤(pán)表示不僅有利于著法生成中各個(gè)搜索節(jié)點(diǎn)的存儲(chǔ)，也將有利于局面評(píng)估函數(shù)對(duì)當(dāng)前節(jié)點(diǎn)的評(píng)價(jià)。

2.1 棋盤(pán)表示

中國(guó)象棋的棋盤(pán)為9×10的矩形，一般采用9×10的二維數(shù)組表示。但是，這種表示方法將不利于棋盤(pán)邊界的判斷?；谶吔绲呐袛嗫紤]，也可以采用16×16的擴(kuò)展棋盤(pán)來(lái)表示。通常，采用一個(gè)大小為256的一維數(shù)組來(lái)表示的帶擴(kuò)展邊界的棋盤(pán)，對(duì)于棋子，數(shù)字0表示空位（即該位置沒(méi)有棋子），數(shù)字8～14依次表示紅方的帥、仕、相、馬、車(chē)、炮和兵;數(shù)字16～22依次表示黑方的將、士、象、馬、車(chē)、炮和卒。因此棋盤(pán)的初始局面可以表示為：

int ChessBoard[256]={

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，20，19，18，17，16，17，18，19，20，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，21，0，0，0，0，0，0，21，0，0，0，0，

0，0，0，22，0，22，0，22，0，22，0，22，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，14，0，14，0，14，0，14，0，14，0，0，0，0，

0，0，0，0，13，0，0，0，0，0，0，13，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，21，0，21，0，21，0，21，0，21，0，0，0，0，

0，0，0，12，11，10，9，8，9，10，11，12，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0};

這里判斷是否超出邊界非常簡(jiǎn)單，利用如下所示的數(shù)組，判斷棋子所在位置是否為0就行了。

int IsInBoard[256]={

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，1，1，1，1，1，1，1，1，1，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0};

2.2 著法生成

著法生成主要是用來(lái)判斷用戶的著法是否正確，以及生成計(jì)算機(jī)的所有著法，用以從中選取最好的著法。對(duì)于象棋的各個(gè)兵種，我們可以將其各個(gè)合理的著法存儲(chǔ)起來(lái)，在生成時(shí)直接取出來(lái)就可以了，這樣就省去了很多工作，提高了系統(tǒng)的性能。

3 搜索算法

3.1 最小一最大搜索及負(fù)極大值搜索

對(duì)于博弈雙方，每方都在尋求對(duì)己方局面有利的著法。假設(shè)黑方（為討論問(wèn)題方便，可假定為黑方為對(duì)弈的人，紅方為計(jì)算機(jī)）贏的局面評(píng)估函數(shù)分值為負(fù)無(wú)窮，紅方贏的局面評(píng)估函數(shù)分值為正無(wú)窮，那么，黑方肯定選擇當(dāng)前評(píng)估函數(shù)分值較小的著法而紅方應(yīng)對(duì)時(shí)，則選擇當(dāng)前評(píng)估函數(shù)分值較大的著法。如此交替，即是最小一最大搜索。于是，對(duì)于計(jì)算機(jī)來(lái)說(shuō)，其搜索最有利于己方著法時(shí)，必須考慮對(duì)方的應(yīng)對(duì)著法，其搜索目標(biāo)為使得經(jīng)過(guò)交替最小一最大搜索，最終得到當(dāng)前局面的最小評(píng)估值。最小一最大搜索原理可如圖1所示。

圖中展示了黑方當(dāng)前可以有A、B兩種著法，對(duì)應(yīng)黑方的著法A、B，紅方對(duì)應(yīng)的著法分別為（C，D）和（E，F(xiàn)），其對(duì)應(yīng)的當(dāng)前局面評(píng)估函數(shù)分值分別如上圖所示。顯然，當(dāng)黑方選擇著法A的話，那么紅方肯定會(huì)回應(yīng)D，使估分變?yōu)?（紅方有利）。但是如果黑方選擇著法B，那么紅方即使選擇最佳著法E，其估分還是-4（黑方有利）?？梢钥吹?，每次遞歸時(shí)，走子方改變，選擇方式也相應(yīng)改變，我們可以將其優(yōu)化為負(fù)極大值搜索，即每次遞歸時(shí)將返回值轉(zhuǎn)為負(fù)值，以反映當(dāng)前局面的更改。偽代碼如下：

int NegaMax（int depth）

{

int best=-無(wú)窮大;

if（depth<=0）

return評(píng)價(jià)值;

調(diào)用著法生成函數(shù)，生成所有合法著法;

while（生成的著法）

{

試走一個(gè)著法;

value=-NegaMax（depth-1）;

撤銷(xiāo)該著法;

if（value>best）

best-value;

}

return best;

}。

3.2 Alpha-Beta搜索

隨著搜索深度的增加，局面是呈指數(shù)級(jí)增長(zhǎng)的，所以在有限的時(shí)間內(nèi)，計(jì)算機(jī)搜索的層數(shù)很淺。而計(jì)算機(jī)要找到更好的著法，搜索的層數(shù)應(yīng)該盡可能深。因此在搜索過(guò)程中，應(yīng)及時(shí)停止擴(kuò)展那些已無(wú)必要再擴(kuò)展的子節(jié)點(diǎn)，即相當(dāng)于剪去博弈樹(shù)上的一些分枝。如圖2所示。

圖2中左邊部分由于節(jié)點(diǎn)C取極小值，可以判斷C的值將小于或等于16;而節(jié)點(diǎn)A的值為Max（B，C）=18，因此我們不再需要評(píng)估節(jié)點(diǎn)C的其他節(jié)點(diǎn)E、F便可以得出父節(jié)點(diǎn)A的值了，這種剪枝策略稱(chēng)為Alpha剪枝。

同樣，如圖2右邊部分所示，我們可以判定節(jié)點(diǎn)C的值將大于或等于18，而節(jié)點(diǎn)A為Min（B，C）=8，因此我們也不再需要評(píng)估節(jié)點(diǎn)C的其他節(jié)點(diǎn)的值，這種剪枝策略稱(chēng)為Beta剪枝。將Alpha剪枝及Beta剪枝加入負(fù)極大值搜索便得到Alpha-Beta搜索算法。偽代碼如下：

int A1phaBetaSearch（int alpha，int beta，intdepth）

{

if（depth=0）

return局面評(píng)價(jià)函數(shù);

調(diào)用著法生成子函數(shù)，生成所有著法;

for（每個(gè)生成的著法）

{

在博弈樹(shù)中，取出一個(gè)著法;

int value=-A1phaBeta（-beta，-alpha，depth-1）;

在博弈樹(shù)中，剪枝一個(gè)著法;

if（value>=beta）

break;

if（value>alpha）

alpha=value;

}

return alpha;

}

這就是Alpha-Beta算法，只要有一步好的著法，就可以淘汰很多沒(méi)必要搜索的節(jié)點(diǎn)，包括節(jié)點(diǎn)之下的子樹(shù)，使得搜索效率大為提高。

3.3 MID搜索

我們也可以通過(guò)一個(gè)估算值（g，g+1）作為窗口來(lái)進(jìn)行探測(cè)，設(shè)定一個(gè)上界upperbound和一個(gè)下界lowerbound，如果結(jié)果大于g，則修改lowerbound，如果小于g，則修改upperbound，如此反復(fù)，不斷修改邊界值，知道upperbound和lowerbound收斂于一點(diǎn)。偽代碼如下：

int MTD（）

{

g=初始值;

upperbound=INFINITY;

lowerbound=-INFINITY;

while（lowerbound

{

if（g==lowerbound）

beta=g+1;

else

beta=g;

g=AlphaBeta Seach（beta-1 ，beta，nDepth-1）

if（g

upperbound=g;

else

lowerbound=g

}

returng;

}

4 局面評(píng)估

一般而言，都是通過(guò)局面評(píng)估來(lái)判斷著法的好壞。如果把紅方的價(jià)值總和設(shè)為RedValue，黑方價(jià)值總和設(shè)為BIackValue，那么Value=BIaekValue-RedValue，就是對(duì)于黑方而言的局面的情況。以上分析表明，對(duì)于局面評(píng)估，著法價(jià)值的計(jì)算非常重要。我們可以從以下若干角度對(duì)著法價(jià)值進(jìn)行計(jì)算。

4.1 子力價(jià)值

子力價(jià)值即是博弈雙方各有哪些棋子，以及價(jià)值如何。根據(jù)文獻(xiàn)[5]，可以讓一個(gè)車(chē)的價(jià)值為500，一個(gè)馬的價(jià)值為300，一個(gè)兵的價(jià)值為100等等，而將的價(jià)值設(shè)為無(wú)窮大或計(jì)算機(jī)所能表示的最大的數(shù)值。

4.2 機(jī)動(dòng)性及對(duì)棋盤(pán)的控制

機(jī)動(dòng)性值是棋子的活動(dòng)范圍的度量，通常棋子的活動(dòng)范圍越大，其機(jī)動(dòng)性也越好，而對(duì)棋盤(pán)的控制范圍則是一個(gè)棋子的合法著法的范圍內(nèi)，可以通過(guò)雙方控制該位置的棋子數(shù)量及棋子價(jià)值來(lái)決定哪方的機(jī)動(dòng)性占優(yōu)。

4.3 棋子位置

對(duì)于同一個(gè)棋子，位置不同，其價(jià)值也有所不同，比方說(shuō)，過(guò)河卒子要比未過(guò)河的價(jià)值高得多?？梢越o每個(gè)不同的兵種在棋盤(pán)上的各個(gè)位置給出經(jīng)驗(yàn)評(píng)估值，以確保評(píng)估的準(zhǔn)確性。

5 性能優(yōu)化

5.1 迭代深化

在搜索過(guò)程中對(duì)搜索樹(shù)作出裁剪，可以有效地降低計(jì)算機(jī)的搜索時(shí)間，從而增加計(jì)算機(jī)搜索嘗試。對(duì)搜索樹(shù)剪枝的關(guān)鍵在于能夠搜索到好的著法，否則裁剪效率很低。通常，可以通過(guò)一個(gè)歷史啟發(fā)表來(lái)存儲(chǔ)搜索過(guò)的好的著法，這大大增加了剪枝的效率。剪枝的效率越高，可使得算法迭代層次越深。

5.2 靜態(tài)搜索

在下棋的過(guò)程有時(shí)會(huì)遇到這種情況，就是計(jì)算機(jī)搜索的層次不夠深，因而有些厲害的殺著可能搜索不出來(lái)，這就導(dǎo)致棋力下降。我們?cè)诰置姘l(fā)生震蕩的時(shí)候加深搜索的層次，直到局面沒(méi)有吃子或者將軍的情況，這較大幅度地提高象棋的棋力。

6 結(jié)束語(yǔ)

博弈理論與人工智能的研究有著相互推動(dòng)的作用：博弈理論對(duì)于人工智能研究的發(fā)展提出要求;人工智能的研究成果反過(guò)來(lái)可以應(yīng)用于博弈系統(tǒng)實(shí)踐。

本文對(duì)計(jì)算機(jī)博弈理論進(jìn)行了研究，在深入研究了計(jì)算機(jī)中國(guó)象棋理論基礎(chǔ)上，探討了中國(guó)象棋人機(jī)對(duì)弈系統(tǒng)的設(shè)計(jì)原理。但是用Alpha-Beta搜索算法或其變種以及啟發(fā)式搜索的方法，采用局面估值函數(shù)對(duì)各搜索節(jié)點(diǎn)進(jìn)行估值，這樣人為的主觀因素很強(qiáng)，而要克服這個(gè)問(wèn)題，則需要計(jì)算機(jī)進(jìn)行自學(xué)習(xí)，以取得更高的獨(dú)立性及自適應(yīng)性。

參考文獻(xiàn)

[1]王驕，王濤，羅艷紅.徐心和.中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)評(píng)估函數(shù)的自適應(yīng)遺傳算法實(shí)現(xiàn)[J].東北大學(xué)學(xué)報(bào)，2005，26（10）：949-952.

[2]危春波.中國(guó)象棋博弈系統(tǒng)的研究與實(shí)現(xiàn)[D].昆明理工大學(xué)碩士學(xué)位論文，2008.

[3]徐心和，王驕.中國(guó)象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27（06）：962-969.

[4]劉淑琴，劉淑英.基于博弈樹(shù)搜索算法的中國(guó)象棋游戲的設(shè)計(jì)與實(shí)現(xiàn)[J].自動(dòng)化與儀器儀表，2017（10）：96-98.

[5]金朋，馮速.博弈樹(shù)搜索算法概述[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2009（09）：203-207.

[6]蔡屾.一種中國(guó)象棋機(jī)器博弈剪枝策略的改進(jìn)方法[J].國(guó)外電子技術(shù)，2016，35（03）：47-49.

[7]郝卿，黎利輝.基于 Android的中國(guó)象棋局域網(wǎng)博弈平臺(tái)的設(shè)計(jì)與實(shí)現(xiàn)[J].廣西民族師范學(xué)院學(xué)報(bào)，2017，34（03）：145-148，113.