張娜 譚亮

（商洛學院電子信息與電氣工程學院 商洛 726000）

1 引言

當計算機誕生，人們就已經(jīng)想到用計算機來下棋，這就是機器博弈。機器博弈是人工智能的一個傳統(tǒng)研究領域［1～2］。在國際象棋計算機博弈高度發(fā)展的今天，基于兩個原因，中國象棋則具有得天獨厚的發(fā)展優(yōu)勢［3～4］：它是世界上最流行最古老的棋類游戲之一，且現(xiàn)在已經(jīng)存在較高棋力的中國象棋程序；它的復雜度介于國際象棋與圍棋之間。

國際象棋機器博弈的研究已經(jīng)有很長一段時間，其中不得不提的就是卡斯帕洛夫與IBM公司研制的“深藍”（DEEP）計算機及其升級版“更深的藍”（DEEPERBLUE）進行的震驚世界的象棋比賽，這場前無古人的人機大戰(zhàn)給世界留下了深遠的影響，更多的人開始認識人工智能，認識機器博弈［5］。

中國象棋是由兩個人依次走子，把對方的將吃掉為勝的一種棋類運動，在中國乃至世界有著數(shù)以億計的愛好者［6］。它不僅能夠豐富人們的生活，陶冶情操，更有助于開發(fā)青少年的智力，啟迪思維，鍛煉辨證分析能力和培養(yǎng)頑強的意志。用于中國象棋博棄的計算機成果可以運用到各個領域，甚至深入到我們目前無法企及的領域，從而更好地服務人類［7～8］。

本文以Qt為平臺，采用QPainter類中的畫筆來進行繪制棋盤，用一個有32個數(shù)據(jù)元素的數(shù)組來存儲棋子的ID，利用窮舉法生成棋子的走法，實現(xiàn)了人人對戰(zhàn)，再加上TCP通信、極大值極小值搜索算法和優(yōu)化-剪枝算法來實現(xiàn)人機對戰(zhàn)。

2 基于Qt的中國象棋設計

Qt是一個跨平臺的C++應用程序框架，支持Windows、Linux、Android、iOS、嵌入式系統(tǒng)［9～10］。Qt可以同時支持桌面應用程序開發(fā)、嵌入式開發(fā)和移動開發(fā)，覆蓋了現(xiàn)在的所有移動平臺，只需要編寫一次代碼，發(fā)布到不同的平臺上重新編譯即可。

人人對戰(zhàn)即傳統(tǒng)下棋方式，采用肉眼觀察雙方的形勢，然后考慮接下來的一步或者多步走法，最后選擇最好的一種走法，這一過程如圖1所示。

圖1 人人對戰(zhàn)示意圖

2.1 局面表示

局面是指一盤棋經(jīng)過若干個回合之后當前所處的形勢［11］。在中國象棋中局面既包含棋盤、棋子和當前是哪一方走棋，還包含對弈雙方所走的步數(shù)、是否將軍、未吃子步數(shù)、走棋時間等。要讓計算機能夠理解當前的局面，就必須把局面所包含的信息通過某種數(shù)據(jù)結(jié)構存儲起來，這些信息在棋局進行的過程中會一直更新變化。局面表示除了要求存儲和修改方便以外，更重要的是要計算方便，這個直接影響到搜索算法的效率。

2.2 棋盤表示

中國象棋是一個9行8列的類似表的網(wǎng)絡，從而我們可以使用Qt中QPainter類中的畫筆來進行繪制棋盤。如圖2所示。

圖2 棋盤示意圖

2.3 棋子表示

在棋子表示方面，紅黑雙方各有16顆棋子，用一個有32個數(shù)據(jù)元素的數(shù)組來存儲棋子的ID，并且將32顆棋子初始化。初始化完成后開始繪制棋子，棋子由兩部分組成，一個是圓圈，一個是棋子對應的字，如圖3所示。

圖3 繪制棋子

2.4 走法生成

各種棋類規(guī)則的不同，走法產(chǎn)生的復雜程度也有很大的差別。例如五子棋的棋盤上的任意空白點都是合法的下一步，而在象棋里，要仔細判斷，比如說象只可以走田字，這時候就要檢查目標位置有沒有自己的棋子，并且要檢查相眼是否有棋子；而兵則要注意過河之后是不能往后退的。

