象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、<p><b>　　目 錄</b></p><p>　　1．軟硬件運(yùn)行環(huán)境1</p><p>　　1.1 運(yùn)行環(huán)境1</p><p>　　1.2 編寫(xiě)語(yǔ)言1</p><p>　　1.3 編寫(xiě)工具1</p><p>　　2．算法設(shè)計(jì)思想2</p><p>

2、;　　2.1 走法生成2</p><p>　　2.2 選擇最佳走法2</p><p>　　2.3 局面評(píng)估3</p><p>　　3．算法的流程圖4</p><p>　　3.1 走法生成4</p><p>　　3.1.1 馬的走法生成4</p><p>　　3.1.2 兵的走法生成

3、5</p><p>　　3.1.3 炮的走法生成6</p><p>　　3.1.4 車(chē)的走法生成7</p><p>　　3.1.5 搜索算法8</p><p>　　4．算法的實(shí)現(xiàn)與分析9</p><p>　　4.1 走法生成9</p><p>　　4.1.1 馬的走法生成9</

4、p><p>　　4.1.2 炮的走法生成9</p><p>　　4.1.3 車(chē)的走法生成10</p><p>　　4.1.4 兵的走法生成10</p><p>　　4.2 搜索算法11</p><p>　　4.2.1 搜索樹(shù)11</p><p>　　4.3 局面評(píng)估12</p>

5、;<p>　　4.3.1 棋子價(jià)值評(píng)估12</p><p>　　4.3.2 棋子位置分值12</p><p>　　4.3.3 棋子靈活性分值12</p><p>　　4.3.4 其他復(fù)雜的局面評(píng)估13</p><p>　　5．運(yùn)行結(jié)果與分析14</p><p><b>　　6．總結(jié)1

6、5</b></p><p><b>　　參考文獻(xiàn)16</b></p><p><b>　　1．軟硬件運(yùn)行環(huán)境</b></p><p><b>　　1.1 運(yùn)行環(huán)境</b></p><p>　　Windows XP，Windows 7。</p><

7、;p><b>　　1.2 編寫(xiě)語(yǔ)言</b></p><p><b>　　C++</b></p><p><b>　　1.3 編寫(xiě)工具</b></p><p>　　Visual C++ 6.0</p><p><b>　　2．算法設(shè)計(jì)思想</b><

8、;/p><p><b>　　2.1 走法生成</b></p><p>　　走法就是一個(gè)棋子從一個(gè)位置移動(dòng)到另一個(gè)位置。所以走法包含三要素：棋子、起點(diǎn)、終點(diǎn)。</p><p>　　每種棋子都有自己的行走規(guī)則，計(jì)算機(jī)程序進(jìn)行走法生成，都是先窮舉再排除。即先列舉出全部可能的位置，再一個(gè)一個(gè)除去不合規(guī)則的走法，剩下的就是合理的走法。</p>

9、<p>　　不同棋子走法生成的共同點(diǎn)：</p><p>　　找出棋子的下一個(gè)可能位置n。</p><p>　　? 判斷n是否在棋盤(pán)上。</p><p>　　? 判斷n是否被本方棋子占據(jù)。</p><p>　　不同棋子應(yīng)考慮的問(wèn)題：</p><p>　　? 將、士是否走出九宮。</p>&l

10、t;p>　　? 象是否過(guò)河，象眼是否被堵。</p><p><b>　　? 馬是否蹩腳。</b></p><p>　　? 炮要翻山吃子。</p><p>　　? 兵過(guò)河前只能前進(jìn)，過(guò)河后可以前進(jìn)和左右移動(dòng)。</p><p>　　(1)各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等

11、（這里需要特別注意的是卒的行子規(guī)則隨其所在位置不同而會(huì)發(fā)生變化——過(guò)河后可以左右平移）。</p><p>　　(2)行子不能越出棋盤(pán)界限。當(dāng)然所有子都不能走到棋盤(pán)的外面，同時(shí)某些特定的子還有自己的行棋界限，如將、士不能出九宮，象不能過(guò)河。</p><p>　　(3)行子的半路上不能有子阻攔（除了炮隔子打子之外）以及行子的目的點(diǎn)不能有本方棋子（當(dāng)然不能自己吃自己了）。</p>

