趙娟

[摘要]通過對人下棋過程的分析，得出計(jì)算機(jī)行棋的整個流程以及計(jì)算機(jī)在實(shí)現(xiàn)人機(jī)互戰(zhàn)中所采用的技術(shù)和知識，例如，估值函數(shù)、走法產(chǎn)生器、遍歷算法、剪枝算法等。根據(jù)這些分析，具體地實(shí)現(xiàn)這些算法。但系統(tǒng)還有很多不完善的地方有待進(jìn)一步提高。

[關(guān)鍵詞]數(shù)據(jù)結(jié)構(gòu)；函數(shù)；MFC；C++

[DOI]1013939/jcnkizgsc201537131

1引言

中國象棋游戲電腦與人對戰(zhàn)的研究最先是從國際象棋起步的，1950年美國大數(shù)學(xué)家香農(nóng)經(jīng)過幾十年的不懈研究，終于找到了編寫國際象棋程序的方法。但是近些年來經(jīng)過很多中國象棋游戲編程愛好者及多個象棋開發(fā)團(tuán)隊(duì)的不懈努力，使得中國象棋游戲水平有了長足的進(jìn)步，慢棋已經(jīng)達(dá)到了業(yè)余大師的水平，快棋也可以和象棋大師進(jìn)行對抗了[1]。

2游戲開發(fā)的需求分析和總體設(shè)計(jì)

要開發(fā)這樣一個象棋游戲系統(tǒng)，首先必須對下棋的過程進(jìn)行分析。圖1就是對人下棋過程的一個抽象描述。用下面的圖模擬人的行棋規(guī)則。

根據(jù)人的行棋規(guī)則，編程如何模擬實(shí)現(xiàn)下棋過程。圖2給出了電腦的行棋規(guī)則。綜上所述，做好一個人和電腦對戰(zhàn)的象棋游戲需要以下幾個方面：棋盤數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)；棋子的行棋規(guī)則；走法產(chǎn)生器；棋子的價值設(shè)計(jì)及界面的優(yōu)勢評斷；遍歷算法；界面設(shè)計(jì)[2]。

3游戲的詳細(xì)設(shè)計(jì)

31棋盤和棋子的實(shí)現(xiàn)

311棋盤的實(shí)現(xiàn)

一般采用9×10的二維數(shù)組作為棋盤數(shù)據(jù)結(jié)構(gòu)，然而這樣的話，后面判斷棋子在棋盤內(nèi)和對棋子走棋規(guī)則的判斷需要大量的運(yùn)算和規(guī)則。為了節(jié)省時間，采用空間換取時間的做法，采用16×16的棋盤數(shù)組數(shù)據(jù)結(jié)構(gòu)，雖然浪費(fèi)了空間，但是大大增加了效率。判斷棋子是否在棋盤內(nèi)可以用一個輔助的數(shù)組來實(shí)現(xiàn)。

312棋子表示的改變

紅方棋子：一個帥，兩個車，馬，炮，相，士和五個兵

黑方棋子：一個將，兩個車，馬，炮，象，仕和五個卒

用不同的數(shù)字來抽象表示每一種棋子，如表1所示。

33走法產(chǎn)生器

331車（車）的走法器設(shè)計(jì)

車（車）的走法是縱橫可達(dá)，所能到達(dá)的位置廣，防守攻擊的點(diǎn)多。車的走法一般是左右上下都可以到達(dá)，可以說是勇往直前。它在一個方向所能到達(dá)的最大長度是9，因?yàn)槠灞P最多是10×9的位置，所以第二層循環(huán)的判斷是以9作為判斷的。在遇到以下情況時不再往前走。遇到要吃對方棋子，或者說前方有對方棋子的情況，前方有自己本方的棋子，超出了棋盤邊界[3]。

332炮的走法設(shè)計(jì)

炮在不吃子的情況下，和車的走法是一樣的。在吃子的情況下有著“隔山打?！钡墓τ?。因?yàn)樗淖叻ê蛙嚨淖叻ú畈欢?，就是增加了一個翻山的標(biāo)志。

333馬的走法設(shè)計(jì)

馬一共有八個方向的位置可以走，但是走的方向上不能被絆腿，否則無法走動，所以對馬還設(shè)置了絆腿標(biāo)志輔助數(shù)組。

334卒的走法設(shè)計(jì)

卒的走法是三個方向，過河之前只有一個方向，根據(jù)輔助數(shù)組來判斷是否過河。

335相、仕、將（帥）的走法設(shè)計(jì)

相的走法要注意相田被塞，有一個輔助的，相田被塞數(shù)組。仕和將的走法簡單，不再贅述。

34遍歷算法的設(shè)計(jì)與實(shí)現(xiàn)

341遍歷算法

在棋面中，當(dāng)輪到一方行棋的時候，本方可能有好幾十種行棋方法，然而只有其中一個被選擇執(zhí)行，本方無論走了哪一步棋，棋面變成另一個棋面情況了，而且輪到另一方行棋，那么另一方也有好幾十種的行棋方法，然而它也只能選擇其中一個行棋方法，本方在選擇棋子走法的時候既要考慮本方行棋方法的好壞，而且要想到它行棋之后另一個會怎么行棋。這樣產(chǎn)生了一個東西，那就是遍歷搜索樹。倘若各個局面有30個可行的走法，那么就得到一個搜索遍歷的樹[4]。如圖3所示。

