算法課程設(shè)計(jì)報(bào)告

1、算法設(shè)計(jì)與分析課程設(shè)計(jì)題目跳棋問題班級(jí)：姓名：學(xué)號(hào)：正文1、課程設(shè)計(jì)報(bào)告1.1問題描述國際跳棋（draughts）也稱西洋跳棋，它的棋盤是由深淺兩色相間的10X10的小方 格 組成的一個(gè)大正方形。國際象棋的棋盤是6 4格的，它比國際象棋的棋盤整整多了一圈。 棋盤上深色的格子叫黑格，淺色的格子叫白格。對(duì)局時(shí)，棋盤放在對(duì)局者中間，雙方左下角 的第一個(gè)格子必須是黑格，不能擺錯(cuò)。與國際象棋不同的是，棋盤上的黑格才是國際跳棋擺 棋子和行棋的地方，無論任何時(shí)候，都不能把任何棋子放到白格中去。對(duì)局時(shí)，棋子的原始 擺法為：20枚白兵排列在已方后四排的黑格內(nèi)，白方棋子同黑，白棋擺在1到20棋位，黑 棋擺在31到

2、50棋位。經(jīng)過一段對(duì)局，任何一方的兵沖破重重障礙，走至并停留在對(duì)方底線， 即升變?yōu)橥跗?，如果沒有停留在對(duì)方底線不能立即成王。王棋可以用兩個(gè)兵摞起來表示，也 可以將兵翻轉(zhuǎn)過來做王棋。兵與王棋的走法：對(duì)局開始，由執(zhí)白棋者先行，然后由黑棋行棋；雙方輪流走子，直到終局。白、黑各走一著 叫一個(gè)回合。對(duì)局開始時(shí)，出現(xiàn)在棋盤上的都是兵。兵在走棋時(shí)，每步棋只能向前方鄰近的 空棋位上向左或向右移動(dòng)一格，并且只能前進(jìn)，不允許后退。兵的吃子法是用跳的形式進(jìn)行 的。這和一般跳棋的走法相似，只要自己的一個(gè)兵與對(duì)方的一枚棋子相遇，并且與這兩枚棋 子成一斜行的、緊挨著對(duì)方棋子的棋位是空著的，那么，輪至走子的一方就要用自己的

3、兵跳 過對(duì)方的棋子，放在緊挨著對(duì)方棋子后面的空棋位上，將對(duì)方的那枚棋子吃掉。吃子時(shí)，可 以象普通跳棋一樣一次連跳連吃幾枚棋子，但連跳時(shí)不允許以自己的棋子為橋梁，也就是說 ，自己的棋子不能從自己的棋子上越過去再去吃對(duì)方的棋子。兵吃子時(shí)可以后退。王棋的走 法與兵不同，它可以前進(jìn)，可以后退，只要在一條斜線上，一次移動(dòng)幾格都可能。王棋的跳 吃，也比兵的跳吃自由度要大得多。只要在同一斜線上，不管距離多么遠(yuǎn)，都可以跳過對(duì)方 的這枚棋子，停在它后而的任何一個(gè)空格里，從而將對(duì)方這枚棋子吃掉。王棋的連跳，與兵 的連跳大致相同，只是不限距離，只要有機(jī)會(huì)，一次可以跳吃對(duì)方的數(shù)枚棋子。吃子的三條重要規(guī)則：第一，能吃子

4、必須吃子，不能不吃；第二，能多吃子，必須多吃，不能少吃；第三，能吃子的時(shí)候必須吃到底，不許半路停下不再吃了 .以上規(guī)則無論是否對(duì)自己有利都必須執(zhí)行.如果將對(duì)方的棋子吃光或者讓對(duì)方?jīng)]有可以走的棋了即為獲勝。1.2需求分析國際跳棋是由各國的民族跳棋演變而來。其歷史源遠(yuǎn)流長是世界上最古老、最普及的智 力游戲之一。傳說國際跳棋起源于6000年前的古埃及，其根據(jù)是古埃及巖畫上有類似的圖 案。1723年，居住在法國的一名波蘭軍官把跳棋革新為10X10的一百格跳棋，國際跳棋被 規(guī)范定型。1894年，首屆國際跳棋世界大賽在法國舉行。目前世界上跳棋水平最高的國家 有法國、荷蘭、俄羅斯等國，亞洲水平最高的是受俄羅

