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