中国象棋对弈软件的设计论文

1、中国象棋对弈软件的设计论文 中国象棋对弈软件的设计中国象棋对弈软件的设计 摘 要:随着人工智能及计算机硬件的发展,计算机象棋程序的下棋水平也不断地得到提高。20世纪60年代初,麦卡锡提出了alpha-beta修剪算法,把为决定下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根,大大地提高了机器下棋的水平。IBM的超级计算机“Deep Blue”更是一个神话,让棋迷们神往。本文根据国际象棋程序设计的一些成功经验,提出中国象棋程序设计的一些思路和方法。关 键 词:中国象棋,位棋盘,Zobrist键值,alpha-beta搜索,置换表,局面评价Abstract:Along with th

2、e development of the Artificial Intelligence and computer hardware, the capability of computer chess program have advanced continually.At the beginning of 60s,20th century, McCaxi brought forword alpha-beta pruning algorism which made the chess program advanced more by reducing the order of magnitud

3、e of the number of searching nodes deciding next step,named “State Space” from OXn to OXn/2. IBMs super-computer “Deep Blue” is more like a myth for all computer chess fans. In my article, I will describe some ideas and methods of designing Chinese Chess program along with some successful experience

4、s and cases of the Chess.Keywords: Chinese Chess, bit board, zobrist keys, alpha-beta search, transposition table, Evaluation目 录引言3第一章 概述4 1.1 棋盘的标记4 1.2 棋子的名称5 1.3 棋谱的记录方法5 1.4 历史局面的表示及存储7 1.5 棋谱记录文件的格式8第二章 基本数据结构?位棋盘10 2.1 什么是位棋盘10 2.2 位棋盘的作用10 2.3 位棋盘的基本运算12 2.4 Java中位棋盘的实现13第三章 基本数据结构?Zobrist键值1

5、7 3.1 比较局面的方法17 3.2 Zobrist键值的实现方法17 3.3 Zobrist键值的工作原理及用途17 3.4 Java中实现Zobrist键值18第四章 着法生成20 4.1伪合法着法的生成20 4.2 合法着法的生成25第五章 搜索算法29 5.1 最小-最大搜索29 5.2 Alpha-Beta搜索33 5.3 迭代加深36 5.4 置换表37 5.5 其他策略41第六章 局面评价函数47 6.1 评价函数的实现方法48 6.2 评价函数所需的信息48第七章 程序的设计及实现51 7.1 搜索引擎的实现(engine包)51 7.2 信息传输机制(message包)52

6、 7.3 棋子生成(pieces包)52 7.4 主控模块(main包)52附件1:搜索算法主程序SearchMove.java55附件2:程序运行界面及功能说明74引言象棋水平的发展是需要靠信息技术来推动的,国际象棋有两个很好的范例,一个是象棋棋谱编辑和对弈程序的公共平台?WinBoard平台,另一个是商业的国际象棋数据库和对弈软件?ChessBase,他们为国际象棋爱好者和研究者提供了极大的便利。国际象棋软件有着成功的商业运作,已发展成一种产业。然而,电脑在中国象棋上的运用还刚刚起步,尽管国内涌现出一大批中国象棋的专业网站和专业软件,但是由于缺乏必要的基础工作,电脑技术在中国象棋上的应用优

7、势还无法体现出来。在设计中国象棋软件过程中,国际象棋软件有很多值得借鉴的成功经验和优秀的思想。例如B. Moreland,微软Microsoft的程序设计师,业余从事国际象棋引擎Ferret的开发,他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。然而,中国象棋与国际象棋存在着很大的差异,因此国际象棋的某些成熟技术,无法直接应用于中国象棋,需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题,总结出一些搜索引擎的设计方法,并给出java语言的实现。 第一章 概述中国象棋是由两人下的。一方称为红方(或白方),一方称为黑方。对局时由红方先走,黑方后走,一次一着,双方轮流

