算法课程设计报告

1、算法设计与分析课程设计题目跳棋问题班级：姓名：学号：正文1、课程设计报告1.1问题描述国际跳棋（draughts）也称西洋跳棋，它的棋盘是由深浅两色相间的10X10的小方 格 组成的一个大正方形。国际象棋的棋盘是6 4格的，它比国际象棋的棋盘整整多了一圈。 棋盘上深色的格子叫黑格，浅色的格子叫白格。对局时，棋盘放在对局者中间，双方左下角 的第一个格子必须是黑格，不能摆错。与国际象棋不同的是，棋盘上的黑格才是国际跳棋摆 棋子和行棋的地方，无论任何时候，都不能把任何棋子放到白格中去。对局时，棋子的原始 摆法为：20枚白兵排列在已方后四排的黑格内，白方棋子同黑，白棋摆在1到20棋位，黑 棋摆在31到

2、50棋位。经过一段对局，任何一方的兵冲破重重障碍，走至并停留在对方底线， 即升变为王棋，如果没有停留在对方底线不能立即成王。王棋可以用两个兵摞起来表示，也 可以将兵翻转过来做王棋。兵与王棋的走法：对局开始，由执白棋者先行，然后由黑棋行棋；双方轮流走子，直到终局。白、黑各走一着 叫一个回合。对局开始时，出现在棋盘上的都是兵。兵在走棋时，每步棋只能向前方邻近的 空棋位上向左或向右移动一格，并且只能前进，不允许后退。兵的吃子法是用跳的形式进行 的。这和一般跳棋的走法相似，只要自己的一个兵与对方的一枚棋子相遇，并且与这两枚棋 子成一斜行的、紧挨着对方棋子的棋位是空着的，那么，轮至走子的一方就要用自己的

3、兵跳 过对方的棋子，放在紧挨着对方棋子后面的空棋位上，将对方的那枚棋子吃掉。吃子时，可 以象普通跳棋一样一次连跳连吃几枚棋子，但连跳时不允许以自己的棋子为桥梁，也就是说 ，自己的棋子不能从自己的棋子上越过去再去吃对方的棋子。兵吃子时可以后退。王棋的走 法与兵不同，它可以前进，可以后退，只要在一条斜线上，一次移动几格都可能。王棋的跳 吃，也比兵的跳吃自由度要大得多。只要在同一斜线上，不管距离多么远，都可以跳过对方 的这枚棋子，停在它后而的任何一个空格里，从而将对方这枚棋子吃掉。王棋的连跳，与兵 的连跳大致相同，只是不限距离，只要有机会，一次可以跳吃对方的数枚棋子。吃子的三条重要规则：第一，能吃子

4、必须吃子，不能不吃；第二，能多吃子，必须多吃，不能少吃；第三，能吃子的时候必须吃到底，不许半路停下不再吃了 .以上规则无论是否对自己有利都必须执行.如果将对方的棋子吃光或者让对方没有可以走的棋了即为获胜。1.2需求分析国际跳棋是由各国的民族跳棋演变而来。其历史源远流长是世界上最古老、最普及的智 力游戏之一。传说国际跳棋起源于6000年前的古埃及，其根据是古埃及岩画上有类似的图 案。1723年，居住在法国的一名波兰军官把跳棋革新为10X10的一百格跳棋，国际跳棋被 规范定型。1894年，首届国际跳棋世界大赛在法国举行。目前世界上跳棋水平最高的国家 有法国、荷兰、俄罗斯等国，亚洲水平最高的是受俄罗

5、斯影响颇深的蒙古。国际跳棋（draughts）也称西洋跳棋，该项棋种和其它棋类项目一样有着娱乐、健心益 智、竞技等多方面的功能。西洋跳棋在国际上开展较早，世界西洋跳棋联合会于1947年成 立，如今已经发展成为有约50个会员协会的组织，最近世界西洋跳棋联合会又加入了 “国 际单项体联”。世界西洋跳棋联合会还成立了各大洲的分会。西洋跳棋有自己独立的技术体 系，包括下法、技术等级标准、规则等。世界西洋跳棋联合会举办的国际赛事有世界锦标赛、 世界女子锦标赛、世界青年锦标赛、世界学生锦标赛、世界女学生锦标赛、团体锦标赛、欧 洲锦标赛。本软件需要完成的功能有：（1）用户能自由完成人机对奕和玩家之间对奕（2

6、）程序可以自动记录各种走法的得分（3）程序可以显示最高得分的走法（4）储存并记录软件框架设计：本程序设计有两部分：窗体结构和算法程序，这样可以使程序简洁明了，方便于以后 对程序的局部修改，也使得本程序更有可读性。运行平台：程序采用VB语言，为编程提供了一个集成开发环境。程序员可根据程序和界面设计要 求，直接在屏幕上“画”出窗口、菜单、按钮等不同类型的对象，并为每个对象设置属性。 VB继承了 BASIC语言简单易学的特点，又适应于开发视窗类应用程序，是制作国际跳棋程 序的最好的选择。1.3概要设计窗体结构设计:新棋.运算1涝饥窗体结构设计:新棋.运算1涝饥:如刎1加.如1101101101101

