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

象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄1．軟硬件運(yùn)行環(huán)境 ．軟硬件運(yùn)行環(huán)境1.1運(yùn)行環(huán)境WindowsXP，Windows7。1.2編寫語言C++1.3編寫工具VisualC++6.0象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第2頁。2．算法設(shè)計(jì)思想2.1走法生成走法就是一個(gè)棋子從一個(gè)位置移動(dòng)到另一個(gè)位置。所以走法包含三要素：棋子、起點(diǎn)、終點(diǎn)。每種棋子都有自己的行走規(guī)則，計(jì)算機(jī)程序進(jìn)行走法生成，都是先窮舉再排除。即先列舉出全部可能的位置，再一個(gè)一個(gè)除去不合規(guī)則的走法，剩下的就是合理的走法。不同棋子走法生成的共同點(diǎn)：找出棋子的下一個(gè)可能位置n。?判斷n是否在棋盤上。?判斷n是否被本方棋子占據(jù)。不同棋子應(yīng)考慮的問題：?將、士是否走出九宮。?象是否過河，象眼是否被堵。?馬是否蹩腳。?炮要翻山吃子。?兵過河前只能前進(jìn)，過河后可以前進(jìn)和左右移動(dòng)。(1)各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等（這里需要特別注意的是卒的行子規(guī)則隨其所在位置不同而會(huì)發(fā)生變化——過河后可以左右平移）。(2)行子不能越出棋盤界限。當(dāng)然所有子都不能走到棋盤的外面，同時(shí)某些特定的子還有自己的行棋界限，如將、士不能出九宮，象不能過河。(3)行子的半路上不能有子阻攔（除了炮隔子打子之外）以及行子的目的點(diǎn)不能有本方棋子（當(dāng)然不能自己吃自己了）。(4)將帥不能碰面（本程序中只認(rèn)為將帥碰面是非法的，而其它“送死”的著法并不非法，只是產(chǎn)生敗局罷了）產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來我往好幾步，這樣才有利于對(duì)局面進(jìn)行評(píng)估而盡可能避免“目光短淺”），所以在存著法隊(duì)列的時(shí)候還要同時(shí)存儲(chǔ)該著法所屬的搜索層數(shù)。因此我將著法隊(duì)列定義為二維數(shù)組MoveList[12][80]，第一個(gè)下標(biāo)為層數(shù)，第二個(gè)下標(biāo)為每一層的全部著法數(shù)。2.2選擇最佳走法考慮到下棋的情景。棋局進(jìn)行到某個(gè)時(shí)候，輪到電腦走棋。電腦可能有幾十種走法，但它只能選擇一個(gè)走法。電腦走任何一步棋，局面發(fā)生變化輪到人走棋，人也可能有幾十種走法，他也只能選擇一個(gè)。電腦要考慮每一個(gè)走法的好壞，同時(shí)也要考慮它走了之后人會(huì)如何走棋。整個(gè)問題像樹一樣展開，問題復(fù)雜度呈幾何指數(shù)上象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第3頁。2.3局面評(píng)估局面評(píng)估，也可以說是局面估值，就是判斷局面對(duì)某一方的優(yōu)勢(shì)，并把優(yōu)勢(shì)進(jìn)行量化。在象棋程序中如果說搜索算法是心臟，那么局面評(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)行比較，從而得到有利得局面，并得到合適的走法。局面評(píng)估中需要考慮幾個(gè)因素包括如下四點(diǎn)：(1)棋子價(jià)值評(píng)估(2)棋子位置分值（控制區(qū)域）(3)棋子靈活性分值(4)其他復(fù)雜的局面評(píng)估象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第4頁。3．算法的流程圖3.1走法生成3.1.1馬的走法生成如圖3-1所示：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第5頁。圖象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第5頁。3.1.2兵的走法生成如圖3-2所示：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第6頁。圖3-象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第6頁。3.1.3炮的走法生成如圖3-3所示：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第7頁。圖3-象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第7頁。3.1.4車的走法生成如圖3-4所示：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第8頁。圖3-4