8、走棋,直到对局结束为止。棋子的走法及详细规则见中国象棋竞赛规则,本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。1.1 棋盘的标记 象棋的着法表示,简而言之就是某个棋子从什么位置走到什么位置。通常,表示方法可以分为“纵线方式”和“坐标方式”两种,现在作简要说明: 1.1.1 纵线方式这是中国象棋常用的表示方法,即棋子从棋盘的哪条线走到哪条线。中国象棋规定,对于红方来说的纵线从右到左依次用“一”到“九”表示,黑方则是“1”到“9”如图1所示,这种表示方式体现了古代中国象棋研究者的智慧。 1.1.2 坐标方式这是套用国际象棋中的表示方法,即把每个格子按坐标编号如图二所示,只要知

9、道起始格子和到达格子,就确定了着法,这种表示方式更方便也更合理,而且还可以移植到其他棋类游戏中。采用这种方法来表示,棋盘的纵线从左到右红方依次为a b c d e f g h i,横线从下到上红方依次为0 1 2 3 4 5 6 7 8 9如图2所示。123456789九八七六五四三二一 aBcdefghi 99887766554433221100 aBcdefghi (图1)(图2)1.2棋子的名称 为方便表示,中国象棋的棋子名称除了用汉字以外,还可以用字母,字母可从国际象棋中稍加改动得到,而数字是为了方便着法的输入以便用在数字小键盘上见表1:红方黑方字母英文单词数字帅将KKing1仕士AA

10、dvisor2相象BBishop3马马NKnight4车车RRook5炮炮CCannon6兵卒PPawn7(表1)1.3棋谱的记录方法现以如下局面为例说明各种记谱方法对于右图的局面,记法如下:1.炮二平五 炮8平52.炮五进四 士4进53.马二进三 马8进74.炮八平五 马2进35.前炮退二 车9平81.3.1 坐标记法坐标格式包括:棋子的名称、起点和终点的位置(起点和终点用-连接),对上面的走法,记录如下(省略了吃子、将军等信息):1、Ch2-e2炮二平五Ch7-e7炮8平52、Ce2-e6炮五进四Ad9-e8士4进53、Nh0-g2马二进三Nh9-g7马8进74、Cb2-e2炮八平五Nb9

11、-c7马2进35、Ce6-e4前炮退二Ri9-h9车9平81.3.2 中文纵线记法这种格式是中国象棋棋谱的常规记法,在各类出版物中最为普遍。但是这里还是要说明两个重要的细节。 1、仕士和相象如果在同一纵线上,不用“前”和“后”区别,因为能退的一定在前,能进的一定在后。 2、兵要按情况讨论:1 三个兵在一条纵线上:用“前”、“中”和“后”来区别; 2 三个以上兵在一条纵线上:最前面的兵用“一”代替“前”,以后依次是“二”、“三”、“四”和“五”; 3 在有两条纵线,每条纵线上都有一个以上的兵:按照“先从右到左,再从前到后”即先看最左边一列,从前到后依次标记为“一”和“二”,可能还有“三”,再看右

12、边一列的顺序,把这些兵的位置标依次标记为“一”、“二”、“三”、“四”和“五”,不在这两条纵线上的兵不参与标记。 如右图局面,四个兵分别位于四线和六线,下表列举了几种走法的坐标格式和纵线格式。中文纵线格式符号纵线格式坐标格式一兵平五Pa.5Pf8-e8二兵平五Pb.5Pf6-e6兵五进一P5+1Pe7-e8三兵平五Pc.5Pd8-e8四兵平五Pd.5Pd6-e6 另外需要注意的是: 1 如果黑方出现数字,不管数字代表纵线标号还是前进或后退的格数,都用阿拉伯数字表示,在计算机中显示全角的数字。但是代表同一纵线上不同兵的“一二三四五”它们类似于“前中后”的作用例外,例如例局面红黑互换,那么某步着法

13、就应该写成“一卒平5”。 2 在传统的象棋记谱中,如果发生以上这种情况,通常用五个字来表示,例如“前兵四平五”等,在计算机处理过程中就比较麻烦,因为4个汉字一个汉字占16位的着法可以储存在一个64位的字当中在C语言中数据类型为_int64或long long,而增加到5个汉字就比较麻烦了。黑方用全角的数字是同一个道理。 1.3.3 符号纵线记法这种格式仅仅是用字母和数字代替汉字,其中“进”、“退”和“平”分别用符号“+”、“-”和“.”表示,“前”、“中”和“后”也分别用符号“+”、“-”和“.”表示,并且写在棋子的后面例如“前炮退二”写成“C+-2”而不是“+C-2”,多个兵位于一条纵线时,