12、<p>　　(4)將帥不能碰面（本程序中只認(rèn)為將帥碰面是非法的，而其它“送死”的著法并不非法，只是產(chǎn)生敗局罷了）</p><p>　　產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來(lái)我往好幾步，這樣才有利于對(duì)局面進(jìn)行評(píng)估而盡可能避免“目光短淺” ），所以在存著法隊(duì)列的時(shí)候還要同時(shí)存儲(chǔ)該著法所屬的搜索層數(shù)。因此我將著法隊(duì)列定義為二維數(shù)組MoveList[12][80]，第一個(gè)

13、下標(biāo)為層數(shù)，第二個(gè)下標(biāo)為每一層的全部著法數(shù)。</p><p>　　2.2 選擇最佳走法</p><p>　　考慮到下棋的情景。棋局進(jìn)行到某個(gè)時(shí)候，輪到電腦走棋。電腦可能有幾十種走法，但它只能選擇一個(gè)走法。電腦走任何一步棋，局面發(fā)生變化輪到人走棋，人也可能有幾十種走法，他也只能選擇一個(gè)。電腦要考慮每一個(gè)走法的好壞，同時(shí)也要考慮它走了之后人會(huì)如何走棋。整個(gè)問(wèn)題像樹(shù)一樣展開(kāi)，問(wèn)題復(fù)雜度呈幾何指數(shù)

14、上</p><p><b>　　2.3 局面評(píng)估</b></p><p>　　局面評(píng)估，也可以說(shuō)是局面估值，就是判斷局面對(duì)某一方的優(yōu)勢(shì)，并把優(yōu)勢(shì)進(jìn)行量化。在象棋程序中如果說(shuō)搜索算法是心臟，那么局面評(píng)估就是大腦。搜索算法負(fù)責(zé)驅(qū)動(dòng)整個(gè)程序，而局面評(píng)估則負(fù)責(zé)對(duì)搜索的內(nèi)容進(jìn)行判斷評(píng)價(jià)對(duì)局面進(jìn)行評(píng)估并量化結(jié)果的目的是為了在多個(gè)局面之間進(jìn)行比較，從而得到有利得局面，并得到合適的走

15、法。局面評(píng)估中需要考慮幾個(gè)因素包括如下四點(diǎn)：</p><p><b>　　(1)棋子價(jià)值評(píng)估</b></p><p>　　(2)棋子位置分值（控制區(qū)域）</p><p>　　(3)棋子靈活性分值</p><p>　　(4)其他復(fù)雜的局面評(píng)估</p><p><b>　　3．算法的流程圖&

16、lt;/b></p><p><b>　　3.1 走法生成</b></p><p>　　3.1.1 馬的走法生成</p><p><b>　　如圖3-1所示：</b></p><p><b>　　圖 3-1</b></p><p>　　3.1.2

17、兵的走法生成</p><p><b>　　如圖3-2所示：</b></p><p><b>　　圖 3-2</b></p><p>　　3.1.3 炮的走法生成</p><p><b>　　如圖3-3所示：</b></p><p><b>　　

18、圖 3-3</b></p><p>　　3.1.4 車(chē)的走法生成</p><p><b>　　如圖3-4所示：</b></p><p>　　3.1.5 搜索算法</p><p><b>　　如圖3-5所示：</b></p><p><b>　　圖 3-5

19、</b></p><p>　　4．算法的實(shí)現(xiàn)與分析</p><p><b>　　4.1 走法生成</b></p><p>　　4.1.1 馬的走法生成</p><p><b>　　輸入：馬的位置p</b></p><p>　　輸出：馬的所有可能走法</p&g

