中国象棋程序设计探索(转，算是找到好东西了@周立功GD32）

1万 · 2013-8-31 19:56

2005年6月初稿，2007年12月修订

1万 · 2013-8-31 19:57

(一) 引言　　　2005年2月我写出了象棋程序ElephantEye的第一个版本(0.90)，本来它只是象棋界面ElephantBoard(现改名为象棋巫师)的调试引擎。在设计程序的过程中，我尝试性地加入了很多算法，发现每次改进都能让程序的棋力有大幅度的提高，因此便对象棋程序的算法产生了浓厚的兴趣。到现在我已经陆续对ElephantEye作了无数次加工，使得它的棋力接近了顶尖商业软件的水平，在非商业的象棋程序中，ElephantEye无疑是最强的一个。　　我希望能通过公开源代码的方式，推动中国象棋程序水平的整体发展，然而根据很多网友的反馈意见，发现源代码中的很多部分并不是那么容易理解的，为此我花了大量的时间为源程序加了注释。尽管如此，很多思想还是有必要以文字的形式保留下来，因此我才打算以《中国象棋程序设计探索》为题，写几篇详细介绍ElephantEye算法的连载，希望能让源代码充分发挥它的作用。　　总的来说，对弈程序是个系统工程，它是以下四个系统的有机结合：(1) 棋盘结构，(2) 局面评价，(3) 搜索技术，(4) 其他。以ElephantEye为例，这四个部分在程序中的比例各占25%，也就是说，每个方面都很重要。那么这四个部分应该以什么样的方式逐步建立呢？另一个公开源代码的程序VSCCP(Very Simple Chinese Chess Program)给出了一个方向，这是本很好的对弈程序设计的入门教材。尽管VSCCP在棋力上还有很大的提升空间，但是它的结构体系是比较完整的，参考下面一组公式，找到有待提升的空间，只要稍作改进就能成为ElephantEye。　棋盘结构 = 局面表示 + 着法移动 + 着法生成 + 特殊局面判断局面评价 = 知识 + 优化的局面表示搜索技术 = 完全搜索 + 静态搜索 + 启发 + 裁剪 + 选择性延伸 + 置换表 + 残局库 + 并行技术其他 = 开局库 + 时间控制 + 后台思考 + 引擎协议　　　现在我来回答读者最关心的一个问题——ElephantEye的源程序可以从哪里找到。

　　ElephantEye的源程序发布在SourceForge的XiangQi Wizard项目中，其页面是：

　　　　http://sourceforge.net/projects/xqwizard/

　　ElephantEye的版本改进，实时同步地发布在SourceForge的SVN站点上，获取地址是：

　　　　https://xqwizard.svn.sourceforge.net/svnroot/xqwizard/

　　读者可以使用TortoiseSVN等SVN客户端程序获取到最新的(跟我完全同步的)代码，TortoiseSVN在SourceForge的页面是：

　　　　http://sourceforge.net/projects/tortoisesvn/

　　本文初稿时ElephantEye的版本为1.0x，现在已经升级到3.1x。尽管初稿完成之后又有几次修订，但本文所涉及的很多细节问题都没有再更新过，所以代码看上去可能面目全非了。但是万变不离其中，读者若是注意代码中的注释，就会发现其基本原理与本文是一致的。

1万 · 2013-8-31 19:57

(二) 棋盘结构和着法生成器　　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：　　(1) 数据结构——简介(David Eppstein)；　　(2) 数据结构——位棋盘(James Swafford)；　　(3) 数据结构——旋转的位棋盘(James Swafford)；　　(4) 数据结构——着法生成器(James Swafford)；　　(5) 数据结构——0x88着法产生方法(Bruce Moreland)；　　(6) 数据结构——Zobrist键值(Bruce Moreland)；

1万 · 2013-8-31 19:58

2.4 扩展的棋盘数组和棋子数组　　　如今，很少有程序使用Squares[90]和Pieces[32]这样的数组了，浪费一些存储空间以换取速度是流行的做法，例如ElephantEye就用了ucpcSquares[256]和ucsqPieces[48]。把棋盘做成16x16的大小，得到行号和列号就可以用16除，这要比用9或10除快得多。16x16的棋盘还有更大的好处，它可以防止棋子走出棋盘边界。

00

01

02

03

04

05

06

07

08

09

0a

0b

0c

0d

0e

0f

10

11

12

13

14

15

16

17

18

19

1a

1b

1c

1d

1e

1f

20

21

22

23

24

25

26

27

28

29

2a

2b

2c

2d

2e

2f

30

31

32

33

34

35

36

37

38

39

3a

3b

3c

3d

3e

3f

40

41

42

43

44

45

46

47

48

49

4a

4b

4c

4d

4e

4f

50

51

52

53

54

55

56

57

58

59

5a

5b

5c

5d

5e

5f

60

61

62

63

64

65

66

67

68

69

6a

6b

6c

6d

6e

6f

70

71

72

73

74

75

76

77

78

79

7a

7b

7c

7d

7e

7f

80

81

82

83

84

85

86

87

88

89

8a

8b

8c

8d

8e

8f

90

91

92

93

94

95

96

97

98

99

9a

9b

9c

9d

9e

9f

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

aa

ab

ac

ad

ae

af

b0

b1

b2

b3

b4

b5

b6

b7

b8

b9

ba

bb

bc

bd

be

bf

c0

c1

c2

c3

c4

c5

c6

c7

c8

c9

ca

cb

cc

cd

ce

cf

d0

d1

d2

d3

d4

d5

d6

d7

d8

d9

da

db

dc

dd

de

df

e0

e1

e2

e3

e4

e5

e6

e7

e8

e9

ea

eb

ec

ed

ee

ef

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

fa

fb

fc

fd

fe

ff

　　在中国象棋里，短程棋子(短兵器)指的是除车和**以外的其他棋子，它们的着法都有固定的增量(行的增量，列的增量)，因此处理起来非常简单，也是着法生成技术的基础。例如马有8个着法，增量分别是±0x0e、±0x12、±0x1f和±0x21，红方的过河兵有3个着法，增量分别是-0x10和±0x01。　　16x16的扩展棋盘如上图所示，底色是红色的格子都被标上“出界”的标记，目标格在这些格子上就说明着法无效。这样，马的着法产生就非常简单了：　const int cnKnightMoveTab[8] = {-0x21, -0x1f, -0x12, -0x0e, +0x0e, +0x12, +0x1f, +0x21};const int cnHorseLegTab[8] = {-0x10, -0x10, -0x01, +0x01, -0x01, +0x01, +0x10, +0x10};　for (i = MyFirstHorse; i < MyLastHorse; i ++) {　// 在ElephantEye的Pieces[48]中，红方的MyFirstHorse为21，MyLastHorse为22。　SrcSq = ucsqPieces;　if (SrcSq != 0) {　　for (j = 0; j < 8; j ++) {　　　DstSq = SrcSq + cnKnightMoveTab[j];　　　LegSq = SrcSq + cnHorseLegTab[j];　　　if (cbcInBoard[DstSq] && (ucpcSquares[DstSq] & MyPieceMask) == 0 && ucpcSquares[LegSq] == 0) {　　　　MoveList[MoveNum].Src = SrcSq;　　　　MoveList[MoveNum].Dst = DstSq;　　　　MoveNum ++;　　　}　　}　}}　

1万 · 2013-8-31 19:58

　上面的代码是着法生成器的典型写法，用了两层循环，第一层循环用来确定要走的棋子，第二层循环用来确定棋子走到的目标格。如果要加快程序的运行速度，第二个循环可以拆成顺序结构。这个代码还加入了蹩马腿的判断，马腿的位置增量由ccHorseLegTab[j]给出。　　其它棋子的着法也同样处理，只要注意帅(将)和仕(士)把InBoard[DstSq]改为InFort[DstSq]就可以了。而对于兵和象等需要考虑是否能过河的棋子，判断是否过河的方法非常简单：红方是(SrcSq/DstSq & 0x80) != 0，黑方是(SrcSq/DstSq & 0x80) == 0。　　Pieces[48]这个扩展的棋子数组比较难以理解，实际上用了“屏蔽位”的设计，即1位表示红子(16)，1位表示黑子(32)。因此0到16没有作用，16到31代表红方棋子(16代表帅，17和18代表仕，依此类推，直到27到31代表兵)，32到47代表黑方棋子(在红方基础上加16)。这样，棋盘数组Squares[256]中的每个元素的意义就明确了，0代表没有棋子，16到31代表红方棋子，32到47代表黑方棋子。这样表示的好处就是：它可以快速判断棋子的颜色，(Piece & 16)可以判断是否为红方棋子，(Piece & 32)可以判断是否为黑方棋子。　　“屏蔽位”的设计不仅仅限制在判断红方棋子还是黑方棋子，如果在棋子数组上再多加7个屏蔽位，就可以对每个兵种作快速判断，例如判断是否是红兵，不需要用(Piece >= 27 && Piece <= 31)，而只要简单的(Piece & WhitePawnBitMask)即可。这样的话，棋子数组的大小就增加到2^12=4096个了，其中9个屏蔽位，还有3位表示同兵种棋子的编号(注意兵有5个，所以必须占据3位)。事实上，确实有象棋程序是使用Pieces[4096]的。　2.5 着法预生成数组　　　上面提到的着法生成技术，在速度上并不是最快的。我们仍旧以马的着法为例，在很多情况下，马会处于棋盘的边缘，所以往往着法只有很少，而并不需要对每个马都作8次是否出界的判断。因此，对于每个短程子力，都给定一个[256][4]到[256][9]不等的数组，它们保存着棋子可以到达的绝对位置，这些数组称为“着法预生成数组”。例如，ElephantEye里用了ucsqKnightMoves[256][12]和ucsqHorseLegs[256][8]，前一个数组的第二个维度之所以大于8，是因为着法生成器依次读取数组中的值，读到0就表示不再有着法(12则是为了对齐地址)。程序基本上是这样的：　for (i = MyFirstHorse; i <= MyLastHorse; i ++) {　SrcSq = ucsqPieces;　if (SrcSq != 0) {　　j = 0;　　DstSq = ucsqKnightMoves[SrcSq][j];　　while (DstSq != 0) {　　　LegSq = ucsqHorseLegs[SrcSq][j];　　　if (!(ucpcSquares[DstSq] & MyPieceMask) && ucpcSquares[LegSq] == 0) {　　　　MoveList[MoveNum].Src = SrcSq;　　　　MoveList[MoveNum].Dst = DstSq;　　　　MoveNum ++;　　　}　　　j ++;　　　DstSq = ucsqHorseMoves[SrcSq][j];　　}　}}　　　和前一个程序一样，这个程序也同样用了两层循环，不同之处在于第二个循环读取的是着法预生成数组，DstSq从ucsqHorseMoves[256][12]中读出，LegSq从ucsqHorseLegs[256][8]中读出。

1万 · 2013-8-31 19:59

2.6 位行和位列
　
　　车和**的着法分为吃子和不吃子两种，这两种着法生成器原则上是分开的，因此分为车**不吃子、车吃子和**吃子三个部分。不吃子的着法可以沿着上下左右四条射线逐一生成(即并列做4个循环)。我们感兴趣的是吃子的着法，因为静态搜索只需要生成这种着法，能否不用循环就能做到？ElephantEye几乎就做到了。
　　“位行”和“位列”是目前比较流行的着法生成技术，但仅限于车和**的着法，它是否有速度上的优势还很难说，但是设计程序时可以减少一层循环，这个思想就已经比较领先了。以“位”的形式记录棋盘上某一行所有的格子的状态(仅仅指是否有子)，就称为“位行”(BitRank)，与之对应的是“位列”(BitFile)，棋盘结构应该包含10个位行和9个位列，即：
　
struct PositionStruct {
　……
　unsigned short wBitFiles[16];
　unsigned short wBitRanks[16];
　……
};
　
　　值得注意的是，它仅仅是棋盘的附加信息，“棋盘-棋子联系数组”仍旧是必不可少的。它的运作方式有点和“棋盘-棋子联系数组”类似：
　　(1) 同时用位行数组和位列数组表示棋盘上的棋子分布信息，位行数组和位列数组之间可以互相转换；
　　(2) 随时保持这两个数组之间的联系，棋子移动时必须同时更新这两个数组。
　　因此，移走或放入一颗棋子时，必须在位行和位列上置位：
　
void AddPiece(int Square, int Piece) {
　……
　x = Square % 16;
　y = Square / 16;
　wBitFiles[x] = 1 << (y - 3);
　wBitRanks[y] = 1 << (x - 3);
　……
}
　
　　车和**是否能吃子(暂时不管吃到的是我方棋子还是敌方棋子)，只取决于它所在的行和列上的每个格子上是否有棋子，而跟棋子的颜色和兵种无关，因此这些信息完全反映在位行和位列中。预置一个“能吃到的格子”的数组，以位行或位列为指标查找数组，就可以立即知道车或**能吃哪个子了。预置数组到底有多大呢？

1万 · 2013-8-31 19:59

// 某列各个位置的车或**(10)在各种棋子排列下(1024)能走到的最上边或最下边的格子
unsigned char ucsqFileMoveNonCap[10][1024][2];　　// 不吃子
unsigned char ucsqFileMoveRookCap[10][1024][2]; 　// 车吃子
unsigned char ucsqFileMoveCannonCap[10][1024][2]; // **吃子
// 某列各个位置的车或**(9)在各种棋子排列下(512)能走到的最左边或最右边的格子
unsigned char ucsqRankMoveNonCap[9][512][2];
……
　
　　数组中的值记录的是目标格子的偏移值，即相对于该行或列第一个格子的编号。产生吃子着法很简单，以车吃子位例：
　
for (i = MyFirstRook; i <= MyLastRook; i ++) {
　SrcSq = ucsqPieces[i];
　if (SrcSq != -1) {
　　x = SrcSq % 16;
　　y = SrcSq / 16;
　　DstSq = ucsqFileMoveRookCap[y - 3][wBitFiles[x]][0]; // 得到向上吃子的目标格
　　if (DstSq != 0) {
　　　DstSq += x * 16; // 注意：第x列的第一个格子总是x * 16。
　　　MoveList[MoveNum].Src = SrcSq;
　　　MoveList[MoveNum].Dst = DstSq;
　　　MoveNum ++;
　　}
　　…… // 再把FileMoveRookCap[...][...][0]替换成[...][...][1]，得到向下吃子的着法
　　DstSq = ucsqRankMoveRookCap[x - 3][wBitRanks[y]][0]; // 得到向左吃子的目标格
　　if (DstSq != 0) {
　　　DstSq += y; // 注意：第y行的第一个格子总是y。
　　　MoveList[MoveNum].Src = SrcSq;
　　　MoveList[MoveNum].Dst = DstSq;
　　　MoveNum ++;
　　}
　　…… // 再把RankMoveRookCap[...][...][0]替换成[...][...][1]，得到向右吃子的着法
　}
}
　

1万 · 2013-8-31 20:00

2.8 位棋盘
　
　　尽管ElephantEye已经摈弃了“位棋盘”的设计，但是作为一个新兴的数据结构，尤其是“折叠位棋盘”的设计思路，还是值得一提的。“折叠位棋盘”的思想是由湖北襄樊铁路分局计算机中心的章光华提出的，首先于2004年底发表在象棋百科全书网的论坛上，该技术主要用来获得马和相(象)的着法。
　　这个思想的要点是：
　　(1) 棋盘必须按照列的方式对每个格子编号(如下图所示)，格子的编号代表96位位棋盘中的第几位；
09 19 29 39 49 59 69 79 89
08 18 28 38 48 58 68 78 88
07 17 27 37 47 57 67 77 87
06 16 26 36 46 56 66 76 86
05 15 25 35 45 55 65 75 85
04 14 24 34 44 54 64 74 84
03 13 23 33 43 53 63 73 83
02 12 22 32 42 52 62 72 82
01 11 21 31 41 51 61 71 81
00 10 20 30 40 50 60 70 80
　　(2) 初始化数组一个“马腿数组”，以表示某个格子上的马可能存在的马腿，例如：
　
BitBoard HorseLegTable[90];
HorseLegTable[0] = BitMask[1] | BitMask[10];
HorseLegTable[1] = BitMask[11] | BitMask[20]; // BitMask[0]没必要加上去，而加上去也没错。
……
　
　　注意，这里仅仅是拿两个格子举例子，写在程序里的时候要用循环语句来生成马腿数组，以精简代码。

1万 · 2013-8-31 20:00

　　(3) 产生绊马腿的棋子的位棋盘，以红方左边未走过的马为例：
　
HorseLeg = HorseLegTable[10] & AllPieces;
　
　　(4) 根据马的位置和绊马腿的位棋盘，就可以知道马可以走的格子，因此可以构造这样的函数：
　
BitBoard KnightPinMove(int KnightSquare, BitBoard HorseLeg);
　
　　为了增加运算速度，应该用查表代替运算，即把函数变成数组。那么位棋盘HorseLeg如何转化成整数呢？这就引出了“折叠位棋盘”的技术，这可以称得上是一个炫技。折叠位棋盘实际上就是位棋盘的8位校验和(CheckSum)，有了折叠位棋盘后，上面的函数就可以用数组表示：
　
BitBoard KnightPinMove[90][256];
　
　　例如第10个格子上马的所有着法，用位棋盘表示为：
　
KnightMoveBitBoard = KnightPinMove[10][CheckSum(HorseLegTable[10] & AllPieces)];
　
　　相(象)的着法可以采用同样的原理，首先初始化象眼数组：
　
BitBoard ElephantEyeTable[90];
　
　　随后折叠象眼的位棋盘ElephantEye，再从相(象)的着法预产生数组BishopPlugMove[90][256]中找到着法。
1 3 5 7 1 3 5 7 1
0 2 4 6 0 2 4 6 0
7 1 3 5 7 1 3 5 7
6 0 2 4 6 0 2 4 6
5 7 1 3 5 7 1 3 5
4 6 0 2 4 6 0 2 4
3 5 7 1 3 5 7 1 3
2 4 6 0 2 4 6 0 2
1 3 5 7 1 3 5 7 1
0 2 4 6 0 2 4 6 0
1 2 3 4 5 6 7 0 1
0 1 2 3 4 5 6 7 0
7 0 1 2 3 4 5 6 7
6 7 0 1 2 3 4 5 6
5 6 7 0 1 2 3 4 5
4 5 6 7 0 1 2 3 4
3 4 5 6 7 0 1 2 3
2 3 4 5 6 7 0 1 2
1 2 3 4 5 6 7 0 1
0 1 2 3 4 5 6 7 0
按纵线编号的棋盘按横线编号的棋盘
　　看到这里，可能有的读者就会怀疑“折叠位棋盘”的合理性，如果折叠成4位的整数(甚至更少)，把马的着法预产生数组了缩小到90x16，这显然是不合理的，为什么8位就一定合理呢？
　　要说明这个问题，首先来看折叠的本质——校验和(CheckSum)，棋盘上的很多格子对应着校验和上固定的一位。根据这个性质，我们对棋盘重新编号，就如左图所示。假如河界下面蓝色的格子是马，那么相邻的红色格子就是马腿，4条马腿对应4个不同的编号，所以任何一种组合(一共有24 =16种组合)是不重复的。需要指出的是，这个棋盘当中所有的格子，其相邻的四个格子都有不同的编号。有趣的是，象眼同样符合这个规律(注意河界上面蓝色的格子，斜相邻的四个格子是象眼)。
　　折叠位棋盘的唯一性是建立在“按纵线编号”的基础上的。如果按横线编号，情况就不那么幸运了，如右图所示，无论是河界下面的马，还是河界上面的象，马腿或象眼都存在编号重复的格子。
　　位棋盘必须按纵线编号，就是这个原因。
　　当然，初始化KnightPinMove[18][256]这个庞然大物，也不是一件容易的事。其实折叠位棋盘使用起来需要“折叠”，生成起来却需要“展开”(即CheckSum()函数对应的Duplicate()函数，参阅<bitboard.h>)。当8位的整数展开成位棋盘后，再和某个格子的HorseLegTable作“与”运算，就可以还原为HorseLeg了。

1万 · 2013-8-31 23:20

3.2 超出边界的Alpha-Beta搜索
　
　　置换表的大部分问题出在边界上，直到目前笔者还无法彻底明白该如何设置边界，因此想把这个问题留给读者。首先我们从不带置换表的超出边界(Fail-Soft)的Alpha-Beta搜索说起：
　
int AlphaBeta(int Alpha, int Beta, int Depth) {
　if (GameOver() || Depth <= 0) {
　　Value = Evaluate();
　　// if (Value >= Beta) return Beta;
　　// if (Value <= Alpha) return Alpha;
　　return Value;
　}
　Best = -MaxValue;
　GenMoves();
　while (MovesLeft()) {
　　MakeNextMove();
　　Value = -AlphaBeta(-Beta, -Alpha, Depth - 1);
　　UndoMakeMove();
　　if (Value >= Beta) {
　　　// return Beta;
　　　return Value;
　　}
　　if (Value > Best) {
　　　Best = Value;
　　　if (Value > Alpha) {
　　　　Alpha = Value;
　　　}
　　}
　}
　// return Alpha;
　return Best;
}
　
　　以上代码中，蓝色的被注释掉的部分是不超出边界的Alpha-Beta搜索，红色的代码就是超出边界的Alpha-Beta搜索了。如果不使用置换表，那么这种改动和原来没有区别，但是在置换表的作用下，情况就会有微妙的变化。探索置换表的形式(是否超出边界)应该与Alpha-Beta的形式保持一致：
　
int ProbeHash(int Alpha, int Beta, int Depth) {
　……
　if (Hash.Flag == HASH_BETA) {
　　if (Hash.Value >= Beta) {
　　　// return Beta;
　　　return Hash.Value;
　　}
　} else if (Hash.Flag == HASH_ALPHA) {
　　if (Hash.Value <= Alpha) {
　　　// return Alpha;
　　　return Hash.Value;
　　}
　} else if (Hash.Flag == HASH_PV) {
　　// if (Hash.Value >= Beta) return Beta;
　　// if (Hash.Value <= Alpha) return Alpha;
　　return Hash.Value;
　}
}
　
　　同样的问题出现在记录置换表时：
　
int AlphaBeta(int Alpha, int Beta, int Depth) {
　……
　while (……) {
　　……
　　if (Value >= Beta) {
　　　// RecordHash(Beta, HASH_BETA, Depth);
　　　RecordHash(Value, HASH_BETA, Depth);
　　　return ……;
　　}
　　……
　}
　// RecordHash(Alpha, HashFlag, Depth);
　RecordHash(Best, HashFlag, Depth);
　return ……;
}
　
　　在带置换表的Alpha-Beta搜索中，到底超出边界(Fail-Soft)和不超出边界(Fail-Hard)哪个效率更高，到现在为止还很难有定论。从上面的代码中可以看出，采用超出边界算法时，置换表的边界变窄了，即Beta结点的可能值从(Beta, MATE_VALUE缩小为(Value, MATE_VALUE)，本来低于Beta才会命中的结点，现在只要低于Value就能命中了。但是很多试验表明，某些局面在使用了超出边界算法时，搜索的结点数反而增加了。因为置换现象会产生搜索的不稳定性，置换表命中率高也会导致不稳定性的增强，搜索的结点数增加就是其中一个表现。

1万 · 2013-8-31 23:21

3.3 胜利局面的特殊处理
　
　　胜利局面就是程序能搜索到的有杀局的局面，它具有特殊的分值——最大值减去“根结点”到“将死结点”的步数(简称杀棋步数或DTM)。而当这个数值记录到置换表的时候，就必须转化为最大值减去“当前结点”到“将死结点”的步数。
　　除此以外杀局还有一个显著的特点——对一个局面进行某一深度的搜索后，如果已经证明它是杀局，那么就不必进行更深层次的搜索了。利用这点，可以改进探索置换表的程序，提高置换表的命中率，从而提高搜索效率：
　
const int WIN_VALUE = MATE_VALUE - 100;
　
int ProbeHash(int Alpha, int Beta, int Depth) {
　……
　MateNode = false;
　if (Hash.Value > WIN_VALUE) {
　　Hash.Value -= Ply;
　　MateNode = true;
　} else if (Hash.Value < -WIN_VALUE) {
　　Hash.Value += Ply;
　　MateNode = true;
　}
　if (MateNode || Hash.Depth > Depth) {
　　……
　}
}
　
　　这样做似乎在中局阶段并不能起到很好的效果，但是在处理杀局和残局时，搜索的结点数大幅度降低了，ElephantEye在使用了这种方法以后，杀局和残局的处理能力有了很大的提高。
　
3.4 长将禁手局面的特殊处理
　
　　由于单方面长将不变作负的规则，从表面上看，如果发生这种情况就应该，给予-MATE_VALUE的值，再根据杀棋步数作调整。但是由于长将判负并不是对某个单纯局面的评分，而是跟路径有关的，所以使用置换表时就会产生非常严重的后果，这也是搜索不稳定性的一个来源。简而言之，即同一局面由于形成路径不同而有不同的分值。
　　最简单的解决办法就是不要把“利用长将判负策略搜索到的局面”记录到置换表中，为此把长将判负的局面定为BAN_VALUE，定义为MATE_VALUE - 50，再根据杀棋步数作调整。考虑到搜索层数通常不会超过50层，因此如果某个局面分值在WIN_VALUE(即MATE_VALUE - 100)和BAN_VALUE之间，那么这个局面就是“利用长将判负策略搜索到的局面”，不记录到置换表中。根据这个思路，代码就应该写成：
　
const int BAN_VALUE = MATE_VALUE - 50;
　
void RecordHash(int HashFlag, int Value, int Depth) {
　if (Value > WIN_VALUE) {
　　if (Ply > 0 && Value <= BAN_VALUE) {
　　　return;
　　}
　　Value += Ply;
　} else if (Value < -WIN_VALUE) {
　　if (Ply > 0 && Value >= -BAN_VALUE) {
　　　return;
　　}
　　Value -= Ply;
　}
　……
}
　
　　之所以允许Ply == 0的结点写入置换表，是因为这样的结点是根结点，ElephantEye需要依靠它来获得最佳着法。
　
3.5 置换表的覆盖策略
　
　　置换表的覆盖策略通常有两种：深度优先和始终覆盖。ElephantEye以前几个版本只用了深度优先的策略，因此代码并不复杂，并且在搜索时间不太长的情况下，这种策略非常有效。但当置换表接近填满的时候，把深度优先和始终覆盖两种策略结合起来，效果就会很明显了。那么如何把这两种覆盖策略结合起来呢？
　　ElephantEye参考了国际象棋程序Fruit的做法，采用多层结构的置换表。简而言之，一个m层的置换表有n个Hash位置，每个Hash位置记录m个局面，那么整个Hash表可记录m × n个局面信息。记录一个局面时，找到它对应的Hash位置中的m个局面，不考虑该局面本身的搜索深度，而直接覆盖深度最小的那个局面。这种策略的本质就是将深度优先和始终覆盖结合起来——原先深度最小的那个局面是始终覆盖的，而其余m - 1个搜索深度更深的局面则被保留下来。

1万 · 2013-8-31 23:22

(五) 克服水平线效应
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 高级搜索方法——简介(一)(David Eppstein)；
　　(2) 高级搜索方法——静态搜索(Bruce Moreland)；
　　(3) 高级搜索方法——空着裁剪(Bruce Moreland)；
　　(4) 其他策略——重复检测(Bruce Moreland)；
　　(5) 其他策略——藐视因子(Bruce Moreland)。
　
　　在象棋程序的搜索技术中，裁剪和延伸是最有挖掘潜力之处，在各个程序中的差异也比较大。ElephantEye在这方面没有花太多的笔墨，空着裁剪、静态搜索和选择性延伸跟其他程序大同小异，读者可能会认为“历史表裁剪”(History Pruning)是ElephantEye的亮点，但是笔者对该算法的原理并未完全把握，而且很多细节还有待摸索，所以这里就不作介绍，有兴趣的读者可参考ElephantEye源程序中<search.cpp>的相关注释。笔者将对几个比较成熟可靠的算法作一些介绍。
　
5.1 无害裁剪
　
　　很多局面不需要搜索即可知道它的确切评价值，或者至少超出Alpha-Beta窗口，此时就可以把该结点以下的搜索树裁剪掉，而不影响搜索结果，这类裁剪称为“无害裁剪”，ElephantEye使用了以下几种无害裁剪：
　　(1) 杀棋步数(DTM)裁剪。由于DTM调整的缘故，在深度为Ply的结点中，搜索结果不会落在窗口(Ply - MATE_VALUE, MATE_VALUE - Ply)外，所以当(Alpha, Beta)窗口和该窗口没有交叠时，立即可以作出裁剪。裁剪有两种情况，要么MATE_VALUE - Ply <= Alpha，要么Ply - MATE_VALUE >= Beta，ElephantEye只考虑了后者。
　　(2) 重复裁剪。如果出现重复局面，那么应当根据规则直接判和或判某方长打作负，所以应当返回相应的分值。尽管象棋规则规定局面重复三次或更多次才予以判定，但在搜索过程中只要遇到一次重复，继续搜索下去就会有第二次、第三次，所以ElephantEye只要遇到一次重复就不再搜索下去，但根结点要另外处理(否则一个着法也没搜索，就出不了子了)。
　　(3) 和棋裁剪。如果双方都没有明显可以杀死对方的子力，即可返回和棋分值(0或藐视因子)，而不必继续往下搜索。ElephantEye把双方都只剩下仕(士)相(象)的局面规定为和棋局面。
　　(4) 置换裁剪。置换表的一个作用就是利用置换现象裁剪掉某些分枝，前面已经作了详细的介绍。这里要提的是，由于存在“搜索的不稳定性”的原因，置换裁剪并非绝对无害的，ElephantEye就不记录“利用长将判负策略搜索到的局面”，前面也有所介绍。
　
5.2 带检验的空着裁剪
　
　　“带检验的空着裁剪”(Verified Null-Move Pruning)指的是检验空着裁剪是否安全的算法，它首先由Tabibi发表在2002年的ICGA(原ICCA)杂志上(参阅Tabibi OD, Netanyahu NS: Verified Null-Move Pruning, ICGA J. 25 (3): 153-161, 2002，可以从互联网上找到)。其内容可以概括为：
　　(1) 用R = 3的空着裁剪进行搜索；
　　(2) 如果高出边界，那么做浅一层的搜索(这就意味着一层的搜索是无法做带验证的空着裁剪的)；
　　(3) 做浅一层的搜索时，子结点用R = 3的不带验证的空着裁剪；
　　(4) 如果浅一层的搜索高出边界，那么带验证的空着裁剪是成功的，否则必须重新做完全的搜索。
　　笔者认为这里存在很多问题：
　　(1) 用R = 3非常冒进，还是用R = 2比较合适；
　　(2) 检验时做浅一层的搜索太浪费时间，裁剪的层数可以跟空着裁剪一样的R值一样，而且窗口也用以Beta为界的零窗口；
　　(3) 做检验时，子结点仍旧应该做带检验的空着裁剪，否则“连停着杀”就检测不出来了。
　　ElephantEye是否启用空着裁剪，分三种情况讨论：
　　(1) 我方进攻子力达到3个，就使用不带检验的空着裁剪；
　　(2) 我方进攻子力小于3个，则使用带检验的空着裁剪；
　　(3) 我方只有仕(士)相(象)等守子，则禁用空着裁剪。
　　因此，ElephantEye的代码中，和空着裁剪有关的部分如下：
　
const int NULL_REDUCTION = 2
　
int AlphaBeta(int Alpha, int Beta, int Depth, bool Verify = false) {
　……
　if (!Verify && !InCheck() && NullOkay()) {
　　MakeNull();
　　Value = -AlphaBeta(-Beta, 1 - Beta, Depth - 1 - NULL_REDUCTION);
　　UndoNull();
　　if (Value >= Beta && (NullSafe() || AlphaBeta(Beta - 1, Beta, Depth - NULL_REDUCTION, true) >= Beta)) {
　　　return Value;
　　}
　}
　……
}
　
　　这个技术使得ElephantEye在残局中仍旧能启用空着裁剪，而且不会出现走错的情况，因此ElephantEye在几乎不带残局知识的情况下，残局的棋力还是非常高的。

1万 · 2013-8-31 23:22

(六) 并行搜索技术探索
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 高级搜索方法——期望窗口(Bruce Moreland)；
　　(2) 高级搜索方法——主要变例搜索(Bruce Moreland)。
　　并行搜索是博弈搜索技术中最复杂的组成部分，这就是ElephantEye没有采用并行技术的原因。尽管如此，笔者还是在这里简单地谈一下对并行搜索的认识。
　
6.1 并行计算的基本操作
　
　　并行计算有两种体系，一是单机体系，即一个程序在单机的多个处理器上运行，简称SMP(对称多处理器)，二是分布式体系，即一个程序在多个计算机联成的网络上运行，简称Cluster(计算机集群)。两者最大的区别是，单机体系的多个处理器可以共享存储器(并且共享同一地址的存储单元)，而分布式体系则必须通过网络来交换信息(尽管传输速度非常高，通常在1000MBPS以上)。
　　由于博弈搜索需要用到置换表，所以特别适合以SMP的方式作并行计算。Windows、UNIX等多任务操作系统都有线程(Thread)这个概念，线程是处理器任务的最小单位，一个线程是不可能同时在两个处理器上运行的，建立线程后，操作系统就会自动把新建的线程分配到空闲的处理器上。Windows下建立线程的方法是：
　
#include <windows.h>
……
DWORD ThreadId;
CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID) &ArgList, 0, &ThreadId);
　
　　UNIX下建立线程的方式是：
　
#include <pthread.h>
……
pthread_t pthread;
pthread_attr_t pthread_attr;
pthread_attr_init(&pthread_attr);
pthread_attr_setscope(&pthread_attr, PTHREAD_SCOPE_SYSTEM);
pthread_create(&pthread, &pthread_attr, (void *(*)(void *)) ThreadEntry, (void *) &ArgList);
　
　　这里ThreadEntry仅仅是某个线程的入口，以便整理参数ArgList并且在线程中调用其他函数。例如，一个用递归函数来计算斐波那契数列的并行程序(Windows版本)：
　
static volatile int IdleThreads;
　
struct ArgListStruct {
　volatile bool Active;
　volatile int Value;
};
　
static void *ThreadEntry(ArgListStruct *ArgListPtr);
　
static int Fibonacci(int Arg) {
　if (Arg < 2) {
　　return 1;
　} else {
　　return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
　}
}
　
static int FibonacciSMP(int Arg) {
　DWORD ThreadId;
　int Result;
　ArgListStruct ArgList;
　if (Arg < 2) {
　　return 1;
　} else {
　　if (Arg > 30) {
　　　if (Decrement(&IdleThreads) < 0) {
　　　　Increment(&IdleThreads);
　　　　return FibonacciSMP(Arg - 2) + FibonacciSMP(Arg - 1);
　　　} else {
　　　　ArgList.Value = Arg - 2;
　　　　ArgList.Active = true;
　　　　CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE) ThreadEntry, (LPVOID) &ArgList, 0, &ThreadId);
　　　　Result = FibonacciSMP(Arg - 1);
　　　　while (ArgList.Active) {
　　　　　Idle();
　　　　}
　　　　return Result + ArgList.Value;
　　　}
　　} else {
　　　return Fibonacci(Arg - 2) + Fibonacci(Arg - 1);
　　}
　}
}
　
static void *ThreadEntry(ArgListStruct *ArgListPtr) {
　ArgListPtr->Value = FibonacciSMP(ArgListPtr->Value);
　ArgListPtr->Active = false;
　Increment(&IdleThreads);
　return NULL;
}
　
　　由于Fibonacci()函数的递归形式如同二叉树一样扩展开来，所以当处理器有空闲时，就可以把其中一个分枝交给另一个线程，这个操作称为递归树的分割(Split)。为此程序需要维护变量IdleThreads来判断是否还有空闲的处理器，对该变量的操作必须用Increment()和Decrement()函数(即Intel处理器的INC和DEC原子指令，参阅<x86asm.h>)，以保证不会因为有两个线程同时对该变量操作而发生错误，这样的共享变量都应该标记为volatile属性，以避免编译器对这些变量作优化。
　　由于线程的维护需要消耗额外的处理器资源，所以并非每个递归结点要作分割的尝试，以上这段程序的核心问题尽管是FibonacciSMP()的递归，但当递归树不太大(参数不超过30)时，调用单纯的递归函数Fibonacci()会得到更高的效率。