14、代替“前中后”的“一二三四五”分别用“abcde”表示这种情况极少发生。 另外,代表棋子名称的第一个字母,还可以用数字1到7表示,这是为了方便数字小键盘的输入,例如“炮二平五”可以记作“62.5“6代表炮选用符号“+”、“-”和“.”也是出于这个考虑。1.4 历史局面的表示及存储 中国象棋的一个局面可以用一个“FEN格式串”来表示。FEN格式串是由4段ASCII字符串组成的代码彼此3个空格隔开,这4段代码的意义依次是: 1 棋盘上的棋子,这是FEN格式串的主要部分; 2 当前局面轮到哪一方走子; 3 最近一次吃子或者进兵后棋局进行的步数半回合数,用来判断“50回合自然限着”; 4 棋局的回合数

15、。现以最初局面为例详细说明如下:rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w 0 1第一部分w前面的字符:表示棋盘布局,小写表示黑方棋子,大写表示红方棋子。例如前九个字母rnbakabnr表示棋盘第一行的棋子分别为黑方的“车马象士将士象马车”,“/”为棋盘行与行之间的分割;数字“95,1”表示该行从该位置起连续95,1个位置无棋子。第二部分w:表示轮到哪一方走棋,如果是w表示轮到红方白方走,是b表示轮到黑方走。第三部分w后的数字0:表示自然限着。第四部分w后的数字1:表示当前局面的回合数。1.5 棋谱记录文件的格式

16、存放棋谱的文件分为两个部分:标签部分和棋谱部分,现分述如下:1.5.1 标签部分 有如下标签 1、Event:比赛名; 2、Site:比赛地点; 3、Date:比赛日期,格式统一为"/0>." 4、Red:红方棋手; 5、Black:黑方棋手; 6、Result:比赛结果,“红先胜”用“1-0”表示,“黑先胜”用“0-1”表示,和棋用“1/2-1/2” 7、FenStr:起始局面。如果空缺,表示起始局面是最初局面。1.5.2 棋谱记录部分 棋谱记录部分必须在标签部分的后面,棋谱部分当中不能插入标签; 每一回合都由“回合数”、“红方着法”和“黑方着法”三部分组成,回合数

17、后面要跟“.”句点,三者之间用两个分隔符隔开回合数后面的句点也不例外,回合之间也用分隔符隔开。现举一个例子如下:例1:Event "第19届五羊杯全国象棋冠军邀请赛"Date "1998.12"Site "广州"Red "徐天红"Black "许银川"Result "1/2-1/2"1. 炮二平五 马8进7 2. 马二进三 车9平83. 车一平二 马2进3 4. 兵七进一 卒7进15. 车二进六 炮8平9 6. 车二平三 炮9退17. 马八进九 车8进5 8. 兵五进一 马3

18、退59. 炮八进四 炮2平510. 马九进七 炮9平7例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. 兵一进一 卒7进147. 兵一平二 卒7进148. 前兵平三 卒7平649. 马三退五 马5退350. 兵二平三 马3进2

19、51. 马五退六 1.5.3 XML格式全国象棋冠军邀请赛 广州 1999.12.09 许银川 聂卫平 rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/9/1C5C1/9/RN2K2NR r - - 0 11-0炮八平五炮8平5 第二章 基本数据结构?位棋盘2.1 什么是位棋盘 在中国象棋中,棋盘有90个交叉点。位棋盘其实就是一个长度为90位的变量,每个位对应一个交叉点,用来记录棋盘上的某些布尔值。在Java中,用3 个int类型数据(每个32位,共96位多余的6位不用)表示一个位棋盘。2.2 位棋盘的作用 位棋盘的作用,可从回答下面的问题开始:“哪些格子上面有棋子?” “哪些

