解剖大象的眼睛——中国象棋程序设计探索黄晨*2005年6月( * 联系地址：复旦大学化学系表面化学实验室，eMail：morning_yellow@elephantbas )(一) 引言我在今年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的局面结构很庞大(见<ccstruct.h>)，其中大部分存储空间是用来记录历史局面的。
struct CchessPosition {……int MoveNum;MoveStruct MoveList[MaxMoveNum]; // MaxMoveNum = 256char LoopHash[LoopHashMask + 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使用“归位检测法”来判断循环着法，即从最后一个着法开始，依次向前撤消着法，并记录每个移动过的棋子所在的格子。
如果所有移动过的棋子同时归位，那么循环着法就出现了。
因此<ccstruct.h>中的IsLoop()函数建立了两个归位数组，第一个记录了棋子的原始位置，第二个记录了新的位置，当两个位置重合时，说明棋子归位。
2.3 棋盘-棋子联系数组众所周知，棋盘的表示有两种方法。
一是做一个棋盘数组(例如Squares[10][9])，每个元素记录棋子的类型(包括空格)；二是做一个棋子数组(例如Pieces[32])，每个元素记录棋子的位置(包括被吃的状态)。
如果一个程序同时使用这两个数组，那么着法生成的速度就可以快很多。
这就是“棋盘-棋子联系数组”，它的技术要点是：(1) 同时用棋盘数组和棋子数组表示一个局面，棋盘数组和棋子数组之间可以互相转换。
(2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。
根据这两个原则，棋盘-棋子联系数组可以定义为：struct CchessPosition {int Squares[90];int Pieces[32];};棋子数组Pieces[48]是ElephantEye的一个特点，0到16没有作用，16到31代表红方棋子(16代表帅，17和18代表仕，依此类推，直到27到31代表兵)，32到47代表黑方棋子(在红方基础上加16)。
这样，棋盘数组Squares[90]中的每个元素的意义就明确了，0代表没有棋子，16到31代表红方棋子，32到47代表黑方棋子。
这样表示的好处就是：它可以快速判断棋子的颜色，(Piece & 16)可以判断是否为红方棋子，(Piece & 32)可以判断是否为黑方棋子。
棋子数组Squares[90]存储的是每个棋子所在的格子，用“列x 10 + 行”表示(稍后再来解释为什么不用“行x 9 + 列”，红方最左边的车为0，黑方最左边的车为89。