毕业设计（论文）-基于JAVA的中国象棋系统设计.doc

太原理工大学毕业设计 (论文)用纸 i 基于 JAVA 的中国象棋 摘要 近年来，现代化的人工智能以及先进的计算机技术迅猛发展，基于此基础的电脑 象棋程序，其下棋水平也得到了进一步的提升。 然而，早在二十世纪的六十年代初期，来此美国麻省理工学院的约翰麦卡锡就提 出了修剪算法“alpha-beta” 。在该算法提出以前，通常计算机下棋程序在决定每一 步走步时，所需的棋盘状态空间的搜索量都是指数级别的，而该算法则将这一搜索量 的数量级减少为指数的平方根，这极大程度地提高了电脑下棋程序的水平。 而随后 IBM 公司推出的超级计算机“Deep Blue” ，则是一个不择不扣的神话，这 一耗资上千万，耗时 8 年所建造出的世界上最强大的国际象棋“棋手” ，着实为广大棋 迷们所神往。本文内容根据以往国内外象棋程序在设计上所取得的一些成功案例及经 验，为中国象棋设计其基本的思路和算法。 关键词：中国象棋，位棋盘，alpha-beta 搜索，Zobrist 键值，置换表 全套设计加扣 3012250582 太原理工大学毕业设计 (论文)用纸 ii Chinese Chess based on JAVA Abstract In recent years, modern artificial intelligence as well as the rapid development of advanced computer technology, computer chess program based on this foundation, its level of chess also got further improvement. However, as early as the early 60 s of the 20th century, to the United States at the Massachusetts institute of technology, John McCarthy was proposed pruning algorithm - alpha and beta. Before the algorithm is put forward, the computer chess programs usually every step in deciding when walking, the board of state space search volume index level, while the algorithm reduces the search quantity of an order of magnitude as the index to the square root of the drastically increased the level of computer chess program. And then IBM supercomputer Deep Blue, is a myth, not choose the travel this at a cost of tens of millions, spent eight years built by the worlds most powerful chess chess player, is by the masses of chess enthusiasts. This article content based on previous chess programs at home and abroad in the design of some successful cases and experience, design the basic train of thought for Chinese chess and algorithms. Keywords: Chinese Chess, bit board, alpha-beta search, zobrist keys, transposition table 太原理工大学毕业设计 (论文)用纸 目 录 摘要.i Abstract .ii 目 录 .1 引 言 .1 1 概述 .2 1.1 棋盘的标记.2 1.1.1 纵线方式.2 1.1.2 坐标方式.2 1.2 棋子的名称.3 1.3 棋谱的记录方法.3 1.4 历史局面的表示及存储.4 1.5 棋谱记录文件的格式.4 1.5.1 标签部分.4 1.5.2 棋谱记录部分.5 1.5.3 XML 格式 .5 2 基本数据结构位棋盘 .7 2.1 什么是位棋盘.7 2.2 位棋盘的作用.7 2.3 位棋盘的基本运算.9 2.4 Java 中位棋盘的实现 .9 2.4.1 位棋盘类的实现.9 2.4.2 位棋盘的初始化.10 2.4.3 位棋盘的更新.10 3 基本数据结构Zobrist 键值.11 3.1 比较局面的方法.11 3.2 Zobrist 键值的实现方法 .11 3.3 Zobrist 键值的工作原理及用途 .11 3.3.1 Zobrist 键值的工作原理.11 3.3.2 Zobrist 键值的用途.12 3.4 Java 中实现 Zobrist 键值.12 4 着法生成 .14 4.1 伪合法着法的生成 .14 4.1.1 数组及其下标的含义.14 4.1.2 算法示例车炮的伪合法着法生成.16 太原理工大学毕业设计 (论文)用纸 4.2 合法着法的生成.18 5 搜索算法 .21 5.1 最小-最大搜索.21 5.1.1 基于最小-最大的评价函数 .21 5.1.2 最小-最大搜索.21 5.1.3 负值最大函数.23 5.2 Alpha-Beta 搜索.23 5.2.1 最小-最大搜索算法的问题.23 5.2.2 Alpha-Beta 修剪 .24 5.2.3 Alpha-Beta 修剪算法的实现 .25 5.2.4 可能的弱点.26 5.3 迭代加深 .26 5.4 置换表.27 5.4.1 置换表的实现.27 5.4.2 替换策略.29 6 局面评价函数 .30 6.1 评价函数的实现方法.30 6.1.1 算法设计思路.30 6.1.2 评价要素的组合 .31 6.2 评价函数所需的信息 .31 7 程序的设计及实现 .34 7.1 搜索引擎的实现（engine 包） .34 7.2 信息传输机制（message 包）.34 7.3 棋子（pieces 包） .35 7.4 主控模块（main 包） .35 参考文献 .36 致 谢 .37 外文文献 .38 太原理工大学毕业设计 (论文 )用纸 1 引引 言言 计算机象棋水平的发展，依赖的是计算机软硬件技术的不断提高。国际象棋对弈 平台有两个非常好的典范，即 WinBoard 和 ChessBase。前者是作为一个国际象棋对弈 平台的同时，又可以直接对象棋的棋谱进行编辑。后者则是国际象棋的一个商业数据 库和象棋对弈软件。他们都为国际象棋爱好者以及研究人员大开方便之门。国际象棋 软件作为一种新兴产业，它有着自己十分成功的商业运作。与此相对的，中国象棋在 计算机上的运用实则刚刚起步，由于缺乏必要的基础工作，尽管国内有相当一部分制 作计算机中国象棋的专业网站与专业软件，但是，计算机技术在中国象棋上的应用优 势仍然无法清晰明朗地体现出来。 在中国象棋的软件设计过程中，国际象棋软件有很多优秀的思想以及成功经验值 得我们来借鉴。例如，微软公司的程序设计师 B. Moreland，业余时间用来进行国际象 棋引擎软件 Ferret 的研究开发，他写的关于国际象棋程序设计的文章非常值得其他棋 类程序设计人员借鉴。虽然如此，中国象棋也仍然与国际象棋存在着巨大的差异，因 此国际象棋的某些成熟技术，无法直接应用于中国象棋，需要对其加以改进和创新。 本文针对中国象棋程序设计的一系列问题，总结出一些搜索引擎的设计方法，并给 出 java 语言的实现。 太原理工大学毕业设计 (论文 )用纸 2 1 概述 中国象棋是由两人下的。一方称为红方（或白方），一方称为黑方。对局时由红 方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止。棋子的走法及详 细规则见中国象棋竞赛规则，本章只描述计算机实现象棋对弈程序时所涉及的一 些概念及相关的表示方法。 1.1 棋盘的标记 象棋的着法表示，简而言之就是某个棋子从什么位置走到什么位置。通常，表示 方法可以分为“纵线方式”和“坐标方式”两种，现在作简要说明。 1.1.1 纵线方式 这是中国象棋常用的表示方法，即棋子从棋盘的哪条线走到哪条线。中国象棋规 定，对于红方来说的纵线从右到左依次用“一”到“九”表示，黑方则是“1”到 “9”(如图 1.1(左)所示)，这种表示方式体现了古代中国象棋研究者的智慧。 1.1.2 坐标方式 这是套用国际象棋中的表示方法，即把每个格子按坐标编号(如图 1.1(右)所示)， 只要知道起始格子和到达格子，就确定了着法，这种表示方式更方便也更合理，而且 还可以移植到其他棋类游戏中。采用这种方法来表示，棋盘的纵线从左到右(红方)依 次为 a b c d e f g h i，横线从下到上(红方)依次为 0 1 2 3 4 5 6 7 8 9(如图 1.1(右)所示)。 九 八 七 六 五 四 三 二 一 aBcdefghi 99 88 77 66 55 44 33 22 11 00 aBcdefghi （左）（右） 图 1.1 中国象棋与国际象棋常用表示方法 太原理工大学毕业设计 (论文 )用纸 3 1.2 棋子的名称 为方便表示，中国象棋的棋子名称除了用汉字以外，还可以用字母，字母可从国 际象棋中稍加改动得到，而数字是为了方便着法的输入(以便用在数字小键盘上)(见表 1.2)： 表 1.2 中国象棋中英文名称对照表格 红方红方黑方黑方字母字母英文单词英文单词数字数字 帅将KKing1 仕士AAdvisor2 相象BBishop3 马马NKnight4 车车RRook5 炮炮CCannon6 兵卒PPawn7 1.3 棋谱的记录方法 现以如下局面为例说明各种记谱方法 对于右图图 1.3 的局面，记法如下： 1.炮二平五 炮平 2.炮五进四 士进 3.马二进三 马进 4.炮八平五 马进 5.前炮退二 车平 图 1.3 象棋记谱方法示例图 太原理工大学毕业设计 (论文 )用纸 4 坐标格式包括：棋子的名称、起点和终点的位置（起点和终点用-连接），对 上面的走法，记录如表 1.3.1（省略了吃子、将军等信息）： 表 1.3.1 棋子走步记录法 1、Ch2-e2(炮二平五)Ch7-e7(炮平) 2、Ce2-e6(炮五进四)Ad9-e8(士进) 3、Nh0-g2(马二进三)Nh9-g7(马进) 4、Cb2-e2(炮八平五)Nb9-c7(马进) 5、Ce6-e4(前炮退二)Ri9-h9(车平) 1.4 历史局面的表示及存储 中国象棋的一个局面可以用一个“FEN 格式串”来表示。FEN 格式串是由 4 段 ASCII 字符串组成的代码(彼此 3 个空格隔开)，这 4 段代码的意义依次是： (1) 棋盘上的棋子，这是 FEN 格式串的主要部分； (2) 当前局面轮到哪一方走子； (3) 最近一次吃子或者进兵后棋局进行的步数(半回合数)，用来判断“50 回合自 然限着”； (4) 棋局的回合数。 现以最初局面为例详细说明如下： rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w 0 1 第一部分(w 前面的字符)：表示棋盘布局，小写表示黑方棋子，大写表示红方棋 子。例如前九个字母 rnbakabnr 表示棋盘第一行的棋子分别为黑方的“车马象士将 士象马车” ， “/”为棋盘行与行之间的分割；数字“9(5,1)”表示该行从该位置起连 续 9(5，1)个位置无棋子。 第二部分(w)：表示轮到哪一方走棋，如果是 w 表示轮到红方(白方)走，是 b 表示 轮到黑方走。 第三部分(w 后的数字 0)：表示自然限着。 第四部分(w 后的数字 1)：表示当前局面的回合数。 1.5 棋谱记录文件的格式 存放棋谱的文件分为两个部分：标签部分和棋谱部分，现分述如下： 1.5.1 标签部分 有如下标签： 1、Event：比赛名； 2、Site：比赛地点； 3、Date：比赛日期，格式统一为yyyy.mm.dd； 4、Red：红方棋手； 5、Black：黑方棋手； 6、Result：比赛结果，“红先胜”用“1-0”表示，“黑先胜”用“0-1”表示， 和棋用“1/2-1/2” 7、FenStr：起始局面。如果空缺，表示起始局面是最初局面。 太原理工大学毕业设计 (论文 )用纸 5 1.5.2 棋谱记录部分 棋谱记录部分必须在标签部分的后面，棋谱部分当中不能插入标签； 每一回合都 由“回合数”、“红方着法”和“黑方着法”三部分组成，回合数后面要跟“.”(句 点)，三者之间用两个分隔符隔开(回合数后面的句点也不例外)，回合之间也用分隔符 隔开。 现举一个例子如下： 例 1： Event 第 19 届五羊杯全国象棋冠军邀请赛 Date 1998.12.09 Site 广州 Red 徐天红 Black 许银川 Result 1/2-1/2 1. 炮二平五 马进 2. 马二进三 车平 3. 车一平二 马进 4. 兵七进一 卒进 5. 车二进六 炮平 6. 车二平三 炮退 7. 马八进九 车进 8. 兵五进一 马退 9. 炮八进四 炮平 10. 马九进七 炮平 例 2： Event 全国象棋冠军邀请赛 Date 1999.12.15 Site 广州 Red 吕钦 Black 许银川 FEN 3k1ab2/4a4/8b/6NPP/9/4n1P2/6p2/4B4/4A4/2BAK4 w - - 0 46 Result 1-0 46. 兵一进一 卒进 47. 兵一平二 卒进 48. 前兵平三 卒平 49. 马三退五 马退 50. 兵二平三 马进 51. 马五退六 1.5.3 XML 格式 全国象棋冠军邀请赛 太原理工大学毕业设计 (论文 )用纸 6 广州 1999.12.09 许银川 聂卫平 rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/9/1C5C1/9/RN2K2NR r - - 0 1 1-0 炮八平五 炮平 太原理工大学毕业设计 (论文 )用纸 7 2 基本数据结构位棋盘 2.1 什么是位棋盘 在中国象棋中，棋盘有 90 个交叉点。位棋盘其实就是一个长度为 90 位的变量， 每个位对应一个交叉点，用来记录棋盘上的某些布尔值。在 Java 中，用 3 个 int 类型 数据（每个 32 位，共 96 位多余的 6 位不用）表示一个位棋盘。 2.2 位棋盘的作用 位棋盘的作用，可从回答下面的问题开始： “哪些格子上面有棋子？” “哪些格子上面有白棋（黑棋）棋子？” “哪些格子上面有车（马，炮等）？” “哪些格子受到 a7 格上的棋子的攻击？”(不用管格子上是否有棋子或是什么颜 色的棋子。) “如果有马在 a3 格上，哪些格子会受到它的攻击？” 通过回答上面的问题，可设置如下一些位棋盘 1、记录所有棋子位置的位棋盘 AllPieces。AllPieces 告诉我们棋盘上哪些格子有棋子， 哪些没有。当棋子处于最初位置的时候，“AllPieces”看上去是这个样子的(以下描述中， 格子的下标从 0 开始，坐标的图示见第一章“棋盘的标记”): (Hi,89,a9)111111111 000000000 101010101 000000000 000000000 101010101 000000000 010000010 000000000 111111111(Low,0,i0) 其最高位对应第 89 格(a9 格,左上角)，最低位对应第 0 格(a8 格，右下角)。 这样显示位棋盘可能更形象一点： 黑棋 111111111 000000000 010000010 101010101 000000000 000000000 101010101 000000000 010000010 000000000 111111111 红棋 2、记录所有黑棋棋子初始位置的位棋盘 BlackPieces 如下(记录红棋棋子初始位置的位 棋盘 RedPieces 与此类似，在此不再列出) 111111111 000000000 010000010 太原理工大学毕业设计 (论文 )用纸 8 101010101 000000000 000000000 000000000 000000000 000000000 000000000 3、记录各兵种如红棋车的初始位置的位棋盘“redRooks”如下： 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 100000001 4、假如我们创建了一个位棋盘数组 knight90，用“knight0”位棋盘记录当马在 0 格 (即 i0 格)时，棋盘上所有受到它攻击的格子，knight89记录当马在第 89 格(a9 格)时， 棋盘上所有受到它攻击的格子，那么，“knight20”就是这个样子的（为了直观，用 “x”标记出马的位置，实际上该位置是“0”）： 000000000 000000000 000000000 000000000 000000000 000001010 000010001 000000 x00 000010001 000001010 5、用另外一个位棋盘数组 HorseLeg90记录蹩马腿位置的位棋盘。与 Knight20对应 的 HorseLeg20如下(在实际系统中，根据马的行走方向单独设置只有一个蹩腿位的位 棋盘，knight 数组更改为 knight908)： 000000000 000000000 000000000 000000000 000000000 000000000 000000100 太原理工大学毕业设计 (论文 )用纸 9 000001x10 000000100 000000000 6、建立全局数组“BitBoard bitMask90” ，用来屏蔽或设置位棋盘中的某位。 bitMask0是这样的： 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000001 mask89 是这样的： 100000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 2.3 位棋盘的基本运算 1、与( Mid = Arg2; Hi = Arg3; public static BitBoard opAnd(BitBoard arg1,BitBoard arg2) /位棋盘的“与”操作，保存结果。 int low=arg1.Low int mid=arg1.Mid int hi=arg1.Hi return new BitBoard(low,mid,hi); public static BitBoard opOr(BitBoard arg1,BitBoard arg2) /位棋盘的“或”操作，保存结果。 public static BitBoard opXor(BitBoard arg1,BitBoard arg2) /位棋盘的“异或”操作，保存结果。 public static int count(BitBoard arg) /计算位棋盘中非零位的个数 public static BitBoard duplicate(int arg) /复制位棋盘 public static boolean equals(BitBoard arg1,BitBoard arg2) /位棋盘是否相等（所有 90 位对应的位相同即/为相等） public static BitBoard leftShift(BitBoard arg,int num) /位棋盘 arg 左位移 num 位 public static rightShift(BitBoard,int num) /位棋盘右位移 num 位 public static int LSB(BitBoard Arg) /位棋盘最低非 0 位的位置（从 0 开始计数） public static int MSB(BitBoard Arg) /位棋盘最高非 0 位的位置（从 0 开始计数） public static boolean notZero(BitBoard Arg) /是否非“0”。当 90 位中有非 0 位时返回 true。 2.4.2 位棋盘的初始化 某些位棋盘从程序开始运行到结束都不会改变。例如上面所述的那个位棋盘数组 “knight90”。(他实际上记录了当马在任意格子上时，它下一步可以走的格子。)这个 数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例 如“AllPieces”位棋盘。当中国象棋棋盘变化时，它也跟着变化。然而，他们的初始化 方式相同。对于诸如 knight90这样不变化的位棋盘的初始化，将在“伪着法生成”章 节详述。此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。 2.4.3 位棋盘的更新 当棋盘局面变动后，某些位棋盘就需要被更新。例如记录白子所在位置的 “WhitePieces”位棋盘。假如我们把 h2 格的红炮移动到 h9 格（炮二进七），吃掉黑棋 的一个马，需要更新如下位棋盘： allPieces，redPieces ，redCannons，blackpieces，blackKnights 首先，把 redPieces，redCannons 位棋盘的“h2”位清零，然后把他们的“h9”位置 1。 最后我们要将 blackPieces 和 blackKnights 位棋盘的 h9 位清除，因为那里的黑马被吃掉 太原理工大学毕业设计 (论文 )用纸 11 了。 3 基本数据结构Zobrist 键值 3.1 比较局面的方法 在写中国象棋程序时，需要比较两个局面看它们是否相同。如果比较每个棋子的 位置，或许不需要花很多时间，但是实战中每秒种需要做成千上万次比较，因此这样 会使比较操作变成瓶颈的。另外，需要比较的局面数量多得惊人，要存储每个棋子的 位置，需要占用非常大的空间。 一个解决方案是建立一个标签，通常是 64 位。由于 64 位不足以区别每个局面， 所以仍然存在冲突的标签，但实战中这种情况非常罕见。 3.2 Zobrist 键值的实现方法 Zobrist 散列(也称为 Zobrist 键或 Zobrist 签名)是一个散列函数构造中使用计算 机程序的抽象的棋盘游戏,比如国际象棋和围棋,实现换位表,一种特殊的哈希表,由董 事会的位置索引,用来避免多次分析相同的位置。Zobrist 散列以其发明者的名字命名,阿 尔伯特林赛 Zobrist。它也被应用作为识别的方法置换合金配置模拟晶体材料。 Zobrist 散列开始通过随机生成 bitstrings 为每个可能的棋盘游戏的元素,即每 一块和一个位置(在国际象棋的游戏,这是 12 件64 板位置,或 14 如果国王可能仍城 堡和一个棋子,捕获顺道分别处理)。现在任何董事会配置可分为独立片/位置组件,映 射到生成随机 bitstrings 早些时候。最后 Zobrist 散列计算这些 bitstrings 使用位 XOR 相结合。 实现 Zobrist 必须从多维的 64 位数组开始，每个数组含有一个随机数。在 Java 中， “rand.nextLong()”函数返回一个 64 位的随机数值。 这个函数用来填满一个 long 型（64 位）的三维数组：棋子的类型、棋子的颜色和棋子 的位置： long zobristpcMAXcoMAXsqMAX; 程序启动时就把这个数组用随机数填满。要为一个局面产生 Zobrist 键值，首先把 键值设成零，然后找棋盘上的每个子，并且让键值跟“zobristpccosq”做异或(通过 “”运算符)运算。 如果局面由白方走，那么别去动它，如果是黑方走，你还要在键值上异或一个 64 位的随机常数。 3.3 Zobrist 键值的工作原理及用途 3.3.1 Zobrist 键值的工作原理 用 Zobrist 技术产生的键值，表面上跟局面没什么关系。如果一个棋子动过了，就 会得到完全不同的键值，所以这两个键值不会挤在一块儿或者冲突。当把它们用作散 列表键值的时候会非常有效。 另一个优点在于，键值的产生是可以逐步进行的。例如，红马在 e5 格，那么键值 里一定异或过一个“zobristKNIGHTREDE5”。如果再次异或这个值，那么根据异或 的工作原理，这个马就从键值里删除了。 太原理工大学毕业设计 (论文 )用纸 12 这就是说，如果有当前局面的键值，并且需要把红马从 e5 移到 f7，你只要异或一 个“红马在 e5”的键值，把马从 e5 格移走，并且异或一个“红马在 f7”的键值，把红马放 在 f7 上。比起从头开始一个个棋子去异或，这样做可以得到同样的键值。 如果要改变着子的一方，只要异或一个“改变着子方”的键值就可以了。用这种方 法，可以在搜索根结点的时候构造一个 Zobrist 键值，在搜索时通过走子函数 “MakeMove()”来更新键值，一直让它保持和当前局面同步。 3.3.2 Zobrist 键值的用途 Zobrist 键值通常用在散列键值当中，而散列键值在象棋程序里有以下几个作用： 1、用 Zobrist 键值来实现置换表。置换表是一个巨大的散列表，来保存以前搜索 过的局面，这样可以节省很多搜索的时间。如果需要对某个局面搜索 9 层，可以从置 换表中查找该局面，如果它已经搜索过 9 层，那么不必去重复搜索。置换表的另一个 并不起眼的作用是，它可以帮助我们改善着法的顺序。 2、可以用 Zobrist 键值制造一个很小的散列表，来检测当前着法路线中有没有重 复局面，以便发现长将或其他导致和局的着法。 3、可以用 Zobrist 键值创建支持置换的开局库。 3.4 Java 中实现 Zobrist 键值 本系统使用一个 key 和一个 lock 结合来区分每个局面，这样发生冲突（即两个局 面对应的 key 和 lock 一样）的概率几乎为 0。示例代码及相关说明如下 1、填充数组。 上述的三维数组现在改变为二维（将颜色与棋子兵种类型合并） public static long ZobristKeyPlayer;/改变走子方的 key public static long ZobristLockPlayer;/改变走子方的 lock public static long ZobristKeyTable = new long1490; public static long ZobristLockTable = new long1490; static zobristGen(); public static void zobristGen() int i, j; Random rand = new Random(); long RandSeed; RandSeed = 1; rand.setSeed(RandSeed); ZobristKeyPlayer = rand.nextLong(); for (i = 0; i 14; i +) /0：红帅 1：红仕 2：红相 3：红马 4：红车 5：红炮 6：红兵 /7：黑将 8：黑士 9：黑象 10：黑马 11：黑车 12：黑炮 13：黑卒 太原理工大学毕业设计 (论文 )用纸 13 for (j = 0; j 90; j +) ZobristKeyTableij = rand.nextLong(); ZobristLockPlayer = rand.nextLong(); for (i = 0; i 14; i +) for (j = 0; j 90; j +) ZobristLockTableij = rand.nextLong(); 2、移子函数 当移动（添加、删除）一个棋子时，将当前局面的 Zobrist 键值与键值表中该棋子的键 值进行异或操作，同时也与改变走子方的键值进行异或操作。 public class ChessPosition long ZobristKey, ZobristLock; /当前局面的 zobrist 键值 public ChessPosition ZobristKey=0;/初始化为 0 ZobristLock=0; public void makeMove(int Square, int Piece, boolean IsAdd) ZobristKey=ZobristKeyTablePieceTypeSquare; ZobristLock=ZobristLockTablePieceTypeSquare; ZobristKey = ZobristKeyPlayer;/改变走子方 ZobristLock = ZobristLockPlayer; 太原理工大学毕业设计 (论文 )用纸 14 4 着法生成 着法生成在不同的象棋引擎中差异较大。本章使用位棋盘生成着法的基本原理。 高级的国际象棋引擎通常具备一次只生成一小部分着法的能力。例如，仅生成象走的 着法，马走的着法，“将”的着法，所有的吃子着法等等，这正是位棋盘的强项。那 为什么用这种方式生成着法呢？原因是生成着法耗费一定的时间。如果引擎在检查了 一部分着法后发现了必须走的棋，那它就无需生成余下的棋步了。因此，可能先生成 所有吃子的着法，如果没有满意的棋再生成余下的着法。(用来减少耗时的着法生成策 略很多发挥你的想象力吧)。 大名鼎鼎的免费国际象棋引擎 Crafty(其作者是 Robert Hyatt 博士)使用三个着 法生成函数。一个用来生成所有伪合法吃子着法，一个生成所有伪合法不吃子着法， 最后一个生成所有摆脱被将军状态的着法。注意前两个函数生成的是伪合法的着法。 就是说，这些函数生成的着法并非都是合法的。例如，你要生成所有将军的着法并且 发现了一步你想走的棋，但随后发现这步不合法再把它抛弃。这看起来很奇怪，但它 确实比那种在所有局面下都严格生成合法着法的策略更快！Hyatt 博士曾经这样解释： 当国王被将时，你需要生成摆脱被将的着法，这时大部分生成的着法是不合法的，在 这种局面中你使用生成所有合法着法的策略会帮你节省时间；但在大多数局面中，生 成的着法都是合法的，推迟验证合法性会更有效率。 中国象棋的着法生成与此类似，先生成所有伪合法的着法，存入静态数组中。在对 局中可以用“查表”的方式查找生成的伪着法，并对其合法性作出判断。这样可以节 省大量的时间。 4.1 伪合法着法的生成 伪合法着法包含几类： 各兵种的不吃子着法 各兵种的吃子着法 “将”和摆脱“将”的着法 其中，马、相（象）、兵、帅（将）、仕（士）的吃子着法与其对应的不吃子着 法规则相同。（伪合法着法并不考虑被吃的棋子的颜色该棋子是对方的棋子还是 己方的棋子，也不考虑该子是否能动，例如动了该子，双方的帅将会面。）炮和车的 不吃子着法规则相同，但分为纵向横向行走两类。炮的吃子着法分为纵向和横向两类， 车的吃子着法也分为纵向和横向两类。马和象的着法要考虑蹩马腿和塞象眼。将军的 着法单独作为一类。 4.1.1 数组及其下标的含义 1、保存帅（将）、仕（士）、相（相）、马、兵的伪合法静态数组如下： public static final int KingMoves=new int908; public static final int AdvisorMoves=new int908; 太原理工大学毕业设计 (论文 )用纸 15 public static final int BishopMoves=new int908; public static final int ElephantEyes=new int904; public static final int KnightMoves=new int9012; public static final int HorseLegs=new int908; public static final int PawnMoves=new int9024; 第一个下标说明棋子所在的格，第二个下标含义不尽相同。帅（将）在某个位置 最多有 4 种走法，例如 KingMoves130=12 表示帅在 13 格（e1 格）时可以走到 12 格（当然，也可以走到 14、4、22 格，保存到其他几个数组元素中）。第 5 种（如果 前面只有 3 种着法，则此处是第 4 种）保存的是非法着法即 KingMoves134=-1，