計算機在獲取到最佳走法之前必須要先獲得所有可能的走法。目前的走法生成除了窮舉法外沒有更好的辦法，同時，走法生成是一個先窮舉后排除的一個過程，具體方式如下：

1）掃描棋盤非空位置上的所有棋子；

2）在充分考慮中國象棋規(guī)則的基礎上，對于棋子下一步可能的位置進行判斷；

3）為了簡化棋子的走法規(guī)則，除了車和炮以外的棋子目標位置的行列和原來棋子的位置之間都有 一 種 關 系 。 r=qAbs（row1-row）*10+qAbs（col1-col）；qAbs為取絕對值，row1、col1為目標位置的行列，row、col為原來棋子的行列，當r等于一定的數(shù)值后，這顆棋子才能正確落子。

2.4.1 馬的走法生成

通過點擊鼠標事件來獲取鼠標點擊棋子在棋盤上的行列值，當需要移動棋子時，會檢查棋子的初始位置和目標位置的情況從而來判斷該棋子的走法是否合法。

如圖4（a）所示，圖中N點表示馬的起步位置，這時根據(jù)棋子的ID知道棋子的行row和列col。馬的走法可以是1～8對應的位置，這些位置也對應著行row1和列col1。圖中黑色三角形都是馬腿的位置，馬的走法程序如下所示。

bool Board：：canMoveMa（int moveid，int，int row，int col）

｛GetRowCol（row1，col1，moveid）；

int r=relation（row1，col1，row，col）；//馬行走的軌跡和行列間關系

if（r！=12 & & r！=21）

return false；if（r==12）

｛if（getStoneId（row1，（col+col1）/2）！=-1）//找“馬腿”

return false；｝

else

｛if（getStoneId（（row+row1）/2，col1）！=-1）

return false；｝

return true；

｝

調(diào)用relation函數(shù)時，如果返回值是12并且坐標（row1，（col+col1）/2）有棋子，此刻棋子不能移到第row1行第col1的位置。如果返回值是21并且坐標（（row+row1）/2，col1）有棋子，此刻棋子不能移到row1行第col1的位置。

2.4.2 將的走法生成

如圖4（b）所示，圖中說明了將走法生成的示意圖，將只能在九宮里面活動，最多有4種走法。通過控制行列的范圍和步長關系就可以約束將的走法，r等于1或者10的時候棋子是可以移動的。

2.4.3 士的走法生成

如圖4（c）所示，士的走法與將的走法差不多，唯一的區(qū)別就是r的值，當r等于11的時候棋子才能移動。

圖4 走法生成

2.4.4 相的走法生成

如圖4（d）所示，該圖是相的走法生成示意圖，相的走法跟馬的規(guī)則類似，要考慮相眼的問題。在步長關系r等于22的基礎上，還要滿足（（row+row1）/2，（col+col1）/2）這個點上沒有棋子，只有滿足這兩個條件，棋子就可以移動到目標位置。

2.4.5 車的走法生成

如圖4（e）所示，該圖是車的走法示意圖，車可以沿著四個方向一直走，直到下列任意事件發(fā)生為止：1）走出棋盤；2）碰到本方棋子；3）吃掉對方棋子。

2.4.6 炮的走法生成

如圖4（f）所示，該圖是炮走法生成示意圖，炮的走法與車的走法類似，但是炮要考慮四種情況分別對應圖中1到4：1）沒有棋子可以一直走到邊界；2）炮翻山后遇到本方棋子，非法走法；3）炮翻山后遇到對方棋子，吃棋；4）翻山后出棋盤，非法走法。

2.4.7 兵的走法生成

如圖4（g）所示，該圖是兵的走法生成示意圖，兵分過河前的走法和過河后的走法。過河前兵只能向前走，過河之后兵除了向前走以外還能向左右移動，通過移動后的行列數(shù)來判斷兵是否過河。

2.5 將軍檢測

在上述走法的基礎上，只要檢查一方所有的棋子可以到達的位置是否有對方的將，唯一需要注意的是雙方的將之間的直線上面沒有棋子的話是可以相互攻擊的。

3 基于Qt的中國象棋程序?qū)崿F(xiàn)

3.1 人人對戰(zhàn)的實現(xiàn)