1万 · 2013-8-31 23:23

6.2 加锁技术和非加锁技术
　
　　如果两个线程同时存取同一存储单元，就有可能产生错误，为此必须建立预防错误的机制，通常的措施是加锁(Lock)。一个比较简单的加锁方法是调用函数Exchange()(即Intel处理器的XCHG原子指令，参阅<x86asm.h>)，因为两个线程的原子语句是不可能同时存取同一存储单元的(正因为如此，处理器对存储单元作INC、DEC、XCHG等操作就需要考虑冲突，所以比较耗时)。在某块共享的存储单元中，第一个变量就是加锁标志，false表示未加锁，true表示加锁。加锁时只要用true和加锁标志交换，换出false就表示加锁成功(原来加锁标志是false，交换后变成true)，该线程就获得对共享单元的操作权，换出true则表示加锁失败(原来加锁标志是true，交换后仍旧是true)。对共享单元操作完毕后，再将加锁标志设成false来解锁。
　　并行计算的博弈程序会偶尔出现一种情况，即两个线程同时存取同一置换表项，为避免错误可以使用加锁技术：
　
struct HashRecord {
　volatile int Lock;
　……
};
　
void RecordHash / ProbeHash (……) {
　HashRecord *HashPtr = HashList + ZobristKey % HashSize;
　while (Exchange(&HashPtr->Lock, true)) {
　}
　……
　HashPtr->Lock = false;
}
　
　　但是，并行国际象棋程序的典范Crafty并没有这样做，而是采用了不加锁的技术，来避免置换表的存取冲突。简而言之，该算法的思想是当置换表项的校验码存取正确时，必须保证局面信息也存取正确(但允许校验码存取不正确，此时探索置换表的例程就会跳过以后的操作而不会引发错误)。
　　为此Crafty的128位置换表项定义为两个64位数W1和W2，W1是局面信息，而W2存储了W1和校验码的异或值，探测置换表项时，校验码必须由W1和W2的异或值求得，这样一旦W1读取错误，就得不到正确的校验码，换句话说，校验码的正确就保证了局面信息的正确。
　　Crafty的这种不加锁算法是针对64位处理器而设计的，这种技术当然也适用于32位处理器，而笔者认为32位处理器还有更为简单的处理方式，即设计如下的置换表项：
　
struct HashRecord {
　long CheckSum1, PositionInfo1, PositionInfo2, CheckSum2;
};
　
　　以上128位的置换表项由4个32位单元组成，存取置换表时四个单元依次读取或写入。只要位于首尾的校验码都能存取正确，就确保了中间两个局面信息单元的正确。
　
6.3 搜索树的分割策略
　
　　Alpha-Beta搜索是递归式的，因此作并行计算时可以仿照上面提到的Fibonacci()递归的例子，但这里有两个问题需要解决，一是某个子线程产生Beta截断时，如何通知其他子线程中止搜索，二是考虑什么样的结点需要分割，什么样的结点不需要分割。这两个问题都是并行搜索技术的难点，为此Crafty花了大量的代码来解决这些问题，其作者Robert Hyatt对Crafty的并行算法DTS(Dynamic Tree Split，即搜索树的动态分割算法)有专门的介绍。这里笔者只简单地介绍第二个问题，即搜索树的分割策略。
　　通常Alpha-Beta搜索树的结点可分为三个类型，即PV结点、Beta结点和Alpha结点，并且有明确的定义——搜索值在窗口(Alpha, Beta)之间的是PV结点(根据最小-最大原理，最佳着法的搜索值必须落在窗口内)，搜索值达到或超过Beta(即高出边界)的是Beta结点(仅需要有一个着法超过Beta即可)，搜索值未能超过Alpha(即低出边界)的是Alpha结点(所有着法都不能超过Alpha)。由此可以看出，PV结点和Alpha结点都需要搜索所有的着法，而Beta结点在最好的情况下只要搜索一个着法即可。
　　如果能在搜索之前预测出结点的类型，就可以决定是否对该结点作分割了，在Crafty及其相关论文中，预测的三类结点命名为PV结点、Cut结点和All结点，分别对应刚才提到的PV结点、Beta结点和Alpha结点。显然，PV结点和All结点是有分割价值的，只要预测正确，这些结点下的全部着法都要搜索，不会因为产生截断而浪费搜索时间，而对Cut结点作分割是没有意义的，因为目前的搜索技术使得Cut结点的第一着法截断率高达80%以上，对结点作分割只会浪费处理器资源。
　　至于如何来预测结点类型，在Crafty及其相关论文也有介绍，但是另一个国际象棋程序Fruit则描绘得更加明确，其分类策略是：
　　(1) 根结点总是PV结点。
　　(2) PV结点采用PVS算法，即第一个着法以后首先尝试零窗口的搜索，由于期望每个着法都低出边界(即子结点都高出边界)，所以预测这些零窗口的结点为Cut结点。
　　(3) Cut结点和All结点是互相交替的，即Cut结点的子结点是All结点，All结点的子结点是Cut结点，空着裁剪同样这么处理。
　　(4) Cut结点的第一个子结点(All结点)如果不能产生截断，就说明原来预测的Cut结点是错的，应该是All结点，那么以后的子结点都预测为Cut结点。换句话说，不管预测是否正确，Cut结点的第一个子结点(不包括空着裁剪)是All结点，其余的结点(如果有必要搜索的话)仍旧是Cut结点。
　　(5) PV结点不采用各种形式的向前裁剪(Null-Move、History、Futility等)。
　　由于Fruit不支持并行搜索，所以Cut结点和All结点没有区别，但给并行搜索留下了伏笔。
　　我们关注的是PV结点的分割，显然PV结点是有必要分割的，因为分割越早，新的线程所处理的搜索树就越大，并行效率就越高。(注意Fibonacci()递归的例子，为保证效率只有参数充分大时才会分割，Alpha-Beta递归也一样。)但是PV结点的分割会遇到一个问题——窗口宽度可能会变窄，如果让所有的子结点都作相同窗口的搜索，就无法体现Alpha-Beta算法的效率了。为此，Crafty对根结点的迭代加深过程用了期望窗口(Aspiration Window)，即让所有的子结点都搜索一个较窄的窗口，这要比直接分割(-MATE_VALUE, MATE_VALUE)有效得多。而另一个极端的做法是MTD(f)的零窗口，根结点从一开始就预测为Cut或All结点，即可实施有效的分割，这就是MTD(f)算法在并行计算上的优势。