20、t;<p><b>　　現(xiàn)在位置p</b></p><p>　　八個(gè)可行方向（i=0…7）</p><p><b>　　計(jì)算下一個(gè)位置n</b></p><p><b>　　n是否在棋盤(pán)上</b></p><p><b>　　是，轉(zhuǎn)第5步</b&g

21、t;</p><p><b>　　否，轉(zhuǎn)第2步</b></p><p>　　從p到n的馬腿位置m上是否有棋子</p><p><b>　　有，轉(zhuǎn)第2步</b></p><p><b>　　沒(méi)有，轉(zhuǎn)第6步</b></p><p>　　n是否被本方棋子占據(jù)&

22、lt;/p><p><b>　　是，轉(zhuǎn)第2步</b></p><p>　　否，保存可行的走法，考慮下一位置轉(zhuǎn)第2步</p><p>　　4.1.2 炮的走法生成</p><p><b>　　輸入：炮的位置p</b></p><p>　　輸出：炮的所有可能走法</p>

23、<p><b>　　現(xiàn)在位置p</b></p><p><b>　　四個(gè)可行方向</b></p><p>　　翻山標(biāo)志0，OverFlag=0</p><p>　　沿這個(gè)方向繼續(xù)前進(jìn)一步（最多前進(jìn)9步）</p><p><b>　　計(jì)算下一個(gè)位置n</b></

24、p><p><b>　　n是否在棋盤(pán)上</b></p><p><b>　　是，轉(zhuǎn)第6步</b></p><p><b>　　否，轉(zhuǎn)第2步</b></p><p><b>　　n位置上是否有棋子</b></p><p><b>

25、;　　沒(méi)有棋子</b></p><p>　　如果OverFlag==0，保存可行的走法（不吃子走法），轉(zhuǎn)第3步</p><p><b>　　否則，轉(zhuǎn)第3步</b></p><p><b>　　有棋子則</b></p><p>　　如果OverFlag==0，則令OverFlag=1（翻山

26、）</p><p>　　否則，該棋子是否為本方棋子</p><p>　　不是，保存可行的走法（吃子走法），轉(zhuǎn)第2步</p><p><b>　　是，轉(zhuǎn)第2步</b></p><p>　　4.1.3 車(chē)的走法生成</p><p>　　輸入：車(chē)的位置position</p><p&

27、gt;　　輸出：車(chē)的所有可能走法</p><p>　　現(xiàn)在位置position</p><p>　　四個(gè)可行方向 //第一重循環(huán)</p><p>　　沿著這個(gè)方向繼續(xù)前進(jìn)一步（最多9步） //第二重循環(huán)</p><p>　　計(jì)算下一位置next</p><p>　　next是否在棋盤(pán)上</p>

28、;<p><b>　　是，轉(zhuǎn)第6步</b></p><p><b>　　否，轉(zhuǎn)第2步</b></p><p>　　next位置上是否有棋子</p><p>　　沒(méi)有，保存可行走法，考慮下一位置轉(zhuǎn)第3步（不吃子走法）</p><p>　　有棋子，判斷該棋子是否本方棋子</p>

29、<p><b>　　是，轉(zhuǎn)第2步</b></p><p>　　否，保存可行走法，考慮下一位置轉(zhuǎn)第2步（吃子走法）</p><p>　　4.1.4 兵的走法生成</p><p>　　輸入：兵的位置position</p><p>　　輸出：兵的所有可能的走法</p><p>　　現(xiàn)在的

30、位置position</p><p><b>　　三個(gè)可行方向</b></p><p>　　計(jì)算下一個(gè)位置next=position+PawnDir[side][n];</p><p>　　Next是否在棋盤(pán)上</p><p><b>　　是，轉(zhuǎn)第5步</b></p><p>

31、;<b>　　否，轉(zhuǎn)第2步</b></p><p><b>　　是否未過(guò)河橫向移動(dòng)</b></p><p><b>　　是，轉(zhuǎn)第2步</b></p><p><b>　　否，轉(zhuǎn)第6步</b></p><p>　　next是否被本方棋子占據(jù)</p>