人人對戰(zhàn)是兩個人面對面下棋。利用Qt中的鼠標點擊事件來處理棋子的移動，再加上各個棋子的走法規(guī)則，就能輕易的實現(xiàn)人人對戰(zhàn)。鼠標點擊事件部分程序如下，人人對戰(zhàn)的截圖如圖5（a）所示。

void Board：：mouseReleaseEvent（QMouseEvent*ev）

｛if（ev-＞button（）！=Qt：：LeftButton）

｛return；

｝

click（ev-＞pos（））；

｝

mouseReleaseEvent（QMouseEvent*ev）這個函數(shù)能夠獲取棋子的坐標，通過配合各個棋子的走法和規(guī)則進行落子，從而實現(xiàn)人人對戰(zhàn)的功能。

3.2 人機對戰(zhàn)的實現(xiàn)

在人人對戰(zhàn)的基礎上，加上TCP通信，用于實現(xiàn)數(shù)據(jù)的同步，人機對戰(zhàn)截圖如圖5（b）所示。QTcpServer用于創(chuàng)建TCP服務器端。當newCon?nection信號激發(fā)時，我們調(diào)用指定的槽函數(shù)創(chuàng)建一個通信的套接字。QTcpSocket用于創(chuàng)建TCP通信套接字。當connected信號激發(fā)時，我們向服務器端發(fā)送消息，當readyRead信號激發(fā)時，我們就可以讀取數(shù)據(jù)。客戶端與服務端通信時用數(shù)組buf來發(fā)送數(shù)據(jù)，如下所示。

圖5 基于Qt的中國象棋實現(xiàn)截圖

1）執(zhí)紅棋還是執(zhí)黑棋由服務器發(fā)出，buf的第一個字節(jié)固定為1，第二個字節(jié)為0或者1（隨機），1代表執(zhí)紅棋，0代表執(zhí)黑棋；

2）點擊棋子的信息雙發(fā)都可以發(fā)出，buf的一個字節(jié)固定為2，第二個字節(jié)為棋子的id，第三個字節(jié)為棋子的row，第四個字節(jié)為棋子的col；

3）悔棋的信息雙方都可以發(fā)出，buf的第一個字節(jié)固定為3，當雙方接受到此消息時代表悔棋操作。

3.3 局面評估

局面評估就是識別棋局的好壞，以便在博弈樹搜索時作為路徑選擇條件尋找最佳著法［12］?？尚械霓k法就是對局面進行量化，通過數(shù)值評判棋局對我方的優(yōu)劣，并得到合適的走法。評估函數(shù)的準確性將直接影響搜索的方向，同時評估函數(shù)的效率對搜索性能也有直接的影響［13］。一種最簡單的局面評估是計算本方棋子價值之和與對方棋子價值之和的差值，我們把這個差值叫做局面分，這里就涉及到棋子價值的問題。一般來說，象棋中棋子的價值關系大致如下：將＞車〉馬、炮＞士、相＞兵。各棋子價值如表1所示。

表1 棋子價值表

3.3.1 極大值極小值算法

在通常的局面中，我們往往想通過少量的搜索，為當前局面選擇一步較好的走法，然而在通常的棋局中，一個局面的評估往往不像輸、平、贏3種狀態(tài)這么簡單，在分不出輸贏的局面中棋局也有優(yōu)劣之分。也就是說，要用更細致的方法來刻畫局面的優(yōu)劣，而不是僅僅使用1，-1，0三個數(shù)字刻畫3種終了局面。假定我們有一個函數(shù)可以為每一個局面的優(yōu)劣評分。例如甲勝為正無窮，乙勝為負無窮，和局為0；其他的情形依據(jù)雙方剩余棋子的數(shù)量及位置評定從負無窮到正無窮之間的具體分數(shù)。這樣我們可以建立一棵固定深度的搜索樹，其葉子節(jié)點不必是終了狀態(tài)，只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，如同前面提到的那樣，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。

一方走棋的過程中，選擇價位最大的子節(jié)點法，即實行“Max搜索”，一方走棋則選擇價位小的子節(jié)點法，即實行“Min搜索”，這就足象棋博弈中的一個極大極小過程［14］。如圖6所示，該圖表示了一個極大極小搜索過程，粗箭頭為最佳路徑片段。

圖6 極大極小搜索

圖7中方形節(jié)點為紅方走棋的局面，圓形節(jié)點為黑方走棋局面，數(shù)字為局面估值。深度優(yōu)先遍歷這個搜索樹：

