版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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 編寫語言1</p><p> 1.3 編寫工具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 車的走法生成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 車的走法生成10</p><p> 4.1.4 兵的走法生成10</p><p> 4.2 搜索算法11</p><p> 4.2.1 搜索樹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 編寫語言</b></p><p><b> C++</b></p><p><b> 1.3 編寫工具</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><p> ? 判斷n是否被本方棋子占據(jù)。</p><p> 不同棋子應(yīng)考慮的問題:</p><p> ? 將、士是否走出九宮。</p>&l
10、t;p> ? 象是否過河,象眼是否被堵。</p><p><b> ? 馬是否蹩腳。</b></p><p> ? 炮要翻山吃子。</p><p> ? 兵過河前只能前進(jìn),過河后可以前進(jìn)和左右移動(dòng)。</p><p> (1)各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等
11、(這里需要特別注意的是卒的行子規(guī)則隨其所在位置不同而會(huì)發(fā)生變化——過河后可以左右平移)。</p><p> (2)行子不能越出棋盤界限。當(dāng)然所有子都不能走到棋盤的外面,同時(shí)某些特定的子還有自己的行棋界限,如將、士不能出九宮,象不能過河。</p><p> (3)行子的半路上不能有子阻攔(除了炮隔子打子之外)以及行子的目的點(diǎn)不能有本方棋子(當(dāng)然不能自己吃自己了)。</p>
12、<p> (4)將帥不能碰面(本程序中只認(rèn)為將帥碰面是非法的,而其它“送死”的著法并不非法,只是產(chǎn)生敗局罷了)</p><p> 產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用,由于搜索會(huì)搜索多層(即考慮雙方你來我往好幾步,這樣才有利于對(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è)問題像樹一樣展開,問題復(fù)雜度呈幾何指數(shù)
14、上</p><p><b> 2.3 局面評(píng)估</b></p><p> 局面評(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)行比較,從而得到有利得局面,并得到合適的走
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 車的走法生成</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是否在棋盤上</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> 沒有,轉(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是否在棋盤上</b></p><p><b> 是,轉(zhuǎn)第6步</b></p><p><b> 否,轉(zhuǎn)第2步</b></p><p><b> n位置上是否有棋子</b></p><p><b>
25、; 沒有棋子</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 車的走法生成</p><p> 輸入:車的位置position</p><p&
27、gt; 輸出:車的所有可能走法</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>
28、;<p><b> 是,轉(zhuǎn)第6步</b></p><p><b> 否,轉(zhuǎn)第2步</b></p><p> next位置上是否有棋子</p><p> 沒有,保存可行走法,考慮下一位置轉(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><p><b> 是,轉(zhuǎn)第5步</b></p><p>
31、;<b> 否,轉(zhuǎn)第2步</b></p><p><b> 是否未過河橫向移動(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 搜索樹</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=無窮大</p><p> 黑方,best=無窮小<
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à)值。詳見下表:</p><p> 根據(jù)基本價(jià)值,可以得到一個(gè)最初的評(píng)估算法:</p><p><b> 輸入:棋盤數(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ù)組來表示在不同棋子在不同位置的分值:</p><p> static const unsigned char PositionValues[2][7][256] ; </p><p> 第一維表示走方,0為黑方,1為紅方,第二維表示棋子種類,0到6分別表示士、象、炮、將、馬、卒、車,第三維表示位置。</p><p> 位置分值根據(jù)棋手多年的經(jīng)驗(yàn)而得,有些難
43、以量化,只能盡量模擬。</p><p> 4.3.3 棋子靈活性分值</p><p> 棋子所在位置的重要性,通過位置分值已經(jīng)體現(xiàn)。但即使是在同一位置,如果周圍全是棋子,限制了棋子的靈活性,這樣往往會(huì)陷入被動(dòng)挨打的局面。由此可見,靈活性在行棋中還是占有相當(dāng)重要的作用。</p><p><b> 棋子靈活性的度量:</b></p>
44、;<p> 棋子靈活性的度量只能以棋子能走棋步數(shù)來體現(xiàn),能走的位置越多,靈活性越高。因此,在估值函數(shù)中計(jì)算每一個(gè)棋子的行棋步數(shù),然后再給以一定分值的獎(jiǎng)勵(lì)。</p><p> 各個(gè)棋子的靈活性分值分別為:</p><p> 將:2,士:2,馬:5,車:4,炮:3,卒:2</p><p> 棋子每有一種走法,就增加一個(gè)靈活性分值。</p>
45、;<p> 4.3.4 其他復(fù)雜的局面評(píng)估</p><p> 一盤棋局的局勢(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),都可以說是協(xié)作。還有一些固定的進(jìn)攻組合和防守組合,也應(yīng)該考慮,如馬炮,車馬,過河卒連在一起,擔(dān)子炮,等等。</p><p> 當(dāng)一個(gè)棋子收到對(duì)方棋子的攻擊時(shí),就是受到對(duì)方棋子的牽制,應(yīng)該減分。</p><p><b> 還有更多的因素:</b></p><p> 區(qū)域合作問題,典型的三子歸邊。凡有車、馬、炮等三個(gè)進(jìn)攻
47、性的棋子集結(jié)在一起,就有可能構(gòu)成各種殺勢(shì)。</p><p> 對(duì)將得威脅。如,車炮置中路或底路,都有潛在對(duì)將的威脅。</p><p> 每一種情況的加分減分只有通過實(shí)驗(yàn)來解決。設(shè)置不同的加減分值,看程序如何表現(xiàn),通過不斷調(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> 通過本次課程設(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編寫窗口程序。</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++中國象棋程序入門與提高. 電子工業(yè)出版社, 2009:1-166</p>
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)----huffman編碼
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
- 數(shù)據(jù)結(jié)構(gòu)迷宮課程設(shè)計(jì)
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---迷宮
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (3)
評(píng)論
0/150
提交評(píng)論