5、斯影響頗深的蒙古。國際跳棋（draughts）也稱西洋跳棋，該項(xiàng)棋種和其它棋類項(xiàng)目一樣有著娛樂、健心益 智、競技等多方面的功能。西洋跳棋在國際上開展較早，世界西洋跳棋聯(lián)合會(huì)于1947年成 立，如今已經(jīng)發(fā)展成為有約50個(gè)會(huì)員協(xié)會(huì)的組織，最近世界西洋跳棋聯(lián)合會(huì)又加入了 “國 際單項(xiàng)體聯(lián)”。世界西洋跳棋聯(lián)合會(huì)還成立了各大洲的分會(huì)。西洋跳棋有自己獨(dú)立的技術(shù)體 系，包括下法、技術(shù)等級(jí)標(biāo)準(zhǔn)、規(guī)則等。世界西洋跳棋聯(lián)合會(huì)舉辦的國際賽事有世界錦標(biāo)賽、 世界女子錦標(biāo)賽、世界青年錦標(biāo)賽、世界學(xué)生錦標(biāo)賽、世界女學(xué)生錦標(biāo)賽、團(tuán)體錦標(biāo)賽、歐 洲錦標(biāo)賽。本軟件需要完成的功能有：（1）用戶能自由完成人機(jī)對(duì)奕和玩家之間對(duì)奕（2

6、）程序可以自動(dòng)記錄各種走法的得分（3）程序可以顯示最高得分的走法（4）儲(chǔ)存并記錄軟件框架設(shè)計(jì)：本程序設(shè)計(jì)有兩部分：窗體結(jié)構(gòu)和算法程序，這樣可以使程序簡潔明了，方便于以后 對(duì)程序的局部修改，也使得本程序更有可讀性。運(yùn)行平臺(tái)：程序采用VB語言，為編程提供了一個(gè)集成開發(fā)環(huán)境。程序員可根據(jù)程序和界面設(shè)計(jì)要 求，直接在屏幕上“畫”出窗口、菜單、按鈕等不同類型的對(duì)象，并為每個(gè)對(duì)象設(shè)置屬性。 VB繼承了 BASIC語言簡單易學(xué)的特點(diǎn)，又適應(yīng)于開發(fā)視窗類應(yīng)用程序，是制作國際跳棋程 序的最好的選擇。1.3概要設(shè)計(jì)窗體結(jié)構(gòu)設(shè)計(jì):新棋.運(yùn)算1澇饑窗體結(jié)構(gòu)設(shè)計(jì):新棋.運(yùn)算1澇饑:如刎1加.如1101101101101

7、101101101101101101101101運(yùn)算謚算2程序界面設(shè)計(jì)如圖，面板分為四個(gè)部分，分別為棋盤，選擇項(xiàng)，算法提示，分?jǐn)?shù)計(jì)算 其中棋盤和算法（走法）提示是主要部分操作區(qū)中，用戶通過對(duì)選項(xiàng)的選擇來使程序完成相應(yīng)的功能，當(dāng)用戶在走每一步的時(shí) 候都會(huì)有相應(yīng)的走法和提示語句，在用戶選擇好走法以后可以單擊存譜按鈕來進(jìn)行存儲(chǔ)。用戶也可以單擊人機(jī)對(duì)戰(zhàn)選項(xiàng)來選擇對(duì)戰(zhàn)目標(biāo)，利用新棋鍵來重新開局如果用戶走的步驟不合法，系統(tǒng)會(huì)彈出提示語來提示用戶，使得本次走棋無效。當(dāng)某 方的的棋子被全部吃掉，判次方輸，棋局結(jié)束。程序算法設(shè)計(jì)：程序算法設(shè)計(jì)控制跳棋程序按跳棋規(guī)則運(yùn)行，此層的設(shè)計(jì)主要分為：1，數(shù)據(jù)初始 化模塊；