1万 · 2013-8-31 23:23

(七) 开局库
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 其他策略——开局库(Martin Fierz)。
　
7.1 象棋程序对开局库的处理
　
　　开局库是象棋程序中知识含量最多的部分，各种程序的棋力会因为开局库的不同而有所差距。互联网上介绍国际象棋开局库的**很多，而中国象棋开局库的原理和国际象棋是完全一样的，因此笔者就不作太多的介绍了。
　　很多国际象棋的程序中，开局库并不被引擎处理，而是由界面来完成的，棋局进入中局脱离棋谱后，才让引擎作搜索。ChessBase的系列软件Junior和Fritz，以及支持UCI协议的Shredder，都使用这种工作方式，由于它们使用同一套ChessBase的界面，因此开局库格式是统一的。由于WinBoard本身并不能处理开局库，因此支持WinBoard的引擎都具有处理开局库的能力，而且每个引擎都有各自的开局库格式。
　　而中国象棋目前没有统一的界面，因此也没有统一的开局库格式，开局库一般由引擎来处理，各种引擎有各自定义的开局库格式。
　　ElephantEye早期开局库具有非常明显的特点——它是文本格式的，每一行记录一个着法，依次是着法(红色部分)、权重(绿色部分)和局面(紫色部分)：
　
b2e2 5895 rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w - - 0 1
　
　　由于记录局面时使用FEN串，这就增加了开局库的可读性，但同时使开局库变得特别庞大，ElephantEye的开局库(BOOK.DAT)仅有20,000多个着法却达到了1.6M。
　　从ElephantEye 2.0以后，每个局面仅占用8字节(4字节的Zobrist键值、2字节的着法和2字节的权重)，而且对称局面作了合并，因此由10,000多个着法组成的开局库大小不超过100K。
　
7.2 开局库的制作
　
　　ElephantEye现有的开局库是从象棋百科全书网上收录的8000多局对局中整理出来的，这些对局涵盖了1990年到2004年的全国顶级象棋比赛(团体赛、个人赛、甲级联赛和五羊杯)，因此具有代表性。现在简要介绍一下开局库的制作流程：
　　(1) 把所有的对局中的每个着法解析出来，记录到临时文件中，临时文件的每个着法记录占16字节(8字节的Zobrist键值、4字节的着法和2字节的权重)；
　　(2) 对临时文件的着法记录按Zobrist键值(第一关键字)和着法(第二关键字)排序；
　　(3) Zobrist键值和着法作关键字，对权重进行叠加；
　　(4) 按照笔者观点，权重 = 胜局数 ×3 + 和棋局数 - 负局数，因此在第(1)步中，导致胜局的着法的权重置3，和局置1，负局置-1；
　　(5) 过滤掉权重小于4的着法(即收入开局库的着法至少是一胜一和的)，把Zobrist键值的后4字节、2字节表示的着法和权重除以4的16位整数值记录到开局库文件(BOOK.DAT)中。
　
7.3 开局着法的选择
　
　　象棋程序在处理一个局面时，首先要从开局库中寻找是否有相同的局面，当开局库中找不到局面时，才会调用搜索程序进行思考。ElephantEye从开局库中找到着法的过程如下：
　　(1) 由于开局库是按Zobrist键值排序的，因此用二分查找法可以很快找到所有符合的局面及其着法；
　　(2) 如果当前局面在开局库中没有，那么查找对称局面，找到的着法也要作对称处理；
　　(3) 由于开局库中的Zobrist键值只有4字节，因此有可能产生冲突，必须从着法列表中排除不合理着法；
　　(4) 用随机数根据着法的权重选择着法；
　　(5) 如果该着法没有构成重复局面，那么将该着法作为最佳着法直接返回。