20、格子上面有白棋(黑棋)棋子?” “哪些格子上面有车(马,炮等)?” “哪些格子受到a7格上的棋子的攻击?”不用管格子上是否有棋子或是什么颜色的棋子。 “如果有马在a3格上,哪些格子会受到它的攻击?” 通过回答上面的问题,可设置如下一些位棋盘1、记录所有棋子位置的位棋盘AllPieces。AllPieces告诉我们棋盘上哪些格子有棋子,哪些没有。当棋子处于最初位置的时候,“AllPieces”看上去是这个样子的以下描述中,格子的下标从0开始,坐标的图示见第一章“棋盘的标记”:Hi,89,a9111111111 000000000 101010101 000000000 000000000 101

21、010101 000000000 010000010 000000000 111111111Low,0,i0 其最高位对应第89格a9格,左上角,最低位对应第0格a8格,右下角。 这样显示位棋盘可能更形象一点: 黑棋111111111000000000010000010101010101000000000000000000101010101000000000010000010000000000111111111红棋2、记录所有黑棋棋子初始位置的位棋盘BlackPieces如下记录红棋棋子初始位置的位棋盘RedPieces与此类似,在此不再列出11111111100000000001000001

22、0101010101000000000000000000000000000000000000000000000000000000 3、记录各兵种如红棋车的初始位置的位棋盘“redRooks”如下:000000000000000000000000000000000000000000000000000000000000000000000000000000000100000001 4、假如我们创建了一个位棋盘数组knight90,用“knight0”位棋盘记录当马在0格即i0格时,棋盘上所有受到它攻击的格子,knight89记录当马在第89格a9格时,棋盘上所有受到它攻击的格子,那么,“knight

23、20”就是这个样子的(为了直观,用“x”标记出马的位置,实际上该位置是“0”): 000000000000000000000000000000000000000000000000001010000010001000000x000000100010000010105、用另外一个位棋盘数组HorseLeg90记录蹩马腿位置的位棋盘。与Knight20对应的HorseLeg20如下在实际系统中,根据马的行走方向单独设置只有一个蹩腿位的位棋盘,knight数组更改为knight908:00000000000000000000000000000000000000000000000000000000000

24、0100000001x100000001000000000006、建立全局数组“BitBoard bitMask90” ,用来屏蔽或设置位棋盘中的某位。bitMask0是这样的: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001mask89 是这样的: 1000000000000000000000000000000000000000000000000000000000000000000000000000000002.3 位棋盘的基本运算 1、与& 0 1

25、0 1 1 0 0 1 ? 0 0 0 1 2、或| 0 1 0 1 1 0 0 1 ? 1 1 0 1 3、异或 0 1 0 1 1 0 0 1 ? 1 1 0 0 4、取补 a 0001,a 1110。 2.4 Java中位棋盘的实现2.4.1 位棋盘类的实现 Java中,位棋盘用3个int型的数据表示,最高六位不用。Java中“与、或、非、异或、左位移,右位移(注意,位棋盘的右位移是无符号位移)”分别是“&、|、”。代码摘要(详细代码见附件)及相关说明如下: public class BitBoardprivate int Low,Mid,Hi/用3个int字段表示位棋盘,最高位

26、Hi的高/6位不用 public BitBoardint Arg1, int Arg2, int Arg3 /构造函数 Low Arg1; Mid Arg2; Hi Arg3; public static BitBoard opAndBitBoard arg1,BitBoard arg2 /位棋盘的“与”操作,保存结果。 int lowarg1.Low & arg2.Low; int midarg1.Mid & arg2.Mid; int hiarg1.Hi & arg2.Hi; return new BitBoardlow,mid,hi; public static

27、BitBoard opOrBitBoard arg1,BitBoard arg2 /位棋盘的“或”操作,保存结果。 public static BitBoard opXorBitBoard arg1,BitBoard arg2 /位棋盘的“异或”操作,保存结果。 public static int countBitBoard arg /计算位棋盘中非零位的个数public static BitBoard duplicateint arg /复制位棋盘public static boolean equalsBitBoard arg1,BitBoard arg2 /位棋盘是否相等(所有90位对应的

28、位相同即/为相等)public static BitBoard leftShiftBitBoard arg,int num /位棋盘arg左位移num位public static rightShiftBitBoard,int num /位棋盘右位移num位public static int LSBBitBoard Arg /位棋盘最低非0位的位置(从0开始计数) public static int MSBBitBoard Arg /位棋盘最高非0位的位置(从0开始计数) public static boolean notZeroBitBoard Arg /是否非“0”。当90位中有非0位时返回