32、;<p><b>　　是，轉(zhuǎn)第2步</b></p><p>　　否，保存可行走法，考慮下一位置轉(zhuǎn)第2步</p><p><b>　　4.2 搜索算法</b></p><p><b>　　4.2.1 搜索樹(shù)</b></p><p>　　定義搜索深度depth，本方最

33、優(yōu)值best</p><p><b>　　返回值value</b></p><p>　　search(depth,best,worst)</p><p><b>　　{</b></p><p>　　紅方走棋時(shí)，best=無(wú)窮大</p><p>　　黑方，best=無(wú)窮小<

34、;/p><p>　　若深度小于等于0，調(diào)用局面評(píng)估函數(shù)分析局面</p><p>　　若深度大于0，調(diào)用生成走法函數(shù)，并判斷可用走法。</p><p>　　for每一個(gè)可用走法</p><p><b>　　執(zhí)行走法</b></p><p>　　遞歸調(diào)用搜索函數(shù)value = - search(); de

35、pth -1;</p><p><b>　　撤銷算法</b></p><p><b>　　If 紅方走棋</b></p><p>　　If(value >best)</p><p>　　Best=value</p><p>　　If(depth=Maxdepth) //

36、Maxdepth為設(shè)置的最多搜索層數(shù)</p><p>　　Bestmove = 當(dāng)前走法</p><p><b>　　Else</b></p><p>　　If(value<best)</p><p>　　Best=value</p><p>　　If(depth=Maxdepth)<

37、/p><p>　　Bestmove=當(dāng)前走法</p><p>　　Return best</p><p><b>　　}</b></p><p><b>　　4.3 局面評(píng)估</b></p><p>　　4.3.1 棋子價(jià)值評(píng)估</p><p>　　不同的

38、棋子都有不同的價(jià)值。詳見(jiàn)下表：</p><p>　　根據(jù)基本價(jià)值，可以得到一個(gè)最初的評(píng)估算法：</p><p><b>　　輸入：棋盤(pán)數(shù)組</b></p><p><b>　　輸出：局面估值</b></p><p>　　wValue：紅方棋子價(jià)值的總和</p><p>　　b

39、Value：黑方棋子價(jià)值的總和</p><p>　　wValue = bValue = 0 ;</p><p>　　1 行變量 row = 3 to 12</p><p>　　2 列變量 list = 3 to 11</p><p>　　對(duì)應(yīng)一維數(shù)組下標(biāo)chessman = row<<4 + j ;</p><

40、p>　　如果chessman位置已出界，則</p><p><b>　　返回第2步</b></p><p>　　pc為chessman位置對(duì)應(yīng)的棋子</p><p>　　如果pc為紅方棋子，則</p><p>　　wValue += pc棋子對(duì)應(yīng)的子力值</p><p><b>　

41、　否則</b></p><p>　　bValue += pc棋子對(duì)應(yīng)的子力值</p><p>　　return wValue – bValue</p><p>　　4.3.2 棋子位置分值</p><p>　　一個(gè)棋子在棋局中的真正價(jià)值，不僅與固定分值有關(guān)，還與所處位置有關(guān)。</p><p>　　定義一個(gè)三

42、維數(shù)組來(lái)表示在不同棋子在不同位置的分值：</p><p>　　static const unsigned char PositionValues[2][7][256] ; </p><p>　　第一維表示走方，0為黑方，1為紅方，第二維表示棋子種類，0到6分別表示士、象、炮、將、馬、卒、車(chē)，第三維表示位置。</p><p>　　位置分值根據(jù)棋手多年的經(jīng)驗(yàn)而得，有些難