8、2,規(guī)則定義模塊；3,搜索算法模塊；初始化模塊:主要完成各數(shù)據(jù)結(jié)構(gòu)的定義和初始化，并為各數(shù)據(jù)結(jié)構(gòu)分配存儲(chǔ)空間， 初始化模塊的許多數(shù)據(jù)結(jié)構(gòu)將會(huì)在其他模塊中被反復(fù)讀入和存儲(chǔ)，初始化模塊中還定義有一 些函數(shù)，負(fù)責(zé)構(gòu)建程序的初始運(yùn)行狀態(tài)，此函數(shù)還可以在運(yùn)行時(shí)有選擇的使程序復(fù)位，方便 用戶的使用。規(guī)則定義模塊：主要完成對(duì)程序運(yùn)行過程中的搜索算法進(jìn)行條件設(shè)定，就是按照國 際跳棋的規(guī)則對(duì)搜索算法進(jìn)行一定限制，使算法的結(jié)果符合國際象棋的規(guī)則，同時(shí)簡化搜索 模塊的設(shè)計(jì)難度和代碼復(fù)雜度。該模塊中由幾個(gè)函數(shù)組成，主要負(fù)責(zé)定義棋子基本的走法， 棋子的吃子走法，其中還包含有邊界檢查，保證棋子落在棋盤內(nèi)。走法得分的計(jì)算，

9、搜索算 法模塊的搜索算法函數(shù)會(huì)調(diào)用該模塊中的函數(shù)來確定搜索的范圍，并會(huì)根據(jù)各走法的得分來 確定最佳的走法，從而得到最優(yōu)解。搜索算法模塊：該模塊就是搜索算法函數(shù)，是整個(gè)程序的核心，該模塊主要完成棋 子的最高得分走法的搜索，用于人機(jī)對(duì)戰(zhàn)模式時(shí)，計(jì)算出機(jī)器的走法。搜索算法通過調(diào)用規(guī) 則定義模塊的函數(shù)確定搜索的范圍，函數(shù)采用遞歸的方式搜索，通過計(jì)算出的當(dāng)前分?jǐn)?shù)與記 錄中最高分進(jìn)行比較，更新記錄的最高分，同時(shí)記錄最高分的走法，當(dāng)遞歸搜索玩所有走法 的解時(shí)通過記錄的最高分得到相應(yīng)的走法。在遞歸搜索過程中還有剪枝操作，以進(jìn)一步減少 搜索的范圍。2源程序代碼Dim ChessBoard(-2 To 10, -

10、2 To 10) As Byte 棋盤(8 豎*8 棋)Dim x(10) As Integer, y(10) As Integer搜索的每種走法Dim x1(10) As Integer, y1(10) As Integer搜索的每種走法的可吃子坐標(biāo)Dim BestLocate As CHESSERDim CurrentPlayer As Byte 當(dāng)前玩家Dim CurrentStep As Integer 當(dāng)前步Dim人機(jī)模式As BooleanDim cSel As Byte玩家選擇了哪個(gè)棋子Dim tTemp As BooleanConst MAXDOWNPOINT = 7Rem如果

11、Cer為1(黑方)，則返回2(紅方)，否則返加1(黑方)Public Function NextCer(ByVal Cer As Byte) As ByteNextCer = 1If Cer = 1 Then NextCer = 2End FunctionRem 棋盤Private Sub Initial()Dim i As Integer, j As IntegerFor i = 1 To 8: For j = 1 To 8: ChessBoard(i, j) = 0: Next j: Next iChessBoard(1, 2)=201ChessBoard(1, 4)=201ChessBo