7、101101101101101101101101运算谥算2程序界面设计如图，面板分为四个部分，分别为棋盘，选择项，算法提示，分数计算 其中棋盘和算法（走法）提示是主要部分操作区中，用户通过对选项的选择来使程序完成相应的功能，当用户在走每一步的时 候都会有相应的走法和提示语句，在用户选择好走法以后可以单击存谱按钮来进行存储。用户也可以单击人机对战选项来选择对战目标，利用新棋键来重新开局如果用户走的步骤不合法，系统会弹出提示语来提示用户，使得本次走棋无效。当某 方的的棋子被全部吃掉，判次方输，棋局结束。程序算法设计：程序算法设计控制跳棋程序按跳棋规则运行，此层的设计主要分为：1，数据初始 化模块；

8、2,规则定义模块；3,搜索算法模块；初始化模块:主要完成各数据结构的定义和初始化，并为各数据结构分配存储空间， 初始化模块的许多数据结构将会在其他模块中被反复读入和存储，初始化模块中还定义有一 些函数，负责构建程序的初始运行状态，此函数还可以在运行时有选择的使程序复位，方便 用户的使用。规则定义模块：主要完成对程序运行过程中的搜索算法进行条件设定，就是按照国 际跳棋的规则对搜索算法进行一定限制，使算法的结果符合国际象棋的规则，同时简化搜索 模块的设计难度和代码复杂度。该模块中由几个函数组成，主要负责定义棋子基本的走法， 棋子的吃子走法，其中还包含有边界检查，保证棋子落在棋盘内。走法得分的计算，

9、搜索算 法模块的搜索算法函数会调用该模块中的函数来确定搜索的范围，并会根据各走法的得分来 确定最佳的走法，从而得到最优解。搜索算法模块：该模块就是搜索算法函数，是整个程序的核心，该模块主要完成棋 子的最高得分走法的搜索，用于人机对战模式时，计算出机器的走法。搜索算法通过调用规 则定义模块的函数确定搜索的范围，函数采用递归的方式搜索，通过计算出的当前分数与记 录中最高分进行比较，更新记录的最高分，同时记录最高分的走法，当递归搜索玩所有走法 的解时通过记录的最高分得到相应的走法。在递归搜索过程中还有剪枝操作，以进一步减少 搜索的范围。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搜索的每种走法的可吃子坐标Dim BestLocate As CHESSERDim CurrentPlayer As Byte 当前玩家Dim CurrentStep As Integer 当前步Dim人机模式As BooleanDim cSel As Byte玩家选择了哪个棋子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反显示(将屏幕显示的内容存入ChessBoard数组) 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数组的内容显示到屏幕后) 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胜负判断 End SubRem 胜负判断Private Sub胜负判断()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 计算玩家的棋子数 If Int(ChessBoard(i, j) / 100) = 2 Then b = b + 1 计算电脑的棋子数Next jNext iIf a = 0 Then Call MsgBox(我赢了！ ，vbOKOnly + 32,提示：):Exit SubIf b = 0 Then Call MsgBox(我认输了！ ，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) 对方的棋子,棋子为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：即如果基本走法的位置有对方的棋子则可以跳吃(走法 限制：Cer为1或棋子为加强棋才可走)If Int(ChessBoard(i - 1, j - 1) / 100) = NextCer(Cer) And (Cer = 1 Or ChessBoard(i, j) Mod 100 = 2) Thenx = (i - 1) - 1 目标坐标y = (j - 1) - 1x1 = i - 1吃子坐标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 默认情况下所有走法皆 不允许，如果所有值均为False则皆允许End IfEAT = FalseFor i = 0 To 7: IsEat(7) = False: Next i默认情况所有搜索到的走法都没有吃子Steps = Steps - 1If Steps 1 And IsLine2(Cer) = False Then，如果我方无子可吃时才返回估值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：即如果基本走法的位置有对方的棋子则可以跳吃（走法 限制：Cer为1或棋子为加强棋才可走)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 ，目标坐标 y(4) = (j - 1) - 1 x1(4) = i - 1吃子坐标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*如果可连续吃子v = CurrentValue(Cer) + 300V为当前局面价值加 300 分Elsev = Search(NextCer(Cer), Steps - 1, False, -UpMax)没有连续可 吃子，继续搜索End If恢复棋盘ChessBoard(Sc(i).x1, Sc(i).y1) = b 恢复被吃子ChessBoard(Sc.Initx, Sc(i).Inity) = b1 记录起点棋

27、子和终点棋子 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如果这种走法分数高，记录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结果4测试程序运行过程如下：点击“新棋”按钮，棋盘上会出现用数字显示的棋子，101代表己方的普通棋子，201 代表对方的普通棋子，再点击“人机对战”按钮，就可以开始下棋了，棋子只能斜着走，（1）当你的落棋位置不符合规则时，会弹出消息提示框，显示“落棋无效”。（2）当你的棋子可以连续吃子，会弹出消息提示框，显示“我还想再吃”。（3）当吃子时会显示相应的加分或减分。当某方的棋子到达对方的底线时，棋子代号 的最后一位会变成2代表给棋子变成王棋，王棋的

30、跳吃范围比普通棋子的跳吃范围大。（4）当电脑的棋子被吃完时，会弹出消息提示框，显示“我认输了”表示你获胜，电 脑认输。（5）当你的棋子被电脑吃完，会弹出消息提示框，显示“我赢了 “，表示你输了，电 脑获胜。（6）提示：电脑很“聪明”的哦！不懂点脑筋还赢不了它呢！说明我们的算法实现是 有效正确的。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搜索的每种走法的可吃子坐标Dim BestLocate As CHESSERDim CurrentPlayer As Byte当前玩家Dim CurrentStep As Integer 当前步Dim人机模式As BooleanDim cSel As By