象棋数据结构课程设计

象棋数据结构课程设计目录1．软硬件运行环境 ．软硬件运行环境1.1运行环境WindowsXP，Windows7。1.2编写语言C++1.3编写工具VisualC++6.0象棋数据结构课程设计全文共象棋数据结构课程设计全文共17页，当前为第2页。2．算法设计思想2.1走法生成走法就是一个棋子从一个位置移动到另一个位置。所以走法包含三要素：棋子、起点、终点。每种棋子都有自己的行走规则，计算机程序进行走法生成，都是先穷举再排除。即先列举出全部可能的位置，再一个一个除去不合规则的走法，剩下的就是合理的走法。不同棋子走法生成的共同点：找出棋子的下一个可能位置n。•判断n是否在棋盘上。•判断n是否被本方棋子占据。不同棋子应考虑的问题：•将、士是否走出九宫。•象是否过河，象眼是否被堵。•马是否蹩脚。•炮要翻山吃子。•兵过河前只能前进，过河后可以前进和左右移动。(1)各棋子按其行子规则行子。诸如马跳“日”字、象走“田”字、士在九宫内斜行等等（这里需要特别注意的是卒的行子规则随其所在位置不同而会发生变化——过河后可以左右平移）。(2)行子不能越出棋盘界限。当然所有子都不能走到棋盘的外面，同时某些特定的子还有自己的行棋界限，如将、士不能出九宫，象不能过河。(3)行子的半路上不能有子阻拦（除了炮隔子打子之外）以及行子的目的点不能有本方棋子（当然不能自己吃自己了）。(4)将帅不能碰面（本程序中只认为将帅碰面是非法的，而其它“送死”的着法并不非法，只是产生败局罢了）产生了着法后要将其存入着法队列以供搜索之用，由于搜索会搜索多层（即考虑双方你来我往好几步，这样才有利于对局面进行评估而尽可能避免“目光短浅”），所以在存着法队列的时候还要同时存储该着法所属的搜索层数。因此我将着法队列定义为二维数组MoveList[12][80]，第一个下标为层数，第二个下标为每一层的全部着法数。2.2选择最佳走法考虑到下棋的情景。棋局进行到某个时候，轮到电脑走棋。电脑可能有几十种走法，但它只能选择一个走法。电脑走任何一步棋，局面发生变化轮到人走棋，人也可能有几十种走法，他也只能选择一个。电脑要考虑每一个走法的好坏，同时也要考虑它走了之后人会如何走棋。整个问题像树一样展开，问题复杂度呈几何指数上象棋数据结构课程设计全文共象棋数据结构课程设计全文共17页，当前为第3页。2.3局面评估局面评估，也可以说是局面估值，就是判断局面对某一方的优势，并把优势进行量化。在象棋程序中如果说搜索算法是心脏，那么局面评估就是大脑。搜索算法负责驱动整个程序，而局面评估则负责对搜索的内容进行判断评价对局面进行评估并量化结果的目的是为了在多个局面之间进行比较，从而得到有利得局面，并得到合适的走法。局面评估中需要考虑几个因素包括如下四点：(1)棋子价值评估(2)棋子位置分值（控制区域）(3)棋子灵活性分值(4)其他复杂的局面评估象棋数据结构课程设计全文共象棋数据结构课程设计全文共17页，当前为第4页。3．算法的流程图3.1走法生成3.1.1马的走法生成如图3-1所示：象棋数据结构课程设计全文共17页，当前为第5页。图象棋数据结构课程设计全文共17页，当前为第5页。3.1.2兵的走法生成如图3-2所示：象棋数据结构课程设计全文共17页，当前为第6页。图3-象棋数据结构课程设计全文共17页，当前为第6页。3.1.3炮的走法生成如图3-3所示：象棋数据结构课程设计全文共17页，当前为第7页。图3-象棋数据结构课程设计全文共17页，当前为第7页。3.1.4车的走法生成如图3-4所示：象棋数据结构课程设计全文共17页，当前为第8页。图3-4