12、ard(1, 6)=201ChessBoard(1, 8)=201定義新開局的棋子擺放位置ChessBoard(2, 1)=201ChessBoard(2, 3)=201ChessBoard(2, 5)=201ChessBoard(2, 7)=201ChessBoard(3, 2)=201ChessBoard(3, 4)=201ChessBoard(3, 6)=201ChessBoard(3, 8)=201ChessBoard(6, 1)=101ChessBoard(6, 3)=101ChessBoard(6, 5)=101ChessBoard(6, 7)=101ChessBoard(7, 2

13、)=101ChessBoard(7, 4)=101ChessBoard(7, 6)=101ChessBoard(7, 8)=101ChessBoard(8, 1)=101ChessBoard(8, 3) = 101ChessBoard(8, 5) = 101 ChessBoard(8, 7) = 101 End Sub Rem反顯示(將屏幕顯示的內(nèi)容存入ChessBoard數(shù)組) Private Sub ReDisplay()Dim i As Integer, j As Integer, k As Integer k = 0For i = 1 To 8For j = 1 To 8If cbTe

14、xt(k).Text = Then ChessBoard(i, j) = 0 TOC o 1-5 h z If cbText(k).Text=101ThenChessBoard(i,j)=101If cbText(k).Text=201ThenChessBoard(i,j)=201If cbText(k).Text=102ThenChessBoard(i,j)=102If cbText(k).Text=202ThenChessBoard(i,j)=202k = k + 1Next j Next i End SubRem顯示(將ChessBoard數(shù)組的內(nèi)容顯示到屏幕后) Private Sub

15、 Display()Dim i As Integer, j As Integer, k As Integer k = 0For i = 1 To 8For j = 1 To 8If ChessBoard(i, j) = 0 Then cbText(k).Text = Else cbText(k).Text = ChessBoard(i, j) End If k = k + 1 Next j Next i Call勝負(fù)判斷 End SubRem 勝負(fù)判斷Private Sub勝負(fù)判斷()Dim i As Integer, j As Integer Dim a As Integer, b As I

16、nteger a = 0: b = 0 For i = 1 To 8For j = 1 To 8If Int(ChessBoard(i, j) / 100) = 1 Then a = a + 1 計(jì)算玩家的棋子數(shù) If Int(ChessBoard(i, j) / 100) = 2 Then b = b + 1 計(jì)算電腦的棋子數(shù)Next jNext iIf a = 0 Then Call MsgBox(我贏了！ ，vbOKOnly + 32,提示：):Exit SubIf b = 0 Then Call MsgBox(我認(rèn)輸了！ ，vbOKOnly + 32,提示：):Exit SubEnd

17、SubRem返回估值Private Function CurrentValue(Cer As Byte) As IntegerDim i As Integer, j As IntegerCurrentValue = 0For i = 1 To 8For j = 1 To 8If Int(ChessBoard(i, j) / 100) = Cer Then _ CurrentValue = CurrentValue + ChessBoard(i, j) Mod 100 * 100 + 100 是我方的棋子，棋子為1加100分,棋子為2加200分If Int(ChessBoard(i, j) /

18、100) = NextCer(Cer) Then - CurrentValue = CurrentValue - (ChessBoard(i, j) Mod 100 * 100 + 100) 對(duì)方的棋子,棋子為1減100分,棋子為2減200分Next jNext iEnd FunctionRem如果Cer方i,j的棋子還可以吃子則返回TruePrivate Function IsLine(Cer As Byte, i As Byte, j As Byte) As BooleanDim x As Byte, y As Byte, x1 As Byte, y1 As ByteIsLine = Fa