29、true。 2.4.2 位棋盘的初始化 某些位棋盘从程序开始运行到结束都不会改变。例如上面所述的那个位棋盘数组“knight90”。他实际上记录了当马在任意格子上时,它下一步可以走的格子。这个数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例如“AllPieces”位棋盘。当中国象棋棋盘变化时,它也跟着变化。然而,他们的初始化方式相同。对于诸如knight90这样不变化的位棋盘的初始化,将在“伪着法生成”章节详述。此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。 首先,初始化“BitBoard bitMask90”数组: BitBoard b new Bit

30、Board0,0,1; for int c 0; c 90; c + maskc BitBoard.leftShiftb,c; 其次,用一个叫 ChessPosition类记录棋盘上某一状态的所有有用信息。它包含了一个整型数组 int piece_in_square90,还包含了一些位棋盘。 public class ChessPosition int piece_in_square90; int player; /轮到哪方走棋,0:红方走,1:黑方走 BitBoard allPieces; BitBoard redKing;/红帅 BitBoard blackKing;/黑将 BitBoar

31、d redRooks;/红车 BitBoard blackRooks;/黑车 BitBoard redKnights;/红马 BitBoard blackKnights;/黑马 BitBoard redCannon;/红炮 BitBoard redCannon;/黑炮 BitBoard redBishops;/红相 BitBoard blackBishops;/黑象 BitBoard redAdvisor;/红仕 BitBoard blackAdvisor;/黑士 BitBoard redPawns;/红兵 BitBoard blackPawns;/黑卒 BitBoard redPieces;

32、/所有红棋子 BitBoard blackPieces;/所有黑棋子; 初始化“piece_in_square”数组。 piece_in_square0 RED_ROOK; piece_in_square1 RED_KNIGHT;piece_in_square2 RED_BISHOP; piece_in_square89 BLACK_ROOK; 现在初始化其他一些位棋盘:for c 0; c 90; c + switch piece_in_squarec case : RED_ROOK position.redPieces /.Pieces,bitMaskc; position.redRook

33、s/.Rooks,bitMaskc; break; 2.4.3 位棋盘的更新当棋盘局面变动后,某些位棋盘就需要被更新。例如记录白子所在位置的“WhitePieces”位棋盘。假如我们把h2格的红炮移动到h9格(炮二进七),吃掉黑棋的一个马,需要更新如下位棋盘:allPiecesredPieces redCannonsblackpiecesblackKnights首先,要把redPieces,redCannons位棋盘的“h2”位清零,然后把他们的“h9”位置1。/* clear a bit with the "XOR" operation */ position.allPi

34、eces /.Pieces,bitMaskh2;position.redPieces /.Pieces,bitMaskh2; position.redCannons /.Cannons,bitMaskh2; /* set a bit with the "OR" operation */ position.redPieces /.Pieces,bitMaskh9; position.redCannons /.Cannons,bitMaskh9; 现在我们要将blackPieces和blackKnights位棋盘的h9位清除,因为那里的黑马被吃掉了。/* clear the c

35、aptured piece */ position.blackPieces /.ckPieces,bitMaskh9; position.blackKnight /.ckPieces,bitMaskh9第三章 基本数据结构?Zobrist键值3.1 比较局面的方法 在写中国象棋程序时,需要比较两个局面看它们是否相同。如果比较每个棋子的位置,或许不需要花很多时间,但是实战中每秒种需要做成千上万次比较,因此这样会使比较操作变成瓶颈的。另外,需要比较的局面数量多得惊人,要存储每个棋子的位置,需要占用非常大的空间。 一个解决方案是建立一个标签,通常是64位。由于64位不足以区别每个局面,所以仍然存在冲