43、以量化，只能盡量模擬。</p><p>　　4.3.3 棋子靈活性分值</p><p>　　棋子所在位置的重要性，通過(guò)位置分值已經(jīng)體現(xiàn)。但即使是在同一位置，如果周?chē)瞧遄?，限制了棋子的靈活性，這樣往往會(huì)陷入被動(dòng)挨打的局面。由此可見(jiàn)，靈活性在行棋中還是占有相當(dāng)重要的作用。</p><p><b>　　棋子靈活性的度量：</b></p>

44、;<p>　　棋子靈活性的度量只能以棋子能走棋步數(shù)來(lái)體現(xiàn)，能走的位置越多，靈活性越高。因此，在估值函數(shù)中計(jì)算每一個(gè)棋子的行棋步數(shù)，然后再給以一定分值的獎(jiǎng)勵(lì)。</p><p>　　各個(gè)棋子的靈活性分值分別為：</p><p>　　將：2，士：2，馬：5，車(chē)：4，炮：3，卒：2</p><p>　　棋子每有一種走法，就增加一個(gè)靈活性分值。</p>

45、;<p>　　4.3.4 其他復(fù)雜的局面評(píng)估</p><p>　　一盤(pán)棋局的局勢(shì)跟本方棋子間的協(xié)作有關(guān)，跟對(duì)方棋子的牽制有關(guān)。</p><p>　　馬踏在九宮格附近威脅較大，應(yīng)該加分，而當(dāng)馬踏在四條邊線上時(shí)，因走法受限很容易被對(duì)方攻擊，應(yīng)該減分。</p><p>　　當(dāng)兩個(gè)馬踏成連環(huán)馬時(shí)，威力比兩個(gè)單馬要大，這是棋子之間的協(xié)作，應(yīng)該加分。一個(gè)棋子處于另

46、一個(gè)棋子的保護(hù)范圍內(nèi)，都可以說(shuō)是協(xié)作。還有一些固定的進(jìn)攻組合和防守組合，也應(yīng)該考慮，如馬炮，車(chē)馬，過(guò)河卒連在一起，擔(dān)子炮，等等。</p><p>　　當(dāng)一個(gè)棋子收到對(duì)方棋子的攻擊時(shí)，就是受到對(duì)方棋子的牽制，應(yīng)該減分。</p><p><b>　　還有更多的因素：</b></p><p>　　區(qū)域合作問(wèn)題，典型的三子歸邊。凡有車(chē)、馬、炮等三個(gè)進(jìn)攻

47、性的棋子集結(jié)在一起，就有可能構(gòu)成各種殺勢(shì)。</p><p>　　對(duì)將得威脅。如，車(chē)炮置中路或底路，都有潛在對(duì)將的威脅。</p><p>　　每一種情況的加分減分只有通過(guò)實(shí)驗(yàn)來(lái)解決。設(shè)置不同的加減分值，看程序如何表現(xiàn)，通過(guò)不斷調(diào)整，最后達(dá)到一個(gè)相對(duì)合理的值。</p><p><b>　　5．運(yùn)行結(jié)果與分析</b></p><p

48、>　　運(yùn)行正常，所有的錯(cuò)誤操作都有判斷。</p><p><b>　　6．總結(jié)</b></p><p>　　通過(guò)本次課程設(shè)計(jì)課，我們的編程能力得到了加強(qiáng)，而且使我們更深刻的體會(huì)到數(shù)據(jù)結(jié)構(gòu)與算法的重要性。為了讓電腦能更快速的做出更準(zhǔn)確的判斷，我們不斷改進(jìn)算法。</p><p>　　在技術(shù)上，知道了很多先進(jìn)的算法，例如Alpha-Beta搜索

49、算法。還學(xué)會(huì)了用MFC編寫(xiě)窗口程序。</p><p>　　在團(tuán)隊(duì)合作上，我們分工明確，這使得我們的進(jìn)展一直按著計(jì)劃進(jìn)行。同時(shí)，我們的團(tuán)隊(duì)意識(shí)也得到了提高。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　1 蔣鵬, 雷貽祥,陳園園. C\C++中國(guó)象棋程序入門(mén)與提高. 電子工業(yè)出版社, 2009：1-166</p>