1万 · 2013-8-31 23:23

(八) 后台思考和时间策略
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 其他策略——后台思考(Bruce Moreland)。
　
8.1 后台思考
　
　　UCCI协议不需要对后台思考作特别处理，如果引擎接收了指令“go ponder ...”，那么搜索过程中时钟暂时不起作用，直到收到“ponderhit”指令后才启用时钟。因此，后台思考实际上相当于无限制的思考。
　
8.2 时间策略
　
　　时间策略在各个象棋程序中差异很大，有的程序根本没有时间策略，只能设定固定的搜索深度，或者在固定的时间中止思考，例如浅红象棋协议目前就没有时间策略。UCCI协议可以把时限规则告诉引擎，由引擎自动分配时间，时限规则可以是以下两种：
　　(1) 时段制，即在限定时间内走完规定的步数，用“go time <time> movestogo <moves_to_go>”命令；
　　(2) 加时制，即在限定时间内走完整盘棋，但每步会加上几秒，用“go time <time> increment <increment>”命令。
　　ElephantEye的时间策略由<search.h>里的SearchMain()函数来处理，不管处理哪个规则，都会分配一个合适的时间(ProperTime)用来走棋，这个时间是这样计算的：
　　(1) 时段制：分配时间 = 剩余时间 / 要走的步数；
　　(2) 加时制：分配时间 = 每步增加的时间 + 剩余时间 / 20 (即假设棋局会在20步内结束)；
　
　　在每次迭代加深的过程中，一个深度结束后，即将进行更深一层的搜索时，需要根据用时来判断是否终止搜索，判断的依据通常有：
　　(1) 一般情况下，用时超过分配时间的一半，就要终止搜索；
　　(2) 如果连续 n 次的迭代加深返回同样的着法，那么用时超过分配时间的1/4时就可以终止搜索，因为更深一层的搜索很有可能还是得到同样的着法；
　　(3) 如果当前深度得到的分值比上一深度到的分值低很多，那么用时超过分配时间才终止搜索(仅仅超过分配时间的一半是不够的)，期待搜索得更深以挽回劣势。
　　另外，搜索程序还会确定一个最大搜索时间(通常是剩余时间的一半)，如果搜索花费的时间超过预先设定的最大搜索时间，则强行中止搜索，这个检测过程由Interrupt()函数来完成。
　
8.3 搜索杀棋的策略
　
　　ElephantEye没有专门搜索杀棋的功能，如果存在杀棋的话(不管是杀死对方还是被对方杀死)，会在搜索中自动找到。是否能找到杀棋和搜索深度有关，某一深度下找不到杀棋，但深一层搜索就可能找到；但和一般局面不同的是，如果一定深度能找到杀棋，那么再深的深度会得到同样的结果。因此，如果找到杀棋，那么程序要使用不同的策略。ElephantEye处理杀棋局面时，用到以下几个策略：
　　(1) 置换表的存取策略，前面曾经介绍过，如果置换表中存储的某个局面已被确认找到杀棋，那么探测到这样的局面时就不需要考虑深度条件。
　　(2) 根结点做迭代加深时，找到杀棋后搜索就立即停止。ElephantEye为杀局设定了边界WIN_VALUE，其值略比MATE_VALUE小一些，局面分值在区间(-WIN_VALUE, WIN_VALUE)以外，就说明该局面有杀棋。
　　(3) 如果根结点的所有着法中，除了一个着法可以支撑(即分值大于-WIN_VALUE)以外，其余着法都会输掉(即分值都小于-WIN_VALUE)，那么应该立即返回这个唯一着法。
　　最后一点是ElephantEye最有特色之处，这就是说，当迭代加深过程中遇到这种情况时，就没有必要做更深的搜索了。在对某个深度的完全搜索完成后，对最佳着法设为禁着，再对根结点作一次搜索，如果分值小于-WIN_VALUE，则说明除这个最佳着法以外其余着法都会输掉，这种搜索称为“唯一着法检验搜索”，<search.cpp>中需要用变量bCheckUnique来控制。启用唯一着法检验搜索时，有两个地方要注意：
　　(1) 使用零窗口的技巧，即用(-WIN_VALUE, 1 - WIN_VALUE)窗口作搜索，以减少搜索的结点数；
　　(2) 根结点不记录到置换表中。