36、突的标签,但实战中这种情况非常罕见。3.2 Zobrist键值的实现方法 实现Zobrist必须从多维的64位数组开始,每个数组含有一个随机数。在Java中,“rand.nextLong”函数返回一个64位的随机数值。 这个函数用来填满一个long型(64位)的三维数组:棋子的类型、棋子的颜色和棋子的位置: long zobristpccosq; 程序启动时就把这个数组用随机数填满。要为一个局面产生Zobrist键值,首先把键值设成零,然后找棋盘上的每个子,并且让键值跟“zobristpccosq”做异或通过“”运算符运算。 如果局面由白方走,那么别去动它,如果是黑方走,你还要在键值上异或一个

37、64位的随机常数。3.3 Zobrist键值的工作原理及用途3.3.1 Zobrist键值的工作原理 用Zobrist技术产生的键值,表面上跟局面没什么关系。如果一个棋子动过了,就会得到完全不同的键值,所以这两个键值不会挤在一块儿或者冲突。当把它们用作散列表键值的时候会非常有效。 另一个优点在于,键值的产生是可以逐步进行的。例如,红马在e5格,那么键值里一定异或过一个“zobristKNIGHTREDE5”。如果再次异或这个值,那么根据异或的工作原理,这个马就从键值里删除了。 这就是说,如果有当前局面的键值,并且需要把红马从e5移到f7,你只要异或一个“红马在e5”的键值,把马从e5格移走,并

38、且异或一个“红马在f7”的键值,把红马放在f7上。比起从头开始一个个棋子去异或,这样做可以得到同样的键值。 如果要改变着子的一方,只要异或一个“改变着子方”的键值就可以了。用这种方法,可以在搜索根结点的时候构造一个Zobrist键值,在搜索时通过走子函数“MakeMove”来更新键值,一直让它保持和当前局面同步。 3.3.2 Zobrist键值的用途 Zobrist键值通常用在散列键值当中,而散列键值在象棋程序里有以下几个作用: 1、用Zobrist键值来实现置换表。置换表是一个巨大的散列表,来保存以前搜索过的局面,这样可以节省很多搜索的时间。如果需要对某个局面搜索9层,可以从置换表中查找该局

39、面,如果它已经搜索过9层,那么不必去重复搜索。置换表的另一个并不起眼的作用是,它可以帮助我们改善着法的顺序。 2、可以用Zobrist键值制造一个很小的散列表,来检测当前着法路线中有没有重复局面,以便发现长将或其他导致和局的着法。3、可以用Zobrist键值创建支持置换的开局库。 3.4 Java中实现Zobrist键值 本系统使用一个key和一个lock结合来区分每个局面,这样发生冲突(即两个局面对应的key和lock一样)的概率几乎为0。示例代码及相关说明如下 1、填充数组。 上述的三维数组现在改变为二维(将颜色与棋子兵种类型合并) public static long ZobristKe

40、yPlayer;/改变走子方的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.setSeedRandSeed; Z

41、obristKeyPlayer rand.nextLong; for i 0; i 14; i + /0:红帅1:红仕2:红相3:红马4:红车5:红炮6:红兵 /7:黑将8:黑士9:黑象10:黑马11:黑车12:黑炮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、移子函数 当移动(添加、删除)一个棋子时,将当前局面的

42、Zobrist键值与键值表中该棋子的键值进行异或操作,同时也与改变走子方的键值进行异或操作。public class ChessPositionlong ZobristKey, ZobristLock; /当前局面的zobrist键值public ChessPosition ZobristKey0;/初始化为0 ZobristLock0; public void makeMoveint Square, int Piece, boolean IsAdd ZobristKeyZobristKeyTablePieceTypeSquare; ZobristLockZobristLockTablePie

43、ceTypeSquare; ZobristKey ZobristKeyPlayer;/改变走子方 ZobristLock ZobristLockPlayer; 3、开局库:开局库的实现,将在“搜索方法”中说明。第四章 着法生成着法生成在不同的象棋引擎中差异较大。本章使用位棋盘生成着法的基本原理。高级的国际象棋引擎通常具备一次只生成一小部分着法的能力。例如,仅生成象走的着法,马走的着法,“将”的着法,所有的吃子着法等等,这正是位棋盘的强项。那为什么用这种方式生成着法呢?原因是生成着法耗费一定的时间。如果引擎在检查了一部分着法后发现了必须走的棋,那它就无需生成余下的棋步了。因此,可能先生成所有吃子