3.1.5搜索算法象棋数据结构课程设计全文共17页，当前为第8页。图3-4如图3-5所示：象棋数据结构课程设计全文共17页，当前为第9页。图3-5象棋数据结构课程设计全文共17页，当前为第9页。4．算法的实现与分析4.1走法生成4.1.1马的走法生成输入：马的位置p输出：马的所有可能走法现在位置p八个可行方向（i=0…7）计算下一个位置nn是否在棋盘上是，转第5步否，转第2步从p到n的马腿位置m上是否有棋子有，转第2步没有，转第6步n是否被本方棋子占据是，转第2步否，保存可行的走法，考虑下一位置转第2步4.1.2炮的走法生成输入：炮的位置p输出：炮的所有可能走法现在位置p四个可行方向翻山标志0，OverFlag=0沿这个方向继续前进一步（最多前进9步）计算下一个位置nn是否在棋盘上是，转第6步否，转第2步n位置上是否有棋子没有棋子 如果OverFlag==0，保存可行的走法（不吃子走法），转第3步 否则，转第3步有棋子则 如果OverFlag==0，则令OverFlag=1（翻山）否则，该棋子是否为本方棋子 不是，保存可行的走法（吃子走法），转第2步 是，转第2步象棋数据结构课程设计全文共17页，当前为第10页。象棋数据结构课程设计全文共17页，当前为第10页。4.1.3车的走法生成输入：车的位置position输出：车的所有可能走法现在位置position四个可行方向//第一重循环沿着这个方向继续前进一步（最多9步）//第二重循环计算下一位置nextnext是否在棋盘上是，转第6步否，转第2步next位置上是否有棋子没有，保存可行走法，考虑下一位置转第3步（不吃子走法）有棋子，判断该棋子是否本方棋子 是，转第2步 否，保存可行走法，考虑下一位置转第2步（吃子走法）4.1.4兵的走法生成输入：兵的位置position输出：兵的所有可能的走法现在的位置position三个可行方向计算下一个位置next=position+PawnDir[side][n];Next是否在棋盘上是，转第5步否，转第2步是否未过河横向移动是，转第2步否，转第6步next是否被本方棋子占据是，转第2步否，保存可行走法，考虑下一位置转第2步象棋数据结构课程设计全文共17页，当前为第11页。象棋数据结构课程设计全文共17页，当前为第11页。4.2搜索算法4.2.1搜索树定义搜索深度depth，本方最优值best返回值valuesearch(depth,best,worst){红方走棋时，best=无穷大黑方，best=无穷小若深度小于等于0，调用局面评估函数分析局面若深度大于0，调用生成走法函数，并判断可用走法。for每一个可用走法执行走法递归调用搜索函数value=-search();depth-1;撤销算法If红方走棋If(value>best)Best=valueIf(depth=Maxdepth)//Maxdepth为设置的最多搜索层数Bestmove=当前走法ElseIf(value<best)Best=valueIf(depth=Maxdepth)Bestmove=当前走法Returnbest}象棋数据结构课程设计全文共17页，当前为第12页。象棋数据结构课程设计全文共17页，当前为第12页。4.3局面评估4.3.1棋子价值评估不同的棋子都有不同的价值。详见下表：卒士象马炮车将1020204045901000根据基本价值，可以得到一个最初的评估算法：输入：棋盘数组输出：局面估值wValue：红方棋子价值的总和bValue：黑方棋子价值的总和wValue=bValue=0;1行变量row=3to12 2列变量list=3to11 对应一维数组下标chessman=row<<4+j; 如果chessman位置已出界，则 返回第2步 pc为chessman位置对应的棋子 如果pc为红方棋子，则 wValue+=pc棋子对应的子力值 否则 bValue+=pc棋子对应的子力值returnwValue–bValue4.3.2棋子位置分值一个棋子在棋局中的真正价值，不仅与固定分值有关，还与所处位置有关。定义一个三维数组来表示在不同棋子在不同位置的分值： staticconstunsignedcharPositionValues[2][7][256]; 第一维表示走方，0为黑方，1为红方，第二维表示棋子种类，0到6分别表示士、象、炮、将、马、卒、车，第三维表示位置。 位置分值根据棋手多年的经验而得，有些难以量化，只能尽量模拟。4.3.3棋子灵活性分值棋子所在位置的重要性，通过位置分值已经体现。但即使是在同一位置，如果周围全是棋子，限制了棋子的灵活性，这样往往会陷入被动挨打的局面。由此可见，灵活性在行棋中还是占有相当重要的作用。棋子灵活性的度量：棋子灵活性的度量只能以棋子能走棋步数来体现，能走的位置越多，灵活性越高。因此，在估值函数中计算每一个棋子的行棋步数，然后再给以一定分值的奖励。象棋数据结构课程设计全文共17页，当前为第13页。各个棋子的灵活性分值分别为：象棋数据结构课程设计全文共17页，当前为第13页。将：2，士：2，马：5，车：4，炮：3，卒：2棋子每有一种走法，就增加一个灵活性分值。4.3.4其他复杂的局面评估一盘棋局的局势跟本方棋子间的协作有关，跟对方棋子的牵制有关。马踏在九宫格附近威胁较大，应该加分，而当马踏在四条边线上时，因走法受限很容易被对方攻击，应该减分。当两个马踏成连环马时，威力比两个单马要大，这是棋子之间的协作，应该加分。一个棋子处于另一个棋子的保护范围内，都可以说是协作。还有一些固定的进攻组合和防守组合，也应该考虑，如马炮，车马，过河卒连在一起，担子炮，等等。当一个棋子收到对方棋子的攻击时，就是受到对方棋子的牵制，应该减分。还有更多的因素：区域合作问题，典型的三子归边。凡有车、马、炮等三个进攻性的棋子集结在一起，就有可能构成各种杀势。对将得威胁。如，车炮置中路或底路，都有潜在对将的威胁。每一种情况的加分减分只有通过实验来解决。设置不同的加减分值，看程序如何表现，通过不断调整，最后达到一个相对合理的值。象棋数据结构课程设计全文共17页，当前为第14页。

象棋数据结构课程设计全文共17页，当前为第14页。5．运行结果与分析运行正常，所有的错误操作都有判断。象棋数据结构课程设计全文共17页，当前为第15页。象棋数据结构课程设计全文共17页，当前为第15页。6．总结通过本次课程设计课，我们的编程能力得到了加强，而且使我们更深刻的体会到数据结构与算法的重要性。为了让电脑能更快速的做出更准确的判断，我们不断改进算法。在技术上，知道了很多先进的算法，例如Alpha-Beta搜索算法。还学会了用MFC编写窗口程序。在团队合作上，我