1万 · 2013-8-31 23:24

(九) 局面评价函数
　
　　在阅读本章前，建议读者先阅读象棋百科全书网中《对弈程序基本技术》专题的以下几篇译文：
　　(1) 局面评估函数——简介(一)(David Eppstein)；
　　(2) 局面评估函数——简介(二)(David Eppstein)。

1万 · 2013-8-31 23:24

(十) 实用程序片段
　
　　ElephantEye的源程序包里有个<utility>目录，其中包含了很多实用程序片段，不仅仅是针对象棋程序的。由于程序片段中没有中文注释，所以这里作一下简要的介绍。
　
10.1 Visual Basic下的原子语句(atom.c/atom.bas)
　
　　ElephantEye的部分代码可编译成CCHESS.DLL，成为界面程序ElephantBoard的一部分。然而由于Visual Basic处理数据结构的能力很弱，调用CCHESS.DLL时需要调用一些低级语句(例如QuickBasic的VARPTR、MKI、CVI等在Visual Basic中已经淘汰的语句)，为此ElephantEye提供了这些原子，以保证数据结构使用的便利。
　　在Visual Basic调用API函数的参数传递过程中，注意事项有：
　　(1) 指针型变量用ByRef声明，自定义结构只能用ByRef(引用方式)传递参数；
　　(2) 如果自定义结构用ByVal(传值方式)传递参数，则必须把它们转化为Visual Basic的内部类型；
　　(3) Visual Basic的字符串类型(Windows内部类型是BSTR)必须用ByVal传递参数，Visual Basic会自动将其转化为LPCSTR类型；
　　(4) API函数返回LPCSTR类型时，在Visual Basic下必须假定为Long类型。
　　我们最感兴趣的是最后一条，LPCSTR类型的字符串由<atom.bas>中的MkBStr函数转换为Visual Basic的字符串类型(BSTR)。例如在Visual Basic下调用开局编号分析器ECCO.DLL，调用方式如下：
　
Declare Function EccoIndex Lib "ECCO.DLL" Alias "_EccoIndex@4" (ByVal FileMoveStr As String) As Long ' ECCO.DLL中的EccoIndex函数在Visual Basic下的接口
Declare Function EccoOpening Lib "ECCO.DLL" Alias "_EccoOpening@4" (ByVal EccoIndex As Long) As Long ' ECCO.DLL中的EccoOpening函数在Visual Basic下的接口
EccoStr = MkL(EccoIndex("C2.5N8+7")) ' 获得ECCO编号的字符串，这里将返回"B05"
OpeningStr = MkBStr(CvL(EccoStr)) ' 获得上述编号对应的开局名称，这里将返回"中**对进左马"
　
10.2 汇编语言(x86asm.h)
　
　　汇编语言是为了弥补C语言的不足，<x86asm.h>主要提供以下两方面的功能：
　　(1) 操控互斥(Mutex)变量的原子语句，有Increment、Decrement、Exchange等，用于多线程的调度；
　　(2) 位搜索，即调用BSF(Bit-Scan-Forward)和BSR(Bit-Scan-Reverse)指令；
　　(3) 32位和64位整数的乘除法和位移，有LongMulDiv、LongMulMod等，解决了“Int64 = Int32 × Int32”等计算问题。
　　尽管Windows和Unix也有相应的库函数来支持这些功能，但是汇编语言通常以内联的形式调用，所以速度上会有优势。
　
10.3 基本功能(base.h)
　
　　<base.h>包括以下几个实用的函数：
　
　　(1) 空闲函数Idle()：
　　在程序空闲期间，应该把CPU资源交还给系统，这时就要调用空转函数Idle()，也可以直接调用Windows或Unix下都的休眠函数(Sleep()或usleep())。
　
　　(2) 伪随机数LongRand()：
　　不使用<stdlib.h>中的rand()函数，是出于以下几点考虑的：
　　A. rand()函数的有效位数只有15位(最大数为0x7fff)，这远不能满足程序的需要，用多个rand()函数来拼凑只是权益之计；
　　B. rand()函数的可靠性无法得到保障，因为我们不知道它的算法；
　　C. 如果以Zobrist键值的形式来描述开局库中的局面，那么每次给定相同的种子以后，产生的Zobrist键值都必须相同。但各种C语言的编译器中给出的rand()函数，我们无法确定其工作原理是否相同，因此也就不知道它们是否会产生相同的Zobrist键值了。
　　LongRand()采用了“乘同余法”，公式是这样的：
Ij+1 = (a x Ij) mod m
　　该公式可以用<x86asm.h>中的LongMulMod()函数来实现。这个算法在1969年首先由Lewis、Goodman和Miller提出，这里a和m的推荐值是：
a = 75 = 16807
m = 231 - 1 = 2147483647
　　这就使得随机数I的范围从1到231 - 2(即31位)，初始化种子数时，可以用1到231 - 2中的任意一个数。ElephantEye在产生Zobrist键值时，用1作种子数，而用作其他用途时，可以用time()作种子数。
　
　　(3) 计时函数TimerStruct::Init()和TimerStruct::GetTimer：
　　C语言里有很多计时函数，如<time.h>中的time()、ftime()、clock()等，笔者认为能达到精确计时功能的只有ftime()，为此针对该函数设计了计时器，在调用时可以避开对btime结构的直接处理。计时器是类型为TimerStruct的对象，成员函数Init()把当前时间写入该计时器，而GetTimer()返回当前时间和该计时器的差值(毫秒)。
　
10.4 管道的行输入和行输出(pipe.h/pipe.cpp)
　
　　ElephantEye是用“轮转”方式来接收行输入的(从1.1版本开始)。轮转不需要增加线程，只需要每隔一定时间让搜索过程去处理一下接收命令的子过程就可以了。轮转的操作原理在每个操作系统下都是一样的，这种方式甚至能在不支持多任务的DOS系统下运行。在轮转中调用ReadFile()(Windows的标准库函数)或read()(UNIX的标准库函数)函数时，使用起来要非常小心，通常需要调用检测输入的函数，只有确认标准输入句柄有输入时，才调用读入信息的函数。然而就检测和读取输入信息的操作而言，程序严重依赖于操作系统，有兴趣的读者可注意<pipe.cpp>中的“#ifdef _WIN32”语句，比较一下Windows代码和UNIX代码的区别。
　　如果输入输出的对象不是标准输入输出句柄而是程序，那么必须用管道来连接子进程的标准输入输出句柄和主进程的控制句柄。用CreatePipe()(Windows的标准库函数)或pipe()(UNIX的标准库函数)建立管道时，务必要明确输入输出的方向，一个管道有两个句柄，数据总从后一个句柄输入(称为“写入端”)，从前一个句柄输出(称为“读出端”)，因此可以用两种方式来使用管道：
　　(1) 写入端定向为子进程的标准输入句柄，读出端用来向子进程发送指令；
　　(2) 写入端用来接收子程序的反馈信息，读出端定向为子进程的标准输出句柄。
　　因此，如果象棋程序的界面要控制引擎，必须建立2个管道，产生4个句柄，其中2个定向给引擎，2个用来发送和接收数据，操作非常烦琐。好在<pipe.cpp>可自动完成这一切操作，具体应用可参阅UCCI2QH(UCCI引擎的浅红象棋适配器)和UCCILEAG(UCCI引擎联赛模拟器)的源程序。
　
10.5 位处理(popcnt.h/popcnt.cpp)
　
　　位搜索(BitScan)主要用于位棋盘的操作，Intel处理器提供了两个指令，即搜索最低位(BSF，BitScan-Forward)和搜索最高位(BSR，BitScan-Reverse)的操作，位棋盘的国际象棋程序Crafty用了FirstOne()和LastOne()两个函数，就是专门调用这两个指令的。然而很多试验表明，这两个指令是非常耗时的，而“查表代替计算”会比直接用汇编指令快得多。
　　<bitscan.cpp>为查表计算分配了两个64K的表，直接获得16位数的位搜索结果，32位数则分解成两个16位数再分别查表，同时该模块还包含位计数(BitCount)的操作，同样用了64K的表。用<bitscan.h>提供的BitScanForward()和BitScanReverse()函数做位搜索操作，耗时比直接调用汇编指令少一半，但切记使用查表函数前务必用BitScanInit()函数初始化。
　
10.6 字符串分析(parse.h)
　
　　提供了字符串比较和文件路径定位的若干实用函数。
　
10.7 96位位棋盘(bitboard.h)
　
　　尽管ElephantEye没有使用位棋盘，但位棋盘(BitBoard)仍然是一个富有活力的数据结构，为此ElephantEye的源程序包里保留了位棋盘结构的描述，即<bitboard.h>。位棋盘的赋值、比较、位操作(与或非等)、位移、位搜索都由该文件来定义(定义为内联函数的运算符)，另外还有为“折叠位棋盘”(专门处理蹩马腿和塞象眼的算法)而设计的操作，即CheckSum()和Duplicate()函数。