44、的着法,如果没有满意的棋再生成余下的着法。用来减少耗时的着法生成策略很多?发挥你的想象力吧。 大名鼎鼎的免费国际象棋引擎Crafty其作者是Robert Hyatt博士使用三个着法生成函数。一个用来生成所有伪合法吃子着法,一个生成所有伪合法不吃子着法,最后一个生成所有摆脱被将军状态的着法。注意前两个函数生成的是伪合法的着法。就是说,这些函数生成的着法并非都是合法的。例如,你要生成所有将军的着法并且发现了一步你想走的棋,但随后发现这步不合法再把它抛弃。这看起来很奇怪,但它确实比那种在所有局面下都严格生成合法着法的策略更快!Hyatt博士曾经这样解释:当国王被将时,你需要生成摆脱被将的着法,这时大

45、部分生成的着法是不合法的,在这种局面中你使用生成所有合法着法的策略会帮你节省时间;但在大多数局面中,生成的着法都是合法的,推迟验证合法性会更有效率。中国象棋的着法生成与此类似,先生成所有伪合法的着法,存入静态数组中。在对局中可以用“查表”的方式查找生成的伪着法,并对其合法性作出判断。这样可以节省大量的时间。4.1伪合法着法的生成伪合法着法包含几类:各兵种的不吃子着法各兵种的吃子着法“将”和摆脱“将”的着法其中,马、相(象)、兵、帅(将)、仕(士)的吃子着法与其对应的不吃子着法规则相同。(伪合法着法并不考虑被吃的棋子的颜色?该棋子是对方的棋子还是己方的棋子,也不考虑该子是否能动,例如动了该子,双

46、方的帅将会面。)炮和车的不吃子着法规则相同,但分为纵向横向行走两类。炮的吃子着法分为纵向和横向两类,车的吃子着法也分为纵向和横向两类。马和象的着法要考虑蹩马腿和塞象眼。将军的着法单独作为一类。本程序使用静态数组存储生成的位合法着法,先对其作一些说明。4.1.1 数组及其下标的含义1、保存帅(将)、仕(士)、相(相)、马、兵的伪合法静态数组如下:public static final int KingMovesnew int908;public static final int AdvisorMovesnew int908;public static final int BishopMovesn

47、ew int908;public static final int ElephantEyesnew int904;public static final int KnightMovesnew int9012;public static final int HorseLegsnew int908;public static final int PawnMovesnew int9024;第一个下标说明棋子所在的格,第二个下标含义不尽相同。帅(将)在某个位置最多有4种走法,例如KingMoves13012表示帅在13格(e1格)时可以走到12格(当然,也可以走到14、4、22格,保存到其他几个数组元

48、素中)。第5种(如果前面只有3种着法,则此处是第4种)保存的是非法着法即KingMoves134-1,其作用作为查询算法的“哨兵”,提高查询算法的速度。为了速度(以位移运算取代除法运算),第2个坐标值用2的整次方幂。(在后面所讲的开局库和置换表的大小设置是2的整次方幂也是这个道理。)兵的走棋规则需要分颜色,红色的垂直走棋方向和黑色的垂直走棋方向是相反的。兵最多有三种走棋方法。AdvisorMoves908保存的是士的着法。BishopMoves908保存的是相(象)的着法,ElephanEyes904保存的是相(象)着法对应的塞象眼的位置。KnightMoves和HorseLegs是马的着法和

49、蹩马腿的位置。2、车、炮的伪合法着法静态数组如下:public static final int FileNonCapMovesnew int10102412;/共十条横线,FileNonCapMovesybitWordYindexnewY,进public static final int FileRookCapMovesnew int1010244;public static final int FileCannonCapMovesnew int1010244;public static final int RankNonCapMovesnew int951212;/RankNonCapMovesxbitWordXindexnewX,平public sta