中國象棋游戲的設計與實現

趙娟

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

[關鍵詞]數據結構；函數；MFC；C++

[DOI]1013939/jcnkizgsc201537131

1引言

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

2游戲開發的需求分析和總體設計

要開發這樣一個象棋游戲系統，首先必須對下棋的過程進行分析。圖1就是對人下棋過程的一個抽象描述。用下面的圖模擬人的行棋規則。

根據人的行棋規則，編程如何模擬實現下棋過程。圖2給出了電腦的行棋規則。綜上所述，做好一個人和電腦對戰的象棋游戲需要以下幾個方面：棋盤數據結構設計；棋子的行棋規則；走法產生器；棋子的價值設計及界面的優勢評斷；遍歷算法；界面設計[2]。

3游戲的詳細設計

31棋盤和棋子的實現

311棋盤的實現

一般采用9×10的二維數組作為棋盤數據結構，然而這樣的話，后面判斷棋子在棋盤內和對棋子走棋規則的判斷需要大量的運算和規則。為了節省時間，采用空間換取時間的做法，采用16×16的棋盤數組數據結構，雖然浪費了空間，但是大大增加了效率。判斷棋子是否在棋盤內可以用一個輔助的數組來實現。

312棋子表示的改變

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

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

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

33走法產生器

331車（車）的走法器設計

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

332炮的走法設計

炮在不吃子的情況下，和車的走法是一樣的。在吃子的情況下有著“隔山打牛”的功用。因為它的走法和車的走法差不多，就是增加了一個翻山的標志。

333馬的走法設計

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

334卒的走法設計

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

335相、仕、將（帥）的走法設計

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

34遍歷算法的設計與實現

341遍歷算法

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

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

342極大值節點和極小值節點遍歷算法

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

343剪枝函數的設計與實現

運用電腦強大的運算能力對整個對戰樹進行遍歷搜索。但是遍歷搜索的層數深了也是需要時間的，對10×9的棋盤進行幾層遍歷搜索是需要相當的時間的，極其影響效率，而且好多節點是不需要搜索的，通過裁剪遍歷算法對沒有用的節點分支進行裁剪，這樣大大地提高效率[4]。

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

5結論

本文通過對中國象棋游戲設計與實現的思想進行分析，介紹了棋盤、棋子、走棋、走棋棧等重要數據結構。設定棋子走棋規則，滿足每個棋子特定的走棋規則。探討了走法生成器的設計與實現，對搜索遍歷算法的運用。對每個棋子的價值進行擬定，對其所能到達位置的價值進行計算。系統還有很多地方有待進一步優化，例如，遍歷搜索算法、剪枝算法等。這些會在以后的文章中再進行探討。

參考文獻：

[1]韓偉，任建敏，吳瑞芳基于數據庫技術的中國象棋軟件開局庫的設計與實現[J].科學技術與工程，1998（3）：556

[2]徐心和，王驕中國象棋計算機博弈關鍵技術分析[J].小型微型計算機系統，2006（6）：3-5

[3]危春波中國象棋系統的研究與實現[D].昆明：昆明理工大學，2000

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