中国象棋算法

解剖大象的眼睛中国象棋程序设计探索 黄晨 *2005年6月 ( * 联系地址：复旦大学化学系表面化学实验室，eMail：morning_) (一) 引言 我在今年2月写出了象棋程序ElephantEye的第一个版本(0.90)，本来它只是象棋界面ElephantBoard的调试引擎。在设计程序的过程中，我尝试性地加入了很多算法，发现每次改进都能让程序的棋力有大幅度的提高，因此便对象棋程序的算法产生了浓厚的兴趣。到现在我已经陆续对ElephantEye作了几十次加工(目前版本为0.94)，使得它的棋力接近了中等商业软件的水平，在公开源代码的象棋程序中，ElephantEye是最强的一个。 我希望能通过公开源代码的方式，推动中国象棋程序水平的整体发展，然而根据很多网友的反馈意见，发现源代码中的很多部分并不是那么容易理解的。因此我才打算以中国象棋程序设计探索为题，写几篇详细介绍ElephantEye算法的连载，希望能让的源代码充分发挥它的作用。 下面我先简要谈一下我自己对ElephantEye的体会。 1.1 ElephantEye用到了哪些算法？ 在我写本次连载以前，我已经完成了象棋百科全书网站上对弈程序基本技术专题中所有文章的翻译，ElephantEye的大部分算法都参考了这些文章，这些算法我会在连载中一笔带过，详细的内容希望读者参考这些译文，那里还有我加的很多译注，希望它们能够加深读者对这些算法的体会。 当然，仅根据这些文章所提供的算法，是写不出很好的程序的，我参考了王小春的PC游戏编程人机博弈一书，也参考了一些国际象棋的源程序，并通过自己的探索，在ElephantEye中加入了另外的非常重要的算法，尤其是启发算法，我认为它们在程序中发挥了关键性的作用，而且很多细节在绝大多数文字资料中没有详细给出，我会在我的连载中重点介绍。 我猜读者最感兴趣的内容是ElephantEye的着法生成器，这应该算是象棋程序的核心部分，同时也是各个程序差异最大的部分。在写ElephantEye以前，我在象棋百科全书网站上刊登了大量介绍“位棋盘”的文章，这是个非常有吸引力的思想，但是我试验下来觉得它的速度并不快，在ElephantEye的程序里我只把位棋盘运用在将军判断上。尽管如此，ElephantEye短短10行的将军判断也许是程序的一个亮点吧，那么这部分内容我将尽量介绍得详细一点。 此外，一些看似和棋力关系不大的技术，诸如开局库、长将检测、后台思考、时间策略、引擎协议等等，其实也直接影响着象棋程序的稳定性，因此也有必要逐一讲解。 总之，每个技术都很重要，我的连载虽然不能面面俱到，但我会尽我所能来作详细阐述的。 1.2 如何正确评价ElephantEye目前的棋力？ ElephantEye是“蛮力型”象棋程序，与大多数商业程序的不同之处在于，它没有审局能力，那么它的棋力到底有多强？网友对这个问题众说纷纭，有人认为它无法跟一流的商业软件相比，毕竟ElephantEye是免费程序，其源代码又是公开的，为什么非要去和顶尖程序去比呢？也有人认为它能战胜中等商业软件，但电脑对电脑和电脑对人类根本就不是一回事，这么一个不懂得防守空头炮的程序怎能说它厉害呢？还有人喜欢在同一搜索水平(比如6层、8层或10层)上比较两个不同的程序，这种标准去比较“蛮力型”程序和“知识型”程序，这有意义吗？ 要正确认识这个问题，我想说明几点： (1) 测试标准要合理，这个标准只能是“时限”，即给两个程序以同样多的时间，可以对每步都限定时间，也可以是比赛所采用的时段制或加时制，而不能以同样的搜索水平作标准。另外，如果两个程序运行在同一台电脑上，那么不能启用后台思考功能。 (2) 某几盘对局并不能说明问题，我以“浅红象棋”为平台用ElephantEye对阵“梦入神蛋”，ElephantEye遗憾地以2:3败北。我有充分的信心表明ElephantEye的棋力比梦入神蛋强得多，因为两者用了相同的评价函数，但同样时间ElephantEye通常要比梦入神蛋多搜索一层以上，那么2:3的比分又能说明什么问题呢？ (3) 跟人类比和跟电脑比是两回事，每个电脑程序都有弱点，这些弱点很容易被人类棋手抓住，但其他电脑程序则不会抓住你的弱点。一般认为，知识缺乏的程序弱点也多(例如ElephantEye不懂得防守空头炮)，因此对阵人类棋手失败的几率要比对阵其他程序高得多。 1.3 ElephantEye对象棋有哪些认识？ 要说ElephantEye一点象棋知识都不具备，这种观点我是无法接受的。很多搜索算法确实只能用在象棋上，这一点ElephantEye做得比很多商业程序都好，这些算法体现在以下几个方面： (1) 杀棋局面在置换表中的特殊处理，这使得ElephantEye识别杀棋的速度快了很多； (2) 将军扩展，这使得ElephantEye对可能有杀棋的线路特别感兴趣，它会在搜索上增加对这些路线的投入； (3) 带检验的适应性空着裁剪，这个算法首先由一个以色列学者发表于2002年(不是“适应性”的)，最近我对该算法作了改进，使得它能正确处理残局中的等着杀和连等着杀，速度也快了很多。 这些算法使得ElephantEye有很强的处理杀局和残局的能力，我相信绝大多数商业软件都没它做得好。如果一个程序能在很短的时间内告诉你，几步之后必定有一方会被将死，或者几步之后优势一方就可以破士或破象，那么这个程序的实用价值还算小吗？(二) 棋盘结构和着法生成器 在阅读本章前，建议读者先阅读象棋百科全书网站中对弈程序基本技术专题的以下几篇译文： (1) 数据结构简介(David Eppstein)； (2) 数据结构位棋盘(James Swafford)； (3) 数据结构旋转的位棋盘(James Swafford)； (4) 数据结构着法生成器(James Swafford)； (5) 数据结构0x88着法产生方法(Bruce Moreland)； (6) 数据结构Zobrist键值(Bruce Moreland)； (7) 其他策略重复检测(Bruce Moreland)。 2.1 局面和着法的表示 局面是象棋程序的核心数据结构，除了要包括棋盘、棋子、哪方要走、着法生成的辅助结构、Zobrist键值等，还要包含一些历史着法，来判断重复局面。ElephantEye的局面结构很庞大(见)，其中大部分存储空间是用来记录历史局面的。 struct CchessPosition int MoveNum; MoveStruct MoveListMaxMoveNum; / MaxMoveNum = 256 char LoopHashLoopHashMask + 1; / LoopHashMask + 1 = 1024 其中MoveStruct这个结构记录了四个信息：(1) 着法的起始格(Src)，(2) 着法的目标格(Dst)，(3) 着法吃掉的棋子(Cpt)，(4) 着法是否将军(Chk)。有意思的是，每个部分都只占一个字节，后两个部分(Cpt和Chk)与其说有特殊作用，不如说是为了凑一个32位整数。在MoveStruct出现的很多地方(置换表、杀手着法表、着法生成表)里，这两项都是没作用的，而只有在CchessPosition结构的记录历史着法的堆栈中才有意义。 Cpt一项主要用在撤消着法上，它可以用来还原被吃的棋子，而Chk一项则可以记录当前局面是否处于将军状态。ElephantEye是用MovePiece()函数来走棋的，每走完一步棋就做两次将军判断：第一次判断走完子的一方是否被将军，即Checked(Player)，如果被将则立即撤消着法，并返回走子失败的信息；第二次判断要走的一方是否被将军，由于交换了走子方(即执行了Player = 1 - Player)，所以仍旧是Checked(Player)，如果被将则Chk置为1，这个着法被压入历史着法堆栈。因此LastMove().Chk就表示当前局面是否被将军。 2.2 循环着法的检测 Cpt和Chk的另一个作用就是判断循环着法：ElephantEye判断循环着法时，依次从堆栈顶往前读，读到吃过子的着法(Cpt不为零)就结束；而是否有单方面长将的情况，则是通过每个着法的Chk一项来判断的。 在循环着法的检测中，我们感兴趣的不是Cpt和Chk，而是LoopHash结构，这是一个微型的置换表，用来记录历史局面。ElephantEye在做循环着法的判断这之前，先去探测这个置换表，如果命中置换表，则说明可能存在重复局面(由于置换表可能有冲突，所以只是有这个可能)，因而做循环检测；如果没有命中则肯定没有重复局面。 ElephantEye使用“归位检测法”来判断循环着法，即从最后一个着法开始，依次向前撤消着法，并记录每个移动过的棋子所在的格子。如果所有移动过的棋子同时归位，那么循环着法就出现了。因此中的IsLoop()函数建立了两个归位数组，第一个记录了棋子的原始位置，第二个记录了新的位置，当两个位置重合时，说明棋子归位。 2.3 棋盘-棋子联系数组 众所周知，棋盘的表示有两种方法。一是做一个棋盘数组(例如Squares109)，每个元素记录棋子的类型(包括空格)；二是做一个棋子数组(例如Pieces32)，每个元素记录棋子的位置(包括被吃的状态)。如果一个程序同时使用这两个数组，那么着法生成的速度就可以快很多。这就是“棋盘-棋子联系数组”，它的技术要点是： (1) 同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。 (2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。 根据这两个原则，棋盘-棋子联系数组可以定义为： struct CchessPosition int Squares90; int Pieces32; ; 棋子数组Pieces48是ElephantEye的一个特点，0到16没有作用，16到31代表红方棋子(16代表帅，17和18代表仕，依此类推，直到27到31代表兵)，32到47代表黑方棋子(在红方基础上加16)。这样，棋盘数组Squares90中的每个元素的意义就明确了，0代表没有棋子，16到31代表红方棋子，32到47代表黑方棋子。这样表示的好处就是：它可以快速判断棋子的颜色，(Piece & 16)可以判断是否为红方棋子，(Piece & 32)可以判断是否为黑方棋子。 棋子数组Squares90存储的是每个棋子所在的格子，用“列 x 10 + 行”表示(稍后再来解释为什么不用“行 x 9 + 列”，红方最左边的车为0，黑方最左边的车为89。这个数值整除10得到的商就是列号，余数就是行号，如果是-1，就代表这个子已被吃掉。 在棋盘上删除一个棋子，需要做两个操作(分别修改棋盘数组和棋子数组)。同样，添加一个棋子时也需要两个操作。执行一个着法时有三个步骤： (1) 如果目标格上已经有棋子，就要先把它从棋盘上拿走(吃子的过程)； (2) 把棋子从起始格上拿走； (3) 把棋子放在目标格上。 因此执行着法简单地说就是两个ClearPiece()操作(其中一个只发生在吃子时)和一个SetPiece()操作，撤消着法的过程正好相反，但也是两个ClearPiece()和一个SetPiece()。当然，ElephantBoard为了减少代码，把ClearPiece()和SetPiece()合并为一个函数ChangePiece()，它除了修改棋盘数组和棋子数组外，还修改Zobrist键值、位棋盘、位行和位列等信息。 “棋盘-棋子联系数组”最大的优势是：移动一步只需要有限的运算。对于着法产生过程，可以逐一查找棋子数组，如果该子没有被吃掉，就产生该子的所有合理着法，由于需要查找的棋子数组的数量(每方只有16个棋子能走)比棋盘格子的数量(90个格子)少得多，因此联系数组的速度要比单纯的棋盘数组快很多。可以说，“棋盘-棋子联系数组”是所有着法生成器的基础，位棋盘等其他方法都只是辅助手段。 如今，很少有程序使用Squares90和Pieces32这样的数组了，浪费一些存储空间以换取速度是流行的做法，例如ElephantEye就用了Pieces48。更多的程序使用Squares256，这样求得行号和列号就可以用16除，这要比用9或10除快得多。当然，把棋盘扩展成16行和16列还有更大的好处，它可以防止棋子走出棋盘边界，这点会在后面提到。 2.4 扩展棋盘和着法预产生数组 在中国象棋里，短程棋子(短兵器)指的是除车和炮以外的其他棋子，它们的着法都有固定的增量(行的增量，列的增量)，因此处理起来非常简单，也是着法生成技术的基础。例如马有8个着法，增量分别是(1, 2)、(-1, 2)、(1, -2)、(-1, -2)、(2, 1)、(2, -1)、(-2, 1)和(-2, -1)，红方的过河兵有3个着法，增量分别是(1, 0)、(0, 1)和(0, -1)。 当棋盘上的格子使用了统一的编号以后，增量也就由两个坐标变成了一个坐标。以16x16的棋盘为例，马的8个增量就是0x0e、0x12、0x1f和0x21，兵的3个增量就是0x01和0x10。在16x16的扩展棋盘如下图所示，底色是红色的格子都被标上“出界”的标记，目标格在这些格子上就说明着法无效。这样，马的着法产生就非常简单了： const int MaxHorseMove = 8; const int HorseMovDeltaMaxHorseMove = -0x21, -0x1f, -0x12, -0x0e, +0x0e, +0x12, +0x1f, +0x21; const int HorseLegDeltaMaxHorseMove = -0x10, -0x10, -0x01, +0x01, -0x01, +0x01, +0x10, +0x10; for (i = MyFirstHorse; i MyLastHorse; i +) / 在ElephantEye的Pieces48中，红方的MyFirstHorse为21，MyLastHorse为22。 SrcSq = Piecesi; if (SrcSq != -1) for (j = 0; j MaxHorseMove; j +) DstSq = SrcSq + HorseMovDeltaj; LegSq = SrcSq + HorseLegDeltaj; if (InBoardDstSq & !(SquaresDstSq & MyPieceMask) & !SquaresLegSq) MoveListMoveNum.Src = SrcSq; MoveListMoveNum.Dst = DstSq; MoveNum +; 上面的代码是着法生成器的典型写法，用了两层循环，第一层循环用来确定要走的棋子，第二层循环用来确定棋子走到的目标格。如果要加快程序的运行速度，第二个循环可以拆成顺序结构。 这个代码还加入了蹩马腿的判断，马腿的位置增量由HorseLegDeltaj给出。另外有个诀窍，如果把所有出界的格子都设置MyPieceMask和OppPieceMask标志(如果用前面所说的Pieces48这个数组，那么出界的格子可以用16 + 32 = 48表示)，那么InBoardDstSq的判断也可以省去了。 其它棋子的着法也同样处理，只要注意帅(将)和仕(士)把InBoardDstSq改为InCityDstSq就可以了。而对于兵和象等需要考虑是否能过河的棋子，判断是否过河的方法非常简单：红方是(SrcSq/DstSq & 0x80)，黑方是!(SrcSq/DstSq & 0x80)。 f0f1f2f3f4f5f6f7f8f9fafbfcfdfeffe0e1e2e3e4e5e6e7e8e9eaebecedeeefd0d1d2d3d4d5d6d7d8d9dadbdcdddedfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfb0b1b2b3b4b5b6b7b8b9babbbcbdbebfa0a1a2a3a4a5a6a7a8a9aaabacadaeaf909192939495969798999a9b9c9d9e9f808182838485868788898a8b8c8d8e8f707172737475767778797a7b7c7d7e7f606162636465666768696a6b6c6d6e6f505152535455565758595a5b5c5d5e5f404142434445464748494a4b4c4d4e4f303132333435363738393a3b3c3d3e3f202122232425262728292a2b2c2d2e2f101112131415161718191a1b1c1d1e1f000102030405060708090a0b0c0d0e0fElephantEye用的是Squares90，着法生成器就没这么简单了。对于每个短程子力，都给定一个904到909不等的数组，它们保存着棋子可以到达的绝对位置，这些数组称为“着法预产生数组”。ElephantEye的着法预产生数组数组有些奇怪，用了HorseMovs909(在目前的中，则是KnightMoves9012)和HorseLegs908，前一个数组的第二个维度之所以是9，是因为着法生成器依次读取数组中的值，读到-1就表示不再有着法。程序基本上是这样的： for (i = MyFirstHorse; i = MyLastHorse; i +) SrcSq = Piecesi; if (SrcSq != -1) j = 0; DstSq = HorseMovsSrcSqj; while (DstSq != -1) LegSq = HorseLegsSrcSqj; if (!(SquaresDstSq & MyPieceMask) & !SquaresLegSq) MoveListMoveNum.Src = SrcSq; MoveListMoveNum.Dst = DstSq; MoveNum +; j +; DstSq = HorseMovsSrcSqj; 和前一个程序一样，这个程序也同样用了两层循环，不同之处在于第二个循环读取的是着法预产生数组，DstSq从HorseMovs909中读出，LegSq从HorseLegs908中读出，DstSq中最后一个值总是-1，所以HorseMovs的第二个维度要比HorseLeg多1。ElephantEye的着法生成器由提供，着法预产生数组则在程序初始化时生成，初始化过程由提供。 2.5 位行和位列 车和炮的着法分为吃子和不吃子两种，这两种着法生成器原则上是分开的，因此分为车炮不吃子、车吃子和炮吃子三个部分。不吃子的着法可以沿着上下左右四条射线逐一生成(即并列做4个循环)。我们感兴趣的是吃子的着法，因为静态搜索只需要生成这种着法，能否不用循环就能做到？ElephantEye几乎就做到了。 “位行”和“位列”是目前比较流行的着法生成技术，但仅限于车和炮的着法，它是否有速度上的优势还很难说，但是设计程序时可以减少一层循环，这个思想就已经比较领先了。以“位”的形式记录棋盘上某一行所有的格子的状态(仅仅指是否有子)，就称为“位行”(BitRank)，与之对应的是“位列”(BitFile)，棋盘结构应该包含10个位行和9个位列，即： struct CchessPosition int BitFiles9; int BitRanks10; ; 值得注意的是，它仅仅是棋盘的附加信息，“棋盘-棋子联系数组”仍旧是必不可少的。它的运作方式有点和“棋盘-棋子联系数组”类似： (1) 同时用位行数组和位列数组表示棋盘上的棋子分布信息，位行数组和位列数组之间可以互相转换； (2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。 因此，移走或放入一颗棋子时，必须在位行和位列上置位： void SetPiece(int Square, int Piece) x = Square / 10; y = Square % 10; BitFilesx = 1 y; BitRanksy = 1 x; 车和炮是否能吃子(暂时不管吃到的是我方棋子还是敌方棋子)，只取决于它所在的行和列上的每个格子上是否有棋子，而跟棋子的颜色和兵种无关，因此这些信息完全反映在位行和位列中。预置一个“能吃到的格子”的数组，以位行或位列为指标查找数组，就可以立即知道车或炮能吃哪个子了。预置数组到底有多大呢？ int FileRookCapUp101024; / 某列各个位置的车(10)在各种棋子排列下(1024)能吃到的左边的子 int FileRookCapDown101024; int RankCannonCapLeft9512; int RankCannonCapRight9512; 数组中的值记录的是目标格子的偏移值，即相对于该行或列第一个格子的编号。产生吃子着法很简单，以车吃子位例： for (i = MyFirstRook; i = MyLastRook; i +) SrcSq = Piecesi; if (SrcSq != -1) x = SrcSq / 10; y = SrcSq % 10; DstSq = FileRookCapUpyBitFilesx; if (DstSq != -1) DstSq += x * 10; / 注意：第x列的第一个格子总是x*10。 MoveListMoveNum.Src = SrcSq; MoveListMoveNum.Dst = DstSq; MoveNum +; / 再把FileRookCapUp替换成FileRookCapDown DstSq = RankRookCapLeftxBitRanksy; if (DstSq != -1) DstSq += y; / 注意：第y行的第一个格子总是y。 MoveListMoveNum.Src = SrcSq; MoveListMoveNum.Dst = DstSq; MoveNum +; / 再把RankRookCapLeft替换成RankRookCapRight ElephantEye的处理又和上面的代码有所不同，它把FileRookCapLeft和FileRookCapRight合并成一个数组：FileRookCapMoves1010243，用循环以减少代码。这样的着法预产生数组，还可以移植到不吃子的着法中去，即FileNonCapMoves10102410和RankNonCapMoves95129。为了提高代码的运行效率，ElephantEye把数组的最后一个维度改成4和12。 2.6 着法合理性的判断 ElephantEye搜索每个结点时，着法都有三个来源：(1) 置换表，(2) 杀手着法表，(3) 着法生成器。这三种来源分别代表了三种启发式算法：(1) 内部迭代加深，(2) 杀手着法启发，(3) 历史表启发，这会在以后的章节中介绍。 我们感兴趣的是杀手着法，它是以前搜索过的局面遗留下来的着法，当前的局面如果要使用这些着法，只需要做合理性的判断就可以了，如果杀手着法能产生截断，那么着法生成就没有必要了。因此，如何快速判断着法合理性，其意义可能比着法生成器还大。 ElephantEye判断着法合理性的程序包含在中，它分为三个步骤： (1) 判断棋子是否在棋盘上存在，如果不存在那么肯定不是合理着法； (2) 如果棋子是帅(将)、仕(士)或兵(卒)，那么肯定是合理着法； (3) 相(象)、马、车和炮需要作额外的判断。 我们感兴趣的是相(象)马车炮四子的判断，其中相(象)的判断最简单，由于象眼的位置总能用(SrcSq+DstSq)/2表示(不管是9x10还是16x16的棋盘)，所以判断合理性只需要一条语句： return !Squares(SrcSq + DstSq) 1; ElephantEye在马的判断上用了一个诀窍：构造了一个巧妙的数组： const int HorseLegTab43 = -10, 0, -10, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,10, 0,10, ; 上面的数组中，正中心的数代表马步的起始格(红色表示)，21、19、12和8是马步的增量(蓝色表示)(能被程序读到的就是这些位置)，它们记录了马腿的增量(马腿的位置用绿色表示)。这样，判断合理性也只需要一条语句： return !SquaresSrcSq + HorseLegTabDstSq - SrcSq + 21; 车和炮的判断就需要用到前面所说的位行和位列，对于吃子着法很容易理解，而不吃子着法只需要跟车吃子的着法相比较。方法很简单，如果不吃子着法的增量(绝对值)不超过不吃子着法的最大增量，那么着法就是合理的。这就需要首先要判断是否是吃子着法，然后根据不同情况作相应的判断。ElephantEye中有专门的判断着法合理性的数组，也在中生成，结构跟前面提到的着法预产生数组类似，只是把FileRookCapMoves1010243拆成了FileRookCapMax101024和FileRookCapMin101024了，它们和FileRookCapMoves1010243是一起生成的。 2.7 位棋盘与将军判断 将军判断是ElephantEye的一大特色，但这已经是时髦的“位棋盘”在ElephantEye中的最后一块阵地了。与大多数象棋程序不同，ElephantEye每执行一个着法就进行一次将军判断，这使得将军判断占用了很多程序运行的时间。更普遍的做法是延迟将军的判断，即当帅(将)被吃掉后程序才认识到前一个局面是将军，这会使得程序多花一层搜索才能判断出杀棋，但是毕竟将军不是经常发生的。笔者很早就考虑把将军判断从ElephantEye的代码中移走，但是担心这样会影响程序解杀局的速度，所以这使得位棋盘直到现在还保留在ElephantEye的代码中。 ElephantEye判断将军的方法，不是让每个子都走到帅(将)的位置看看是否能走，而是反过来问一个问题：敌方的子在哪些位置上，自己的将(帅)会被将军？ 对于每个兵种，ElephantEye都用了BitBoard .Check18.的结构，代表将(帅)的18个位置(双方的两个城池)上可能被这些棋子攻击的格子。判断将军时，只要用这个位棋盘“与”上该兵种所占格子的位棋盘，不为零就说明被将军了。对于兵来说，这样做具有非常高的效率，因为五个兵所占的格子被一张位棋盘表示，所以只需要做一次判断，不必五个兵逐一判断。而对于车马炮，这样做也不浪费时间，尤其是车，它的位棋盘可以和帅(将)合并在一起，被车将军和双王照脸可以一起判断。 从中看出，判断车(连同双王照脸)和炮将军的位棋盘数组，包括了纵线上将军的数组181024和横线上将军的数组18512，查找数组时分别要调用将所在的位置的位行和位列。而最有意思马将军的位棋盘数组18256，显然第二个指标代表蹩马腿的信息。可是为什么是256呢？这里面蕴涵着“折叠位棋盘”的思想。 “折叠位棋盘”的思想是由湖北襄樊铁路分局计算机中心的章光华提出的，首先于2004年底发表在象棋百科全书网站的论坛上。这个思想的要点是： (1) 棋盘必须按照列的方式对每个格子编号(如下图所示)，格子的编号代表96位位棋盘中的第几位； 091929394959697989081828384858687888071727374757677787061626364656667686051525354555657585041424344454647484031323334353637383021222324252627282011121314151617181001020304050607080(2) 初始化数组一个“马腿数组”，以表示某个格子上的马可能存在的马腿，例如： BitBoard HorseLegTable90; HorseLegTable0 = BitMask1 | BitMask10; HorseLegTable1 = BitMask11 | BitMask20; / BitMask0没必要加上去，而加上去也没错。 注意，这里仅仅是拿两个格子举例子，写在程序里的时候要用循环语句来生成马腿数组，以精简代码。 (3) 产生绊马腿的棋子的位棋盘，以红方左边未走过的马为例： HorseLeg = HorseLegTable10 & AllPieces; (4) 根据马的位置和绊马腿的位棋盘，就可以知道马可以走的格子，因此可以构造这样的函数： BitBoard KnightPinMove(int KnightSquare, BitBoard HorseLeg); 为了增加运算速度，应该用查表代替运算，即把函数变成数组。那么位棋盘HorseLeg如何转化成整数呢？这就引出了“折叠位棋盘”的技术，这可以称得上是一个炫技。折叠位棋盘实际上就是位棋盘的8位校验和(CheckSum)，有了折叠位棋盘后，上面的函数就可以用数组表示： BitBoard KnightPinMove90256; 例如第10个格子上马的所有着法，用位棋盘表示为： KnightMoveBitBoard = KnightPinMove10CheckSum(HorseLegTable10 & AllPieces); 相(象)的着法可以采用同样的原理，首先初始化象眼数组： BitBoard ElephantEyeTable90; 随后折叠象眼的位棋盘ElephantEye，再从相(象)的着法预产生数组BishopPlugMove90256中找到着法。 135713571024602460713571357602460246571357135460246024357135713246024602135713571024602460123456701012345670701234567670123456567012345456701234345670123234567012123456701012345670按纵线编号的棋盘按横线编号的棋盘看到这里，可能有的读者就会怀疑“折叠位棋盘”的合理性，如果折叠成4位的整数(甚至更少)，把马的着法预产生数组了缩小到90x16，这显然是不合理的，为什么8位就一定合理呢？ 要说明这个问题，首先来看折叠的本质校验和(CheckSum)，棋盘上的很多格子对应着校验和上固定的一位。根据这个性质，我们对棋盘重新编号，就如左图所示。假如河界下面蓝色的格子是马，那么相邻的红色格子就是马腿，4条马腿对应4个不同的编号，所以任何一种组合(一共有24 =16种组合)是不重复的。需要指出的是，这个棋盘当中所有的格子，其相邻的四个格子都有不同的编号。有趣的是，象眼同样符合这个规律(注意河界上面蓝色的格子，斜相邻的四个格子是象眼)。 折叠位棋盘的唯一性是建立在“按纵线编号”的基础上的。如果按横线编号，情况就不那么幸运了，如右图所示，无论是河界下面的马，还是河界上面的象，马腿或象眼都存在编号重复的格子。 位棋盘必须按纵线编号，就是这个原因。 ElephantEye并没有用“折叠位棋盘”的技术来做马和相(象)的着法生成器，但它在将军判断的过程中展示了风采。由于将军判断是从帅(将)出发的，所以将军的马腿CheckLegTable18实际上是象眼的位棋盘。 初始化KnightPinCheck18256这个庞然大物， 似乎处理起来一点头绪也没有。其实折叠位棋盘使用起来需要“折叠”，生成起来却需要“展开”(即CheckSum()函数对应的Duplicate()函数)。当8位的整数展开成位棋盘后，再和某个格子的CheckLegTable作“与”运算，就可以还原为CheckLeg了。 2.8 小节 棋盘结构和着法生成是众多象棋程序中区别最大的部分，以上只是介绍了几种比较流行的思路，具体的实现方法需要读者自己体会。ElephantEye在着法生成方面并不是做得最好的，但它主要体现了“着法预产生数组”的思想，ElephantEye产生了三种不同功能的数组：(1) 着法产生；(2) 着法合理性判断；(3) 将军判断。数组的生成方法在这里就不介绍了，建议读者先完全了解中的着法生成技术，回过头来再剖析中的代码。 解剖大象的眼睛中国象棋程序设计探索 黄晨 *2005年6月 ( * 联系地址：复旦大学化学系表面化学实验室，eMail：morning_) (三) 搜索与置换表 在阅读本章前，建议读者先阅读象棋百科全书网站中对弈程序基本技术专题的以下几篇译文： (1) 基本搜索方法简介(一)(David Eppstein)； (2) 基本搜索方法简介(二)(David Eppstein)； (3) 基本搜索方法简介(三)(David Eppstein)； (4) 基本搜索方法最小-最大搜索(Bruce Moreland)； (5) 基本搜索方法Alpha-Beta搜索(Bruce Moreland)； (6) 基本搜索方法迭代加深(Bruce Moreland)； (7) 基本搜索方法置换表(Bruce Moreland)； (8) 高级搜索方法简介(二)(David Eppstein)； (9) 高级搜索方法期望窗口(Bruce Moreland)； (10) 高级搜索方法主要变例搜索(Bruce Moreland)； (11) 高级搜索方法搜索的不稳定性(Bruce Moreland)； (12) 其他策略主要变例的获取(Bruce Moreland)； (13) 其他策略胜利局面(David Eppstein)。 3.1 搜索技术概述 搜索算法是象棋程序的核心算法，在众多搜索算法中，如何选择适合自己的算法，并有效地把它们组合起来，是决定搜索效率的关键所在。要做好这点，首先必须明确搜索的概念，把各种搜索算法作一下分类。 象棋程序的搜索算法都是基于“最小-最大”策略的，因此衍生出以Alpha-Beta为基础的完全搜索算法以及带裁剪的搜索算法。尽管Alpha-Beta算法也有裁剪的过程，但是这种裁剪被证明是绝对可靠的，没有无负面作用，即通常所说的“截断”(Cut-off)，它属于申朗所说的A策略。 我们现在所说的“裁剪”(Pruning)，特指“向前裁剪”(Forward Pruning)，即需要承担风险地对某些线路作的裁剪，也就是申朗所说的B策略。尽管它是完全搜索算法的对立面，但为了克服完全搜索中的“水平线效应”(Horizon Effect)，它是程序中必不可少的部分。把裁剪反过来，对某些重要线路进行“延伸”(Extension)，这种思想和裁剪有异曲同工之妙。 如今，“带置换表的启发式Alpha-Beta搜索”成了象棋程序的主流，这种思想强调对着法排序的重要性，排序着法是由“启发”(Heuristic