3.1.5搜索算法象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第8頁。圖3-4如圖3-5所示：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第9頁。圖3-5象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第9頁。4．算法的實(shí)現(xiàn)與分析4.1走法生成4.1.1馬的走法生成輸入：馬的位置p輸出：馬的所有可能走法現(xiàn)在位置p八個(gè)可行方向（i=0…7）計(jì)算下一個(gè)位置nn是否在棋盤上是，轉(zhuǎn)第5步否，轉(zhuǎn)第2步從p到n的馬腿位置m上是否有棋子有，轉(zhuǎn)第2步?jīng)]有，轉(zhuǎn)第6步n是否被本方棋子占據(jù)是，轉(zhuǎn)第2步否，保存可行的走法，考慮下一位置轉(zhuǎn)第2步4.1.2炮的走法生成輸入：炮的位置p輸出：炮的所有可能走法現(xiàn)在位置p四個(gè)可行方向翻山標(biāo)志0，OverFlag=0沿這個(gè)方向繼續(xù)前進(jìn)一步（最多前進(jìn)9步）計(jì)算下一個(gè)位置nn是否在棋盤上是，轉(zhuǎn)第6步否，轉(zhuǎn)第2步n位置上是否有棋子沒有棋子 如果OverFlag==0，保存可行的走法（不吃子走法），轉(zhuǎn)第3步 否則，轉(zhuǎn)第3步有棋子則 如果OverFlag==0，則令OverFlag=1（翻山）否則，該棋子是否為本方棋子 不是，保存可行的走法（吃子走法），轉(zhuǎn)第2步 是，轉(zhuǎn)第2步象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第10頁。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第10頁。4.1.3車的走法生成輸入：車的位置position輸出：車的所有可能走法現(xiàn)在位置position四個(gè)可行方向//第一重循環(huán)沿著這個(gè)方向繼續(xù)前進(jìn)一步（最多9步）//第二重循環(huán)計(jì)算下一位置nextnext是否在棋盤上是，轉(zhuǎn)第6步否，轉(zhuǎn)第2步next位置上是否有棋子沒有，保存可行走法，考慮下一位置轉(zhuǎn)第3步（不吃子走法）有棋子，判斷該棋子是否本方棋子 是，轉(zhuǎn)第2步 否，保存可行走法，考慮下一位置轉(zhuǎn)第2步（吃子走法）4.1.4兵的走法生成輸入：兵的位置position輸出：兵的所有可能的走法現(xiàn)在的位置position三個(gè)可行方向計(jì)算下一個(gè)位置next=position+PawnDir[side][n];Next是否在棋盤上是，轉(zhuǎn)第5步否，轉(zhuǎn)第2步是否未過河橫向移動(dòng)是，轉(zhuǎn)第2步否，轉(zhuǎn)第6步next是否被本方棋子占據(jù)是，轉(zhuǎn)第2步否，保存可行走法，考慮下一位置轉(zhuǎn)第2步象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第11頁。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第11頁。4.2搜索算法4.2.1搜索樹定義搜索深度depth，本方最優(yōu)值best返回值valuesearch(depth,best,worst){紅方走棋時(shí)，best=無窮大黑方，best=無窮小若深度小于等于0，調(diào)用局面評(píng)估函數(shù)分析局面若深度大于0，調(diào)用生成走法函數(shù)，并判斷可用走法。for每一個(gè)可用走法執(zhí)行走法遞歸調(diào)用搜索函數(shù)value=-search();depth-1;撤銷算法If紅方走棋If(value>best)Best=valueIf(depth=Maxdepth)//Maxdepth為設(shè)置的最多搜索層數(shù)Bestmove=當(dāng)前走法ElseIf(value<best)Best=valueIf(depth=Maxdepth)Bestmove=當(dāng)前走法Returnbest}象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第12頁。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第12頁。4.3局面評(píng)估4.3.1棋子價(jià)值評(píng)估不同的棋子都有不同的價(jià)值。詳見下表：卒士象馬炮車將1020204045901000根據(jù)基本價(jià)值，可以得到一個(gè)最初的評(píng)估算法：輸入：棋盤數(shù)組輸出：局面估值wValue：紅方棋子價(jià)值的總和bValue：黑方棋子價(jià)值的總和wValue=bValue=0;1行變量row=3to12 2列變量list=3to11 對(duì)應(yīng)一維數(shù)組下標(biāo)chessman=row<<4+j; 如果chessman位置已出界，則 返回第2步 pc為chessman位置對(duì)應(yīng)的棋子 如果pc為紅方棋子，則 wValue+=pc棋子對(duì)應(yīng)的子力值 否則 bValue+=pc棋子對(duì)應(yīng)的子力值returnwValue–bValue4.3.2棋子位置分值一個(gè)棋子在棋局中的真正價(jià)值，不僅與固定分值有關(guān)，還與所處位置有關(guān)。定義一個(gè)三維數(shù)組來表示在不同棋子在不同位置的分值： staticconstunsignedcharPositionValues[2][7][256]; 第一維表示走方，0為黑方，1為紅方，第二維表示棋子種類，0到6分別表示士、象、炮、將、馬、卒、車，第三維表示位置。 位置分值根據(jù)棋手多年的經(jīng)驗(yàn)而得，有些難以量化，只能盡量模擬。4.3.3棋子靈活性分值棋子所在位置的重要性，通過位置分值已經(jīng)體現(xiàn)。但即使是在同一位置，如果周圍全是棋子，限制了棋子的靈活性，這樣往往會(huì)陷入被動(dòng)挨打的局面。由此可見，靈活性在行棋中還是占有相當(dāng)重要的作用。棋子靈活性的度量：棋子靈活性的度量只能以棋子能走棋步數(shù)來體現(xiàn)，能走的位置越多，靈活性越高。因此，在估值函數(shù)中計(jì)算每一個(gè)棋子的行棋步數(shù)，然后再給以一定分值的獎(jiǎng)勵(lì)。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第13頁。各個(gè)棋子的靈活性分值分別為：象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第13頁。將：2，士：2，馬：5，車：4，炮：3，卒：2棋子每有一種走法，就增加一個(gè)靈活性分值。4.3.4其他復(fù)雜的局面評(píng)估一盤棋局的局勢(shì)跟本方棋子間的協(xié)作有關(guān)，跟對(duì)方棋子的牽制有關(guān)。馬踏在九宮格附近威脅較大，應(yīng)該加分，而當(dāng)馬踏在四條邊線上時(shí)，因走法受限很容易被對(duì)方攻擊，應(yīng)該減分。當(dāng)兩個(gè)馬踏成連環(huán)馬時(shí)，威力比兩個(gè)單馬要大，這是棋子之間的協(xié)作，應(yīng)該加分。一個(gè)棋子處于另一個(gè)棋子的保護(hù)范圍內(nèi)，都可以說是協(xié)作。還有一些固定的進(jìn)攻組合和防守組合，也應(yīng)該考慮，如馬炮，車馬，過河卒連在一起，擔(dān)子炮，等等。當(dāng)一個(gè)棋子收到對(duì)方棋子的攻擊時(shí)，就是受到對(duì)方棋子的牽制，應(yīng)該減分。還有更多的因素：區(qū)域合作問題，典型的三子歸邊。凡有車、馬、炮等三個(gè)進(jìn)攻性的棋子集結(jié)在一起，就有可能構(gòu)成各種殺勢(shì)。對(duì)將得威脅。如，車炮置中路或底路，都有潛在對(duì)將的威脅。每一種情況的加分減分只有通過實(shí)驗(yàn)來解決。設(shè)置不同的加減分值，看程序如何表現(xiàn)，通過不斷調(diào)整，最后達(dá)到一個(gè)相對(duì)合理的值。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第14頁。

象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第14頁。5．運(yùn)行結(jié)果與分析運(yùn)行正常，所有的錯(cuò)誤操作都有判斷。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第15頁。象棋數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全文共17頁，當(dāng)前為第15頁。6．總結(jié)通過本次課程設(shè)計(jì)課，我們的編程能力得到了加強(qiáng)，而且使我們更深刻的體會(huì)到數(shù)據(jù)結(jié)構(gòu)與算法的重要性。為了讓電腦能更快速的做出更準(zhǔn)確的判斷，我們不斷改進(jìn)算法。在技術(shù)上，知道了很多先進(jìn)的算法，例如Alpha-Beta搜索算法。還學(xué)會(huì)了用MFC編寫窗口程序。在團(tuán)隊(duì)合作上，我