19、lse開始搜索棋盤*如果是Cer方的棋子If Int(ChessBoard(i, j) / 100) = Cer Then吃子式走法1：即如果基本走法的位置有對(duì)方的棋子則可以跳吃(走法 限制：Cer為1或棋子為加強(qiáng)棋才可走)If Int(ChessBoard(i - 1, j - 1) / 100) = NextCer(Cer) And (Cer = 1 Or ChessBoard(i, j) Mod 100 = 2) Thenx = (i - 1) - 1 目標(biāo)坐標(biāo)y = (j - 1) - 1x1 = i - 1吃子坐標(biāo)y1 = j - 1If x 0 And y 0 And x 9 An

20、d y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 0 And y 0 And x 9 And y 9 And ChessBoard(x, y)=0 Then IsLine2 = True 有可吃子，返回 TrueEnd IfEnd IfNext jNext iEnd FunctionRem搜索程序Private Function Search(Cer

21、As Byte, Steps As Integer, IsTop As Boolean, UpMax As Integer)Dim a As Integer, b As Integer, b1 As Integer, b2 As Integer, i As Integer, jAs Integer, k As Integer, l As Integer, v As IntegerDim MaxValue As IntegerDim Sc(40) As CHESSERDim IsEat(7) As Boolean 搜索到的7種走法有沒有吃子Dim EAT As Boolean 有沒有吃子 If

22、IsTop ThenList1.ClearFor i = 0 To 40: Sc(i).Allow = False: Next i 默認(rèn)情況下所有走法皆 不允許，如果所有值均為False則皆允許End IfEAT = FalseFor i = 0 To 7: IsEat(7) = False: Next i默認(rèn)情況所有搜索到的走法都沒有吃子Steps = Steps - 1If Steps 1 And IsLine2(Cer) = False Then，如果我方無子可吃時(shí)才返回估值Search = -CurrentValue(Cer)返回估值 Exit FunctionEnd If k = 0

23、 開始搜索棋盤 For i = 1 To 8For j = 1 To 8*如果是Cer方的棋子If Int(ChessBoard(i, j) / 100) = Cer ThenFor i1 = 1 To MAXDOWNPOINT: x(i1) = 0: x1(i1) = 0: Next xi 記載 所有走法，清空x列出所有走法基本走法：上左、上右、下左、下右 TOC o 1-5 h z x(0)=i-1:y(0)=j-1x(1)=i-1:y(1)=j+1x(2)=i+1:y(2)=j-1x(3)=i+1:y(3)=j+1棋子表示方法：白棋101(普通)、102 (過底的威力棋)紅棋201(普通

24、)、202 (過底的威力棋)下一句解釋：如果是白棋(101、102),不允許后退(刪除x(2)、x(3)If Cer = 1 And ChessBoard(i, j) Mod 100 2 Then x(2) = -2: x = -2下一句解釋：如果是紅棋(201、202),不允許后退(刪除x(0)、x(1) If Cer = 2 And ChessBoard(i, j) Mod 100 2 Then x(0) = -2: x(1)= -2吃子式走法1：即如果基本走法的位置有對(duì)方的棋子則可以跳吃（走法 限制：Cer為1或棋子為加強(qiáng)棋才可走)If Int(ChessBoard(i - 1, j -

25、 1) / 100) = NextCer(Cer) And (Cer = 1 Or ChessBoard(i, j) Mod 100 = 2) Then x(4) = (i - 1) - 1 ，目標(biāo)坐標(biāo) y(4) = (j - 1) - 1 x1(4) = i - 1吃子坐標(biāo)y1(4) = j - 1If x(4) 0 And y(4) 0 And x(4) 9 And y(4) 0 And y(5) 0 And x(5) 9 And y(5) 0 And y(6) 0 And x(6) 9 And y(6) 0 And y(7) 0 And x(7) 9 And y(7) 0 And y(a

26、) 0 And x(a) 9 And y(a) 0 And IsLine(Cer, Sc.ObjX, Sc(i).ObjY) = True And EAT = True Then*如果可連續(xù)吃子v = CurrentValue(Cer) + 300V為當(dāng)前局面價(jià)值加 300 分Elsev = Search(NextCer(Cer), Steps - 1, False, -UpMax)沒有連續(xù)可 吃子，繼續(xù)搜索End If恢復(fù)棋盤ChessBoard(Sc(i).x1, Sc(i).y1) = b 恢復(fù)被吃子ChessBoard(Sc.Initx, Sc(i).Inity) = b1 記錄起點(diǎn)棋

27、子和終點(diǎn)棋子 ChessBoard(Sc.ObjX, Sc(i).ObjY) = b2 顯示每種走法的得分 If IsTop ThenList1.AddItem 從& Str(Sc(i).Initx) & , & Str(Sc(i).Inity) & 到& Str(Sc(i).ObjX) & , & Str(Sc(i).ObjY) & 得分：& Str(v)End If如果這種走法分?jǐn)?shù)高，記錄If IsTop And (v MaxValue Or MaxValue = -30000) Then BestLocate.Initx = Sc(i).Initx BestLocate.Inity =