紅方的棋手走棋設(shè)定為用圓形表示，黑方的棋手走棋設(shè)定為正方形表示。最底端的葉子節(jié)點(diǎn)是要到達(dá)的最大深度。從葉子節(jié)點(diǎn)得到最佳行棋走法，保存從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)最佳走法的路徑。然而，實(shí)際中每一方棋手每次只走一次棋，而且不一定按照我們所預(yù)先設(shè)定的走棋，所以一般只保留根節(jié)點(diǎn)的一步最優(yōu)解。

342極大值節(jié)點(diǎn)和極小值節(jié)點(diǎn)遍歷算法

從圖4中可以看出，開始是紅方執(zhí)棋，紅方會選擇當(dāng)前走法中使得棋面優(yōu)勢最大的一個，那就是8。接下來黑方走棋，黑方希望找到最小點(diǎn)，因?yàn)榧t方先執(zhí)棋，所以紅方已經(jīng)選擇了B3走法，黑方只能選擇10的值了，即C7。對于紅方而言，10是極大值，然而對黑方來說10是極小值，極大值和極小值是相對來說的。從上面可以看出，如果搜索深度增加的話，那么步驟應(yīng)該是這樣的：尋找相對最大值—尋找相對最小值—尋找相對最大值，這樣依次循環(huán)直到達(dá)到所要搜索遍歷的深度。

343剪枝函數(shù)的設(shè)計(jì)與實(shí)現(xiàn)

運(yùn)用電腦強(qiáng)大的運(yùn)算能力對整個對戰(zhàn)樹進(jìn)行遍歷搜索。但是遍歷搜索的層數(shù)深了也是需要時間的，對10×9的棋盤進(jìn)行幾層遍歷搜索是需要相當(dāng)?shù)臅r間的，極其影響效率，而且好多節(jié)點(diǎn)是不需要搜索的，通過裁剪遍歷算法對沒有用的節(jié)點(diǎn)分支進(jìn)行裁剪，這樣大大地提高效率[4]。

以下面的遍歷搜索對戰(zhàn)樹為例簡單介紹一下裁剪算法。在遍歷到B2節(jié)點(diǎn)時，紅方已在B1節(jié)點(diǎn)遍歷到了當(dāng)前棋面最優(yōu)值8，紅棋方想經(jīng)過B2節(jié)點(diǎn)找到更加優(yōu)秀的值。在遍歷到C4節(jié)點(diǎn)時得到估值7，7也是當(dāng)前B2節(jié)點(diǎn)的最優(yōu)值。因?yàn)锽2是極小值點(diǎn)，所以在遍歷B2剩下的節(jié)點(diǎn)時，所有比7大的節(jié)點(diǎn)B2節(jié)點(diǎn)都不會考慮，當(dāng)小于7，則取代7作為當(dāng)前最優(yōu)值。不管后面的節(jié)點(diǎn)的估值是什么，結(jié)果是B2節(jié)點(diǎn)的最優(yōu)值不大于7。A節(jié)點(diǎn)找的是極大值點(diǎn)，A節(jié)點(diǎn)已經(jīng)有了一個當(dāng)前棋面最優(yōu)值8，則A節(jié)點(diǎn)的最優(yōu)值一定大于等于8，B2節(jié)點(diǎn)的值超不過7，站在A節(jié)點(diǎn)的立場，B2是沒有用的，對B2后續(xù)節(jié)點(diǎn)繼續(xù)進(jìn)行遍歷是沒有意義的。所以C5、C6幾點(diǎn)不需要進(jìn)行遍歷，回溯到A節(jié)點(diǎn)返回值，對A節(jié)點(diǎn)的后續(xù)其他子節(jié)點(diǎn)進(jìn)行遍歷。裁剪算法樹如圖5所示。

5結(jié)論

本文通過對中國象棋游戲設(shè)計(jì)與實(shí)現(xiàn)的思想進(jìn)行分析，介紹了棋盤、棋子、走棋、走棋棧等重要數(shù)據(jù)結(jié)構(gòu)。設(shè)定棋子走棋規(guī)則，滿足每個棋子特定的走棋規(guī)則。探討了走法生成器的設(shè)計(jì)與實(shí)現(xiàn)，對搜索遍歷算法的運(yùn)用。對每個棋子的價值進(jìn)行擬定，對其所能到達(dá)位置的價值進(jìn)行計(jì)算。系統(tǒng)還有很多地方有待進(jìn)一步優(yōu)化，例如，遍歷搜索算法、剪枝算法等。這些會在以后的文章中再進(jìn)行探討。

參考文獻(xiàn)：

[1]韓偉，任建敏，吳瑞芳基于數(shù)據(jù)庫技術(shù)的中國象棋軟件開局庫的設(shè)計(jì)與實(shí)現(xiàn)[J].科學(xué)技術(shù)與工程，1998（3）：556

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

[3]危春波中國象棋系統(tǒng)的研究與實(shí)現(xiàn)[D].昆明：昆明理工大學(xué)，2000

[4]袁天鑫，傅堯青中國象棋博弈程序中的樹搜索算法[J].上海交通大學(xué)學(xué)報(bào)，1990（4）：12-15