1）初始局面為A，該紅方走棋。紅方有B1、B2、B3三種走法。

2）假設紅方選擇第一種走法，走到了局面B1。

3）在局面B1，該黑方走棋。黑方有C1、C2、C3三種走法。

4）C1、C2、C3是葉子節(jié)點，調(diào)用局面評估函數(shù)，算得局面估值分別是3、7、12。

5）回到局面B1，此時該黑方走棋。黑方后完后，紅方優(yōu)勢越小，對黑方越有利。黑方自然會走到對自己最有利的C1局面。此時我們認為，B1局面的估值是3。

6）同樣的方法，B2、B3的估值分別是9、6。

7）回到初始局面A，紅方走棋?，F(xiàn)在已經(jīng)知道，選擇第一種走法，最終估值為3；選擇第二種走法，最終估值為9；選擇第三種走法，最終估值為6。估值就是紅方的優(yōu)勢，紅方自然會選擇對自己優(yōu)勢最大的走法，也就是走到局面B2。

8）可知行棋路線為A-＞ B2-＞ C4。

3.3.2 優(yōu)化-剪枝算法

由于完整的博弈樹十分龐大，程序能也沒存必要搜索整棵博弈樹的所有節(jié)點，而需耍有選擇性地進行搜索，對于一些已經(jīng)確定不佳的走步可以將以它根節(jié)點的子樹剪掉，從而將這些節(jié)省下來的時間用于更有意義的搜索［14］。博弈搜索的目的是為了獲得一個可能的最佳局面，如果沿著一個結(jié)點搜索下去，絕對不可能有比當前己經(jīng)搜索到的局面更優(yōu)化，這就是一個無用的結(jié)點，該剪掉。如圖7所示，該圖是搜索剪枝的示意圖。

圖7 搜索剪枝示意圖

當搜索到B2點吋，紅方已經(jīng)通過B1的搜索得到一個當前最優(yōu)值8，紅方希望通過B2這條路徑得到更優(yōu)的值。當搜索到C4時得到一個估值7，也就是B2點的當前最優(yōu)值。由于B2是極小值點，在搜索B2的剩余子結(jié)點吋，凡足估值超過7的B2點都不予考慮，一旦有值小于7，就會取代7成為新的最優(yōu)值。即是不管后續(xù)子節(jié)點得到怎樣的估值，其結(jié)果B2的最優(yōu)值小于等于7。A是極大點，A點已經(jīng)有一個當前最優(yōu)值8，那么A點的最優(yōu)值肯定大于等于8，既然B2的最優(yōu)值不會超過7，對于A點來說B2就沒有意義，繼續(xù)搜索B2的子節(jié)點也就毫無意義［15］。C5、C6不必搜索，而直接返回A點，繼續(xù)A點，在搜索C8剩余的子節(jié)點時，凡是估值低于14的C8都不會考慮，一旦有值大于14，就會取代14成為新的最優(yōu)值。也就是不管在后續(xù)子節(jié)點得到怎樣的估值，其結(jié)果就是C8的最優(yōu)值大于等于7。B3是極小值點，且已經(jīng)有一個當前最優(yōu)值10，那么B3點的最優(yōu)值肯定小于等于10，既然C8的值不會低于14，對于B3點來講，C8就沒有意義，繼續(xù)搜索C8的后續(xù)節(jié)點也就毫無意義。D2、D3不必搜索，直接返回B3點，繼續(xù)B3點后續(xù)節(jié)點的搜索。同理D6也不必搜索。

4 結(jié)語

本文基于Qt的中國象棋棋理算法的研究與設計，采用Qt中的QPainter類中的畫筆來進行繪制棋盤，用一個有32個數(shù)據(jù)元素的數(shù)組來存儲棋子的ID，利用窮舉法生成馬、將、士、相、車、炮、兵等的走法，實現(xiàn)了人人對戰(zhàn)，再加上TCP通信在其基礎上實現(xiàn)了網(wǎng)絡對戰(zhàn)和人機對戰(zhàn)。采用極大值極小值算法與優(yōu)化-剪枝算法對棋局的局面進行評估。實驗結(jié)果表明，該系統(tǒng)具有實時性、穩(wěn)定性高、靈活性高等特點，達到了方案預期效果。