28、Sc(i).Inity BestLocate.ObjX = Sc(i).ObjX BestLocate.ObjY = Sc(i).ObjY BestLocate.x1 = Sc(i).x1 BestLocate.y1 = Sc(i).y1 MaxValue = vEnd IfIf v MaxValue Then MaxValue = v下句： 如果MaxValue = -UpMax / a-0剪枝，符合剪枝條件的就Cut 掉。UpMax為上層的MaxValueIf IsTop = False And MaxValue = -UpMax Then i = 100 剪枝程序End IfNext i

29、If IsTop = False Then Search = -MaxValue Else Search = MaxValueEnd Function3結(jié)果4測(cè)試程序運(yùn)行過程如下：點(diǎn)擊“新棋”按鈕，棋盤上會(huì)出現(xiàn)用數(shù)字顯示的棋子，101代表己方的普通棋子，201 代表對(duì)方的普通棋子，再點(diǎn)擊“人機(jī)對(duì)戰(zhàn)”按鈕，就可以開始下棋了，棋子只能斜著走，（1）當(dāng)你的落棋位置不符合規(guī)則時(shí)，會(huì)彈出消息提示框，顯示“落棋無效”。（2）當(dāng)你的棋子可以連續(xù)吃子，會(huì)彈出消息提示框，顯示“我還想再吃”。（3）當(dāng)吃子時(shí)會(huì)顯示相應(yīng)的加分或減分。當(dāng)某方的棋子到達(dá)對(duì)方的底線時(shí)，棋子代號(hào) 的最后一位會(huì)變成2代表給棋子變成王棋，王棋的

30、跳吃范圍比普通棋子的跳吃范圍大。（4）當(dāng)電腦的棋子被吃完時(shí)，會(huì)彈出消息提示框，顯示“我認(rèn)輸了”表示你獲勝，電 腦認(rèn)輸。（5）當(dāng)你的棋子被電腦吃完，會(huì)彈出消息提示框，顯示“我贏了 “，表示你輸了，電 腦獲勝。（6）提示：電腦很“聰明”的哦！不懂點(diǎn)腦筋還贏不了它呢！說明我們的算法實(shí)現(xiàn)是 有效正確的。5性能分析初始化模塊：Dim ChessBoard（-2 To 10, -2 To 10） As Byte 棋盤（8 豎*8 棋）Dim x（10） As Integer, y（10） As Integer搜索的每種走法Dim x1（10） As Integer, y1（10） As Integer搜索的每種走法的可吃子坐標(biāo)Dim BestLocate As CHESSERDim CurrentPlayer As Byte當(dāng)前玩家Dim CurrentStep As Integer 當(dāng)前步Dim人機(jī)模式As BooleanDim cSel As By